Fast Concurrent Memoization Map (Fcmm)
http://projects.giacomodrago.com/fcmm
Fcmm is an almost lock-free concurrent hashmap, providing a limited set of
functionalities:
- The map supports only find() and insert() operations: once an entry is inserted
into the map, it cannot be erased nor updated. The filter() method provides a way
to get a copy of the map containing only certain entries.
- The map can be iterated over with an InputIterator or a range-based for loop.
- The presence of duplicate keys into the map is avoided but the total absence
is not guaranteed. This is not an issue as long as it holds that:
if (k1, v1) and (k2, v2) are entries and k1 == k2, then v1 == v2.
Due to its features, this data structure is fit to be used for memoization in
concurrent environments.
The map is implemented as a single C++ header file with no external dependencies.
IMPORTANT NOTES:
- In order to compile Fcmm, you'll need a C++11 compliant compiler
o Under GNU/Linux, it successfully compiles with gcc 4.7.3
o Under Windows, it successfully compiles with MinGW-w64
(x64-4.8.1-posix-seh-rev2)
o When compiling with gcc, please remember to add the -std=c++11 command
line switch
- Before using Fcmm in a given environment (CPU, Operating System, compiler,
etc...), compile and run test/correctness_test.cpp on that environment.
Please report test failures.
DOCUMENTATION:
- API documentation available at http://projects.giacomodrago.com/fcmm/doc/api
PERFORMANCE CONSIDERATIONS AND BENCHMARKS:
- Fcmm is 'almost' lock-free, in the sense that system-wide progress is always
guaranteed except during map expansion, because of which all threads may block.
- When the map is expanded, it is not rehashed. A new, larger submap is allocated
but the previous submaps are still valid. This means that the more submaps are
allocated, the more time a lookup operation will take.
- For the above reasons, Fcmm delivers its best performance if it never gets
expanded. Therefore, it's strongly recommended to provide Fcmm with a reasonable
estimate of the number of entries the map will store.
- Collisions are resolved using open addressing with double hashing. To achieve
optimal performance, it's important to provide two different hash functions
that are completely independent.
- test/benchmark_tbb.cpp compares Fcmm with tbb::concurrent_hash_map.
Actually, Fcmm and tbb::concurrent_hash_map provide different features (e.g.
Fcmm does not support erase and update) so the benchmark is not meant to be an
'absolute' comparison between the two.
Fcmm may provide a better performance when:
o There is no need to delete or update the entries
o The map shall store a large number of entries and you can provide
a reasonable estimate of their number
o Values are relatively fast to compute
o Concurrency is high (4 threads or more)
If you are interested in some benchmarks, please see BENCHMARKS