Hi!
2013/7/18 Erik Rantapaa
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe