BenchIntrusiveList

BenchIntrusiveList.cpp

#include <cstring>
#include <ctime>
#include <iostream>
#include <list>

#define USE_INTRUSIVE 1
#define USE_POINTER 1
#define MAKE_NOISE_FOR_STD_PTR 1

#if USE_POINTER
static constexpr int objectCount = 50'000'000;
#else
static constexpr int objectCount = 50'000'000;
#endif

struct object {
#if USE_INTRUSIVE
    object *next = nullptr;
    object *prev = nullptr;
#endif
    int value = 1;
    uint8_t someData[256];
};

static uint64_t getUsec()
{
    timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1'000'000 + t.tv_nsec / 1000;
}

#if USE_INTRUSIVE
#if USE_POINTER

// Intrusive list with items allocated in advance.
//
static void bench(uint64_t *createTime, uint64_t *walkTime)
{
    object *head = nullptr;
    object *tail = nullptr;
    object *objects = new object[objectCount];
    uint64_t t = getUsec();
    for (int i = 0; i < objectCount; ++i)
    {
        object *obj = &objects[i];
        if (head == nullptr)
            head = obj;
        else
            tail->next = obj;
        tail = obj;
    }
    *createTime = getUsec() - t;

    uint64_t sum = 0;
    t = getUsec();
    for (const object *pos = head; pos != nullptr; pos = pos->next)
        sum += pos->value;
    *walkTime = getUsec() - t;
    // To make the compiler not drop the sum.
    if (sum == UINT64_MAX)
        abort();
    delete[] objects;
}

#else // USE_POINTER

// Intrusive list with items allocated just before push. Like an intrusive std::list would
// do on emplace/push.
//
static void bench(uint64_t *createTime, uint64_t *walkTime)
{
    object *head = nullptr;
    object *tail = nullptr;
    uint64_t t = getUsec();
    for (int i = 0; i < objectCount; ++i)
    {
        object *obj = new object();
        if (head == nullptr)
            head = obj;
        else
            tail->next = obj;
        tail = obj;
    }
    *createTime = getUsec() - t;

    uint64_t sum = 0;
    t = getUsec();
    for (const object *pos = head; pos != nullptr; pos = pos->next)
        sum += pos->value;
    *walkTime = getUsec() - t;
    // To make the compiler not drop the sum.
    if (sum == UINT64_MAX)
        abort();
    while (head != nullptr)
    {
        object *next = head->next;
        delete head;
        head = next;
    }
}

#endif // USE_POINTER
#else // USE_INTRUSIVE
#if USE_POINTER

// Non-intrusive list of pointers. Most popular option when not too small objects are
// stored. Items allocated in advance.
//
static void bench(uint64_t *createTime, uint64_t *walkTime)
{
    object *objects = new object[objectCount];
#if MAKE_NOISE_FOR_STD_PTR
    std::list<void *> noise1, noise2, noise3, noise4;
    std::list<int> noise5;
    auto makeNoise = [&]()
    {
        noise1.push_back(nullptr);
        noise2.push_back(nullptr);
        noise3.push_back(nullptr);
        noise4.push_back(nullptr);
        noise5.push_back(1);
    };
#endif

    std::list<object *> list;
    uint64_t t = getUsec();
    for (int i = 0; i < objectCount; ++i)
    {
        list.push_back(&objects[i]);
#if MAKE_NOISE_FOR_STD_PTR
        makeNoise();
#endif
    }
    *createTime = getUsec() - t;

    uint64_t sum = 0;
    t = getUsec();
    for (const object *obj : list)
        sum += obj->value;
    *walkTime = getUsec() - t;
    // To make the compiler not drop the sum.
    if (sum == UINT64_MAX)
        abort();
    list.clear();
    delete[] objects;
}

#else // USE_POINTER

// Non-intrusive list of objects. Makes sense for small objects. Items can only be
// allocated just before push/emplace.
//
static void bench(uint64_t *createTime, uint64_t *walkTime)
{
    std::list<object> list;
    uint64_t t = getUsec();
    for (int i = 0; i < objectCount; ++i)
        list.emplace_back();
    *createTime = getUsec() - t;

    uint64_t sum = 0;
    t = getUsec();
    for (const object &obj : list)
        sum += obj.value;
    *walkTime = getUsec() - t;
    if (sum == UINT64_MAX)
        abort();
    list.clear();
}

#endif // USE_POINTER
#endif // USE_INTRUSIVE

int main()
{
    uint64_t createTime = 0;
    uint64_t walkTime = 0;
    bench(&createTime, &walkTime);

    std::cout << "Create: " << createTime << " us" << std::endl;
    std::cout << "Walk:   " << walkTime << " us" << std::endl;
    return 0;
}