4 ms·
That's the absolute best case for the simplest malloc implementation possible. In the real world, a malloc can involve picking an appropriate zone/arena based
by joosters 6y ago
That's the absolute best case for the simplest malloc implementation possible.
In the real world, a malloc can involve picking an appropriate zone/arena based upon allocation size & the current thread, obtaining locks, chasing some pointers through its data structures, doing some book-keeping, perhaps even calling up to the OS to increase the process space.
Maybe in the very best case it can just shuffle a couple of pointers, but over time it has to do a lot more than that.
- kragen 6y agoWell, chrisseaton did say amortised, not worst-case. He wasn't talking about malloc, which is a C function that indeed cannot be that fast, but about a modern language implementation. Results from some trivial benchmarks are in my comments at https://news.ycombinator.com/item?id=26438596 https://news.ycombinator.com/item?id=26438596 and https://news.ycombinator.com/item?id=26449902 https://news.ycombinator.com/item?id=26449902. You can reason it out from first principles, though. Picking the right arena is done at compile time, and you don't obtain locks or chase pointers on the open-coded fast path. Maybe once every 1024 allocations you have to do all that jazz, which costs you another 128 instructions, 0.125 instructions per allocation. And maybe once very 1024 times you do that, you need to call up to the OS to increase the process space at a cost of about 4096 instructions or so, 0.004 instructions per allocation. So the allocation fast path dominates your amortized allocation performance, even though the cases you're talking about are what dominate your worst-case performance.