Re: [Boost-bugs] [Boost C++ Libraries] #9282: performance regression in boost::unordered on 64-bit platforms

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #9282: performance regression in boost::unordered on 64-bit platforms
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-10-23 16:28:29

#9282: performance regression in boost::unordered on 64-bit platforms
--------------------------+------------------------------------------------
  Reporter:  aiapub-      |      Owner:  danieljames
  cpp@…                   |     Status:  assigned
      Type:  Bugs         |  Component:  unordered
 Milestone:  To Be        |   Severity:  Regression
  Determined              |   Keywords:  unordered mix64_policy performance
   Version:  Boost        |
  1.53.0                  |
Resolution:               |
--------------------------+------------------------------------------------

Comment (by aiapub-cpp@…):

 I believe it's the weakness of the mix function - taking it out (just
 using hf(x)) actually improves performance versus the prime_policy. I
 understand that you use the mix function to avoid collisions with simple
 hash-functions and I was also looking into a way to improve it. The test I
 use is simple - add 100M of 64-bit index combined with 0x9876543200000000
 (any number above 32 bits) in reverse order, then make sure they all
 exist, then fetch for non-existing records. The code snippet:

 inline uint64_t NewID(size_t i)
 {
     return (0x9876543200000000ULL | i);
 }

 void test()
 {
     printf("Fill: boost::unordered_set (64K)\t");
     boost::unordered_set<uint64_t> ids(65536);

     size_t N=100000000; // 100M records
     size_t i=0;
     for(; i!=N; ++i)
         ids.insert(NewID(N-i));

     printf("Fetch: boost::unordered_set (64K)\n");
     for(i=0; i!=N; ++i)
     {
         if (ids.find(NewID(i+1))==ids.end())
         {
             printf("\nFailed!\n");
             break;
         }
     }

     printf("Fetch: boost::unordered_set invalid records\n");
     for (i=0; i!=N; ++i)
     {
         if (ids.find((uint64_t)(i | 0xF0000000UL))!=ids.end())
         {
             printf("\nFailed!\n");
             break;
         }
     }
 }

 Thanks for looking into it.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9282#comment:3>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.