Erik Rantapaa | 18 Jul 23:26 2013
Picon

ghc and jump table generation


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?)
Niklas Larsson | 19 Jul 00:07 2013
Picon

Re: ghc and jump table generation

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

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

Gmane