Free Pascal hash maps

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

Maps to compare:
contnrs. TFPHashList TFPDataHashTable
ghashmap. THashMap THashMap.shortstring
gmap. TMap TMap.shortstring
fgl. TFPGMap (sorted)
classes. TStringList (sorted) TStringList (CompareStr)
lazfglhash. TLazFPGHashTable
laz2 xmlutils. THashTable
rtl-generic's linear (TDictionary) quadratic double cuckoo2 cuckoo4 cuckoo6
linear.shortstring quadratic.shortstring double.shortstring cuckoo2.shortstring cuckoo4.shortstring cuckoo6.shortstring
3rd party:
Bero's TFLRECacheHashMap TPasMPHashTable
Yamer's TGenHashMap TGenHashMap.shortstring
Barry Kelly's THashList (fixed size)
CL4L's TStrHashMap (fixed size)
fundamental's TPointerDictionaryA
marcov's lightcontainers generic lightcontainers
hovadur's DeCAL
JUHA's StringHashMap
BeniBela's HAMT mutable HAMT immutable TXQHashmapStr
terrylao's CodaMinaHashMap
avk959's GHashMapLP GHashMapLPT GHashMapQP GChainHashMap GOrderedHashMap GThreadHashMapFG GLiteHashMapLP GLiteChainHashMap

libstdc++'s std::unordered map

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
bubbles: absolute time (abs. memory) abs. memory (abs. time) keys/time (keys/memory) memory/ keys (keys/time) keys/time (memory/keys) memory/keys (time/keys)
ranking: time memory

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 some 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: Then you can choose a metric: 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, the tooltip shows the actual number of keys, time and memory usage.

This benchmark was compiled with freepascal 3.3.1 (r44777), -O4, and run on a 64-bit Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz openSUSE 12.2 system. Older versions: fpc 3.3.1 (r44126), -O3 fpc 3.1.1 (r35800), fpc 3.1.1 (r34557)