This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Hash Function for "switch statement"


Jae Hyuk Kwak wrote:

Now we have a switch statement that has 400 cases or whatever.

switch ( valueFormUser )
{
   case 0: do1(); break;
   case 1: do2(); break;
   case 2: do3(); break;
   ...
   case 399: do399(); break;
   default: break;

Well clearly if you have 400 cases like this, perfect hashing is NOT going to help, since a simple jump table will help.

The case where perfect hashing would help is when there are
a bunch of values that are sparse and somewhat random in
nature, which is rare in practice.

Very often, even sparse cases have ranges which can be quickly
separated and then handled with jump tables. In any case the
most efficient way of handling arbitrary big cases will be some
kind of divide and conquer approach where you use the appropriate
algorithm at each stage.

Clearly you don't want to use a perfect hash for a case that
has cases 0 .. 500  and  55550000 .. 55550999, since simple if tests
will be better in this case.

on the other hand if you have a bunch of 256 values, and you find
that they are distinct in the last 8 bits, then the perfect hash
is just a single and, and in this case clearly the best approach
would be to do the single AND with a jump table. But it is hard
to believe that such a case would occur in any other context than
a test to test this particular clever optimization :-)

In the case the conflict happened, we change the value of "c2" until none of values of cases conflict. In other words, we change c2 value until we get "hash32shiftmult( 0, c2 ) != hash32shiftmult( 1, c2 ) != hash32shiftmult( 2, c2 )...."

Therefore we will have "Perfect hash table", so that there is no
conflict during run-time.
In other words, we will have fixed constant cost for hash table
resolving; there is no 'hash badly" case.

In fact, it will make compile time longer, if it is your interest.
But again, I am talking about run-time speed.


A quote from this article:

" ... the switch very efficiently, even constructing a hash table if this
method of switching is ..."

Yes, it does. Such a old paper mentioned it and we are still not doing it. So it makes me wonder why.

Thanks

Jay


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]