Idea for switch optimization

["Karl M. Hegbloom" <hegbloom at pdx dot edu>]

Consider these ideas to be GPL and from now on part of GCC.  I hearby
assign all rights to the FSF.

While I was reading the "librep" source code (Gnome project, John
Harper; the Lisp in the Sawfish Window Manager), I learned about the
difference between "switch threading", "direct threading" and "indirect
threading".  There are URL references in the librep virtual machine byte
code evaluator source code that refer to documents about "indirect
threaded virtual machines", originated by Forth machine authors.

librep uses a jump table and GCC's computed goto to turn what would
otherwise be a long O(n) test and branch "switch" into an O(1) index and
jump.  It is very interesting code, and I recommend reading it.

What occured to me is that the compiler could optimize large switch
statements like that itself.  I think this could be done almost
trivially when the "case XXX" are sequentially contiguous.  XXX could be
used (perhaps after an adjustment) as an index into a jump table array.

For the case where the XXX are not sequential or contiguous, a mapping
of some sort would need to be constructed and then consulted to come up
with the jump table index.  Perhaps clues to how this can be done lie in
the Linux LVM and/or EVML logical-to-disk block mapping code, and in the
ECL Lisp's lexical environment data structures...

In "Essentials of Programming Languages" (first edition, Friedmann,
Wand, and Haynes, MIT Press) they explain what they call a "ribcage"
structure, and I'm thinking it might be one way of providing this
mapping.  It's an ordered list and an array; the list holds the symbols
and the array the locations where the local binding values are kept.  

For a C "switch", this idea can be adapted as follows.  Rather than a
list and an array, you have one array of small structures.  Each struct
holds the "case XXX" key, an the jump table landing address.  There is
one struct per "case XXX" + default.  The array is kept in XXX order,
and a binary search is used to locate the jump entry.

This optimization turns the O(n) test and branch switch into a O(log_2
n) jump table lookup with one branch.

-----------------------------------------------------------------------
:-)  What if I just said all that then later actually learn to read
compiler code, read GCC, and find that it already does all that? 
Hahah.  I hope someone will code that, if it's not already done, before
I ever get to the point where I can!  It will be more than a year before
I'll have that skill set.

-- 
Karl M. Hegbloom <hegbloom@pdx.edu>

Attachment: signature.asc
Description: This is a digitally signed message part