[Rendello]

> Vectors (in C++) at least aren't necessarily the best fit either

I'm not sure if you use a different allocation strategy or if you're advocating allocating as much as possible up-front, but I'm curious if you have any thoughts on this:

I always end up using (Rust) vectors despite looking at a bunch of slab/arena allocation libraries. Preferably I'd know how much memory I need up front, but barring that I see three options for any allocation that needs to grow:

- Fail;

- Reallocate; or

- Put the overflow in a new allocation, keeping track of where all the "pages" are internally.

In 2, you can't use references/slices (anything with a pointer) because the potential reallocation invalidates those. In 3, it seems ideal because references can stay stable, but you wouldn't be able to have any array-like data cross the "page" barrier as the pointer jump would not be stable. (Although, am I correct in thinking the OS does something like this, and that's why pointer addresses are virtual?).

So, you can't really internally reference data in this sort of context by reference/pointer, it's preferable to use an integer index. In that case, what's the point of the allocator libraries at all? Your standard Vector would have the same reallocation/access characteristics, and you can set a reasonable initial capacity to try and avoid reallocations.

[speedstyle]

To your virtual memory comment, the kernel can only do as it's told, but allocators can indeed tell it to shuffle pages around in virtual memory. On Linux that's `mremap` [0], and `realloc` implementations [1] use it for large enough Vecs (apparently 128kiB for glibc and musl). macOS' libmalloc will try to map new pages that extend large allocations in-place, but memcpy elsewhere if existing virtual mappings are in the way. I don't think Windows' HeapReAlloc does either, but they might reserve a larger virtual region and incrementally commit it or something to similar effect.

[0] https://man7.org/linux/man-pages/man2/mremap.2.html

[1] https://git.musl-libc.org/cgit/musl/tree/src/malloc/mallocng...

[loup-vaillant]

A fourth alternative, in 64-bit systems, is to reserve a stupidly large chunk of memory up front with `mmap()` or equivalent (`malloc()` actually should work about as well). That way you guarantee that any extension will happen in place. There’s a limit to how much you can reserve, but since that limit is much higher than what you can actually use, you can make quite a few of those reservation before you run out of address space.

It feels dirty, but when your system has overcommit you can’t reliably check that the memory you want is actually there anyway, so you might as well reap the benefits.

[Rendello]

In Rust at least, most things have a with_capacity(n) constructor to ensure there's space for n elements (or n bytes, in the case of strings). I suppose there's no getting around the fact that if your collection has no known bounds, you'll have to do bounds checking + potential reallocation in the hot (push) path or risk having your program SIGSEGV.

https://doc.rust-lang.org/std/?search=with_capacity

[loup-vaillant]

You can kinda do this in C++ too with `std::vector::reserve()`. The thing is if my collection has no known bounds, well, maybe this time it requires 64GB of space? Except RAM is at a premium and I only have 16GB right now, and no swap space to speak of. What am I gonna do?

The problem with overcommit, is that there is no reliable way to know in advance how much memory your program can actually use. That system with 16GB of RAM will allow you to "allocate" 128GB of memory. Just try it, call `malloc()` or the `with_capacity()` constructor, it will return a valid pointer or container. Try to write in that giant "buffer" at the beginning, at the end, somewhere in the middle at random… it will still work. Everything works exactly as if you really had a giant 128GB buffer, that you can write to and read back from…

…Until you hit somewhere below 5M different pages, where instead of getting a new page after the page fault, you get killed by the out of memory killer. With SIGTERM if you have the relevant privilege, so you have at least a chance of exiting cleanly, but user programs just get SIGKILL. No appeal, no way to check.

Well there is a way to check, kinda: allocate a fixed amount of memory up front, hit all the pages, and if your program didn't crash, it really has the amount of memory you just gave it. Then perform all your allocations within this real buffer you really have (this means a custom allocator). Any allocation success will be real, and bounds checks will actually work. It just doesn't play well with programs whose actual memory needs are highly unpredictable: most of the time you'll use much more memory than you need, and sometimes you won't have enough, forcing you to raise the threshold.

[inigyou]

In 32-bit systems too, but the limits are lower.

Windows is cleaner, as it lets you reserve address space and then later commit it. The Linux equivalent to reserve is probably mapping with no permissions. Overcommit can be disabled on Linux and doesn't break control flow integrity or valgrind, so I know there is a way.

[Matumio]

The main reason for virtual addresses/TLB is to prevent processes from accessing each other's memory (isolation). For optimization I'd say the page size (64 kB) is a secondary concern. It's handled in hardware (TLB) with the OS only occasionally filling up the mapping. You want to avoid that happening, but you probably should worry more using whole cache lines (64 bytes) instead, and beyond that just keep memory access local (multiple cache hierarchies) and predictable (pre-fetcher).