[fpc-devel] Sorry for poor testing
Franz MÃ¼ller
office at focusdata.at
Wed Jan 16 15:15:56 CET 2019
Hi!
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.
Franz
More information about the fpc-devel
mailing list