Re:A Fast, Growable Array with Stable Pointers in C
by stmw on Wednesday August 06, 2025 @07:56PM
(#44819232)
Same re: virtual memory systems (using guard pages), that is an old idea that works well but it did once produce a really unpleasant bug in production... But that was an unfortunate implementation mishap.
Re:A Fast, Growable Array with Stable Pointers in C
by hinkley on Wednesday August 06, 2025 @06:16PM
(#44818505)
I believe I've seen problems like this also solved with arena allocators. You have certain very special allocations have an arena unto themselves.
Re:A Fast, Growable Array with Stable Pointers in C
by benlwalker on Wednesday August 06, 2025 @09:14PM
(#44819621)
For an expanding array in a 64 bit address space, reserving a big region and mmaping it in as you go is usually the top performing solution by a wide margin. At least on Linux, it is faster to speculatively mmap ahead with MAP_POPULATE rather than relying on page faults, too.
And, if you find you didn't reserve enough address space, Linux has mremap() which can grow the reserved region. Or map the region to two places at once (the original place and a new, larger place).
Re:A Fast, Growable Array with Stable Pointers in C
by OptionOfT on Wednesday August 06, 2025 @10:59PM
(#44820118)
One place I had issues was rapidly allocating space I needed temporarily but then discarding it.
The space I needed was too large to be added to the heap, so I used mmap. Because of the nature of the processing (mmap, process, yeet mmap) I put the system under a lot of pressure. Maintaining the set of mapped blocks and reusing them around fixed the issue.
Re:A Fast, Growable Array with Stable Pointers in C
by vlovich123 on Wednesday August 06, 2025 @11:01PM
(#44820143)
Freeing memory to the OS or doing things like munmap involves a TLB shootdown which by definition is a performance bottleneck. Probably what you ended up experiencing.
Re:A Fast, Growable Array with Stable Pointers in C
by OptionOfT on Friday August 08, 2025 @10:56AM
(#44837771)
Thanks for that. That was an interesting read!
I ended up in this situation like I end up in most, by just learning as I go.
With this I learned that the libc allocator has a max amount that it'll add to the heap, and how mmap works, and that doing frequent munmap is slow.
Now I learned why it is slow!
Re:A Fast, Growable Array with Stable Pointers in C
by vlovich123 on Wednesday August 06, 2025 @11:00PM
(#44820137)
FWIW mremap is very expensive as it involves a TLB shootdown.
In the past I've abused virtual memory systems to block off a bunch of pages after my array. This lets you use an array data structure, have guard pages to prevent out of bounds access, and to have stable pointers in the data structure.