Question about ghc case analysis

[Simon Marlow]

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.

Cheers,
	Simon