runtime problem with hash_map::insert

Help
brendan
2012-08-06
2013-05-13
  • brendan

    brendan - 2012-08-06

    I am seeing a runtime problem with has_map::insert  (actually unordered_map::insert, but it's typedefed to has_map)
    The following code is running very slow, and the issue is the distribution of the entries in the bucket list.  Specifically, inserting these keys in this order results in a big bunch of empty buckets that keep getting updated during each insertion, blowing up the expected O(1) insertion time.

    void
    fill_unordered(int items)
    {
      std::tr1::unordered_map<int,int> hashmap(items);
      for (int i=0,j=items-1; i<j; ++i,-j)
      {
        hashmap_ = j;
        hashmap = i;
      }
    }

    I'll post the full testcase below and some comparison runtimes vs. std::map

    Is there any solution on the horizon for this runtime problem?    I saw a few older posts that refer to the same bucket-filling issue in the context of ::erase, but no solutions other than to have the hash_map shrink.   That is not an option here for obvious reasons.
    _

     
  • brendan

    brendan - 2012-08-06

    here is the full code that you can compile at home  (you can even link it vs. glib implementation of unordered_map, and observe that there is no runtime problem in the glibc ++ implementation)

    #include <unordered_map>
    #include <map>
    #include <iostream>

    double
    msec(clock_t start, clock_t end)
    {
      return ((end - start) * 1000/CLOCKS_PER_SEC);
    }

    void
    fill_unordered(int items)
    {
      std::tr1::unordered_map<int,int> hashmap(items);
      for (int i=0,j=items-1; i<j; ++i,-j)
      {
        hashmap_ = j;
        hashmap = i;
      }
    }

    void
    fill_ordered(int items)
    {
      std::map<int,int>  map;
      for (int i=0,j=items-1; i<j; ++i,-j)
      {
        map = j;
        map = i;
      }
    }

    void
    fill (int items)
    {
      {
        std::cout << "filling unordered\n";
        clock_t start = clock();

        fill_unordered(items);

        clock_t end = clock();
        std::cout << "elapsed time: " << msec(start,end) << "ms\n";
      }

      {
        clock_t start = clock();
        std::cout << "filling ordered\n";

        fill_ordered(items);

        clock_t end = clock();
        std::cout << "elapsed time: " << msec(start,end) << "ms\n";
      }
    }

    int main(int argc, char* argv)
    {
      if (argc < 2) {
        std::cout << "usage: fill <int>\n";
        return 1;
      }

      int items = std::atoi(argv);
      std::cout << "items: " << items << "\n";
      fill(items);
      return 0;
    }

    _

     
  • brendan

    brendan - 2012-08-06

    here is the result of running this code on my linux server:

    items: 100000
    filling unordered
    elapsed time: 3590ms
    filling ordered
    elapsed time: 20ms

    items: 300000
    filling unordered
    elapsed time: 29450ms
    filling ordered
    elapsed time: 80ms

    you can see how fast the runtime is blowing up vs. the insertion time for std::map

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks