Proposal: Performance improvements for Data.Set
Ticket: http://hackage.haskell.org/trac/ghc/ticket/4280 Proposal: Performance improvements for Data.Set Following on from ticket #4277 here is a similar patch for Data.Set. This proposal provides a patch that improves performance for many parts of the API. Three standard techniques are applied to the code: * Worker/Wrapper transformations of recursive functions with constant arguments (aka. the static argument transformation). * Explicit inlining of wrapper functions. * Explicit strictness of keys to functions. Three complementary, but orthogonal patches are provided. * Add a testsuite, with coverage data (currently 51% of top level functions, and all core functions). * Add a micro-benchmark suite based on Criterion, for empirical evidence of improvements to each function. * The optimization patch itself. All 3 patches should be applied, under this proposal. The benchmark results are relatively clear: 32% faster on OS X 10.5.8 on 2 GHz Core 2 Duo The consideration period is 3 weeks (before ICFP). Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan Tibell and Don Stewart.
+1 to the Set, Map, IntMap, etc., performance improvements. The style consistency is probably a good concomitant effect. Testsuite and benchmark make sense in concept too (I haven't looked at the code, I trust that it's fine). Good job! Antoine's "Is this sort of optimization specific to the way GHC compiles things, or will other compilers likely either benefit or not care?" is an interesting question that I'd be curious to hear about. (does Criterion work on non-GHC?). but that in my judgment shouldn't delay these particular patches. -Isaac
On Tue, Aug 31, 2010 at 03:07:41PM +0200, Johan Tibell wrote:
-size t - = case t of - Tip -> 0 - Bin sz _ _ _ -> sz +size = go + where + go Tip = 0 + go (Bin sz _ _ _) = sz +{-# INLINE size #-}
Perhaps just size Tip = 0 size (Bin sz _ _ _) = sz would suffice :-) Other than that, and my standard .Internal comment, looks good. Thanks Ian
On Fri, Sep 3, 2010 at 5:26 PM, Ian Lynagh
On Tue, Aug 31, 2010 at 03:07:41PM +0200, Johan Tibell wrote:
-size t - = case t of - Tip -> 0 - Bin sz _ _ _ -> sz +size = go + where + go Tip = 0 + go (Bin sz _ _ _) = sz +{-# INLINE size #-}
Perhaps just
size Tip = 0 size (Bin sz _ _ _) = sz
would suffice :-)
Yes, you're right. This function doesn't actually benefit from W/W as it doesn't have any higher-order arguments, dictionaries or polymorphic arguments. I will take a second pass over all the code after the proposal period is over. With fresh eyes I might be able to spot more things that could be fixed/improved.
participants (3)
-
Ian Lynagh -
Isaac Dupree -
Johan Tibell