RDESTL - fixed_list

²⁰/Sep 2008 By admin

I didnt have much time to work on RDESTL recently, but I try to commit some new stuff every now and then (usually bug fixes). One rather interesting recent addition is a fixed_list class. Basically, it’s a rough equivalent of already existing fixed_vector. It never allocates any memory and works only withing given buffer. Let’s try to create linked list of integers, that can hold up to 64 elements:

rde::fixed_list<int, 64> lst;
lst.push_back(5);
lst.push_back(10);
lst.push_front(3);

It’s not the coolest feature of this class. It doesnt use any pointers directly, so it’s very easy to relocate. In fact, as long as elements of list can be trivially copied, it can be moved around using memcpy (in fact, this situation is properly detected by the assignment operator):

TEST(FixedListRelocation)
{
    typedef rde::fixed_list<int, 1000> TList;
    TList lst;
    rde::Random::Init(1001);
    for (int i = 0; i < 1000; ++i)
        lst.push_back(rde::Random::NextInt());

    void* mem2 = new char[sizeof(lst)];
    rde::Sys::MemCpy(mem2, &lst;, sizeof(lst));
    TList* lst2 = (TList*)mem2;
    CHECK_EQUAL(lst.size(), lst2->size());
    TList::iterator it = lst.begin();
    TList::iterator it2 = lst2->begin();
    while (it != lst.end())
    {
        CHECK_EQUAL(*it, *it2);
        ++it;
        ++it2;
    }
    CHECK(it2 == lst2->end());
    delete[] (char*)mem2;
}

Another advantage of using indices instead of pointers is that we dont always need 8 bytes per next/prev index. In case of small lists we can easily get away with 2 bytes per-node overhead. List detects at compile-time what index size is needed. Whole lists takes one, continuous portion of memory, so it’s relatively cache friendly (certainly more than typical pointer-based solution).

Nice thing is, it still is linked list under the hood, so it’s quick to remove/insert elements at random positions. I tested typical observer-notifier pattern with 256 observers, removing one every frame and inserting another. Over duration of 100000 frames fixed_list was roughly 2.8 times quicker than vector. Vector was slightly quicker when iterating elements, but the difference was really negligable (around 2-3ms over the course of 10k frames).

PS. Elements table is the first member of fixed_list class, so in practice to control aligment, you’d only have to align whole list object.

.m.m.s.

Maciej Sinilo

RDESTL - fixed_list