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<vanenkj@gmail.com> wrote:
> How bad is the lookup compared to normal?
>
> On Sat, Aug 8, 2009 at 9:02 PM, Thomas
> DuBuisson<thomas.dubuisson@gmail.com> wrote:
>> On Sat, Aug 8, 2009 at 5:30 PM, Felipe Lessa<felipe.lessa@gmail.com> 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