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

➵ robin_hood unordered map & set Release GitHub license

Travis CI Build Status Appveyor Build Status Codacy Badge Total alerts Language grade: C/C++ Coverage Status

robin_hood::unordered_map and robin_hood::unordered_set is a platform independent replacement for std::unordered_map / std::unordered_set which is both faster and more memory efficient for real-world use cases.

Installation & Usage

Direct Inclusion

  1. Add robin_hood.h to your C++ project.
  2. Use robin_hood::unordered_map instead of std::unordered_map
  3. Use robin_hood::unordered_set instead of std::unordered_set

Conan, the C/C++ Package Manager

  1. Setup your CMakeLists.txt (see Conan documentation on how to use MSBuild, Meson and others) like this:
    project(myproject CXX)
    
    add_executable(${PROJECT_NAME} main.cpp)
    
    include(${CMAKE_BINARY_DIR}/conanbuildinfo.cmake) # Include Conan-generated file
    conan_basic_setup(TARGETS) # Introduce Conan-generated targets
    
    target_link_libraries(${PROJECT_NAME} CONAN_PKG::robin-hood-hashing)
  2. Create conanfile.txt in your source dir (don't forget to update the version)
    [requires]
    robin-hood-hashing/3.10.0
    
    [generators]
    cmake
  3. Install and run Conan, then build your project as always:
    pip install conan
    mkdir build
    cd build
    conan install ../ --build=missing
    cmake ../
    cmake --build .
    The robin-hood-hashing package in Conan is kept up to date by Conan contributors. If the version is out of date, please create an issue or pull request on the conan-center-index repository.

Benchmarks

Please see extensive benchmarks at Hashmaps Benchmarks. In short: robin_hood is always among the fastest maps and uses far less memory than std::unordered_map.

Design Choices

  • Two memory layouts. Data is either stored in a flat array, or with node indirection. Access for unordered_flat_map is extremely fast due to no indirection, but references to elements are not stable. It also causes allocation spikes when the map resizes, and will need plenty of memory for large objects. Node based map has stable references & pointers (NOT iterators! Similar to std::unordered_map) and uses const Key in the pair. It is a bit slower due to indirection. The choice is yours; you can either use robin_hood::unordered_flat_map or robin_hood::unordered_node_map directly. If you use robin_hood::unordered_map It tries to choose the layout that seems appropriate for your data.

  • Custom allocator. Node based representation has a custom bulk allocator that tries to make few memory allocations. All allocated memory is reused, so there won't be any allocation spikes. It's very fast as well.

  • Optimized hash. robin_hood::hash has custom implementations for integer types and for std::string that are very fast and falls back to std::hash for everything else.

  • Depends on good Hashing. For a really bad hash the performance will not only degrade like in std::unordered_map, the map will simply fail with an std::overflow_error. In practice, when using the standard robin_hood::hash, I have never seen this happening.

License

Licensed under the MIT License. See the LICENSE file for details.

by martinus

Comments
  • Insert fails with std::overflow_error again

    Insert fails with std::overflow_error again

    Hello.

    I have encountered std::overflow_error again.

    I am using robin hood version 3.10.0.

    This time I cannot create test case. I hope you can give me guidelines to find source of problem. I am working with robin_hood::unordered_flat_set<int32_t>. My application is working with 200 containers and 10 million elements in total, so I cannot find good way to create test example. It takes about 5 minutes of number crunching before application crashes while trying to insert that specific integer into that specific container.

    My application is basically doing this:

    • Create 200 containers.
    • Do work with all containers (container::insert, container::erase, container::clear). This work takes about 5 minutes.
    • At some moment, application has to process some problematic container.
    • Problematic container contains some elements.
    • I know what are new elements that must be inserted into problematic container.
    • Problematic container is cleared before insertion.
    • New elements are inserted into problematic container one-by-one. Insertion fails with std::overflow_error after some number.

    Exception is not thrown if I recreate standalone test case with same elements.

    Thanks.

  • Support for Unique hash map?

    Support for Unique hash map?

    As discussed on https://github.com/CGAL/cgal/issues/4049 I am investigating using robin_hood::unordered_map for a unique hash map. A Unique hash map is a specialization on insertion only and unique hash values allow for a more time and space-efficient implementation. In the case of the implementation in CGAL the memory addresses of Handle objects are used for key-hashes and therefore by their very nature there cannot be duplicates/collisions.

    The CGAL implementation suffers from poor construction speed due to the default hardcoded table size of 512, and this is what I hope to improve by using robin_hood::unordered_map. However the insert speed of the CGAL::Unique_hash_map does seem to outperform by a factor of 0.2, as can be seen in my benchmark project https://github.com/GilesBathgate/hashmap-benchmarks

    What I'd like to establish is whether improvements can be made to either CGAL::Unique_hash_map that would facilitate faster construction, or whether robin_hood::* can be improved with the techniques used in the CGAL implementation.

    I realise that the main purpose of robin hood hashing is to handle the case when there are duplicate keys, so perhaps its not the best candidate. Are there any other faster hash map implementations that can be used for a unique hash map that would be more suitable?

  • robin_hood::map overflow

    robin_hood::map overflow

    Dear developer,

    I am using robin hood map (3.11.2) under MinGW. I got overflow error when insert some number as below log.

    ... Add 20686628 Add 20790466 Add 20950897 Add 20938052 Add 20481416 terminate called after throwing an instance of 'std::overflow_error' what(): robin_hood::map overflow

    I have attach reproduce file. Please check it. :)

    Thank you.

    test.zip

  • Consider porting to C++11 / C++03

    Consider porting to C++11 / C++03

    A large number of development environments still do not have C++14 support, especially in many embedded environments that only support C++03.

    Can you consider porting this powerful and efficient container to these older versions?

    Thanks :-)

  • support remove/erase idiom

    support remove/erase idiom

    I noticed when applying the remove/erase idiom that the following method is not implemented:

    iterator erase ( const_iterator first, const_iterator last );

    Reference: https://en.cppreference.com/w/cpp/container/unordered_map/erase Example: cache.erase( std::remove_if( cache.begin(), cache.end(), [&] ( const pair<int,int>& i ) { return i.second == 1 ); } ), cache.end() );

  • Fix CRC32 support on Windows ARM64 and use runtime detection

    Fix CRC32 support on Windows ARM64 and use runtime detection

    __cpuid isn't present on ARM64 builds in Windows, and CRC32 is always present for ARM64 processors that Windows 10 supports (making runtime detection unnecessary).

    Also, remove the hardware support detection at compile time. You've already added runtime detection (the more flexible method), so use that.

  • Fast CRC32 based hash for hash_bytes and hash_int

    Fast CRC32 based hash for hash_bytes and hash_int

    • [x] CRC with runtime dispatch
    • [x] Use _mm_crc32_u64
    • [x] Don't use upper bits of the hash, only use lower bits. Then a single crc command would be enough
    • [ ] Implement optimized hash_bytes that makes use of CRC32 instruction
  • Not using intrinsics

    Not using intrinsics

    What was the reason for reverting https://github.com/martinus/robin-hood-hashing/commit/f45a309af7d08cb98fc08dc7903ac9a7091db6d5 ? Any reliability concerns or just performance?

    I'm asking because, on certain contexts, including x86intrin.h on Mingw-w64 triggers a bug on g++.

  • Crashing with overflow_error

    Crashing with overflow_error

    Hello,

    I am currently trying to integrate robin hood hashing into my project. As mentioned on your github, I simply included the robin_hood.h and used robin_hood::unordered_map instead of std::unordered_map.

    However, upon start, my program crashes and reports the following error:

    terminate called after throwing an instance of 'std::overflow_error' what(): robin_hood::map overflow Command terminated by signal 6

    Do you have any idea what could cause this?

    Thanks!

    Cheers, Pierre

  • Please add C++ 17 node API to node based map

    Please add C++ 17 node API to node based map

    For node-based maps, these functions can enable writing much more efficient code:

    https://en.cppreference.com/w/cpp/container/unordered_map/extract

    Indeed, I am not using your map in a number of places precisely due to me using this node ptr API.

  • it = map.erase(it) potentially passes object twice

    it = map.erase(it) potentially passes object twice

    It seems @jcageman has stumbled uppon an issue that probably all robin-hood map with backward shift deletion have (see #18). Here is a simple reproducer

    Insert two elements, where both hash to the last bucket of the map. One entry will be the last one of the map, the other one will wrap around and use the first bucket.

    robin_hood::unordered_node_map<int, int, DummyHash> map;
    map[1024] = 1;
    map[2048] = 2;
    
    it = map.begin(); // it points to 2048, the first element which has wrapped around
    ++it;  // it points to the last element, 1024 which is in its original bucket
    it = map.erase(it); // backward shift deletion removes 1024 and wraps back 2048, so it now (again!) points to 2048 and NOT end
    it = map.erase(it); // finally we are at the end.
    

    Also see https://github.com/Tessil/robin-map/issues/20

  • robin_hoodConfig.cmake missing

    robin_hoodConfig.cmake missing

    I'm trying to make Vulkan Validation layers and the make required robin hood but after using conan to install it and use it, I was expecting there to be a robin_hoodConfig.cmake or robin_hood-config.cmake. Everything works except the robin hood.

    I'm using windows 10, Vulkan 1.3.211.0, cmake 3.10.2

    command to make the validation layers:

    cmake -A x64 -DVULKAN_HEADERS_INSTALL_DIR=C:\libraries\VulkanSDK\1.3.211.0 -DGLSLANG_INSTALL_DIR=C:\libraries\VulkanSDK\1.3.211.0 -DSPIRV_HEADERS_INSTALL_DIR=C:\libraries\VulkanSDK\1.3.211.0 -DSPIRV_TOOLS_INSTALL_DIR=C:\libraries\VulkanSDK\1.3.211.0 -DROBIN_HOOD_HASHING_INSTALL_DIR=C:\robin-hood-hashing-master ..

    output from command:

    -- Selecting Windows SDK version 10.0.22000.0 to target Windows 10.0.19042.


    • NOTE: Not adding target to run update_deps.py automatically. *

    CMake Error at CMakeLists.txt:254 (find_package): Could not find a package configuration file provided by "robin_hood" with any of the following names:

    robin_hoodConfig.cmake
    robin_hood-config.cmake
    

    Add the installation prefix of "robin_hood" to CMAKE_PREFIX_PATH or set "robin_hood_DIR" to a directory containing one of the above files. If "robin_hood" provides a separate development package or SDK, be sure it has been installed.

    -- Configuring incomplete, errors occurred! See also "C:/Vulkan-ValidationLayers-master/build/CMakeFiles/CMakeOutput.log".

  • Idea for robin-hood-hashing V2

    Idea for robin-hood-hashing V2

    • Performance is important but not everything

    • Use an std::vector<std::pair<Key, Value>> (maybe customizable) for the content that is always 100% compact. iteration is perfectly fast.

    • Use an indexing structure into that vector, that cannot overflow, e.g. like so:

      • 3 byte offset from original bucket => 2^24-1 = 16777215 collisions possible, should be plenty
      • 1 byte hash
      • 4 byte index into std::vector
    • => limitations are: no more than 16M collisions (so no overflow check necessary?)

    • 4 byte index, so no more than 4 billion elements are allowed. Should be enough for most use cases.

      • 32bit hash would be enough for indexing. Convert mumx to 32bit would work
      • We could use non-power-of-two-hashmap sizes. Given a well distributed 32bit hash, use idx = ((uint64_t)hash * (uint64_t)mapsize) >> 32
    • 1 byte hash: only every 256th key needs to be checked, that's good enough

    • ordering like robin-hood-hash, we we only need a single < comparison

    • how to deal with capacity() changes / rehash? (resize to capacity + 1, then resize to the new capacity(). This sucks.)

  • robin_hood.h: Change hash val shifts for `info` and `idx` generation

    robin_hood.h: Change hash val shifts for `info` and `idx` generation

    Instead of generating the info hash bits with a mask + shift, we can just use an unsigned shift from the end as that will bring in zeros.

    With that change the idx hash bits can start from the begining so we no longer need to shift out the info hash bits.

    Saves 2x instructions. Only ALU but this function is in the critical path.

    There does not appear to be any issue with false hits changing the tag bits used.

    False Tag Match Rates:

                      :   New,   Cur
    

    Insert Seq Ints: 2^10 : 2.539, 2.832 2^12 : 3.076, 3.003 2^14 : 2.960, 3.497 2^16 : 4.048, 4.306 2^18 : 4.543, 4.732 2^20 : 5.182, 5.553 2^22 : 5.579, 5.557 2^24 : 6.237, 6.017 2^26 : 6.599, 6.432

    Insert Rand Ints (seed = 0): 2^10 : 2.637, 4.199 2^12 : 2.979, 3.613 2^14 : 3.662, 3.955 2^16 : 4.309, 4.849 2^18 : 4.626, 4.564 2^20 : 4.849, 5.044 2^22 : 6.050, 5.279 2^24 : 5.664, 6.350 2^26 : 6.640, 6.771

    Insert Strings: All Words(0) : 4.974, 5.231 10k Words(1) : 3.550, 4.000 URLS(2) : 5.548, 5.683 URLS(2) w/ "http://" : 5.466, 5.831 URLS(2) w/ "https://" : 5.569, 5.761

  • Memory blow up for certain payloads when using robin hood unordered node map

    Memory blow up for certain payloads when using robin hood unordered node map

    Hi

    I encountered a memory spike when using robin hood unordered node map with certain payloads. A link to the compiler explorer snippet is as follows Compiler-Explorer-link (I occasionally get a compiler returned -1 error from compiler explorer . I suspect its because of the number of lines of code. If this happens on your side , you can follow the second link where I removed the robin hood comments at the start of the file to get it working ) Here's a second link in case the first doesn't work Compiler-Explorer-Second-Link

    Essentially when I run the following piece of code

    int main()
    {
        struct Value
        {
            int arr[20];
        };
        using Container = robin_hood::unordered_map<int , Value>;
        robin_hood::unordered_map<int , Container> containers;
        unsigned numMapElements = 1'000;
        for(unsigned k =0 ; k < 8 ; ++k)
        {
            printMemory("Memory at the start of iteration " + std::to_string(k));
            for(unsigned i =0 ; i < numMapElements ; ++i)
            {
                Container tmp;
                containers[i] = tmp;
                for(unsigned j =0 ; j < 50 ; ++j)
                {
                    containers[i].emplace(j , Value());
                }
            }
            printMemory("Memory at the end of iteration " + std::to_string(k));
        }
        return 0 ;
    }
    

    I notice that the memory usage is around 11 MB for the first iteration and 170 MB in the next iteration. This issue disappears when I change the Container type to robin_hood::unordered_flat_map or std::unordered_map. This behavior is quite unexpected and I suspect there is some memory issue in the robin_hood::unordered_node_map.

    Additionally this only happens happens when using the copy assignment operator on container. If I change the lines in the inner most loop to the following , the issue disappears

    
    Container tmp;
    containers[i] = std::move(tmp);
    
    

    I have used the following functions to print memory usage

    namespace{
        void parseMemoryValue(const char* buf , const char* prefix , unsigned int& val)
        {
            const std::size_t prefixLen = strlen(prefix);
            if(strncmp(buf , prefix , prefixLen) == 0 )
            {
                val = static_cast<unsigned>(atoi(buf + prefixLen));
            }
        }
        int getMemory(unsigned int& currentRealMem, 
                      unsigned int& peakRealMemory ,
                      unsigned int& currentVirtualMemory, 
                      unsigned int& peakVirtualMemory)
        {
            static constexpr int bufferSize = 1024;
            char buf[bufferSize];
            std::ifstream stream;
            stream.open("/proc/self/status");
            if(!stream.is_open())
                return -1;
            while(!stream.getline(buf,bufferSize).eof())
            {
                const char* pos = strstr(buf , "Vm");
                if(pos == nullptr)
                    continue;
                pos+=2;
                parseMemoryValue(pos , "RSS:" , currentRealMem);
                parseMemoryValue(pos , "HWM:" , peakRealMemory);
                parseMemoryValue(pos , "Size:" , currentVirtualMemory);
                parseMemoryValue(pos , "Peak:" , peakVirtualMemory);
            }
            stream.close();
            return 0 ;
    
        }
        void printMemory(const std::string& title)
        {
            unsigned currentReal = 0 ;
            unsigned realPeak = 0 ;
            unsigned currentVirtual = 0 ;
            unsigned virtualPeak = 0 ;
            if(getMemory(currentReal , realPeak , currentVirtual , virtualPeak))
            {
                return ;
            }
            std::cout<<"Printing "<<title << std::endl;
            std::cout<<std::endl;
            std::cout<<"Current Real " <<currentReal / 1.0e3 << " MB"<<std::endl;
            std::cout<<"Peak Real "<<realPeak / 1.0e3 << " MB"<<std::endl;
            std::cout<<"Current Virual "<<currentVirtual / 1.0e3 << " MB"<<std::endl;
            std::cout<<"Peak Virtual "<<virtualPeak / 1.0e3 << " MB"<<std::endl;
            std::cout<<std::endl;
        }
    }
    
    

    Please let me know if you have any idea why this happens.

    Thanks

  • making unordered_map automatically choose between unordered_node_map and unordered_flat_map is error-prone

    making unordered_map automatically choose between unordered_node_map and unordered_flat_map is error-prone

    Hi!

    First, thanks for the amazing work!

    I understand the motivation, but I think that having unordered_map try to automatically pick between the node and flat implementations is error prone:

    https://github.com/martinus/robin-hood-hashing/blob/9145f963d80d6a02f0f96a47758050a89184a3ed/src/include/robin_hood.h#L2519

    template <typename Key, typename T, typename Hash = hash<Key>,
              typename KeyEqual = std::equal_to<Key>, size_t MaxLoadFactor100 = 80>
    using unordered_map =
        detail::Table<sizeof(robin_hood::pair<Key, T>) <= sizeof(size_t) * 6 &&
                          std::is_nothrow_move_constructible<robin_hood::pair<Key, T>>::value &&
                          std::is_nothrow_move_assignable<robin_hood::pair<Key, T>>::value,
                      MaxLoadFactor100, Key, T, Hash, KeyEqual>;
    

    The problem is that both implementations have different performance characteristics, and more importantly different iterator/reference invalidation semantics.

    For example AFAICT code like this:

    m["a"] = m["b"];
    

    is safe when inserting "a" into m causes a resizing with the node-based implementation, but not with the flat one, resulting in UB.

    And more generally, code which works fine with the node-based one might break subtly with the flat one.

    It can be quite confusing since subtle changes to the key or value types - which can occur for example when compiling with a different compiler/libraries - can cause a change in the underlying implementation used.

C++ implementation of a fast hash map and hash set using hopscotch hashing

A C++ implementation of a fast hash map and hash set using hopscotch hashing The hopscotch-map library is a C++ implementation of a fast hash map and

Dec 23, 2022
A fast, memory efficient hash map for C++

I now recommend using the parallel hashmap instead of sparsepp, unless if you are stuck with a non C++11 compatible compiler, or if using a little bit

Jan 4, 2023
A c++ toolbox of locality-sensitive hashing (LSH), provides several popular LSH algorithms, also support python and matlab.

LSHBOX-0.9 A C++ Toolbox of Locality-Sensitive Hashing for Large Scale Image Retrieval, Also Support Python and MATLAB. Change Log 2015.07.04 A new LS

Nov 13, 2022
🏅State-of-the-art learned data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes

The Piecewise Geometric Model index (PGM-index) is a data structure that enables fast lookup, predecessor, range searches and updates in arrays of bil

Dec 29, 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

Dec 31, 2022
C++ implementation of a fast hash map and hash set using robin hood hashing

A C++ implementation of a fast hash map and hash set using robin hood hashing The robin-map library is a C++ implementation of a fast hash map and has

Dec 26, 2022
C++ implementation of a fast hash map and hash set using robin hood hashing

A C++ implementation of a fast hash map and hash set using robin hood hashing The robin-map library is a C++ implementation of a fast hash map and has

Jan 2, 2023
MarlinRB - 3D Printer Firmware based on Marlin 3D v2.0.9.2, for Flyingbear Reborn with MKS Robin Nano v1.2, MKS Robin Nano v1.3, MKS Robin Nano S v1.3
MarlinRB - 3D Printer Firmware based on Marlin 3D v2.0.9.2, for Flyingbear Reborn with MKS Robin Nano v1.2, MKS Robin Nano v1.3, MKS Robin Nano S v1.3

English Прошивка MarlinRB для принтера Flyingbear Reborn Работает с платами: MKS Robin Nano v1.3 (съемные драйвера, контроллер STM32F407), MKS Robin N

Dec 10, 2022
The Hoard Memory Allocator: A Fast, Scalable, and Memory-efficient Malloc for Linux, Windows, and Mac.

The Hoard Memory Allocator Copyright (C) 1998-2020 by Emery Berger The Hoard memory allocator is a fast, scalable, and memory-efficient memory allocat

Jan 2, 2023
Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin
Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin

A CPU scheduler determines an order for the execution of its scheduled processes; it decides which process will run according to a certain data structure that keeps track of the processes in the system and their status.

Sep 7, 2022
Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin.
Sqrt OS is a simulation of an OS scheduler and memory manager using different scheduling algorithms including Highest Priority First (non-preemptive), Shortest Remaining Time Next, and Round Robin.

A CPU scheduler determines an order for the execution of its scheduled processes; it decides which process will run according to a certain data structure that keeps track of the processes in the system and their status. A process, upon creation, has one of the three states: Running, Ready, Blocked (doing I/O, using other resources than CPU or waiting on unavailable resource).

Apr 15, 2022
C++ implementation of a fast hash map and hash set using hopscotch hashing

A C++ implementation of a fast hash map and hash set using hopscotch hashing The hopscotch-map library is a C++ implementation of a fast hash map and

Dec 23, 2022
C++ implementation of a fast hash map and hash set using hopscotch hashing

A C++ implementation of a fast hash map and hash set using hopscotch hashing The hopscotch-map library is a C++ implementation of a fast hash map and

Dec 23, 2022
Frog is an integration of memory-based natural language processing (NLP) modules developed for Dutch. All NLP modules are based on Timbl, the Tilburg memory-based learning software package.

Frog - A Tagger-Lemmatizer-Morphological-Analyzer-Dependency-Parser for Dutch Copyright 2006-2020 Ko van der Sloot, Maarten van Gompel, Antal van den

Dec 14, 2022
Frog is an integration of memory-based natural language processing (NLP) modules developed for Dutch. All NLP modules are based on Timbl, the Tilburg memory-based learning software package.

Frog - A Tagger-Lemmatizer-Morphological-Analyzer-Dependency-Parser for Dutch Copyright 2006-2020 Ko van der Sloot, Maarten van Gompel, Antal van den

Dec 14, 2022
A fast, memory efficient hash map for C++

I now recommend using the parallel hashmap instead of sparsepp, unless if you are stuck with a non C++11 compatible compiler, or if using a little bit

Jan 4, 2023
BLEND: A Fast, Memory-Efficient, and Accurate Mechanism to Find Fuzzy Seed Matches

BLEND is a mechanism that can efficiently find fuzzy seed matches between sequences to significantly improve the performance and accuracy while reducing the memory space usage of two important applications: 1) finding overlapping reads and 2) read mapping.

Jan 3, 2023
Solve Round Robin problems

Round-Robin-implementation-in-C Solve Round Robin problems using C-programming with Gantt Chart Description Round robin scheduling (RRS) is a job-sche

May 13, 2022
Marlin Firmware configured for FLSUN Super Racer with MKS Robin Nano V3 motherboard.
Marlin Firmware configured for FLSUN Super Racer with MKS Robin Nano V3 motherboard.

If you like my job, you can support me by paying me a ?? or a ☕ . Thanks ?? Marlin 2.0.8 Firmware configured for FLSUN Super Racer with MKS Robin Nano

Dec 18, 2022