sfl::small_segmented_vector

[ZehMatt]

I think this could be a good addition to this already amazing set of containers. So sfl::small_segmented_vector<T, N> would mean that the first block of N items is statically allocated. I'm refactoring some code in OpenLoco that builds a paint graph, sometimes the graph is used to determine interactions where it basically never exceeds more than a few elements but since the items also act as a single linked list I need pointer stability. It would be the best of both worlds from segmented_vector (pointer stability) and small_vector (reduced pressure on heap).

I know its a rather big ask and I would be willing to contribute this portion if you agree with this new container.

[slavenf]

It is possible to make small_segmented_vector, but it is pretty big task. Of course, segmented_vector could be used as a starting point, but even in that case it wouldn't be so easy task.

But, let's consider other options before doing anything.

I do not see point using small_vector if it is long-lived container and number of elements is small because time used by dynamic memory allocation/deallocation is insignificant to container's lifetime. I mean, we do not gain anything if small_ container is long-lived and number of elements is small. We also do not gain anything in small_ container has big number of elements.

I also do not see point using segmented_vector (and small_segmented_vector) if segment size N is small and number of elements is big. Performances of such container are terrible compared to regular vector. For example, if number of elements is 1'000'000 then it is terrible choice to choose N = 1000 because total number of segments is 1000 and time used by dynamic memory allocation/deallocation would be very significant. If number of elements is 1'000'000 then it is much better choice to have N = 10'000 or even N = 100'000.

I also do not see point using segmented_vector (and small_segmented_vector) if segment size N is small and number of elements is small. I mean, what is an advantage of that? Yes, your argument about pointer stability holds, but there wouldn't be any significant impact on heap even plain vector was used. If if segment size N is small and number of elements is big then we go back to the previous paragraph.

It seems to me that the pointer stability is the main requirement. Is that true? If pointer stability is needed then maybe we could consider some other options:

1. stable_vector from boost library
2. std::list with custom pool allocator to avoid calling operator ::new or malloc for each element. Custom pool allocator could be implemented within a day.
3. small_list (this container does not exists, but we could make it) which is similar to std::list, but with small part.
4. std::map/set which are based on red-black tree. Pointers to elements are always stable. We could also use the same custom pool allocator here.
5. sfl::small_map/small_set (coming soon) which are also based on red-black tree. We could also use the same custom pool allocator here.

What do you think?

[ZehMatt]

Thanks for taking the time to respond, I think my requirement is a bit too specific and in this case the container is used more like an allocator/storage.

In this scenario the game marks regions on the screen as dirty and will only re-draw those regions, so the amount of invalidated regions depend on what is going on inside the simulation, most of the time only a small fraction is invalidated. The current storage is fixed size of 4000 PaintNode elements, originally the storage was static, I now refactored the code to allow multithreading so I made that stack local. I've measured to how much of the total storage is used in average and it is roughly 32% out of 4000. So to make the copy cheap, avoid heap and have pointer stability I was thinking of starting with 1000 or even 500 nodes static and once it exceeds that start to use heap. This is is to why I brought this up wondering if we could need such a specific container, I think I've chosen the wrong name here however.

I don't really require access by index. You are also right that its primarily about pointer stability and being able to start with fixed size storage, so calling it small_segmented_vector is definitely wrong and to support indexed access it would be a bit weird to do, I can absolutely see that now that I'm thinking about the poor choice of container name.

Basically what I'm looking for is something like following:

struct NodeStore
{
   sfl::static_vector<PaintNode, 500> first;
   sfl::segmented_vector<PaintNode, 500> second;

   PaintNode& allocate() {
     if(!first.full()) return first.emplace_back();
     return second.emplace_back();
   }
}

I'm not even sure what one would call such very specific container. One of the benefits of having it like this is to keep memory close together.

Also I think small_list would come close to this assuming the allocator also uses blocks. Ideally the memory is all very close together as its one of the more sensitive areas of the code, however there is the small downside by having overhead by two pointers per element which I don't really need as the element is technically a singly linked list, this is mostly about storage. As you can see its highly specific and I might have jumped the gun a bit too early in opening this discussion.

[slavenf]

Aha, I understand it now. Actually, name small_segmented_vector is not so wrong, but it somehow misleading.

Here is quick and dirty solution for segmented vector. We could create allocator just for your specific purpose:

template <typename T, std::size_t N> // N == segment size
class segmented_vector_allocator_with_static_storage
{
private:

    union 
    { 
        T static_storage_[N]; 
    };

    bool static_storage_is_used_ = false;

public:
    
    using value_type = T;

    T* allocate(size_type n, const void* = nullptr)
    {
        if (n == N && !static_storage_is_used_)
        {
            static_storage_is_used_ = true;
            return static_storage_;
        }
        else
        {
            return static_cast<T*>(::operator new(n * sizeof(T)));
        }
    }

    void deallocate(T* p, size_type)
    {
        if (p == static_storage_)
        {
            assert(static_storage_is_used_);
            static_storage_is_used_ = false;
        }
        else
        {
            ::operator delete(p);
        }
    }
};

// NOTE: operator== and operator!= must be implemented. I think that everything else is ok.

There are few caveats if that allocator is used:

• Move constructor must not be used.
• Move assignment operator must not be used.
• Swap must not be used.

If you really do not need random access, then I suggest using linked list:

• Insertion and removal is O(1).
• Iteration should be fast enough (like iterating std::map/set).
• Iterators, pointers and references are always stable (except for erased elements, of course).

For linked list, it is possible to create allocator with static storage. Allocator would also internally allocates larger chunks of memory (similarly to segmented_vector). The negative is that the same caveats apply to this allocator as for segmented vector allocator above.

Finally, if linked list plays the game, then I could create small_list and pool allocator that internally allocates larger chunks of memory. Using that pool allocator together with small_list you wouldn't have any problems as example above, i.e. you could use move constructor, move assignment operator and swap without issues.

[ZehMatt]

I was thinking about a custom solution using blocks as well but I'm also a lazy developer who like to re-use and not re-invent. Also when I say linked list then I was a bit simplistic, its actually a more of a tree structure since nodes can have children as well but that aside I think I will go with something like my previous example for the time being, the nodes are all POD so there is not really a cost of constructing it in static_vector/segmented_vector and can be used as storage just as is. I could use segmented_vector with the custom allocator as well I guess, I will have to play around with it a bit and see what sticks.

[slavenf]

I am now not sure what are you referring to. When I say to not use move constructor, move assignment operator and swap, I mean to not use those operations on segmented_vector with that allocator, not on elements in container.

Nevertheless, I recommend you try plain segmented_vector with N = 500 and see if there is any bottleneck. I am very convinced there wouldn't be any performance improvements if you had small_segmented_vector with N = 500. 500 is relatively big number and time needed to collect and insert 500 elements into container is probably significantly longer than time needed to allocate one segment for 500 elements, so you wouldn't gain any performance improvements with small_segmented_vector with N = 500.

One more thing, default constructed segmented_vector already has allocated memory for 1st segment. This is intentional to make other parts of container more efficient. Even std::deque is made so.

If you really want to have something like struct NodeStore from your previous post, please put segmented vector in std::optional.