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.

This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:14 UTC