[fpc-devel] Sorry for poor testing

Franz Müller office at focusdata.at
Wed Jan 16 15:15:56 CET 2019


I have a proposition for optimizing big case statements with sparse case 
labels. Have you already thought of using a hash function to drastically 
reduce the size of the jump table?

I have made some tests. For example, assume a case statement with 80 
values for case labels in the range between 1 and 5000.

No matter how they are distributed, It is always possible to find a hash 
function of the type y=(a*x^2+b*x) and 252 , to map those 80 values 
directy to a 64 entry hash table with 16 bit jump offset values (this 
hash function gives directly the offset of the correct jump table 
entry), where 3 or less case label values are mapped to each entry. You 
just have to try different prime numbers in the range 20000-30000 for 
the values of a and b, to find a hash function that works well for the 
given combination of case label values. At runtime, after calculation of 
the hash function - one addition, two 16-bit multiplications and one 
"and" operation - you need just three or less 16 bit comparisons to find 
the correct case branch for all possible values of the case variable.


More information about the fpc-devel mailing list