STL Benchmarks

This is a preliminary performance test excercising the performance of complex STL data structures and their manipulation with STL algorithms. It is creating a vector of set of int, returning it by value from factory functions, sorting it, and rotating it. And RVO has been intentionally thwarted, which can easily happen accidently, or even for good reasons in real world code. Thus in most of today's environments, this benchmark is measuring a lot of copying.

Here's timing results for gcc 4.0.1:

N = 3001
construction took 53.02
sort took 90.86
rotate took 23.25
destruction took 20.17
done
Total time = 187.3

The rvalue reference work was designed to eliminate every single copy in this benchmark. Here is a run with rvalue reference enabled (in both the compiler and the library):

N = 3001
construction took 6.71
sort took 0.01
rotate took 0
destruction took 6.88
done
Total time = 13.6

The chart to the right illustrates the above numbers (smaller is faster).

Here's the code:

#include <vector>
#include <iostream>
#include <time.h>
#include <set>
#include <algorithm>

const unsigned N = 3001;

extern bool some_test;

std::set<int>
get_set(int)
{
    std::set<int> s;
    for (int i = 0; i < N; ++i)
        while (!s.insert(std::rand()).second)
            ;
    if (some_test)
        return s;
    return std::set<int>();
}

std::vector<std::set<int> >
generate()
{
    std::vector<std::set<int> > v;
    for (int i = 0; i < N; ++i)
        v.push_back(get_set(i));
    if (some_test)
        return v;
    return std::vector<std::set<int> >();
}

float time_it()
{
    clock_t t1, t2, t3, t4;
    clock_t t0 = clock();
    {
    std::vector<std::set<int> > v = generate();
    t1 = clock();
    std::cout << "construction took " << (float)((t1 - t0)/(double)CLOCKS_PER_SEC) << std::endl;
    std::sort(v.begin(), v.end());
    t2 = clock();
    std::cout << "sort took " << (float)((t2 - t1)/(double)CLOCKS_PER_SEC) << std::endl;
    std::rotate(v.begin(), v.begin() + v.size()/2, v.end());
    t3 = clock();
    std::cout << "rotate took " << (float)((t3 - t2)/(double)CLOCKS_PER_SEC) << std::endl;
    }
    t4 = clock();
    std::cout << "destruction took " << (float)((t4 - t3)/(double)CLOCKS_PER_SEC) << std::endl;
    std::cout << "done" << std::endl;
    return (float)((t4-t0)/(double)CLOCKS_PER_SEC);
}

int main()
{
    std::cout << "N = " << N << '\n';
    float t = time_it();
    std::cout << "Total time = " << t << '\n';
}

bool some_test = true;