The history of gperf

In this post I'll document my research into the history of gperf. A copy of the historical documents and source code referenced in this post can be found here.

If you have worked with hashing you have probably used gperf. It is a tool you give a list of keywords and outputs C/C++ code to lookup if a keyword is contained within the list. The lookup function is incredibly fast and looks like black magic.

In 1979 Richard J. Cichelli wrote an article titled Minimal Perfect Hash Functions Made Simple. January 1980 it was published in Communications of the ACM, Volume 23, Issue 1. Back then Richard worked as a Research Manager for American Newspaper Publishers Association Research Institute, but was doing this as part of his own company Software Consulting Services (SCS) which he ran with his wife Martha Cichelli until 2021.


Today, Richard's article is known as Cichelli's Method and works by computing a hash based on the first and last character of the input, as well as the length of the input, then using that hash with an association table to generate a nearly-minimal perfect hash function. Cichelli describes two disadvantages in his article:
  1. It requires that no two keys share length and the first and last characters
  2. For lists with more than about 45 items, segmentation into sublists may be necessary
These limitations will become important in the next paragraph.

In December 1980, Gerhard Jaeschke and  G. Osterburg from IBM Scientific Center in Heidelberg, West Germany published an article in Communications of the ACM, Volume 23, Issue 12 titled Technical Response to: On Cichelli's Minimal Perfect Hash Functions Method. In the article, they determine that there exists an infinite number of keywords, on which Cichelli's perfect hash method (noted as Cichelli's Condition or CD) does not work. As a response to this, Richard adds a third disadvantage:
  1. For certain contrived lists of keys, it may be impossible to determine in advance whether this method will yield a minimal solution.
Note: Gerhard Jaeschke has himself published several articles pertaining to minimal perfect hash functions which are quite interesting, but let's stay on the subject of gperf.

In 1982 Charlie D. Havener wrote a tool called Perfect and in 1983 posted it in the Usenet newsgroup comp.sources.unix. It is based on Cichelli's method, and is the first public implementation, as the Pascal version written by Richard himself was never published. Charlie notes that Perfect was used to write a Lexical Analyzer Data Structure and posted in Appendix B in the article More on Minimal Perfect Hash Tables by Cook, Curtis R. and Oldehoeft, R. R.

Back then Charlie worked with hardware and software design as a senior principal engineer at GenRad Inc. in the component test division in Bolton, Massachusetts. Later in 1988 he taught computer science at Boston University. Unfortunately, Charlie suffered from myelofibrosis (a rare blood cancer) and died November 10, 2012.

In 1984 Keith Bostic posted an improved version of Charlie's Perfect in the Usenet newsgroup net.sources. He highlights the limitations of the original implementation as mentioned above. Keith needed to hash more keywords than what was supported by Perfect, and therefore, rewrote Perfect to support his use case. He notes the following improvements:
  • No limit on the number of keywords
  • Much faster
  • No need to reorder the keywords
  • The ability to specify which keys to hash
  • It handles keywords that hash to identical values
Instead of just taking the first and last characters, Keith's version allows the user to specify which characters to hash.

In January 1989 Douglas C. Schmidt wrote version 1.1 of gperf in C++ while he was at University of California, Irvine, USA. As mentioned in the manual, it was based on Keith's version of Perfect. In May 1989 Douglas made a C version which was published on comp.sources.unix.

For many years, gperf was part of the libg++ library and the sources can still be found in old releases. The earliest release i could find was libg++-1.35.1. In August 2000, with the release of version 2.7, it was moved to be a separate project.

Comments

Post a Comment

Popular posts from this blog

Reducing the size of self-contained .NET Core applications

Just for note keeping, I've written down some methods of reducing the size of a .NET Core application. I thought others could use it as well, so here you go. Original Size First off, let's see how much disk space a self-contained 'hello world' application takes up. > dotnet new console > dotnet publish -r win-x86 -c release Size: 53.9 MB -  yuck! Trimming Microsoft has built a tool that finds unused assemblies and removes them from the distribution package. This is much needed since the 'netcoreapp2.0' profile is basically .NET Framework all over again, and it contains a truckload of assemblies our little 'hello world' application don't use. > dotnet new console > dotnet add package Microsoft.Packaging.Tools.Trimming -v 1.1.0-preview1-25818-01 > dotnet publish -r win-x86 -c release /p:TrimUnusedDependencies=true Size: 15.8 MB Much better! Although, we have only removed unused assemblies - what about unused...
Read more

.NET Compression Libraries Benchmark

Image
I often find myself needing a compression library in a software development project, and after a few tests with disappointing results I usually fall back to spawning 7Zip as an external process. This time however, the application specification prohibits any data written to disk, which 7Zip needs to do in order to work correctly. I needed to do everything in memory, and so I had to test some of the C# libraries available for compression as well as the different compression algorithms. Here is a full list of the tested libraries: .NET DeflateStream ICSharpCode SharpZip Zlib.NET DotNetZip Managed LZMA LZMA SDK QuickLZ    Compression 101 Before I get to the results of the benchmark, I think it is important to understand the different archive formats and compression algorithms in order to compare the results with other benchmarks/and or tests. Lets get to it! A compression algorithm can be compared to a small machine that takes in some data, do some math on it and...
Read more

The Ramer-Douglas-Peucker Polygon Simplification Algorithm

Image
One of the important algorithms in vector graphics and robotics is the Ramer-Douglas-Peucker algorithm. It simplifies a polygon by reducing the number of points by some tolerance. It was invented independently by Urs Ramer in 1972 and by David Douglas & Thomas Peucker in 1973. In 1992 it was improved by John Hershberger & Jack Snoeyink at the cost of the algorithm only working with simple 2D planar polylines, and not in higher dimentions. Here is how it roughly works: 0. Start with a polygon. 1. Make a polyline between the two endpoints. This is the initial approximation to the simplified polygon. 2. Calculate the distance between the edge and the remaining vertices. If the vertex tested is further away that the user defined tolerance, then the vertex is added to the simplification. 3. Repeat step 2 until you have a complete approximation of the polygon like shown in step 4 in the picture.   The idea with the algorithm is that we can give it an input like t...
Read more