A Fast, Growable Array with Stable Pointers in C

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).

[ Parent | on HN ]

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.

[ Parent | on HN ]

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.

[ Parent | on HN ]

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!

[ Parent | on HN ]

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.

[ Parent | on HN ]