In most modem languages, there is a construct that allows the programmer to directly represent a multiway branch based on the value of an expression. In Pascal, it is the case statement; in C:, it is the switch and in Fortran-90 the SELECT. However, it is quite common that the efficiency of these constructs is far worse than one might reasonably expeat. This paper discusses the construction and use of customized hash functions to consistently improve execution speedl and reduce memory usage for such consuucts. Performance results are given, including some that lead to the suggestion that adding a population count instruction to the instruction set of a processor will greatly improve its hashing performance.


multiway branches, hashing, compiler design, Pascal, C, Fortran-!%, population count

Date of this Version

July 1992