Question about ghc case analysis
simonmar at microsoft.com
Tue Aug 9 08:29:59 EDT 2005
On 09 August 2005 12:25, Adrian Hey wrote:
> Well this is actually a couple of questions..
> First question is how does ghc do case analysis on algebraic
> data type constructors. I always assumed it was by using some
> kind of jump table on a tag field, but I don't know really (I'm
> not even sure ghc makes use of tag fields as such).
If the number of constructors is less than or equal to 8 (currently),
GHC uses vectored returns. The case exrpession pushes a return address
on the stack that is a pointer to a vector, and the code for the
constructor jumps to the appropriate entry.
For >8 constructors, GHC uses a direct return address and then a
comparison on the tag value extracted from the constructor's info table.
> Second question is really the same question but for literals.
> What search algorithm is employed and is it likely to be
> worth hand coding something else? (a binary search maybe).
> I'm thinking of code like this..
> case n of
> 0 ->
> 7 ->
> 34622 ->
> .. lots more
> _ ->
GHC's code generator turns these into binary trees or table jumps, or a
combination of the two, depending on the population. But if you're
compiling via C, then we just generate a switch and leave it up to the C
compiler to choose.
More information about the Glasgow-haskell-users