[faragon]

A good point for both RB trees and linear-addressing hash tables is that they can be implemented with vectors( [1], [2]), allowing the case of initial reservation for N elements, so with a tricky implementation you could even have the data structure with one or zero allocations (e. g. allocate the tree or the hash table in the stack). For tries you could use many memory pools for the different node sizes, apply path compression, and even a LUT accelerator for reaching the Nth level, but hardly could be implemented using a vector.

[1] https://github.com/faragon/libsrt/blob/master/src/saux/stree...

[2] I'm implementing a key-value hash table that will be added to the same library as [1] with "srt_hmap" type, in one continuous allocation. Being able to use hash tables allocated both in the heap and in the stack (e.g. you could use a int32-int32 hash table allocated in the stack for computing the color frequency of a bitmap image). Being the HT performance 4 to 5x the performance of the RB-trees, including cost of rehashing - rehash implementation using techniques for avoiding moving all the data- (rehashing only available for the heap case).

[jstimpfle]

You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.

[kccqzy]

I tend to use C++'s std::deque as a poor man's arena allocator. I find it works even better than vectors with indices: indeed C++ says pushing at the end will validate iterators but not pointers to the elements themselves. This gets rid of the infrequent resizing in vectors.

[jstimpfle]

I think you have a typo in there, "validate iterators" -> "invalidate iterators".

It should be easy to build a non-invalidating version of the iterator that has a pointer to the chunk and an offset within that chunk. That's more like 12 or 16 bytes, though.

What I like about vectors is that an index is not really about the storage that the vector holds at that position. The index is a mathematical identity of an object. It's the object itself. The vector is only a materialized function that holds some attribute for each object. The nice thing is we can have multiple independent vectors for each object type. This is true modularity.

We can get an address from a simple index with deques, too. But only with significant indirection. So I think if (1) no movement cost on reallocation is allowed, and/or (2) stable pointers are needed, deques are a fine choice. But vectors are my first choice.

Given that we have huge address spaces nowadays we could also consider preallocating large global vectors at stable addresses, and expanding them with mmap(). This way the copying when growing the vector is not needed.

[faragon]

Yes, that's how works the RB-tree example I linked. However, it is much harder doing that for implementing tries, except if you work only with the full node case, which would imply wasting a huge amount of space. At least, from my experience.

[vbezhenar]

You can also use vector of vectors. Reallocating would be cheaper. But access would incur extra indirection.

[saagarjha]

You can consider the entire virtual memory space to be a big vector, where a pointer is just an index into it!

[jstimpfle]

However that's a pretty poor vector. It's not homogeneous (you put things of different shapes inside). That also implies you need sophisticated memory management, leading to further overheads. You cannot meaningfully iterate it.

[saagarjha]

I was mostly joking…

[jstimpfle]

Yes and I'm serious :-)

[photon-torpedo]

Yes, that's exactly how we do it in Fortran 77.