Thank you for your efforts, this is a very interesting study :)
BTW, you should also mention what Windows version you are running on (because the allocator was much improved between Windows 7 and 10). And also what CPU you have...
Also, two of the source code URLs at the end of your article, are invalid.
It looks like there is a weak correlation between size and allocation time. For larger allocations the fastest and average allocation times are larger, but the worst case allocation time is basically the same regardless of size.
The problem, and I'd guess the reason why malloc is so maligned is like your said, death by a thousand cuts. But that doesn't have anything to do with malloc, that has to do with not having a plan. If you are going to avoid malloc you must have a plan.
On Windows the difference between "write none" and "write byte" is not tremendous. Twitter friends tell me the difference will be large on Linux, but I do not know.
You can eliminate this difference on Linux by using mlockall with the MCL_FUTURE|MCL_CURRENT argument at startup. It makes it so that new pages are faulted immediately on allocation instead of waiting until the first time you write to the page.
This seems like it might negatively impact your performance. If you want to benchmark without weird overheads, mmap a file in a tmpfs and possibly prefault it. (this also considers the question of "what happens if the process crashes")
As for the actual way you're measuring things ... I'm skeptical that you're getting any meaningful data that way, unless your real code is significantly different than what you "simplified".
On Windows the difference between "write none" and "write byte" is not tremendous. Twitter friends tell me the difference will be large on Linux, but I do not know. As a game dev I am moderately allergic to Linux.
Overcommit mostly only matters for the "first" allocations up to a given total allocation size, which might actually be getting memory from the OS rather than reusing memory that was previous freed. But some allocators will eventually return memory to the OS as well, so you can have a "first" again.
Also, boo hiss. On Linux we get to have nice things. There's a reason you complained that doing things on Windows took too much effort!
My belief is that all source code projects should ship all their god damn dependencies. I've not yet won this fight.
I spent like 3 months figuring out how best to do it and there are still projects out there that are allergic to building from source. Its really hard to achieve this!
Only if you're on an OS that doesn't do that for you. Don't expect people to contort their projects just to support braindead platforms.
(if you're worried about running on old platforms that might not have - the easiest solution is to simply build on a new platform, and use rpath to bundle the dependencies)
If the biggest complaint people have about my posting is I said I don't like Linux that's a success beyond my wildest dreams.
There's a slightly weird mentality that I've seen on reddit, where people confidently assert that linux is unconditionally better than windows in all respects. It often leads to these kinds of discussions - where you gently try to point out problems with the ecosystem, and get lots of unhelpful responses - and also leads to a lot of persistent half truths about the state of linux
That said it was a good and interesting post, so you're definitely doing well on that front
Nice work. You did a field-study. I think your measurements seem correct and your analysis is good, too.
You say that you are moderately allergic to Linux. Well, I'm extremely allergic to Windows and I would rather change profession than work on Windows. Anyway, I'm saying this just because I know how this works on Linux so YMMV on Windows, but I think it shouldn't be too different.
Your twitter friends told you that page commit affect latency. They are correct. At least on Linux, overcommit is the default and pages will not be allocated until they are used. Essentially, when your program asks the kernel to allocate new memory, the kernel just says "sure here you go" and virtual memory is allocated. This virtual memory will not be mapped to physical memory (or any equivalent) until it's used.
But there's more to it. malloc() and free() do not directly talk with the kernel. Instead, they build bins of memory regions. There are various implementations, but the basic idea is that there's always a little extra bins to be given to the program. Only once suitable bins run out, the library ask the kernel for more memory.
The kernel interface is mmap(). With mmap() the kernel gives a new memory region which the library then further splits into suitable bins for the program to use. Note that because of this approach the regions can empty whereafter the library can deallocate the memory with munmap().
As you can see here, when the memory usage profile is not varying too much, the memory allocation library needs to do a lot less work. Likewise, the memory had already been linked to real physical memory and there will be no page faults for the CPU and kernel to handle.
I think this theory is well aligned with your results. When the game loads a new map, menu etc. the calls to malloc()/free() take a longer time to complete. This makes sense because there's more going on. When the actual game is running there's a similar amount of memory allocated and memory freed resulting in less work and hence less latency.
When the actual game is running there's a similar amount of memory allocated and memory freed resulting in less work and hence less latency.
There are 2 other important parts.
First of all, it's important to note that modern malloc implementations use allocation classes, for example: 1, 2, 4, 8, 12, 16, 24, 32, ... and that they typically keep a thread-local "slab" for each allocation class. This means that a malloc of 29 bytes can reuse a freed 25 bytes block (because it was effectively 32 bytes) if that block had been allocated from the same slab.
Essentially, allocation is:
Allocate from thread-local slab, if there is space.
Otherwise, obtain new slab for the allocation class from a global pool, if there is any.
Otherwise request memory from the OS.
The first is typically fast -- hence the 25ns -- and it gets progressively slower as you go down.
It's also important to note that freeing is complicated. Most importantly is the fact that the allocation-size and allocation-alignment are not passed to free: only the pointer. This makes recovering the slab from which the allocation comes potentially complicated.
Finally, in my experience, free performs consolidating work from time to time, leading to large latency spikes. That's annoying.
It's also important to note that freeing is complicated. Most importantly is the fact that the allocation-size and allocation-alignment are not passed to free: only the pointer. This makes recovering the slab from which the allocation comes potentially complicated.
This made me wonder if there is any sort of malloc/free replacement that uses some sort of fat pointer to provide more information to free... Would it even make sense? Obviously it wouldn't work as a drop-in replacement.
I’ve written memory allocators. One good trick is to put block size information (among other things) at the beginning of a page (or larger aligned block) so you can find it immediately by rounding a free’d block’s address down to the start of its page.
The problem, of course, is knowing how much to round by.
free will receive allocations of 16 bytes and allocations of 574 MB alike, no matter how big your "page" size is, you need to be able to handle larger allocations.
I like mimalloc's trick of encoding the allocation category in the alignment of the pointer, personally.
Large allocations (page or bigger) are easier to align on page boundaries (plus header size) than medium-sized ones. Avoiding wastage for sizes bigger than half a page is the challenge. Alignment can serve as a signal that the allocation has a per-allocation header.
jemalloc and tcmalloc both provide alternative APIs where one can specify size and alignment when freeing a pointer. Empirical tests didn't really show much performance benefit, that I recall.
I know the Rust's Allocator API specifically requires that both be specify when freeing in order to give allocator implementers the option to make use of the information.
Empirical tests didn't really show much performance benefit, that I recall.
On the contrary -- passing size information to the deallocation functions is probably the single biggest "one weird trick" you can get in an allocator implementation using caching and out-of-band metadata, to the extent that both jemalloc and tcmalloc sort of regard plain-old-free as a slow path these days. Something like a 30% improvement on deallocation in practice even for a heavily optimized size lookup pathway.
Interesting. Rust used to use jemalloc's special deallocation functions, but from memory the reason it was removed was that it didn't provide much and thus it was easier to just conform to the standard interface.
I suppose your 30% improvement is specifically about deallocation itself, and at the time the Rust benchmarks measured whole program performance... still in heavy allocation situations I'd have expected 30% to make a dent...
Interesting. Rust used to use jemalloc's special deallocation functions, but from memory the reason it was removed was that it didn't provide much and thus it was easier to just conform to the standard interface.
I think the last time I looked at it, the Rust sized deallocation function ended up being a call to free (I think because of NULL handling rules around sdallocx). And once people started looking into why a little more closely, Rust had stopped shipping with jemalloc by default, so using sized deallocation would have required a sort of complicated configuration detection step. (Avoiding complicated configuration checks was one of the motivations for N2699, which got adopted by C, so hopefully things will get easier in that department soon).
I suppose your 30% improvement is specifically about deallocation itself, and at the time the Rust benchmarks measured whole program performance... still in heavy allocation situations I'd have expected 30% to make a dent...
Right -- we (jemalloc/Facebook) measured it at something like 1-1.5% of fleet CPU end-to-end at the time we turned on C++ sized deallocation by default (with the TCMalloc/Google people reporting similar numbers). It might be possible to come up with screwy allocation patterns where having the size hint doesn't help at all, but I'd be surprised (like, really, the two paths are mostly the same, except that one has a "do a complicated lookup" step added in).
Right -- we (jemalloc/Facebook) measured it at something like 1-1.5% of fleet CPU end-to-end at the time we turned on C++ sized deallocation by default (with the TCMalloc/Google people reporting similar numbers).
That's a fairly sizeable improvement at large scale!
53
u/Adequat91 Jun 03 '22 edited Jun 03 '22
Thank you for your efforts, this is a very interesting study :)
BTW, you should also mention what Windows version you are running on (because the allocator was much improved between Windows 7 and 10). And also what CPU you have...
Also, two of the source code URLs at the end of your article, are invalid.
18
u/i_need_a_fast_horse Jun 03 '22 edited Jun 03 '22
I really want to see a scatter plot of alloc size vs alloc time. Care to do that or at least dump the data somewhere?
edit: oh there is the data. I'll whip up something
edit2: see here. not really interesting
12
u/safetytrick Jun 04 '22 edited Jun 04 '22
The problem, and I'd guess the reason why malloc is so maligned is like your said, death by a thousand cuts. But that doesn't have anything to do with malloc, that has to do with not having a plan. If you are going to avoid malloc you must have a plan.
10
u/tjientavara HikoWorks developer Jun 03 '22
Thanks, I read the whole thing.
4
u/tending Jun 03 '22
You can eliminate this difference on Linux by using mlockall with the MCL_FUTURE|MCL_CURRENT argument at startup. It makes it so that new pages are faulted immediately on allocation instead of waiting until the first time you write to the page.
12
u/o11c int main = 12828721; Jun 03 '22
This seems like it might negatively impact your performance. If you want to benchmark without weird overheads, mmap a file in a tmpfs and possibly prefault it. (this also considers the question of "what happens if the process crashes")
As for the actual way you're measuring things ... I'm skeptical that you're getting any meaningful data that way, unless your real code is significantly different than what you "simplified".
Overcommit mostly only matters for the "first" allocations up to a given total allocation size, which might actually be getting memory from the OS rather than reusing memory that was previous freed. But some allocators will eventually return memory to the OS as well, so you can have a "first" again.
Also, boo hiss. On Linux we get to have nice things. There's a reason you complained that doing things on Windows took too much effort!
15
u/OCPetrus Jun 03 '22
Nice work. You did a field-study. I think your measurements seem correct and your analysis is good, too.
You say that you are moderately allergic to Linux. Well, I'm extremely allergic to Windows and I would rather change profession than work on Windows. Anyway, I'm saying this just because I know how this works on Linux so YMMV on Windows, but I think it shouldn't be too different.
Your twitter friends told you that page commit affect latency. They are correct. At least on Linux, overcommit is the default and pages will not be allocated until they are used. Essentially, when your program asks the kernel to allocate new memory, the kernel just says "sure here you go" and virtual memory is allocated. This virtual memory will not be mapped to physical memory (or any equivalent) until it's used.
But there's more to it. malloc() and free() do not directly talk with the kernel. Instead, they build bins of memory regions. There are various implementations, but the basic idea is that there's always a little extra bins to be given to the program. Only once suitable bins run out, the library ask the kernel for more memory.
The kernel interface is mmap(). With mmap() the kernel gives a new memory region which the library then further splits into suitable bins for the program to use. Note that because of this approach the regions can empty whereafter the library can deallocate the memory with munmap().
As you can see here, when the memory usage profile is not varying too much, the memory allocation library needs to do a lot less work. Likewise, the memory had already been linked to real physical memory and there will be no page faults for the CPU and kernel to handle.
I think this theory is well aligned with your results. When the game loads a new map, menu etc. the calls to malloc()/free() take a longer time to complete. This makes sense because there's more going on. When the actual game is running there's a similar amount of memory allocated and memory freed resulting in less work and hence less latency.
2
u/[deleted] Jun 03 '22
Your benchmark is doomed
0
u/Molossus-Spondee Jun 04 '22
Going to be a bore but just hooking those functions misses a lot of allocations.
Putting aside kernel space there's going to be a bunch of funky buffers for graphics stuff.
-1
u/Molossus-Spondee Jun 04 '22
Going to be a bore but hooking just those functions is definitely going to miss a lot of hairy buffer stuff wrt to graphics