3 ms·

CPython and Go's allocators are already faster than simple heap allocation using malloc/free. CPython has a specialized arena allocator for small allocations c

CPython and Go's allocators are already faster than simple heap allocation using malloc/free. CPython has a specialized arena allocator for small allocations called obmalloc. Go's allocator is descended from tcmalloc but faster because it doesn't need to support the free(1) api and all the book-keeping required.

littlestymaar 6y ago
You're missing the point here: modifying tcmalloc can give you percentage point improvement, but a copying collector can speed up the allocation by orders of magnitude (the allocation is done in a contiguous memory space, every object adjacent to each other and allicating just becomes a few asm instructions, like 5 or something). It's like comparing speed of a bike vs airplane: the brand and the quality of the bike doesn't really matter…
- jashmatthews 6y ago
  People repeat this a lot but it's not entirely true and it's not even close to 10x faster. More like 10%. Freelist based allocation is actually very nearly as fast as bump pointer allocation. Like 10% if you compare the allocation function in isolation and 1% if you benchmark the whole object allocation path. http://users.cecs.anu.edu.au/~steveb/pubs/papers/mmtk-sigmetrics-2004.pdf http://users.cecs.anu.edu.au/~steveb/pubs/papers/mmtk-sigmet... Some older malloc implementations like Hoard have bump pointer allocation into empty pages but the newest allocator impementations found that the branch prediction cost of having both paths outweighed the benefits https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf https://www.microsoft.com/en-us/research/uploads/prod/2019/0...
  - littlestymaar 6y ago
    Reading PDF on mobile is annoying so I can't comment on the content of your first link, but your claim that a bump allocator is no more than 10% faster than a free-list-based one is really suspicious: - first, as you said, people repeat the opposite a lot, including world class GC experts. - then, unless I'm missing something, that claim sounds equivalent to claiming than heap allocation is no more than 10% more expensive than stack allocation, which is arguably completely false.
    - jashmatthews 6y ago
      That’s why I linked the paper from JVM GC researchers with the direct quote on freelist vs bump pointer „Finding the right fit is about 10% slower [13] than bump- pointer allocation.”

littlestymaar 6y ago

You're missing the point here: modifying tcmalloc can give you percentage point improvement, but a copying collector can speed up the allocation by orders of magnitude (the allocation is done in a contiguous memory space, every object adjacent to each other and allicating just becomes a few asm instructions, like 5 or something). It's like comparing speed of a bike vs airplane: the brand and the quality of the bike doesn't really matter…

jashmatthews 6y ago
People repeat this a lot but it's not entirely true and it's not even close to 10x faster. More like 10%. Freelist based allocation is actually very nearly as fast as bump pointer allocation. Like 10% if you compare the allocation function in isolation and 1% if you benchmark the whole object allocation path. http://users.cecs.anu.edu.au/~steveb/pubs/papers/mmtk-sigmetrics-2004.pdf http://users.cecs.anu.edu.au/~steveb/pubs/papers/mmtk-sigmet... Some older malloc implementations like Hoard have bump pointer allocation into empty pages but the newest allocator impementations found that the branch prediction cost of having both paths outweighed the benefits https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf https://www.microsoft.com/en-us/research/uploads/prod/2019/0...
- littlestymaar 6y ago
  Reading PDF on mobile is annoying so I can't comment on the content of your first link, but your claim that a bump allocator is no more than 10% faster than a free-list-based one is really suspicious: - first, as you said, people repeat the opposite a lot, including world class GC experts. - then, unless I'm missing something, that claim sounds equivalent to claiming than heap allocation is no more than 10% more expensive than stack allocation, which is arguably completely false.
  - jashmatthews 6y ago
    That’s why I linked the paper from JVM GC researchers with the direct quote on freelist vs bump pointer „Finding the right fit is about 10% slower [13] than bump- pointer allocation.”