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