boost::fast_pool_allocator makes std::forward_list slower

Viewed 258

I wrote code to measure sorting performance of forward_list, and counterintuitively it seems that using memory pool allocator with it actually makes it slower:

// clang++ -O3 -std=c++11 -I/usr/local/include -lboost_system sort-test.cc -o sort-test

#include <boost/pool/pool_alloc.hpp>

#include <algorithm>
#include <cmath>
#include <chrono>
#include <forward_list>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;
using namespace std::chrono;
using namespace boost;

class TSampler {
public:
    void AddSample(double value) {
        NumSamples++;

        if (NumSamples == 1) {
            Mean = value;
            M = value;
            M2 = value * value;
            return;
        }

        double dillutionFactor = 1.0 / NumSamples;

        // variance recurrence
        double cm = value - M;
        M += dillutionFactor * cm;
        M2 += cm * (value - M);

        // mean recurrence
        Mean += dillutionFactor * (value - Mean);
    }

    double GetMean() const {
        return Mean;
    }

    double GetStdDev() const {
        Recalc();
        return StdDev;
    }

    double GetConfidenceRadius() const {
        Recalc();
        return Radius;
    }

    double GetConfidenceLo() const {
        Recalc();
        return Mean - Radius;
    }

    double GetConfidenceHi() const {
        Recalc();
        return Mean + Radius;
    }

private:
    void Recalc() const {
        StdDev = sqrt(M2 / (NumSamples - 1.0));
        Radius = 1.96 * StdDev / sqrt(NumSamples + 0.0);
    }

private:
    size_t NumSamples = 0;
    double Mean = NAN, M = NAN, M2 = NAN;
    mutable double StdDev = NAN, Radius = NAN;
};

void FillSamples(int *samples, size_t size) {
    ifstream r("/dev/urandom");
    r.read(reinterpret_cast<char *>(samples), size * sizeof(*samples));
}

using TList = forward_list<int>;
using TPooledList = forward_list<int, fast_pool_allocator<int>>;
using TVector = vector<int>;

void InitContainer(TList &xs, int *input, size_t size) {
    for (int i = size - 1; i >= 0; --i) {
        xs.push_front(input[i]);
    }
}

void InitContainer(TPooledList &xs, int *input, size_t size) {
    for (int i = size - 1; i >= 0; --i) {
        xs.push_front(input[i]);
    }
}

void InitContainer(TVector &xs, int *input, size_t size) {
    xs.reserve(size);
    copy(input, input + size, back_inserter(xs));
}

void Sort(TPooledList &xs) {
    xs.sort();
}

void Sort(TList &xs) {
    xs.sort();
}

void Sort(TVector &xs) {
    sort(xs.begin(), xs.end());
}

template<typename TContainer>
void RunSort(TSampler &sampler, int *input, size_t size) {
    TContainer xs;
    InitContainer(xs, input, size);

    steady_clock::time_point before = steady_clock::now();
    Sort(xs);
    steady_clock::time_point after = steady_clock::now();

    auto delta = duration_cast<duration<double>>(after - before);
    sampler.AddSample(delta.count());
}

int main(int argc, char **argv) {
    argc--; argv++;
    if (argc != 2) {
        cerr << "Usage: sort-test T N\nT: number of trials\nN: size of the vector/list" << endl;
        exit(1);
    }

    int t = atoi(argv[0]);
    int n = atoi(argv[1]);
    if (t <= 0 || n <= 0) {
        cerr << "Invalid arguments" << endl;
        exit(1);
    }

    TSampler listSampler;
    TSampler pooledListSampler;
    TSampler vectorSampler;
    TVector input;
    input.resize(n);
    for (int trial = 0; trial < t; ++trial) {
        FillSamples(&input[0], n);
        RunSort<TList>(listSampler, &input[0], n);
        RunSort<TPooledList>(pooledListSampler, &input[0], n);
        RunSort<TVector>(vectorSampler, &input[0], n);
    }

    cout << "List:        " << listSampler.GetMean()
         << " ± " << listSampler.GetConfidenceRadius()
         << " (95% confidence)" << endl;
    cout << "Pooled list: " << pooledListSampler.GetMean()
         << " ± " << pooledListSampler.GetConfidenceRadius()
         << " (95% confidence)" << endl;
    cout << "Vector:      " << vectorSampler.GetMean()
         << " ± " << vectorSampler.GetConfidenceRadius()
         << " (95% confidence)" << endl;
}

On my 2013 MacBook Air:

[03:04:59 dev]$ ./sort-test 10 10000
List:        0.00082735 ± 0.000189312 (95% confidence)
Pooled list: 0.00091835 ± 0.000201482 (95% confidence)
Vector:      0.000484268 ± 0.000107911 (95% confidence)
[03:05:03 dev]$ ./sort-test 10 10000
List:        0.000764033 ± 0.000188491 (95% confidence)
Pooled list: 0.00103925 ± 0.00038322 (95% confidence)
Vector:      0.000482046 ± 0.000111277 (95% confidence)
[03:05:08 dev]$ ./sort-test 30 10000
List:        0.000747641 ± 6.93474e-05 (95% confidence)
Pooled list: 0.000912401 ± 9.43897e-05 (95% confidence)
Vector:      0.000526488 ± 9.34585e-05 (95% confidence)
[03:05:13 dev]$ ./sort-test 30 10000
List:        0.000810124 ± 8.71386e-05 (95% confidence)
Pooled list: 0.000946477 ± 0.000115813 (95% confidence)
Vector:      0.000495523 ± 5.44617e-05 (95% confidence)
[03:05:18 dev]$ ./sort-test 30 100000
List:        0.0107134 ± 0.00110686 (95% confidence)
Pooled list: 0.018314 ± 0.00102368 (95% confidence)
Vector:      0.00583989 ± 0.000514794 (95% confidence)

Why is this the case? One reason may be that memory locality is actually worse when using a memory pool because the list nodes are allocated using normal operator ::new, but then I have to ask how one would use fast_pool_allocator properly.

1 Answers
Related