This is really clever but better to call this a list rather than an array; functions which expect array semantics will simply not work, and there's no way to transparently pass slices of this data structure around.

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.

▲

benlwalker 4 days ago | parent | next [-]

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

▲

OptionOfT 3 days ago | parent | next [-]

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.

▲

vlovich123 3 days ago | parent [-]

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.

	▲	OptionOfT 2 days ago \| parent [-]
		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!

▲

vlovich123 3 days ago | parent | prev [-]

FWIW mremap is very expensive as it involves a TLB shootdown.

▲

stmw 4 days ago | parent | prev | next [-]

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.

▲

hinkley 4 days ago | parent | prev [-]

I believe I've seen problems like this also solved with arena allocators. You have certain very special allocations have an arena unto themselves.