sfl::segmented_vector: perform indexed access to elements with one pointer dereference when in the same block.

[pietrom16]

Class sfl::segmented_vector

At the moment: "Indexed access to elements (operator[] and at) must perform two pointer dereferences."

A performance improvement can be obtained with this change: perform indexed access to elements with one pointer dereference when in the same block.

E.g.:

• Access element i in block b1: two pointer dereferences needed.
• Access element j in block b2: two pointer dereferences needed.
• Access element k in block b2: only one pointer dereference needed.

This allows to get better performance when accessing data located in close memory locations.

[slavenf]

Idea sounds great but impossible. First you must understand how operator[] is implemented:

reference operator[](size_type pos) noexcept
{
    SFL_ASSERT(pos < size());

    const auto i = pos / N;
    const auto j = pos - i * N;

    return *(*(data_.seg_first_ + i) + j);
}

First is calculated segment index (stored in variable i),
then is calculated element index in i-th segment (stored in variable j)
and finally reference to required element is returned.
As you can see, two pointer dereferences are always needed.
The same is for member function at.