qsort vs. std::sort -- https://martin-ueding.de/posts/qsort-vs-std-sort/

compile.sh

#!/bin/bash
# Copyright © 2014, 2016 Martin Ueding <mu@martin-ueding.de>
# Licensed under the MIT license

set -e
set -u
set -x

options="-Wall -Wpedantic -O3 -march=native"

gcc $options -std=c99 -o sort-gcc sort.c
g++ $options -std=c++11 -o sort-g++ sort.cpp
clang $options -std=c99 -o sort-clang sort.c
clang++ $options -std=c++11 -o sort-clang++ sort.cpp

for program in sort-gcc sort-g++ sort-clang sort-clang++
do
    ./$program > $program.txt
done

generate-data.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Copyright © 2016 Martin Ueding <mu@martin-ueding.de>
# Licensed under the MIT license

import numpy as np


def main():
    for exp in range(1, 8):
        size = 10**exp
        data = np.random.sample(size)
        np.savetxt('data-{}.txt'.format(size), data)


if __name__ == '__main__':
    main()

sort.c

// Copyright © 2014, 2016 Martin Ueding <mu@martin-ueding.de>
// Licensed under the MIT license

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int compare(void const *this, void const *other) {
    double const a = *((const double *)this);
    double const b = *((const double *)other);
    if (a < b)
        return -1;
    else if (a == b)
        return 0;
    else
        return 1;
}

void time_sorting(char const *const filename, size_t const size) {
    double *data = malloc(size * sizeof(*data));
    double *orig = malloc(size * sizeof(*orig));

    FILE *fp = fopen(filename, "r");
    for (size_t i = 0; i < size; ++i) {
        fscanf(fp, "%lf\n", orig + i);
    }

    printf("%lu", size);
    for (int i = 0; i < 5; ++i) {
        memcpy(data, orig, size * sizeof(*orig));

        clock_t const start = clock();
        qsort(data, size, sizeof(*data), compare);
        clock_t const end = clock();

        double const duration = (end - start) / ((double)CLOCKS_PER_SEC);
        printf("\t%g", duration);
    }
    printf("\n");

    free(data);
    free(orig);
}

int main() {
    time_sorting("data-10.txt", 10);
    time_sorting("data-100.txt", 100);
    time_sorting("data-1000.txt", 1000);
    time_sorting("data-10000.txt", 10000);
    time_sorting("data-100000.txt", 100000);
    time_sorting("data-1000000.txt", 1000000);
    time_sorting("data-10000000.txt", 10000000);
}

sort.cpp

// Copyright © 2014, 2016 Martin Ueding <mu@martin-ueding.de>
// Licensed under the MIT license

#include <algorithm>
#include <ctime>
#include <fstream>
#include <iostream>
#include <vector>

void time_sorting(std::string const &filename, size_t const size) {
    std::vector<double> orig;
    orig.reserve(size);

    std::ifstream ifs(filename);
    for (size_t i = 0; i < size; ++i) {
        double in;
        ifs >> in;
        orig.push_back(in);
    }

    std::cout << size;
    for (int i = 0; i < 5; ++i) {
        auto data = orig;
        clock_t const start = clock();
        std::sort(std::begin(data), std::end(data));
        clock_t const end = clock();

        double const duration = (end - start) / ((double)CLOCKS_PER_SEC);
        std::cout << "\t" << duration;
    }
    std::cout << "\n";
}

int main() {
    time_sorting("data-10.txt", 10);
    time_sorting("data-100.txt", 100);
    time_sorting("data-1000.txt", 1000);
    time_sorting("data-10000.txt", 10000);
    time_sorting("data-100000.txt", 100000);
    time_sorting("data-1000000.txt", 1000000);
    time_sorting("data-10000000.txt", 10000000);
}

test-drive.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Copyright © 2014, 2016 Martin Ueding <mu@martin-ueding.de>
# Licensed under the MIT license

import datetime
import subprocess

import matplotlib.pyplot as pl
import numpy as np


def main():
    fig = pl.figure()
    ax = fig.add_subplot(1, 1, 1)

    all_data = {}

    for compiler, color in [('gcc', '#ff3586'), ('g++', '#ff0000'), ('clang', '#397eff'), ('clang++', '#0000ff')]:
        data = np.loadtxt('sort-{}.txt'.format(compiler))
        sizes = data[:, 0]
        times_val = np.mean(data[:, 1:], axis=1)
        times_err = np.std(data[:, 1:], axis=1)
        ax.errorbar(sizes, times_val, times_err, label=compiler, marker='o', color=color)
        all_data[compiler] = (times_val, times_err)


    ax.set_xscale('log')
    ax.set_yscale('log')
    ax.set_xlabel('Elements to sort')
    ax.set_ylabel('Duration / seconds')
    ax.set_title('qsort vs. std::sort')
    ax.grid(True)
    ax.legend(loc='best')
    ax.margins(0.05)
    fig.tight_layout()
    fig.savefig('time.pdf')
    fig.savefig('time.svg')

    fig = pl.figure()

    i = 1
    for ratios in [(('gcc', 'clang'), ('g++', 'clang++')), (('gcc', 'g++'), ('clang', 'clang++'))]:
        (c1, c2), (c3, c4) = ratios
        r12_val = all_data[c1][0] / all_data[c2][0]
        r12_err = np.sqrt(
            (all_data[c1][1] / all_data[c2][0])**2
            + (all_data[c1][0] / all_data[c2][0]**2 * all_data[c2][1])**2
        )
        r34_val = all_data[c3][0] / all_data[c4][0]
        r34_err = np.sqrt(
            (all_data[c3][1] / all_data[c4][0])**2
            + (all_data[c3][0] / all_data[c4][0]**2 * all_data[c4][1])**2
        )

        ax = fig.add_subplot(1, 2, i)
        ax.errorbar(sizes, r12_val, r12_err, label='{} / {}'.format(c1, c2), marker='o')
        ax.errorbar(sizes, r34_val, r34_err, label='{} / {}'.format(c3, c4), marker='o')

        print(r12_val)
       

        ax.set_xscale('log')
        ax.set_yscale('log')
        ax.set_xlabel('Elements to sort')
        ax.set_ylabel('Ratio')
        ax.grid(True)
        ax.legend(loc='best')
        ax.set_ylim(0.1, 10)

        i += 1
        
    ax = fig.add_subplot(1, 2, 1)
    ax.set_title('GCC vs. LLVM')
    ax = fig.add_subplot(1, 2, 2)
    ax.set_title('C vs. C++')

    fig.tight_layout()
    fig.savefig('Ratios.pdf')
    fig.savefig('Ratios.svg')


if __name__ == "__main__":
    main()