Create micro-benchmarks for core::List

[gavv]

Last revised: Oct 2023

core::List is widely used in Roc, so it'd be useful to have in our hands real numbers for its major operations. We should measure at least insertion (at the end and in the middle), removal, and iteration overhead.

It would be also interesting to add two benchmarks for iterative push_pack using core::List and using core::Array with grow_exp(), and compare results.

We use Google Benchmark. To add a new benchmark, just create a new file bench_FOO.cpp in src/tests/MODULE_NAME (roc_core in this case). Here are examples of existing micro-benchmarks: 1, 2. You can find details on building and running benchmarks here.

[LilMonk]

Hey! I'm new to Open Source and I am interested in contributing. I have written a few lines for this benchmarking but there is an error. Can you help me in fixing this?

#include <benchmark/benchmark.h>

#include "roc_core/list.h"

namespace roc {
namespace core {
namespace {

enum { NumObjects = 5, NumIterations = 500 };

struct Object : ListNode { };

typedef List<Object, NoOwnership> BenchList;

class BM_Lists : public benchmark::Fixture {
public:
    BM_Lists() {
    }
    inline BenchList& get_list() {
        return list_;
    }

    inline Object& alloc_object(int index) {
        return obj[index];
    }

    virtual void SetUp(const benchmark::State&) {
    }

    virtual void TearDown(const benchmark::State&) {
        int size_ = list_.size();
        for (int i = 0; i < size_; i++) {
            list_.remove(*list_.front());
        }
    }

private:
    BenchList list_;
    Object obj[NumObjects];
};

BENCHMARK_DEFINE_F(BM_Lists, PushBack)(benchmark::State& state) {
    BenchList& list = get_list();
    while (state.KeepRunning()) {
        for (int i = 0; i < NumObjects - 1; i++) {
            list.push_back(alloc_object(i));
        }
    }
}
BENCHMARK_REGISTER_F(BM_Lists, PushBack);

} // namespace

} // namespace core

} // namespace roc

I'm getting an error like this:

ERROR: roc_test: list element is member of wrong list: expected (nil), got 0x561dd894ef70

I think that the error is when I'm calling get_list();

[gavv]

@EthicalCoder99 sorry for late reply!

This panic is caused by safety check in List implementation. There are a few checks, sometimes we check that the item belongs to some specific list, sometimes we check that the item doesn't belong to any list (item's list pointer is NULL). expected (nil) means the second.

The panic is located in check_is_member_() method. It is called with NULL only in one place, in List::insert_(). So it seems that you're trying to insert an element that already belongs to some another list, or maybe to the same list, or maybe is not properly initialized.

[8julie]

Hi, does this issue still need help? I would love to contribute but no worries if not!