language: C++ 4.7.2 (gcc-4.7.2)
date: 534 days 19 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <cstdlib>
 
#include <stdint.h>
#include <iostream>
#include <map>
#include <deque>
#include <utility>
#include <vector>
 
typedef std::deque<uint64_t> Deque;
typedef std::map<uint32_t, Deque > MyMumap;
 
typedef std::vector< std::pair<uint32_t,uint64_t> > Vector;
typedef std::multimap<uint32_t, uint64_t> Multimap;
 
const uint32_t num_partitions = 100000;
const size_t num_elements =     500000;
 
int main() {
  srand( 1337 );
  Vector values;
  for( size_t i = 0; i <= num_elements; ++i ) {
    uint32_t key = rand() % num_partitions;
    uint64_t value = rand();
    values.push_back( std::make_pair( key, value ) );
  }
  clock_t start;
  clock_t stop;
  {
    start = clock();
    Multimap mumap;
    for(Vector::const_iterator iter = values.begin(); iter != values.end(); ++iter ) {
      mumap.insert( *iter );
    }
    stop = clock();
    std::cout << "Filling std::multimap: " << stop - start << " ticks" << std::endl;
    
    uint64_t sum = 0;
    start = clock();
    for( uint32_t i = 0; i <= num_partitions; ++i ) {
      uint64_t sum = 0;
      
      std::pair<Multimap::const_iterator, Multimap::const_iterator> range = mumap.equal_range( i );
      for(Multimap::const_iterator iter = range.first; iter != range.second; ++iter ) {
        sum += iter->second;
      }
    }
    stop = clock();
    std::cout << "Reading std::multimap: " << stop - start << " ticks (" << sum << ")" << std::endl;
  }
  {
    start = clock();
    MyMumap mumap;
    for(Vector::const_iterator iter = values.begin(); iter != values.end(); ++iter ) {
      mumap[ iter->first ].push_back( iter->second );
    }
    stop = clock();
    std::cout << "Filling MyMumap: " << stop - start << " ticks" << std::endl;
    
    uint64_t sum = 0;
    start = clock();
    for( uint32_t i = 0; i <= num_partitions; ++i ) {
      uint64_t sum = 0;
      
      MyMumap::const_iterator it = mumap.find(i);
      if (it == mumap.end()) { continue; }
      
      for (Deque::const_iterator iter = it->second.begin(), end = it->second.end(); iter != end; ++iter ) {
        sum += *iter;
      }
    }
    stop = clock();
    std::cout << "Reading MyMumap: " << stop - start << " ticks (" << sum << ")" << std::endl;
  }
}