Skip to content

Instantly share code, notes, and snippets.

@prehistoricpenguin

prehistoricpenguin/container_perf.cpp

Created February 19, 2014 08:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save prehistoricpenguin/9088405 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save prehistoricpenguin/9088405 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
container_perf.cpp
// A simple demo aimed to test the time efficiency for the find operation
// in C++ STL containers, used in vector,map and unordered_map, respectively.
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <cstdio>
#include <ctime>
using namespace std;
const int ktotaltimes = 1e3;
const int kbufsize = 10;
float time_vec[kbufsize];
float time_map[kbufsize];
float time_umap[kbufsize];
int pass = 0;
float calc_time_diff(clock_t start, clock_t end) {
return (float)(end - start) / CLOCKS_PER_SEC ;
}
void init_rand_vector(int size, vector<int>& vec) {
for (int i = 0; i < size; ++i) {
vec.push_back(rand());
}
}
float test_vec_case(vector<int>& vec) {
// one must hit, the other randmize
int tofind1 = vec[rand() % vec.size()];
int tofind2 = rand();
clock_t tmbeg = clock();
auto ite1 = find(begin(vec), end(vec), tofind1);
// disable unwanted optimizing by compilers
if (ite1 != end(vec))
++*ite1;
auto ite2 = find(begin(vec), end(vec), tofind2);
if (ite2 != end(vec))
++*ite2;
clock_t tmend = clock();
// time difference
return calc_time_diff(tmbeg, tmend);
}
template <int size>
float test_vec() {
float cost = 0;
for (int i = 0; i < ktotaltimes; ++i) {
vector<int> vec;
init_rand_vector(size, vec);
cost += test_vec_case(vec);
}
return cost;
}
template <typename T>
void init_rand_map(vector<int>& vec, T& mp) {
for (int val : vec) {
mp[val] = rand();
}
}
template <typename T>
float test_map_case(vector<int>& vec, T& mp) {
int tofind1 = vec[rand() % vec.size()];
int tofind2 = rand();
clock_t tmbeg = clock();
auto it1 = mp.find(tofind1);
if (it1 != end(mp))
++it1->second;
auto it2 = mp.find(tofind2);
if (it2 != end(mp))
++it2->second;
clock_t tmend= clock();
return calc_time_diff(tmbeg, tmend);
}
template <int size, typename T>
float test_map() {
float cost = 0;
for (int i = 0; i < ktotaltimes; ++i) {
T mp;
vector<int> vec;
init_rand_vector(size, vec);
init_rand_map(vec, mp);
cost += test_map_case(vec, mp);
}
return cost;
}
template <int scale>
void test() {
time_vec[pass] = test_vec<scale>();
time_map[pass] = test_map<scale, map<int, int> >();
time_umap[pass] = test_map<scale, unordered_map<int, int> >();
++pass;
}
void performance() {
test<10>();
test<100>();
test<1000>();
test<10000>();
}
void summarize_total() {
const float milipersec = 1000;
printf("Summarize:\n");
printf("Test each container for %d times\n", ktotaltimes);
printf("----------------------------------------------------------------------\n");
printf("scale:\t\t10\t\t100\t\t1000\t\t10000\n");
printf("vector:\t\t%-4gms\t\t%-4gms\t\t%-4gms\t\t%-4gms\n",
time_vec[0] * milipersec,
time_vec[1] * milipersec,
time_vec[2] * milipersec,
time_vec[3] * milipersec);
printf("map:\t\t%-4gms\t\t%-4gms\t\t%-4gms\t\t%-4gms\n",
time_map[0] * milipersec,
time_map[1] * milipersec,
time_map[2] * milipersec,
time_map[3] * milipersec);
printf("hashmap:\t%-4gms\t\t%-4gms\t\t%-4gms\t\t%-4gms\n",
time_umap[0] * milipersec,
time_umap[1] * milipersec,
time_umap[2] * milipersec,
time_umap[3] * milipersec);
printf("----------------------------------------------------------------------\n");
}
int main() {
srand(time(NULL));
performance();
summarize_total();
return 0;
}
/*
debug:
**************************************
release:
Summarize:
Test each container for 1000 times
----------------------------------------------------------------------
scale: 10 100 1000 10000
vector: 0 ms 1 ms 1 ms 7 ms
map: 1 ms 0 ms 0 ms 1 ms
hashmap: 0 ms 0 ms 0 ms 0 ms
----------------------------------------------------------------------
Summarize:
Test each container for 10000 times
----------------------------------------------------------------------
scale: 10 100 1000 10000
vector: 1 ms 0 ms 8 ms 71 ms
map: 0 ms 3 ms 3 ms 1 ms
hashmap: 0 ms 0 ms 0 ms 0 ms
----------------------------------------------------------------------
*/
@prehistoricpenguin
Copy link
Author

prehistoricpenguin commented Feb 19, 2014 

/*
debug mode:
Summarize:
Test each container for 1000 times
----------------------------------------------------------------------
scale:          10              100             1000            10000
vector:         9   ms          9   ms          12  ms          37  ms
map:            9   ms          6   ms          4   ms          10  ms
hashmap:        5   ms          5   ms          7   ms          13  ms
----------------------------------------------------------------------
Press any key to continue . . .



*/

@prehistoricpenguin
Copy link
Author

prehistoricpenguin commented Sep 22, 2014 

#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>

#include <cstdio>
#include <ctime>
#include <windows.h>
using namespace std;

class Timer {
public:
    Timer() : start_(), end_() {
    }

    void Start() {
        QueryPerformanceCounter(&start_);
    }

    void Stop() {
        QueryPerformanceCounter(&end_);
    }

    double GetElapsedMilliseconds() {
        LARGE_INTEGER freq;
        QueryPerformanceFrequency(&freq);
        return (end_.QuadPart - start_.QuadPart) * 1000.0 / freq.QuadPart;
    }

private:
    LARGE_INTEGER start_;
    LARGE_INTEGER end_;
};

Timer gtimer;

const int ktotaltimes = (int)1e3;
const int kbufsize = 10;
double time_vec[kbufsize];
double time_map[kbufsize];
double time_umap[kbufsize];
int pass = 0;

float calc_time_diff(clock_t start, clock_t end) {
    return (float)(end - start) / CLOCKS_PER_SEC;
}

void init_rand_vector(int size, vector<int>& vec) {
    for (int i = 0; i < size; ++i) {
        vec.push_back(rand());
    }
}

double test_vec_case(vector<int>& vec) {
    // one must hit, the other randmize
    int tofind1 = vec[rand() % vec.size()];
    int tofind2 = rand();

    gtimer.Start();
    auto ite1 = find(begin(vec), end(vec), tofind1);
    // disable unwanted optimizing by compilers 
    if (ite1 != end(vec))
        ++*ite1;

    auto ite2 = find(begin(vec), end(vec), tofind2);
    if (ite2 != end(vec))
        ++*ite2;
    gtimer.Stop();
    // time difference
    return gtimer.GetElapsedMilliseconds();
}

template <int size>
double test_vec() {
    double cost = 0;
    for (int i = 0; i < ktotaltimes; ++i) {
        vector<int> vec;
        init_rand_vector(size, vec);
        cost += test_vec_case(vec);
    }
    return cost;
}

template <typename T>
void init_rand_map(vector<int>& vec, T& mp) {
    for (int val : vec) {
        mp[val] = rand();
    }
}

template <typename T>
double test_map_case(vector<int>& vec, T& mp) {
    int tofind1 = vec[rand() % vec.size()];
    int tofind2 = rand();

    gtimer.Start();
    auto it1 = mp.find(tofind1);
    if (it1 != end(mp))
        ++it1->second;
    auto it2 = mp.find(tofind2);
    if (it2 != end(mp))
        ++it2->second;
    gtimer.Stop();
    return gtimer.GetElapsedMilliseconds();
}

template <int size, typename T>
double test_map() {
    double cost = 0;
    for (int i = 0; i < ktotaltimes; ++i) {
        T mp;
        vector<int> vec;
        init_rand_vector(size, vec);
        init_rand_map(vec, mp);
        cost += test_map_case(vec, mp);
    }
    return cost;
}

template <int scale>
void test() {
    time_vec[pass] = test_vec<scale>();
    time_map[pass] = test_map<scale, map<int, int> >();
    time_umap[pass] = test_map<scale, unordered_map<int, int> >();
    ++pass;
}

void performance() {
    test<10>();
    test<100>();
    test<1000>();
    test<10000>();
}

void summarize_total() {
    const float milipersec = 1000;
    printf("Summarize:\n");
    printf("Test each container for %d times\n", ktotaltimes);
    printf("----------------------------------------------------------------------\n");
    printf("scale:\t\t10\t\t100\t\t1000\t\t10000\n");
    printf("vector:\t\t%.4lfms\t%.4lfms\t%.4lfms\t%.4lfms\n",
        time_vec[0] ,
        time_vec[1] ,
        time_vec[2] ,
        time_vec[3] );
    printf("map:\t\t%.4lfms\t%.4lfms\t%.4lfms\t%.4lfms\n",
        time_map[0] ,
        time_map[1] ,
        time_map[2] ,
        time_map[3] );
    printf("hashmap:\t%.4lfms\t%.4lfms\t%.4lfms\t%.4lfms\n",
        time_umap[0] ,
        time_umap[1] ,
        time_umap[2] ,
        time_umap[3] );
    printf("----------------------------------------------------------------------\n");
}

int main() {
    srand((unsigned)time(NULL));
    performance();
    summarize_total();
    return 0;
}
/*
Summarize:
Test each container for 1000 times
----------------------------------------------------------------------
scale:          10              100             1000            10000
vector:         0.0301ms        0.1167ms        0.9285ms        7.5608ms
map:            0.0625ms        0.1001ms        0.1690ms        0.2348ms
hashmap:        0.0343ms        0.0301ms        0.0471ms        0.0702ms
----------------------------------------------------------------------
请按任意键继续. . .
*/

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment