In the late 1980s I implemented an algorithm for computing a Perfect Hash Function, given a fixed set of keys, by Richard J. Cichelli, published in the CACM January 1980. It was just a fun little algorithm, not terribly useful in itself, but at the time it could take some substantial time to run on some sets of keys. I have since maintained this and run it on all kinds of machines that have crossed my path over the years which provides a perhaps interesting view of how computer performance has improved in the last 30-40 years.
One of the tests was a set of 32 reserved words in (pre-ANSI) C, and some of the first machines it was run on were:
- VAX 750: Running time was 32 minutes.
- DECSYSTEM-2060 (PDP-10): 16 minutes.
- Sun-3/160 (Motorola 68020): 11 minutes.
The latest machine it was run on was my current laptop:
- Macbook Pro (M1): 0.17 seconds.
Here is a graph of the performance of different hardware, roughly mapped to the year when it was current.
Note that the program is entirely CPU bound and uses very little memory. For instance, the DECSYSTEM-20 mainframe would run in circles around the little Sun-3 when it came to multi-user and disk I/O performance.
Here are some more noticeable machines where it has been tested:
- HP 9000/350, 68020, 6 minutes 32 seconds
- Apollo DN3500, 68030, 6:27
- Sony NEWS/1750, 68030, 5:24
- HP 9000/820, HPPA, 3:33
- A number of different Sun Sparc Systems and Stations, for instance a SPARCsystem 640/MP, SPARC 50MHz, 24.9 seconds
- SGI Indigo, MIPS R4400 250MHz, 12.9 s
- Raspberry Pi B, armv61 700MHz, 3.2 s
- iPC Max, Pentium 4 3GHz, 0.63 s
- MacBook Pro, Intel i7 2.5GHz, 0.25 s
(The full list contains more than 30 machines.)