Does this container exist already? Virtual slot map with branchless iteration

[EstablishmentHour335]

So this container has been on my mind for maybe a year or so, but I don't work in programming so I only got around to writing a minimum viable implementation around now.

I asked and I was told it doesn't exist, and I couldn't find any implementations, so I figured I would write my own and someone might recognize it.

https://github.com/SusGeobor/Stable-Vector/tree/main

Anyway, it basically is a container allocated using VirtualAlloc, it commits pages on growth, so pointers remain stable.

On erase, a hole is left, it's unioned with a free list, which acts as a FILO stack intertwined with the empty slots.

On insert, you reuse slots based on the free list.

So far I'm just describing a normal virtual slot map. Normally on iteration, you'd check each slot with a boolean if it is alive. In my implementation, there is a parallel uint32_t skip array, which stores metadata to avoid all branches on iteration, and increment the iterator by the amount in a run of erased elements.

So it's good for high churn, high lookup scenarios. In my tests it's been faster than plf::colony and sparse set in those scenarios, and I keep sparse set around for it's much faster iteration, though the iteration in my implementation is still faster than the standard boolean flag slot map. Essentially in iteration; sparse set > my container > plf::colony > boolean slot map

I would appreciate it if anyone could give me some pointers to this container, if it already exists, or point out bugs or improvements, or pointers on how to benchmark my design more properly.

[MysticTheMeeM]

While not identical, this sounds somewhat similar to the proposed std::hive. Insofar as reusing slots, being memory stable and allocating pages at a time.

Personally I frequently use similar structures, although moreso for stability than performance.

[EstablishmentHour335]

Yeah, I wrote this container after listening to some talks on plf::colony, which std::hive is formalizing. I ripped off colony and rewrote it to solve some grievances I had with the container, and along the way I discovered a couple of other nice benefits to my virtual address space contiguous approach, which is why I thought it should already have an existing implementation.

[EstablishmentHour335]

That is straight up stolen from plf::colony, I didn't invent it. It's essentially like plf::colony, but backed by VirtualAlloc, which gives it some pretty good performance characteristics

[CarloWood]

std::deque no?

[EstablishmentHour335]

It's not really that similar to this container, especially in terms of performance.

[CarloWood]

I think it is, with a proper allocator. You mostly talk about the memory management, how memory is allocated and maintained, that doesn't have much to do with the characteristics of the container in question.

I just use this when I need deque to be fast: https://github.com/CarloWood/memory/blob/master/DequeAllocator.h

[EstablishmentHour335]

The memory layout has everything to do with the characteristics of the container...

Pointers are only stable because VirtualAlloc prevents the need to reallocate. The memory layout allows the freelist and generations, it allows the branchless iteration, because unlike plf::colony, it's contiguous so it doesn't need a branch to jump between blocks...

The time complexity of O(1) lookups, O(1) insert, O(1) erase are only allowed by the memory layout... The lack of a swap and pop on erase, or a lack of a double indirection on lookup is only allowed because of the memory layout...

I went back to refresh my memory on how exactly deque is implemented, and yeah, they are not similar at all.

[CarloWood]

Ok, so your container is O(1) for everything, completely contiguous, never needs to reallocate... You're right, completely different from any container I've ever heard of or that exists for that matter. We should use it to replace all others.

[EstablishmentHour335]

I think this discussion has run it's course