Comment by o11c
2 days ago
There's another bug, related to performance - this involves a quadratic amount of memory copying unless your environment can arrange for zero-copy.
2 days ago
There's another bug, related to performance - this involves a quadratic amount of memory copying unless your environment can arrange for zero-copy.
Author here. Quite so. See footnote 3:https://educatedguesswork.org/posts/memory-management-1/#fn3
"If you know you're going to be doing a lot of reallocation like this, many people will themselves overallocate, for instance by doubling the size of the buffer every time they are asked for more space than is available, thus reducing the number of times they need to actually reallocate. I've avoided this kind of trickery to keep this example simple."
Surely that's only the case if realloc() actually resizes and copies on every call? Which it normally doesn't?
I thought that most implementations of realloc() would often "round up" internally to a larger size allocation, maybe power-of-two, maybe page size, or something? So if you ask for 20 bytes, the internal bookkeeping sets aside 32, or 4096, or whatever. And then if you realloc to 24 bytes, realloc will just note that the new allocation fits in the amount its reserved for you and return the same buffer again with no copying?
Some implementations might round up to encourage reuse:
* memory-checking allocators never do.
* purely-size-based allocators always do.
* extent-based allocators try to, but this easily fails if you're doing two interleaving allocations.
* the mmap fallback does only if allowing the kernel to choose addresses rather than keeping virtual addresses together, unless you happen to be on a kernel that allows not leaving a hole
Given that there's approximately zero overhead to do it right, just do it right (you don't need to store capacity, just compute it deterministically from the size).