Free Pascal hash maps

One Benchmark to Rule Them All

This is an exhausive benchmark of string-key based (hash)maps available for Free Pascal.

Maps to compare:
contnrs.TFPHashList contnrs.TFPDataHashTable
ghashmap.THashMap ghashmap.THashMap.shortstring
gmap.TMap gmap.TMap.shortstring
fgl.TFPGMap (sorted)
classes.TStringList (sorted)
rtl-generic's linear rtl-generic's double rtl-generic's cuckoo2 rtl-generic's cuckoo4 rtl-generic's cuckoo6 rtl-generic's linear.shortstring rtl-generic's double.shortstring rtl-generic's cuckoo2.shortstring rtl-generic's cuckoo4.shortstring rtl-generic's cuckoo6.shortstring
Bero's TFLRECacheHashMap Bero's TPasMPHashTable
Yamer's TGenHashMap Yamer's TGenHashMap.shortstring
Barry Kelly's THashList (fixed size)
CL4L's TStrHashMap (fixed size)
fundamental's TPointerDictionaryA
marcov's lightcontainers marcov's generic lightcontainers
hovadur's DeCAL
JUHA's StringHashMap

Datasets: Dictionary words (~16 characters) Short random keys (8 bytes) Long random keys (200 bytes)

Model: (writes,succeeding lookups,failed lookups) Only writes (1,0,0) Balanced (1,3,3) Many Reads (1,20,2) Many Failed Lookups (1,2,20) Custom prediction: , ,

Metric: absolute time (ms) absolute memory (bytes) keys / time keys / memory time, memory memory, time time / memory memory / time time / keys memory / keys

x-axis: linear logarithmic     y-axis: linear logarithmic     keys limit: to

General observations:

Good built-in maps:

Good 3rd-party maps:

Generally, all 3rd-party maps perform well, but two are especially notable as they are faster than the fpc provided maps in most situations:

Other built-in maps:

How to choose a hashmap

This benchmark can be used to select the ideal map for a specific use case: If this page is too slow, you can uncheck all checkboxes in a category, then no plots are shown and selections are instantanously. You can also disable maps by clicking their name on the legend without affecting other plots. Some maps have no datapoints for high key count, then only points with low key counts are shown and the map might appear more efficient than it is in the scatter plot. Move the mouse over the data points to check.

This benchmark was compiled with freepascal 3.1.1 (r34557) and run on a 64-bit 1.6 GHz openSUSE 12.2 computer.