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:
For small keys, TFPHashList is the fastest map of all maps provided by FreePascal. However, for longer keys or dozens of lookups the performances degrades drastically. It uses shortstrings, so there is a hard-limit of 256 byte keys (which can also explain the lookup slowdown, as the benchmark uses ansistrings), and it seems to copy all strings, as its memory usage is very low for small keys, but also increases drastically with the key length.
The maps of the rtl-generic.collections package can be classified in two groups: non-cuckoo maps (linear, double hashing) and cuckoo maps.
With the parameters actually used in this benchmark, the non-cuckoo maps are always faster than the cuckoo map or other maps. Slightly slower than TFPHashList for small keys, but faster for long keys. The linear map appears to be slightly faster than the double hashing one (at least when the keys are truly random).
When the number of reads increases to a few dozen queries/key, the cuckoo maps will be faster than the non-cuckoo maps (shown by the difference between writing and reading speed). They also use less memory and especially cuckoo-6 is the most memory efficient hash map of them all, but also the slowest. Cuckoo-2 is the fastest cuckoo-map, but uses nearly the same memory as the non-cuckoo maps. Cuckoo-4 is in-between.
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:
Yamer's TGenHashMap in the gcontnrs package is faster and uses less memory than the non-cuckoo maps, but requires more memory than the memory-efficient cuckoo-maps. For small keys its characterists even matches TFPHashList.
Bero's FLRE cache map is an internal used map in the FLRE-package, so it is not the easiest map to use. It is the fastest map for long keys, and similar to TFPHashList and Yamer's map for short keys. However, it has slightly higher memory usage.
Other built-in maps:
The array based TStringList and TFPGMap are the most memory efficient, using less memory than even the cuckoo maps. However, as they are not hash maps, their usage is extremely slow, even if the maps are sorted, so they are nearly useless as maps. Their default setting of unsorted and (in case of TStringList) case-insensitive matching are quite dangerous.
ghashmap is as fast as the rtl-generics map for short keys, but similar to TFPHashList its performance degrades with longer keys. Unlike TFPHashList it is not the fastest before the slow-down afterwards, so it becomes one of the slowest. It also has a high memory usage.
gmap.TMap is a slow map, because it is implemented as tree.
TFPDataHashTable (as well as TLazFPGHashTable) is an interesting map. At first it appears very fast, but with more elements it becomes very slow. The explanation is that it has a high-default capacity of around 200 000 items and does not grow. Colliding items are stored in a tree-structure, which becomes inefficient as soon as the initial capacity is exceeded.
How to choose a hashmap
This benchmark can be used to select the ideal map for a specific use case:
Enter the minimal and maximal count of expected items at "keys limit".
Select the metric "time, memory".
Select the model "custom prediction" and enter how often each item will be inserted, read, not found.
Select the dataset that corresponds to your key length.
Select the maps you consider using.
The scatter plot will then show an estimate of time and memory requirements.
The points of fastest map will be on the left side, the maps with the lowest memory usage will be at the bottom. Therefore, if you think of the plot as split into quarters, the bottom left will have optimal maps, the top left will have fast maps with huge memory usage, the bottom right will have memory efficient slow maps, and the top right will have useless maps.
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.