sorting-speed.cpp

/******************************************************************************
 * examples/sorting-speed/sorting-speed.cpp
 *
 * Very simple experiment to measure the speed of std::sort, std::stable_sort,
 * and STL's heapsort implementations on a random integer permutation.
 *
 ******************************************************************************
 * Copyright (C) 2014 Timo Bingmann <tb@panthema.net>
 *
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program.  If not, see <http://www.gnu.org/licenses/>.
 *****************************************************************************/

#include <algorithm>
#include <iostream>
#include <cmath>
#include <sys/time.h>

//! minimum total item count sorted per experiment -> increase for faster
//! machines.
const size_t test_volume = 32*1024*1024;

//! smallest item count to test
const size_t size_min = 1024;

//! largest item count to test
const size_t size_max = 1024*1024*1024;

//! number of iterations of each test size
const size_t iterations = 15;

//! item type
typedef unsigned int item_type;

////////////////////////////////////////////////////////////////////////////////

void test_std_sort(item_type* array, size_t n)
{
    std::sort(array, array + n);
}

void test_std_stable_sort(item_type* array, size_t n)
{
    std::stable_sort(array, array + n);
}

void test_std_heap_sort(item_type* array, size_t n)
{
    std::make_heap(array, array + n);
    std::sort_heap(array, array + n);
}

////////////////////////////////////////////////////////////////////////////////

//! timestamp
double timestamp()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + tv.tv_usec / 1e6;
}

//! the test framework routine
template <void (*test)(item_type* array, size_t n)>
void run_test(const std::string& algoname)
{
    for (size_t size = size_min; size <= size_max; size *= 2)
    {
        size_t repeats = test_volume / size;
        if (repeats == 0) repeats = 1;

        std::cout << "Running algorithm " << algoname
                  << " with size=" << size << " repeats=" << repeats << "\n";

        for (size_t iter = 0; iter < iterations; ++iter)
        {
            std::cout << "iteration=" << iter << "\n";

            item_type* array = new item_type[size];

            for (size_t i = 0; i < size; ++i)
                array[i] = i / 4;

            std::random_shuffle(array, array + size);

            double ts1, ts2;

            if (repeats == 1)
            {
                ts1 = timestamp();

                test(array, size);

                ts2 = timestamp();
            }
            else
            {
                item_type* arraycopy = new item_type[size];
                std::copy(array, array + size, arraycopy);

                ts1 = timestamp();

                for (size_t r = 0; r < repeats; ++r)
                {
                    // copy in new version of random permutation
                    std::copy(arraycopy, arraycopy + size, array);

                    test(array, size);
                }

                ts2 = timestamp();

                // measure time of copying data
                for (size_t r = 0; r < repeats; ++r)
                {
                    size_t rx = r % size;
                    std::copy(arraycopy, arraycopy + size - rx, array + rx);
                }

                double ts3 = timestamp();

                ts2 -= ts3 - ts2;

                volatile item_type x = array[size-1]; // anti-optimization
                x = x + 1;

                delete [] arraycopy;
            }

            std::cout << "time = " << ts2 - ts1 << std::endl;

            delete [] array;

            std::cout << "RESULT"
                      << " algo=" << algoname
                      << " size=" << size
                      << " time=" << ts2 - ts1
                      << " repeats=" << repeats
                      << " iteration=" << iter
                      << " typesize=" << sizeof(item_type)
                      << " datasize=" << size * sizeof(item_type)
                      << std::endl;
        }
    }
}

////////////////////////////////////////////////////////////////////////////////

int main()
{
    run_test<test_std_sort>("std::sort");
    run_test<test_std_stable_sort>("std::stable_sort");
    run_test<test_std_heap_sort>("std::heap_sort");

    return 0;
}

////////////////////////////////////////////////////////////////////////////////