Re: [bug-gperf] bit packing tricks

[Bruno Haible]

Hi Mark,

> FIFTH SUGGESTION ( MORE THAN MEDIUM DIFFICULT )
> 
>   This suggestion is motivated by examples where the word_list is
> somewhat short. Short means that the log base 2 of the length of the
> word list is small.
> 
>   Let's say the maximum hash key is 5 like in example permut2.gperf.
> If we round up to the next power of 2, we get 8. Recall 8 = 2^3.
> So we only need 3 bits to store a number from 0 to 7. To store
> 256 three bit chunks, we would need a minimum of 768 bits.

Using bit packing tricks is a good approach, because it can help
shrinking the array a lot, without introducing more than one additional
conditional jump.

Two approaches can be investigates independently:

  - Making the 'asso_values' array contain n-bit chunks, instead of 8-bit
    chunks, like you say. (Here n = 3.)

  - Viewing the input string not as an array of N bytes (each byte being
    in the range 0..255), but as an array of 2*N nibbles (each nibble being
    in the range 0..15). The resulting asso_values array should become much
    shorter.

>   I could help with all of this if someone points me in the right direction
> and there is an interest in seeing some or all of it done.

Yes, these here would be promising. To go further, you would need to
  1) Learn how to do reliable timing (it is not trivial; maybe use valgrind to
     measure cache misses and such?).
  2) Make actual timings of modified hash functions according to one of the
     ideas.

Bruno