Inlining natFromInt and intFromNat improves things considerably. Using Thomas DuBuisson's benchmarking code (with a larger number of keys):
IntMap: buildMap: 12.2 lookupMap: 2.7 Original EnumMap: buildMap: 13.0s lookupMap: 3.6s EnumMap built with -O2 (not sure the implications of building libraries with -O2) buildMap: 12.9s lookupMap: 2.7s effectively the same time for inserts compared with the original EnumMap improved performance for lookups (effectivly the same as IntMap) EnumMap built with -O2, inline on natFromInt and intFromNat and specialize for insert, and join: (doesn't appear to get a speedup with specialize on lookup and lookupN if EnumMap is built with -O2) buildMap: 12.2s lookupMap: 2.7s The same performance as IntMap! I'm kinda dissapointed ghc can't figure this out automatically, fromEnum/toEnum for Ints is just id. Oh well, a few more annotations in the library and wouldn't see any reason why EnumMap would be slower that IntMap. I'll submit a patch I also tried EnumMap but with a newtyped Int for the keys. I get the same performance for lookups as Int, but the inserts are slower. buildMap: 12.8s lookupMap: 2.7s My guess is that the specialize pragma on insert isn't getting triggered on the newtype (which I think it should) So I have a suggestion for a ghc optimization: Unwrap newtypes before specialization so that the specializer can take advantage of the underlying type. - Job On Sun, Aug 9, 2009 at 12:08 AM, Thomas DuBuisson < [email protected]> wrote: > Inflating the number of elements in the test, I see: > > IntMap > inserts: 5.3 seconds > lookups: 2.0 seconds > > EnumMap > inserts: 6.1 sec (15% slower) > lookups: 2.5 sec (25% slower) > > EnumMap with SPECIALIZE of: > {-# SPECIALIZE join :: Prefix -> EnumMap Int a -> Prefix -> EnumMap > Int a -> EnumMap Int a #-} > {-# SPECIALIZE lookup :: Int -> EnumMap Int a -> Maybe a #-} > {-# SPECIALIZE lookupN :: Nat -> EnumMap Int a -> Maybe a #-} > {-# SPECIALIZE insert :: Int -> a -> EnumMap Int a -> EnumMap Int a #-} > inserts: 5.3 seconds (dead on) > lookups: 2.6 seconds (owch!) > > Additionally specializing the functions used in lookup{,N} doesn't > help. I tried inlining (via INLINE) a couple things but that only > made performance notably worse. > > > Thomas > > On Sat, Aug 8, 2009 at 8:29 PM, John Van Enk<[email protected]> wrote: > > How bad is the lookup compared to normal? > > > > On Sat, Aug 8, 2009 at 9:02 PM, Thomas > > DuBuisson<[email protected]> wrote: > >> On Sat, Aug 8, 2009 at 5:30 PM, Felipe Lessa<[email protected]> > wrote: > >>> On Sat, Aug 08, 2009 at 04:14:15PM -0700, Thomas DuBuisson wrote: > >>>> There exists a small but measurable performance hit for at least one > >>>> test case (using Int as keys, obviously). Perhaps the bias would be > >>>> the other way if we were comparing EnumMap to an IntMap wrapped with > >>>> to/from Enum. > >>> > >>> Perhaps some SPECIALIZE pragmas would help here. > >>> > >> > >> Actually I tried that by adding SPECIALIZE to insert, insertN and > >> lookup. it seemed to make the insert benchmark competitive but not > >> lookup. > >> > >> Thomas > >> _______________________________________________ > >> Haskell-Cafe mailing list > >> [email protected] > >> http://www.haskell.org/mailman/listinfo/haskell-cafe > >> > > > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
