A family of header-only, very fast and memory-friendly hashmap and btree containers.

The Parallel Hashmap Build Status Build Status

Overview

This repository aims to provide a set of excellent hash map implementations, as well as a btree alternative to std::map and std::set, with the following characteristics:

  • Header only: nothing to build, just copy the parallel_hashmap directory to your project and you are good to go.

  • drop-in replacement for std::unordered_map, std::unordered_set, std::map and std::set

  • Compiler with C++11 support required, C++14 and C++17 APIs are provided (such as try_emplace)

  • Very efficient, significantly faster than your compiler's unordered map/set or Boost's, or than sparsepp

  • Memory friendly: low memory usage, although a little higher than sparsepp

  • Supports heterogeneous lookup

  • Easy to forward declare: just include phmap_fwd_decl.h in your header files to forward declare Parallel Hashmap containers [note: this does not work currently for hash maps with pointer keys]

  • Dump/load feature: when a flat hash map stores data that is std::trivially_copyable, the table can be dumped to disk and restored as a single array, very efficiently, and without requiring any hash computation. This is typically about 10 times faster than doing element-wise serialization to disk, but it will use 10% to 60% extra disk space. See examples/serialize.cc. (flat hash map/set only)

  • Tested on Windows (vs2015 & vs2017, vs2019, Intel compiler 18 and 19), linux (g++ 4.8.4, 5, 6, 7, 8, clang++ 3.9, 4.0, 5.0) and MacOS (g++ and clang++) - click on travis and appveyor icons above for detailed test status.

  • Automatic support for boost's hash_value() method for providing the hash function (see examples/hash_value.h). Also default hash support for std::pair and std::tuple.

  • natvis visualization support in Visual Studio (hash map/set only)

@byronhe kindly provided this Chinese translation of the README.md.

Fast and memory friendly

Click here For a full writeup explaining the design and benefits of the Parallel Hashmap.

The hashmaps and btree provided here are built upon those open sourced by Google in the Abseil library. The hashmaps use closed hashing, where values are stored directly into a memory array, avoiding memory indirections. By using parallel SSE2 instructions, these hashmaps are able to look up items by checking 16 slots in parallel, allowing the implementation to remain fast even when the table is filled up to 87.5% capacity.

IMPORTANT: This repository borrows code from the abseil-cpp repository, with modifications, and may behave differently from the original. This repository is an independent work, with no guarantees implied or provided by the authors. Please visit abseil-cpp for the official Abseil libraries.

Installation

Copy the parallel_hashmap directory to your project. Update your include path. That's all.

If you are using Visual Studio, you probably want to add phmap.natvis to your projects. This will allow for a clear display of the hash table contents in the debugger.

A cmake configuration files (CMakeLists.txt) is provided for building the tests and examples. Command for building and running the tests is: mkdir build && cd build && cmake -DPHMAP_BUILD_TESTS=ON -DPHMAP_BUILD_EXAMPLES=ON .. && cmake --build . && make test

Example

#include <iostream>
#include <string>
#include <parallel_hashmap/phmap.h>

using phmap::flat_hash_map;
 
int main()
{
    // Create an unordered_map of three strings (that map to strings)
    flat_hash_map<std::string, std::string> email = 
    {
        { "tom",  "[email protected]"},
        { "jeff", "[email protected]"},
        { "jim",  "[email protected]"}
    };
 
    // Iterate and print keys and values 
    for (const auto& n : email) 
        std::cout << n.first << "'s email is: " << n.second << "\n";
 
    // Add a new entry
    email["bill"] = "[email protected]";
 
    // and print it
    std::cout << "bill's email is: " << email["bill"] << "\n";
 
    return 0;
}

Various hash maps and their pros and cons

The header parallel_hashmap/phmap.h provides the implementation for the following eight hash tables:

  • phmap::flat_hash_set
  • phmap::flat_hash_map
  • phmap::node_hash_set
  • phmap::node_hash_map
  • phmap::parallel_flat_hash_set
  • phmap::parallel_flat_hash_map
  • phmap::parallel_node_hash_set
  • phmap::parallel_node_hash_map

The header parallel_hashmap/btree.h provides the implementation for the following btree-based ordered containers:

  • phmap::btree_set
  • phmap::btree_map
  • phmap::btree_multiset
  • phmap::btree_multimap

The btree containers are direct ports from Abseil, and should behave exactly the same as the Abseil ones, modulo small differences (such as supporting std::string_view instead of absl::string_view, and being forward declarable).

When btrees are mutated, values stored within can be moved in memory. This means that pointers or iterators to values stored in btree containers can be invalidated when that btree is modified. This is a significant difference with std::map and std::set, as the std containers do offer a guarantee of pointer stability. The same is true for the 'flat' hash maps and sets.

The full types with template parameters can be found in the parallel_hashmap/phmap_fwd_decl.h header, which is useful for forward declaring the Parallel Hashmaps when necessary.

Key decision points for hash containers:

  • The flat hash maps will move the keys and values in memory. So if you keep a pointer to something inside a flat hash map, this pointer may become invalid when the map is mutated. The node hash maps don't, and should be used instead if this is a problem.

  • The flat hash maps will use less memory, and usually be faster than the node hash maps, so use them if you can. the exception is when the values inserted in the hash map are large (say more than 100 bytes [needs testing]) and costly to move.

  • The parallel hash maps are preferred when you have a few hash maps that will store a very large number of values. The non-parallel hash maps are preferred if you have a large number of hash maps, each storing a relatively small number of values.

  • The benefits of the parallel hash maps are:
    a. reduced peak memory usage (when resizing), and
    b. multithreading support (and inherent internal parallelism)

Key decision points for btree containers:

Btree containers are ordered containers, which can be used as alternatives to std::map and std::set. They store multiple values in each tree node, and are therefore more cache friendly and use significantly less memory.

Btree containers will usually be preferable to the default red-black trees of the STL, except when:

  • pointer stability or iterator stability is required
  • the value_type is large and expensive to move

When an ordering is not needed, a hash container is typically a better choice than a btree one.

Changes to Abseil's hashmaps

  • The default hash framework is std::hash, not absl::Hash. However, if you prefer the default to be the Abseil hash framework, include the Abseil headers before phmap.h and define the preprocessor macro PHMAP_USE_ABSL_HASH.

  • The erase(iterator) and erase(const_iterator) both return an iterator to the element following the removed element, as does the std::unordered_map. A non-standard void _erase(iterator) is provided in case the return value is not needed.

  • No new types, such as absl::string_view, are provided. All types with a std::hash<> implementation are supported by phmap tables (including std::string_view of course if your compiler provides it).

  • The Abseil hash tables internally randomize a hash seed, so that the table iteration order is non-deterministic. This can be useful to prevent Denial Of Service attacks when a hash table is used for a customer facing web service, but it can make debugging more difficult. The phmap hashmaps by default do not implement this randomization, but it can be enabled by adding #define PHMAP_NON_DETERMINISTIC 1 before including the header phmap.h (as is done in raw_hash_set_test.cc).

  • Unlike the Abseil hash maps, we do an internal mixing of the hash value provided. This prevents serious degradation of the hash table performance when the hash function provided by the user has poor entropy distribution. The cost in performance is very minimal, and this helps provide reliable performance even with imperfect hash functions.

Memory usage

type memory usage additional peak memory usage when resizing
flat tables flat_mem_usage flat_peak_usage
node tables node_mem_usage node_peak_usage
parallel flat tables flat_mem_usage parallel_flat_peak
parallel node tables node_mem_usage parallel_node_peak
  • size() is the number of values in the container, as returned by the size() method
  • load_factor() is the ratio: size() / bucket_count(). It varies between 0.4375 (just after the resize) to 0.875 (just before the resize). The size of the bucket array doubles at each resize.
  • the value 9 comes from sizeof(void *) + 1, as the node hash maps store one pointer plus one byte of metadata for each entry in the bucket array.
  • flat tables store the values, plus one byte of metadata per value), directly into the bucket array, hence the sizeof(C::value_type) + 1.
  • the additional peak memory usage (when resizing) corresponds the the old bucket array (half the size of the new one, hence the 0.5), which contains the values to be copied to the new bucket array, and which is freed when the values have been copied.
  • the parallel hashmaps, when created with a template parameter N=4, create 16 submaps. When the hash values are well distributed, and in single threaded mode, only one of these 16 submaps resizes at any given time, hence the factor 0.03 roughly equal to 0.5 / 16

Iterator invalidation for hash containers

The rules are the same as for std::unordered_map, and are valid for all the phmap hash containers:

Operations Invalidated
All read only operations, swap, std::swap Never
clear, rehash, reserve, operator= Always
insert, emplace, emplace_hint, operator[] Only if rehash triggered
erase Only to the element erased

Iterator invalidation for btree containers

Unlike for std::map and std::set, any mutating operation may invalidate existing iterators to btree containers.

Operations Invalidated
All read only operations, swap, std::swap Never
clear, operator= Always
insert, emplace, emplace_hint, operator[] Yes
erase Yes

Example 2 - providing a hash function for a user-defined class

In order to use a flat_hash_set or flat_hash_map, a hash function should be provided. This can be done with one of the following methods:

  • Provide a hash functor via the HashFcn template parameter

  • As with boost, you may add a hash_value() friend function in your class.

For example:

#include <parallel_hashmap/phmap_utils.h> // minimal header providing phmap::HashState()
#include <string>
using std::string;

struct Person
{
    bool operator==(const Person &o) const
    { 
        return _first == o._first && _last == o._last && _age == o._age; 
    }

    friend size_t hash_value(const Person &p)
    {
        return phmap::HashState().combine(0, p._first, p._last, p._age);
    }

    string _first;
    string _last;
    int    _age;
};
  • Inject a specialization of std::hash for the class into the "std" namespace. We provide a convenient and small header phmap_utils.h which allows to easily add such specializations.

For example:

file "Person.h"

#include <parallel_hashmap/phmap_utils.h> // minimal header providing phmap::HashState()
#include <string>
using std::string;

struct Person
{
    bool operator==(const Person &o) const
    { 
        return _first == o._first && _last == o._last && _age == o._age; 
    }

    string _first;
    string _last;
    int    _age;
};

namespace std
{
    // inject specialization of std::hash for Person into namespace std
    // ----------------------------------------------------------------
    template<> struct hash<Person>
    {
        std::size_t operator()(Person const &p) const
        {
            return phmap::HashState().combine(0, p._first, p._last, p._age);
        }
    };
}

The std::hash specialization for Person combines the hash values for both first and last name and age, using the convenient phmap::HashState() function, and returns the combined hash value.

file "main.cpp"

#include "Person.h"   // defines Person  with std::hash specialization

#include <iostream>
#include <parallel_hashmap/phmap.h>

int main()
{
    // As we have defined a specialization of std::hash() for Person,
    // we can now create sparse_hash_set or sparse_hash_map of Persons
    // ----------------------------------------------------------------
    phmap::flat_hash_set<Person> persons = 
        { { "John", "Mitchell", 35 },
          { "Jane", "Smith",    32 },
          { "Jane", "Smith",    30 },
        };

    for (auto& p: persons)
        std::cout << p._first << ' ' << p._last << " (" << p._age << ")" << '\n';

}

Thread safety

Parallel Hashmap containers follow the thread safety rules of the Standard C++ library. In Particular:

  • A single phmap hash table is thread safe for reading from multiple threads. For example, given a hash table A, it is safe to read A from thread 1 and from thread 2 simultaneously.

  • If a single hash table is being written to by one thread, then all reads and writes to that hash table on the same or other threads must be protected. For example, given a hash table A, if thread 1 is writing to A, then thread 2 must be prevented from reading from or writing to A.

  • It is safe to read and write to one instance of a type even if another thread is reading or writing to a different instance of the same type. For example, given hash tables A and B of the same type, it is safe if A is being written in thread 1 and B is being read in thread 2.

  • The parallel tables can be made internally thread-safe for concurrent read and write access, by providing a synchronization type (for example std::mutex) as the last template argument. Because locking is performed at the submap level, a high level of concurrency can still be achieved. Read access can be done safely using if_contains(), which passes a reference value to the callback while holding the submap lock. Similarly, write access can be done safely using modify_if, try_emplace_l or lazy_emplace_l. However, please be aware that iterators or references returned by standard APIs are not protected by the mutex, so they cannot be used reliably on a hash map which can be changed by another thread.

  • Examples on how to use various mutex types, including boost::mutex, boost::shared_mutex and absl::Mutex can be found in examples/bench.cc

Using the Parallel Hashmap from languages other than C++

While C++ is the native language of the Parallel Hashmap, we welcome bindings making it available for other languages. One such implementation has been created for Python and is described below:

Acknowledgements

Many thanks to the Abseil developers for implementing the swiss table and btree data structures (see abseil-cpp) upon which this work is based, and to Google for releasing it as open-source.

Owner
Comments
  • Question: keys with multiple integers

    Question: keys with multiple integers

    Good morning, I have a very simple question.

    Let's say that I want to create a hash table and use keys identified by 3 integer values. For example:

    {1, 4, 5} ---> 3 {3, 4, 6} ---> 7 ecc...

    Namely, each key can have only one single value associated to it, but the key itself is identified by 3 (ore more!) integers.

    Is that possible to do something like this with these hash tables?

    If the answer is yes, could you please provide me a super easy example which explains how to achieve this? Otherwise, if the answer is no, is there an easy way to do something like in c++, for example using the STL?

    Thank you very much for your help and congratulations!

  • Recommendation for  deserializing a large hashmap?

    Recommendation for deserializing a large hashmap?

    Thank you Greg for this awesome contribution, I am finding it quite useful for my application.

    I plan to generate a very large hashmap with bitsets as the key and integers as the value. The size of the hashmap will be 10GB when serialized to binary. It might also be important to note that the hashmap will not be modified after generation; purely used for look-up purposes.

    I went ahead and serialized a 1GB flat hashmap using cereal and that took about 10 minutes, while it took about 20 minutes to deserialize.

    From what I could gather, hashmaps are slow to deserialize due to the fact they need to repopulate the entire map again from scratch (or so I've been told).

    To mitigate the slow deserialization process I was thinking to split the hashmap up and by some means parallelize the process of deserialization. Or maybe pre-allocating the memory necessary for the hashmap will speed things up. I am not really sure.

    I look forward to receiving your response.

  • Threadsafe combined erase and insert

    Threadsafe combined erase and insert

    I would like to use a parallel_hash_set to keep only the set of keys that have not been inserted once already. Upon a second insert, if the key already exists in the set, it should be erased. Keys will ONLY ever be inserted either once or twice. In other words, every time I go to insert a key, something like,

    if (!set.erase(key))
            set.insert(key);
    
    

    This would work fine without threads, but I would like to do this on the order of a billion keys and the erase and insert are happening concurrently on many threads. Is there an efficient way to do this with the existing parallel_hash_set and it's own blocks and own mutex?

  • C++20 support

    C++20 support

    Can you please tell me when you plan to release a version with C++20 support? Or can I use the https://github.com/greg7mdp/parallel-hashmap/tree/c%2B%2B20 branch?

  • Explore using highbits from the hash for subtable selection

    Explore using highbits from the hash for subtable selection

    Hey, just wanted to say that I really like the work you are doing here. We have found that SwissTables performance can suffer dramatically when there is not enough entropy in the hash function. By using a hash of (h ^ (h >> 4)) & 0x0F to select your subtables, you are creating just such a reduction of entropy. Given that tables rarely grow large enough to use all their high bits, you can probably get better performance by doing something like h >> 56. At the very least it is worth exploring.

  • Ability to manipulate a hash_map value behind the write lock

    Ability to manipulate a hash_map value behind the write lock

    I've encounter a case where I would like to modify the value inside the hash map in a thread-safe way. I would like to propose a function similar to if_contains that I have so far named if_modify. The difference between the two functions is if_modify is not const, and it locks the unique_lock rather than the shared_lock. Otherwise they use the same function body.

  • Building with Intel Compiler

    Building with Intel Compiler

    C++ isn't my strong suit so I haven't quite figured out what this issue is yet. But, when I try to build the example in MSVS 2017 and 2019 with Windows SDK 10.0.17763.0, using ICC 2019 update 3 (all are debug builds using default settings), I get these errors:

    Severity Code Description Project File Line Suppression State Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 4144 Error (active) E1389 redeclaration cannot add dllexport/dllimport to "ldexpf" (declared at line 706 of "C:\Program Files (x86)\Windows Kits\10\Include\10.0.17763.0\ucrt\corecrt_math.h") hash C:\Program Files (x86)\IntelSWTools\compilers_and_libraries_2019\windows\compiler\include\math.h 704 Error (active) E1389 redeclaration cannot add dllexport/dllimport to "powf" (declared at line 743 of "C:\Program Files (x86)\Windows Kits\10\Include\10.0.17763.0\ucrt\corecrt_math.h") hash C:\Program Files (x86)\IntelSWTools\compilers_and_libraries_2019\windows\compiler\include\math.h 799 Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 557 Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 573 Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 604 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 2166 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 3304 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 4203 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 4262 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 4321 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 4372 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 4419 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 4470 Error #3466 inheriting constructors must be inherited from a direct base class hash d:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap.h 4520

    Works fine with Clang and MSVC using c++14 standard though.

    Under c++17 with Clang I get:

    Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 557 Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 573 Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 604 Error cannot convert 'const std::basic_string_view<char, std::char_traits >' to 'size_t' (aka 'unsigned int') without a conversion operator hash C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xhash 31

    And with MSVC

    Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 557 Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 573 Error (active) E2512 the argument to a feature-test macro must be a simple identifier hash D:\Downloads\parallel-hashmap-master\parallel_hashmap\phmap_config.h 604

    Though you might want to know.

    Cheers

  • Added dump&&load interface for trivially_copyable types

    Added dump&&load interface for trivially_copyable types

    I need to dump and load the hash map/set very quickly for trivially_copyable types such as uint32,uint64 and so on. Fortunately all necessary data of these types are stored in ctrl_ and slots_ area so we can dump&load ctrl_ and slots_ directly.

  • insert in parallel problem

    insert in parallel problem

    Hi, I'm using your hash map to write data to it in parallel. Here is the function that is being called in parallel (using concurrency lib on Windows, c++, VS2019):

    // class member: phmap::parallel_flat_hash_map<SimpleString, int, phmap::priv::hash_default_hash,
    phmap::priv::hash_default_eq,
    std::allocator<std::pair<const SimpleString, int>>, 8, srwlock> m_stringsMap;

    // class func:

    int addParallel(const SimpleString& str, volatile long* curIdx) { int newIndex = -1;

        auto inserted = m_stringsMap.insert(std::make_pair(str, newIndex));
        if (inserted.second) // we are the first to insert
        {
            newIndex = InterlockedIncrement(curIdx);
            m_stringsMap[str] = newIndex;
        }
        else // we are NOT first - someone already inserted the pair
        {
            while (newIndex < 0)
            {
                ::SwitchToThread();
                newIndex = m_stringsMap[str]; // 
            }
        }
        
        return newIndex;
    }
    

    My assumption is that insert behaves same way as concurrency::concurrent_unordered_map:

    1. If this thread was the one that inserted the key, it can safely modify the value for it, since only this thread will have inserted.second set to true.
    2. if other thread already inserted that key (and doesn't matter what is the value for that key is!), then inserted.second is false, and all that we need to do is to read from it until the value is modified to be something other than -1 (curIdx starts with 0).

    Most of the time, this works. But occasionally, it goes into forever loop in that while loop. This can happen, as I understand, in the following cases:

    • either thread that actually inserted the key received inserted.second as false; OR
    • newIndex = m_stringsMap[str] keeps reading initially inserted value instead of reading the updated value.

    Similar logic works flawlessly with concurrency::concurrent_unordered_map. I really wanted to use your map, since it's faster almost twice than concurrency::concurrent_unordered_map; but this bug stops me from using it. Can you please take a look?

  • Keep original bucket count when copying a map

    Keep original bucket count when copying a map

    Hello, I am facing the following issue: I want to assign a map to other, however I lose the bucket count while doing so. The following code explains it better:

    auto map1 = phmap::parallel_flat_hash_map<int, int>(15000);
    for (int j = 0; j < 1000; j++)
        map1.insert(std::make_pair(j, j));
    phmap::parallel_flat_hash_map<int, int> map2;
    map2 = map1;
    std::cout << "map1 " << map1.size() << " " << map1.bucket_count() << "\n";
    std::cout << "map2 " << map2.size() << " " << map2.bucket_count() << "\n";
    

    The output of this is:

    map1 1000 262128
    map2 1000 1648
    

    I would like map2 to have 26k buckets too. I know there are other ways to copy, but I am implementing code with templates and this is just the simpler way to assign. Any idea on how to fix this?

  • Multiple threads using the same hash table

    Multiple threads using the same hash table

    Good morning, I have a pretty simple question.

    How can you make sure that more threads (therefore on the same machine) can use the same hash table loaded in memory?

    I have a situation like this:

    struct MyKey
    {
      friend size_t hash_value(const MyKey &k)
      {
        return phmap::HashState().combine(0, k.key[0], k.key[1], k.key[2], k.key[3], k.key[4], k.key[5], k.key[6], k.key[7], k.key[8]);
      }
    
      bool operator==(const MyKey o) const { return key == o.key; }
    
      uint8_t &operator[](int idx) { return key[idx]; }
    
      std::array<uint8_t, 9> key;
    };
    

    I am using a Class:

    class MyClass
    {
    
    (...)
    
    public:
    
      using Hash = phmap::flat_hash_map<MyKey, double>;
      Hash h{};
    
    };
    

    Here below I would like to load into memory a hash table (just once) and then initialize the hash table in each class object constructor (each one belonging to a different thread) with the hash table loaded into memory:

       (...)
        std::string hashed_tables_path_assigned = "generic/path/to/stored/hash/table";
    
        omp_set_num_threads(number_of_threads);
    
        using Hash = phmap::flat_hash_map<MyKey, double>;
        Hash h{};
        phmap::BinaryInputArchive ar_in(&hashed_tables_path_assigned[0]);
        h.phmap_load(ar_in);
    
    #pragma omp parallel for
        for (int thread_id = 0; thread_id < number_of_threads; thread_id++)
        {
            MyClass Classobject (... )   // here I would like to initialize each object so that it can use the same hash table
        }
    
    

    Please tell me if I explained myself properly or if something is unclear.

    It should be a simple syntax problem. The only way I was able to get this to work was to have each thread load a copy of the hash table into memory, which is obviously a terrible solution.

    A thousand thanks!

  • Seg Fault on malloc failure/out of memory

    Seg Fault on malloc failure/out of memory

    I find that flat_hash_map will sometimes cause a seg fault when the memory limit of the process is reached and malloc() returns null. The seg fault is on the free() call made on the nested container in the map called from the flat_hash_map destructor. The following block of code will consistently seg fault when inserted into my larger project if I use "ulimit -v" to set a process memory limit: phmap::flat_hash_map< size_t, string > hm; for( size_t i = 0; i < 1000000000; ++i ) { hm.insert( std::make_pair( i, "sfaasdfgasdgdfgsdhfghfgsdgfdgsdfgsdfgdfgfgsfdg" ) ); } However, this code appears to work fine and throw std::bad_alloc when I put these lines in a standalone binary. So it has something to do with the context or state of the program at the time when this code is run.

    A few more notes:

    • This only seems to happen when the map key or value are types with internal allocations such as std::vector or std::string.
    • Changing the hash_map type to unordered_map or spp::sparse_hash_map result in the expected std::bad_alloc.
    • Changing the hash_map type to google::sparse_hash_map results in the error "sparsehash FATAL ERROR: failed to allocate 32 groups" and call to exit().
    • Passing in a custom allocator that checks for a null return from malloc() inside the allocate() call and throws std::bad_alloc fixes the problem.

    The stack trace starting at the flat_hash_map destructor is: #0 0x000000000173776d in __exchange_and_add (__val=-1, __mem=0xfffffffffffffff8) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/ext/atomicity.h:82 #1 __exchange_and_add_dispatch (__val=-1, __mem=0xfffffffffffffff8) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/ext/atomicity.h:82 #2 __exchange_and_add_dispatch (__val=-1, __mem=0xfffffffffffffff8) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/ext/atomicity.h:78 #3 _M_dispose (__a=..., this=0xffffffffffffffe8) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/bits/basic_string.h:3311 #4 _M_dispose (__a=..., this=0xffffffffffffffe8) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/bits/basic_string.h:3295 #5 ~basic_string (this=0x7fffef1a0028, __in_chrg=) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/bits/basic_string.h:3706 #6 ~pair (this=0x7fffef1a0020, __in_chrg=) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/bits/stl_pair.h:208 #7 destroy<std::pair<unsigned long, std::basic_string > > (this=0x7fffffffc648, __p=0x7fffef1a0020) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/ext/new_allocator.h:153 #8 destroy<std::pair<unsigned long, std::basic_string > > (__a=..., __p=0x7fffef1a0020) at /grid/common/pkgsData/gcc-v9.3.0p1/Linux/RHEL6.0-2013-x86_64/include/c++/9.3.0/bits/alloc_traits.h:497 #9 destroy_impl<std::allocator<std::pair<unsigned long const, std::basic_string > >, std::pair<unsigned long, std::basic_string > > (a=..., p=0x7fffef1a0020) at ../src/parallel_hashmap/phmap_base.h:1542 #10 destroy<std::pair<unsigned long, std::basic_string > > (a=..., p=0x7fffef1a0020) at ../src/parallel_hashmap/phmap_base.h:1500 #11 destroy<std::allocator<std::pair<unsigned long const, std::basic_string > > > (alloc=0x7fffffffc648, slot=0x7fffef1a0020) at ../src/parallel_hashmap/phmap_base.h:4695 #12 destroy<std::allocator<std::pair<unsigned long const, std::basic_string > > > (alloc=0x7fffffffc648, slot=0x7fffef1a0020) at ../src/parallel_hashmap/phmap.h:3996 #13 destroy<std::allocator<std::pair<unsigned long const, std::basic_string > > > (alloc=0x7fffffffc648, slot=0x7fffef1a0020) at ../src/parallel_hashmap/phmap_base.h:479 #14 phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned long, std::string>, phmap::Hash, phmap::EqualTo, std::allocator<std::pair<unsigned long const, std::string> > >::destroy_slots (this=0x7fffffffc620) at ../src/parallel_hashmap/phmap.h:1906 #15 0x0000000000c34eaf in ~raw_hash_set (this=0x7fffffffc620, __in_chrg=) at ../src/parallel_hashmap/phmap.h:4397 #16 ~raw_hash_map (this=0x7fffffffc620, __in_chrg=) at ../src/parallel_hashmap/phmap.h:2228 #17 ~flat_hash_map (this=0x7fffffffc620, __in_chrg=) at ../src/parallel_hashmap/phmap.h:4397

  • Custom pointer type support ?

    Custom pointer type support ?

    It seems custom pointer types are not supported with the parallel hashmap: https://github.com/greg7mdp/parallel-hashmap/blob/master/parallel_hashmap/phmap.h#L843-L846

    Would this be difficult to add ? Because I would like to apply the parallel hashmap to a project to process openstreetmap data. This involves loading several billions of geometrical data. We do this by loading the the data into a boost unordered_map backed by a boost interprocess mmap file. This way, the data is hashed but backed by a file on filesystem. This is required, because converting the planet actually involved processing 60G of compressed data.

    The loading process is now completely single threaded, but ideally, we would like to load the node/ways/relations store with openstreetmap from the planet osm file in parallel. Parallel hashmap provides an interesting approach for this, but this approach would require using the boost interprocess offset pointer.

    https://github.com/systemed/tilemaker

    Is there a particular reason why custom pointer types are not allowed ?

A fast and efficient non-iterating hashmap library

libhash: a fast and efficient non-iterating hashmap library Libhash is a fast and efficient non-iterating hashmap library Usage Usage is easy and simp

Jan 18, 2022
Hashmap data structure with string keys

Hashmap Library implementing the hash map data structure with open addressing, robin hood hashing more presicely, as a collision resolution strategy.

Dec 21, 2021
Cross-platform STL-styled and STL-compatible library with implementing containers, ranges, iterators, type traits and other tools; actors system; type-safe config interface.

Yato A small repository where I'm gatherting useful snippets and abstractions for C++ development. Yato includes 3 main modules: multidimensional cont

Mar 7, 2022
Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).
Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).

M*LIB: Generic type-safe Container Library for C language Overview M*LIB (M star lib) is a C library enabling to use generic and type safe container i

May 10, 2022
Allocator Aware Containers Made Easy

Custom Allocator Aware containers made easy with "wit" Have you ever looked at the allocator specification and thought about how hard it would be to

Sep 25, 2021
A C++ data container replicating std::stack functionality but with better performance than standard library containers in a stack context.

plf::stack A data container replicating std::stack functionality but with better performance than standard library containers in a stack context. C++9

Apr 11, 2022
BladeBit - Fast Chia (XCH) RAM-only k32-only Plotter

BladeBit Chia Plotter A fast RAM-only, k32-only, Chia plotter. Requirements 416 GiB of RAM are required to run it, plus a few more megabytes for stack

May 11, 2022
Very Fast Non-Cryptographic Hash Function

KOMIHASH - Very Fast Hash Function Introduction The komihash() function available in the komihash.h file implements a very fast 64-bit hash function,

Apr 25, 2022
C++ library to create dynamic structures in plain memory of shared-memory segments

Ищи описание на хабре @mrlolthe1st. #define _CRT_SECURE_NO_WARNINGS #include "shared_structures.h" #include <iostream> #include <fstream> #include <ca

Mar 30, 2022
This is a beginner-friendly project aiming to build a problem-set on different data structures and algorithms in different programming languages.

DSAready Overview This is a beginner-friendly project that aims to create a problem-set for various Data Structures and Algorithms. Being a programmer

Sep 22, 2021
A realtime/embedded-friendly C++11 variant type which is never empty and prevents undesirable implicit conversions

strict variant Do you use boost::variant or one of the many open-source C++11 implementations of a "tagged union" or variant type in your C++ projects

Apr 18, 2022
Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20

➵ robin_hood unordered map & set robin_hood::unordered_map and robin_hood::unordered_set is a platform independent replacement for std::unordered_map

May 16, 2022
A simple single header 64 and 32 bit hash function using only add, sub, ror, and xor.
A simple single header 64 and 32 bit hash function using only add, sub, ror, and xor.

K-HASH A simple single header 64 bit hash function using only add, sub, ror, and xor. This a just general-purpose hash function for like making hash m

Jan 12, 2022
R :package: and header-only C++ library for geospatial space-division based compression and encoding
R :package: and header-only C++ library for geospatial space-division based compression and encoding

spress spress provides utilities for encoding and compressing geospatial objects, such as sf objects. Installation This package requires C++11 for com

Dec 9, 2021
R :package: and header-only C++ library for geospatial space-division based compression and encoding
R :package: and header-only C++ library for geospatial space-division based compression and encoding

spress spress provides utilities for encoding and compressing geospatial objects, such as sf objects. Installation This package requires C++11 for com

Dec 9, 2021
Easy to use, header only, macro generated, generic and type-safe Data Structures in C
Easy to use, header only, macro generated, generic and type-safe Data Structures in C

C Macro Collections Easy to use, header only, macro generated, generic and type-safe Data Structures in C. Table of Contents Installation Contributing

May 9, 2022
ring-span lite - A C++yy-like ring_span type for C++98, C++11 and later in a single-file header-only library

ring-span lite: A circular buffer view for C++98 and later Contents Example usage In a nutshell Dependencies Installation Synopsis Reported to work wi

May 13, 2022
Step is a C++17, header-only library of STL-like algorithms and data structures
Step is a C++17, header-only library of STL-like algorithms and data structures

Step is a C++17, header-only library of STL-like algorithms and data structures. Installation git clone --depth 1 https://github.com/storm-ptr/step.gi

Dec 12, 2021