Simulate Redis set/zset intersection

C++03

#include <iostream>
#include <tr1/unordered_map>
#include <map>
#include <set>

// 37 ms per intersection for Redis
// 29 ms per intersection for this C++ program

using namespace std;
using namespace std::tr1;

int main()
{
  // Build a set 
  set<long> s;
  for ( long i=0; i<25000; ++i )
    s.insert(i);

  // Build a zset (i.e. multimap + unordered_map)
  typedef pair<long,double> Object;
  unordered_map<long,Object *> z1;
  multimap<double, Object *> z2;
  for ( long i=0; i<25000; ++i ) {
    Object *p = new Object();
    p->first = i;
    p->second = double(i);
    z1.insert( make_pair(i,p ));
    z2.insert( make_pair(double(i),p ));
  }

  for ( int n=0; n<1000; ++n )
  {
    // Calculate intersection, the result is a zset
    // Note: objects are shared across containers here
    unordered_map<long,Object *> r1;
    multimap<double, Object *> r2;
    unordered_map<long,Object *>::const_iterator i;
    for ( i=z1.begin(); i != z1.end(); ++i )
      if ( s.find( i->first ) != s.end() )
      {
        r1.insert( make_pair(i->first,i->second ));
        r2.insert( make_pair(i->second->second, i->second ));
      }
  }

  // Note: objects never freed
  
  return 0;
}

C++11 version

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <memory>

// This one uses unordered sets and smart pointers
// Compile with g++ -std=c++0x -O2 toto.cc
// 34 ms per intersection for this C++ program
// 37 ms per intersection for Redis

using namespace std;

int main()
{
  unordered_set<long> s;
  for ( long i=0; i<25000; ++i )
    s.insert(i);

  typedef pair<long,double> Object;
  typedef shared_ptr<Object> Ptr;

  unordered_map<long, Ptr > z1;
  multimap<double, Ptr > z2;
  for ( long i=0; i<25000; ++i ) {
    Ptr p( new Object() );
    p->first = i;
    p->second = double(i);
    z1.insert( make_pair(i,p ));
    z2.insert( make_pair(double(i),p ));
  }

  for ( int n=0; n<1000; ++n )
  {
    unordered_map<long,Ptr> r1;
    multimap<double, Ptr> r2;
    unordered_map<long,Ptr>::const_iterator i;
    
    for ( i=z1.begin(); i != z1.end(); ++i )
      if ( s.find( i->first ) != s.end() )
      {
        r1.insert( make_pair(i->first, i->second ));
        r2.insert( make_pair(i->second->second, i->second ));
      }      
  }
  
  return 0;
}

C03

#include <iostream>
#include <tr1/unordered_map>
#include <map>
#include <set>

// 37 ms per intersection for Redis
// 29 ms per intersection for this C++ program

using namespace std;
using namespace std::tr1;

int main()
{
  // Build a set 
  set<long> s;
  for ( long i=0; i<25000; ++i )
    s.insert(i);

  // Build a zset (i.e. multimap + unordered_map)
  typedef pair<long,double> Object;
  unordered_map<long,Object *> z1;
  multimap<double, Object *> z2;
  for ( long i=0; i<25000; ++i ) {
    Object *p = new Object();
    p->first = i;
    p->second = double(i);
    z1.insert( make_pair(i,p ));
    z2.insert( make_pair(double(i),p ));
  }

  for ( int n=0; n<1000; ++n )
  {
    // Calculate intersection, the result is a zset
    // Note: objects are shared across containers here
    unordered_map<long,Object *> r1;
    multimap<double, Object *> r2;
    unordered_map<long,Object *>::const_iterator i;
    for ( i=z1.begin(); i != z1.end(); ++i )
      if ( s.find( i->first ) != s.end() )
      {
        r1.insert( make_pair(i->first,i->second ));
        r2.insert( make_pair(i->second->second, i->second ));
      }
  }

  // Note: objects never freed
  
  return 0;
}

C03.cc

#include <iostream>
#include <tr1/unordered_map>
#include <map>
#include <set>

// 37 ms per intersection for Redis
// 29 ms per intersection for this C++ program

using namespace std;
using namespace std::tr1;

int main()
{
  // Build a set 
  set<long> s;
  for ( long i=0; i<25000; ++i )
    s.insert(i);

  // Build a zset (i.e. multimap + unordered_map)
  typedef pair<long,double> Object;
  unordered_map<long,Object *> z1;
  multimap<double, Object *> z2;
  for ( long i=0; i<25000; ++i )
  {
    Object *p = new Object();
    p->first = i;
    p->second = double(i);
    z1.insert( make_pair(i,p ));
    z2.insert( make_pair(double(i),p ));
  }

  for ( int n=0; n<1000; ++n )
  {
    // Calculate intersection, the result is a zset
    // Note: objects are shared across containers here
    unordered_map<long,Object *> r1;
    multimap<double, Object *> r2;
    unordered_map<long,Object *>::const_iterator i;
    for ( i=z1.begin(); i != z1.end(); ++i )
      if ( s.find( i->first ) != s.end() )
      {
        r1.insert( make_pair(i->first,i->second ));
        r2.insert( make_pair(i->second->second, i->second ));
      }
  }

  // Note: objects never freed
  
  return 0;
}

C11 version

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <memory>

// This one uses unordered sets and smart pointers
// Compile with g++ -std=c++0x -O2 toto.cc
// 34 ms per intersection for this C++ program
// 37 ms per intersection for Redis

using namespace std;

int main()
{
  unordered_set<long> s;
  for ( long i=0; i<25000; ++i )
    s.insert(i);

  typedef pair<long,double> Object;
  typedef shared_ptr<Object> Ptr;

  unordered_map<long, Ptr > z1;
  multimap<double, Ptr > z2;
  for ( long i=0; i<25000; ++i ) {
    Ptr p( new Object() );
    p->first = i;
    p->second = double(i);
    z1.insert( make_pair(i,p ));
    z2.insert( make_pair(double(i),p ));
  }

  for ( int n=0; n<1000; ++n )
  {
    unordered_map<long,Ptr> r1;
    multimap<double, Ptr> r2;
    unordered_map<long,Ptr>::const_iterator i;
    
    for ( i=z1.begin(); i != z1.end(); ++i )
      if ( s.find( i->first ) != s.end() )
      {
        r1.insert( make_pair(i->first, i->second ));
        r2.insert( make_pair(i->second->second, i->second ));
      }      
  }
  
  return 0;
}

C11.cc

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <memory>

// This one uses unordered sets and smart pointers
// Compile with g++ -std=c++0x -O2 toto.cc
// 34 ms per intersection for this C++ program
// 37 ms per intersection for Redis

using namespace std;

int main()
{
  unordered_set<long> s;
  for ( long i=0; i<25000; ++i )
    s.insert(i);

  typedef pair<long,double> Object;
  typedef shared_ptr<Object> Ptr;

  unordered_map<long, Ptr > z1;
  multimap<double, Ptr > z2;
  for ( long i=0; i<25000; ++i )
  {
    Ptr p( new Object(i,double(i)) );
    z1.insert( make_pair(i,p ));
    z2.insert( make_pair(double(i),p ));
  }

  for ( int n=0; n<1000; ++n )
  {
    unordered_map<long,Ptr> r1;
    multimap<double, Ptr> r2;
    
    for ( auto i=z1.begin(); i != z1.end(); ++i )
      if ( s.find( i->first ) != s.end() )
      {
        r1.insert( *i );
        r2.insert( make_pair(i->second->second, i->second ));
      }      
  }
  
  return 0;
}