Static search structures and GNU gperf

A static search structure is an Abstract Data Type with certain fundamental operations, e.g., initialize, insert, and retrieve. Conceptually, all insertions occur before any retrievals. In practice, gperf generates a static array containing search set keywords and any associated attributes specified by the user. Thus, there is essentially no execution-time cost for the insertions. It is a useful data structure for representing static search sets. Static search sets occur frequently in software system applications. Typical static search sets include compiler reserved words, assembler instruction opcodes, and built-in shell interpreter commands. Search set members, called keywords, are inserted into the structure only once, usually during program initialization, and are not generally modified at run-time.

Numerous static search structure implementations exist, e.g., arrays, linked lists, binary search trees, digital search tries, and hash tables. Different approaches offer trade-offs between space utilization and search time efficiency. For example, an n element sorted array is space efficient, though the average-case time complexity for retrieval operations using binary search is proportional to log n. Conversely, hash table implementations often locate a table entry in constant time, but typically impose additional memory overhead and exhibit poor worst case performance.

Minimal perfect hash functions provide an optimal solution for a particular class of static search sets. A minimal perfect hash function is defined by two properties:

• It allows keyword recognition in a static search set using at most one probe into the hash table. This represents the "perfect" property.
• The actual memory allocated to store the keywords is precisely large enough for the keyword set, and no larger. This is the "minimal" property.

For most applications it is far easier to generate perfect hash functions than minimal perfect hash functions. Moreover, non-minimal perfect hash functions frequently execute faster than minimal ones in practice. This phenomena occurs since searching a sparse keyword table increases the probability of locating a "null" entry, thereby reducing string comparisons. gperf's default behavior generates near-minimal perfect hash functions for keyword sets. However, gperf provides many options that permit user control over the degree of minimality and perfection.

Static search sets often exhibit relative stability over time. For example, Ada's 63 reserved words have remained constant for nearly a decade. It is therefore frequently worthwhile to expend concerted effort building an optimal search structure once, if it subsequently receives heavy use multiple times. gperf removes the drudgery associated with constructing time- and space-efficient search structures by hand. It has proven a useful and practical tool for serious programming projects. Output from gperf is currently used in several production and research compilers, including GNU C, GNU C++, GNU Pascal, and GNU Modula 3. The latter two compilers are not yet part of the official GNU distribution. Each compiler utilizes gperf to automatically generate static search structures that efficiently identify their respective reserved keywords.