robin-hood-hashing

robin-hood-hashing copied to clipboard

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

It seams an important issue to me, too.

But this repository is not maintained anymore.

Maybe we can find a solution in ankerl::unordered_dense::{map, set}