4 ms·
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 tr
by andrewla 1y ago
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.
- hinkley 1y agoI believe I've seen problems like this also solved with arena allocators. You have certain very special allocations have an arena unto themselves.
- stmw 1y agoSame 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.
- benlwalker 1y agoFor 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 1y agoOne 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 1y agoFreeing 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 1y agoThanks 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 1y agoFWIW mremap is very expensive as it involves a TLB shootdown.