This repository contains different implementation of a dictionary in C++. The dictionary can either insert/erase/search words in it. When searching, it will return a pair containing the closest word matching the query and the Damerau-levenshtein distance of the query and the closes word.
There are multiple implementations in this repository. Some of them are asynchronous and some are synchronous. You can measure the different implementations performance with the bench running:
$ ./bench --benchmark_filter='BenchGenericShort/*'
Example benchmark result:
2018-06-21 10:16:11
Running ./bench
Run on (4 X 3500 MHz CPU s)
CPU Caches:
L1 Data 32K (x4)
L1 Instruction 32K (x4)
L2 Unified 256K (x4)
L3 Unified 6144K (x1)
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations
------------------------------------------------------------------------------------
BenchGenericShort/Naive_NoAsync/real_time 107255 ms 107137 ms 1 9.32356 items/s
BenchGenericShort/Naive_Async/real_time 107783 ms 107644 ms 1 9.27792 items/s
BenchGenericShort/Trie_NoAsync/real_time 5664 ms 5657 ms 1 176.554 items/s
BenchGenericShort/Trie_GlobalAsync/real_time 1958 ms 11 ms 1 510.754 items/s
BenchGenericShort/Trie_Async/real_time 1834 ms 10 ms 1 545.189 items/s
The most efficient implementation is the TrieAsync class. It uses atomic
operations to ensure safety. Careful as it uses a logical delete. If you need to
be efficient in memory using a lot of erase procedure, this implementation
will fail as it does not free memory unless the Trie is destroyed.