[Haskell-cafe] ghc and jump table generation

[Niklas Larsson]

Hi!


2013/7/18 Erik Rantapaa <erantapaa at yahoo.com>

>
>
> I've been looking at the assembly code that ghc generates for simple
> pattern matching for situations like:
>
> foo :: Int -> Int
> foo 1 = 3
> foo 2 = 10
> foo 3 = 2
> foo 4 = 42
> -- ... other random assignments
>
> and I noticed that it doesn't seem to generate a jump table (or even a
> table lookup)  like, for instance, gcc would for this switch statement:
>
> int foo(int x) {
>   switch (c) {
>     case 1: return 3;
>     case 2: return 10;
>     case 3: return 2;
>     case 4: return 42;
>     // ... etc.
>   }
> }
>
> Under -O3 ghc seems to produce a binary-search of the cases.
>
> Questions: Would generating a jump/lookup table for pattern matches like
> this (i.e. with a suitable density of cases) be beneficial? And, if so,
> would it be difficult to add to ghc? And would it be a good first project
> for someone who wants to get into the ghc code base (perhaps with some
> mentoring from the community?)
>

I was just digging around in the native code generator so I have a few
leads for you.

GHC can already generate jump tables, look at genSwitch in
compiler/nativeGen/X86/CodeGen.hs, and it is what a CmmSwitch gets compiled
into. Follow that into the codeGen and you see CmmSwitch is only created in
emitSwitch in StgCmmExpr.hs. You can follow that farther and see when that
is invoked.

I have no clue if it's a worthwhile thing to do. Try it and measure the
impact.

Niklas


> _______________________________________________
> 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/20130719/e2a5b188/attachment.htm>