respu / fcmm Goto Github PK

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