Re: [Haskell-cafe] Announce: EnumMap-0.0.1

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 < thomas.dubuisson@gmail.com> 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 wrote:

...

How bad is the lookup compared to normal?

On Sat, Aug 8, 2009 at 9:02 PM, Thomas DuBuisson wrote:

...

On Sat, Aug 8, 2009 at 5:30 PM, Felipe Lessa 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe