Re: Adapting switch(x){case(y):...} with hashing

[Michael Meissner <meissner at cygnus dot com>]

On Fri, Dec 01, 2000 at 01:21:25AM -0600, Andy Walker wrote:
> One of the obscure to-do list entries had an interesting request.
> Currently, g++ uses a binary-tree / jump-table solution to handle
> "switch"-"case" processing.  The request was for hashing to be added as
> an alternative when it would be appropriate (the note suggested sparse
> sets).  Obviously, the problem is more complex than it appears, and
> binary searches have their strengths.  Also, memory requirements may be
> critically fatal.

A few years after I started working in compilers (1979), there were a couple of
papers on the subject, and I did some heuristics for the proprietary C compiler
front end I wrote where if the jump array is too large, it would see if it
could take a few elements off the switch array and implementing them as ifs and
using a jump table for the rest (this was useful in our environment, because we
had global error messages, and the UNIX E* error codes where mapped to starting
at a large offset, and if the user had a case 0: in addition to the E*
messages, you could still use a table).

One concern is that many of our embedded machines don't have divide
instructions, and/or the divide instructions takes an ungoodly amount of cycles
(also if the divide emulation functions happened to contain a switch that the
compiler would do via hashing).

Another thing to think about is the size of the hash table, either may force a
hash table that is much larger the number of instructions it takes to do it via
binary search, or cause the data section to be unacceptably bloated (some
embedded processors have very limited data spaces but somewhat larger text
spaces).

> Is anyone working on this?  If not, would anyone like to engage in a
> little discussion before I waste a lot of time on something *really*
> stupid (in the hope that I learn about it before, rather than after
> coding and testing :-P).
> 
> It just really ticks me off every time I use my debugger at work.  I use
> it on compiled C++ output from a well-known commercial vendor, and I
> have to sequentially step through every "case" statement to reach the
> one it should have used in the first place (obviously, they did not use
> binary searches, either.)  There is probably a good reason for that
> behavior, and I will know it after trying to code it    However, it
> makes no sense to me right now.
> 
> Your critical comments are invited.
> 
>     Andy
> 

-- 
Michael Meissner, Red Hat, Inc.
PMB 198, 174 Littleton Road #3, Westford, Massachusetts 01886, USA
Work:	  meissner@redhat.com		phone: +1 978-486-9304
Non-work: meissner@spectacle-pond.org	fax:   +1 978-692-4482