Skip navigation

By now everyone should know std::vector<T> beats std::list<T> at pretty much everything.

But splicing one container into another is std::list‘s specialty.

Here’s a rather long but complete framework to test the idea, copy-and-paste ready:

#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <list>
#include <string>
#include <type_traits>
#include <vector>

static const std::size_t Trials = 100;
static const bool PreallocateVector = false;

template <typename T>
void use(const volatile T& x)
{
    char c = reinterpret_cast<const volatile char&>(x);
    (void)c;
}

template <typename Container>
void touch_up_container(Container&)
{
    // do nothing
}

template <typename T, typename Alloc>
void touch_up_container(std::vector<T, Alloc>& vec)
{
    if (PreallocateVector)
        vec.reserve(vec.size() * 2);
}

template <typename T, typename Alloc>
std::list<T, Alloc>
combine(
    std::list<T, Alloc>&& first,
    std::list<T, Alloc>&& second
    )
{
    std::list<T, Alloc> result = std::move(first);

    result.splice(result.end(), std::move(second));

    return result;
}

template <typename T, typename Alloc>
std::vector<T, Alloc>
combine(
    std::vector<T, Alloc>&& first,
    std::vector<T, Alloc>&& second
    )
{
    std::vector<T, Alloc> result = std::move(first);

    result.insert(
        result.end(),
        std::make_move_iterator(second.begin()),
        std::make_move_iterator(second.end())
        );

    return result;
}

template <typename Container>
double test(Container first, Container second)
{
    const auto startTime = std::chrono::high_resolution_clock::now();

    // combine the two containers, use result
    Container result = combine(std::move(first), std::move(second));
    use(result);

    const auto endTime = std::chrono::high_resolution_clock::now();

    const auto duration = endTime - startTime;
    const auto seconds = std::chrono::duration<double>(duration);

    return seconds.count();
}

template <typename Container, typename Func>
Container generate_container(const std::size_t size, Func dataSource)
{
    Container result;

    std::generate_n(std::back_inserter(result), size, dataSource);

    return result;
}

template <typename Container, typename Func>
double test_container(const std::size_t size, Func dataSource)
{
    const auto generateContainer =
        [&]{ return generate_container<Container>(size, dataSource); };

    auto sourceA = generateContainer(), sourceB = generateContainer();

    double sum = 0.0;
    for (std::size_t trial = 0; trial < Trials; ++trial)
    {
        auto testSourceA = sourceA, testSourceB = sourceB;

        // optionally preallocate vector (note: not timed)
        touch_up_container(testSourceA);
        touch_up_container(testSourceB);

        sum += test(std::move(testSourceA), std::move(testSourceB));
    }

    return sum / static_cast<double>(Trials);
}

template <typename T, typename Func>
void test_containers(const std::size_t size, Func dataSource)
{
    std::cout << "Testing containers of size " << size
              << " with " << (std::is_pod<T>::value ? "pod" : "non-pod")
              << " objects of size " << sizeof(T)
              << "..." << std::endl;

    std::cout << "Testing std::vector<T>..." << std::endl;
    const double vecTime = test_container<std::vector<T>>(size, dataSource);

    std::cout << "Testing std::list<T>..." << std::endl;
    const double listTime = test_container<std::list<T>>(size, dataSource);

    const char* winner;
    double winnerPercent;

    if (vecTime < listTime)
    {
        winner = "std::vector<T> wins";
        winnerPercent = 100 * (listTime / vecTime);
    }
    else if (listTime < vecTime)
    {
        winner = "std::list<T> wins";
        winnerPercent = 100 * (vecTime / listTime);
    }
    else
    {
        winner = "tie";
        winnerPercent = 0.0;
    }

    std::cout << "Times:\n"
              << "\tstd::vector<T>: " << vecTime << '\n'
              << "\tstd::list<T>: " << listTime << '\n'
              << "\t" << winner << " (" << winnerPercent << "% faster)\n"
              << std::endl;
}

template <typename T, typename Func>
void test_container_sizes(Func dataSource)
{
    const std::size_t testSizes[] =
        {
           4, 256, 4096, 65536, 2097152,
        };

    for (const auto size : testSizes)
        test_containers<T>(size, dataSource);
}

struct small_pod
{
    char data[sizeof(std::string)];

    static small_pod create()
    {
        small_pod result;

        std::fill(std::begin(result.data), std::end(result.data), 0);

        return result;
    }
};

struct big_pod
{
    int r, g, b, a;
    double x, y, z, w;

    static big_pod create()
    {
        big_pod result;

        result.r = std::rand();
        result.g = std::rand();
        result.b = std::rand();
        result.a = std::rand();
        result.x = static_cast<double>(std::rand());
        result.y = static_cast<double>(std::rand());
        result.z = static_cast<double>(std::rand());
        result.w = static_cast<double>(std::rand());

        return result;
    }
};

struct small_nonpod
{
    std::string data;

    static small_nonpod create()
    {
        small_nonpod result;

        result.data = "abcdefghijklmnopqrstuvwxyz";

        return result;
    }
};

struct big_nonpod
{
    big_pod data;
    std::string otherdata;

    static big_nonpod create()
    {
        big_nonpod result;

        result.data = big_pod::create();
        result.otherdata = "abcdefghijklmnopqrstuvwxyz";

        return result;
    }
};

int main()
{
    test_container_sizes<char>(std::rand);
    test_container_sizes<std::intmax_t>(std::rand);

    test_container_sizes<small_pod>(small_pod::create);
    test_container_sizes<small_nonpod>(small_nonpod::create);

    test_container_sizes<big_pod>(big_pod::create);
    test_container_sizes<big_nonpod>(big_nonpod::create);

    std::cout << "\n\nDone" << std::endl;
}

And some example output. For reference, my machine is 12-core (note: the program is single-threaded) Intel Xeon E5-1650 3.20GHz, 16GB RAM:

Testing containers of size 4 with pod objects of size 1...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 256 with pod objects of size 1...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 4096 with pod objects of size 1...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 65536 with pod objects of size 1...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 2.002e-005
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 2097152 with pod objects of size 1...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.0013114
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 4 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 256 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 4096 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 65536 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.00027024
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 2097152 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.0109292
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 4 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 256 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 4096 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 65536 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.00028018
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 2097152 with pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.0106587
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 4 with non-pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 256 with non-pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 4.003e-005
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 4096 with non-pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.00059051
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 65536 with non-pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.0104887
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 2097152 with non-pod objects of size 8...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.4064
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 4 with pod objects of size 48...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 256 with pod objects of size 48...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 1.001e-005
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 4096 with pod objects of size 48...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 5.006e-005
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 65536 with pod objects of size 48...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.00211195
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 2097152 with pod objects of size 48...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.066437
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 4 with non-pod objects of size 56...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0
    std::list: 0
    tie (0% faster)

Testing containers of size 256 with non-pod objects of size 56...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 2.001e-005
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 4096 with non-pod objects of size 56...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.00085074
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 65536 with non-pod objects of size 56...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.0130311
    std::list: 0
    std::list wins (inf% faster)

Testing containers of size 2097152 with non-pod objects of size 56...
Testing std::vector...
Testing std::list...
Times:
    std::vector: 0.533389
    std::list: 0
    std::list wins (inf% faster)



Done

std::list<T> never loses.

This isn’t surprising, but it should settle any small disputes. 😉 All std::list has to do is shuffle some pointers around, while std::vector has to allocate memory for both containers, then copy both to the new storage. (Even if the memory is preallocated, this second copying still takes a bit of time. Preallocating the destination buffer shaves off about 50%.)

This all said, unless you find:

  1. You can or need to populate both lists at separate times, and
  2. Need to combine them, and
  3. Aren’t going to lose against std::vector during processing anyway

std::list<T> should stay out of sight. It is possible to mitigate the main issue (#3) with std::list<T>, cache coherency, with a custom allocator, but that’s even more work.

(As always, if you want to fix your performance issues: profile it.)

Leave a Reply

Your email address will not be published. Required fields are marked *