[Haskell-cafe] Announce: EnumMap-0.0.1

[Job Vranish]

 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 at 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 at gmail.com> wrote:
> > How bad is the lookup compared to normal?
> >
> > On Sat, Aug 8, 2009 at 9:02 PM, Thomas
> > DuBuisson<thomas.dubuisson at gmail.com> wrote:
> >> On Sat, Aug 8, 2009 at 5:30 PM, Felipe Lessa<felipe.lessa at 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 at haskell.org
> >> http://www.haskell.org/mailman/listinfo/haskell-cafe
> >>
> >
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090809/13ac48ae/attachment.html