Thread

Comparison of Malloc() Algorithms

142 points · 51 comments · egberts1

Loading the complete thread in the background. This saved snapshot is available now. Refresh

benjojo12 · 1789628818 · focus · HN ↗
ERR_SSL_VERSION_OR_CIPHER_MISMATCH on my phone it seems?
1. j4k0bfr · 1789631254 · focus · HN ↗
  Same, from Chrome on Android
2. Rygian · 1789637350 · focus · HN ↗
  TLS_CHACHA20_POLY1305_SHA256 (256 bit keys, TLS 1.3) successfully negotiated here (Firefox esr 140.14.0).
Nnnes · 1789629125 · focus · HN ↗
<a href="https://web.archive.org/web/20260915165314/https://egbert.net/blog/articles/comparison-of-arena-architecture-in-malloc.html" rel="nofollow">https://web.archive.org/web/20260915165314/https://egbert.ne...
Funny SSL setup. Explanation from here <a href="https://news.ycombinator.com/item?id=49133598">https://news.ycombinator.com/item?id=49133598
> Oh, certain browser will not work with this blog if it cannot negotiate ONLY for Cha-Cha/Poly. It's by design as a showcase of why that particular web browser refuses to do that.
I assume the "particular web browser" is Chromium, which won't load it on any OS I've tried. On Windows, Firefox and the built-in curl.exe also refuse to connect.
1. bom-d-van · 1789632270 · focus · HN ↗
  legend.
2. [deleted] · 1789633733 · focus · HN ↗
  [deleted]
3. ncruces · 1789634357 · focus · HN ↗
  Thanks for the link.
  Article makes it look like nothing happened in the embed/low-memory/single-threaded malloc space in decades since Doug Lea's malloc.
  I just implemented TLSF for my minimal Wasm libc: fragmentation is just as good, performance is a lot more consistent and better of average, for a significant reduction in code size.
  <a href="http://www.gii.upv.es/tlsf/index.html" rel="nofollow">http://www.gii.upv.es/tlsf/index.html
  <a href="https://github.com/ncruces/wasm2go/blob/main/libc-gen/c/malloc_tlsf.c" rel="nofollow">https://github.com/ncruces/wasm2go/blob/main/libc-gen/c/mall...
  1. egberts1 · 1789644949 · focus · HN ↗
    [delayed]
  2. thomasmg · 1789660229 · focus · HN ↗
    Interesting! I have also implemented a versionn of TLSF for my (currently single-threaded) programming language. I also found it to be good for my use case (embedded / minimal code size). I'll compare it against yours. One improvement I did is some kind of preallocation for small blocks. <a href="https://github.com/thomasmueller/bau-lang/blob/main/src/main/java/org/bau/parser/StandardLib.java#L9" rel="nofollow">https://github.com/thomasmueller/bau-lang/blob/main/src/main...
4. egberts1 · 1789646164 · focus · HN ↗
  [delayed]
5. quietbritishjim · 1789650468 · focus · HN ↗
  Firefox on Windows user here, and it loads the blog fine. I don't have Chrome installed but Edge (which is Chromium engine based) doesn't load it.
6. dark-star · 1789715840 · focus · HN ↗
  I don't get what this is supposed to prove. That my browser doesn't allow websites to declare what encryption they use? I am pretty sure there's a point to all of this, but please let me (and my browser) choose which encryptions I want to trust.
  Is this a spec violation or something?
  1. gspr · 1789757849 · focus · HN ↗
    Isn't the idea that the server and client should agree on a common subset? Here, the server's subset is very small, but not esoteric – so then surely it's the client that's lacking in features?
    egberts1 · 1789845755 · focus · HN ↗
    [delayed]
    dark-star · 1789847604 · focus · HN ↗
    Yeah but I don't want Chachacha, I prefer AES. If you can't do AES, I'm not interested in the website :)
ligarota · 1789632871 · focus · HN ↗
Please write a "how to setup SSL" article
1. eqvinox · 1789635020 · focus · HN ↗
  It seems to be intentional & if somebody wants to make a statement about TLS with their personal website that's their choice to make and execute.
  1. entrope · 1789641369 · focus · HN ↗
    On the bright side, lots of people will be saved from reading bad prose like "Malloc (libc) is the worst memory allocation API to use" and "Programs should avoid, if possible, allocating/deallocating memory too often". (By definition, "too often" means it can possibly be avoided, and usually that it can practically be avoided.)
    0c3ca83 · 1789655304 · focus · HN ↗
    Beats the hell out of most of the LLM-generated "honest assesments" of things on this site.
    dezsiszabi · 1789662257 · focus · HN ↗
    I might be stupid, but what's wrong with those sentences?
    entrope · 1789720175 · focus · HN ↗
    The first one was offered with no explanation and no claimed better alternative. malloc() is probably the simplest interface for generic runtime allocation, and simplicity has a lot in its favor. malloc() does not provide type safety, is susceptible to external fragmentation, and makes it harder to meet the performance goals outlined in the rest of the blog post. So malloc() reflects trade-offs, but saying that the standard API "is the worst memory allocation API to use" should be supported, even if briefly, instead of simply asserted: meeting the goals I listed inflicts other drawbacks, like needing to create and manage separate heaps.
    I thought my explanation for the second one was already clear: "Programs should avoid, if possible, [doing X] too often" is a truism because "too often" implies that some reduction is possible. One should leave out the ", if possible," -- although deciding what is "too often" can be challenging and sometimes a matter of taste. (Is reducing allocation frequency by 5% worth doubling the CPU usage or memory usage or code complexity? Maybe in some cases, but often not.)
  2. egberts1 · 1789643791 · focus · HN ↗
    Yes
2. egberts1 · 1789643769 · focus · HN ↗
  No
Someone · 1789634591 · focus · HN ↗
Not a good article, IMO.
FTA: “When multiple threads simultaneously allocate or deallocate memory from the allocator, the allocator will serialize them. Programs making intensive use of the allocator actually slow down as the number of processors increases.”
The article does later retract on that, but that’s no reason to lead with such a blatantly false (with current allocators) statement.
Also FTA “In 2006, a third pool was introduced (after operating system memory pool and library-based memory pool) called the “arena”. Arena is a jemalloc-term”
Jemalloc is from around 2005 (<a href="http://jemalloc.net/" rel="nofollow">http://jemalloc.net/), the idea of arenas is from the 1960s, and Wikipedia claims the term was coined in 1990 (<a href="https://en.wikipedia.org/wiki/Region-based_memory_management#History_and_concepts" rel="nofollow">https://en.wikipedia.org/wiki/Region-based_memory_management...), and the linked paper (<a href="https://www.cs.princeton.edu/techreports/1988/191.pdf" rel="nofollow">https://www.cs.princeton.edu/techreports/1988/191.pdf) is from 1988.
Then, a typo: “as well as memory tied to specific to each of the multiple CPU core or even CPU infinity.”
“Infinity” should be “affinity” there.
1. eqvinox · 1789635154 · focus · HN ↗
  The tables look mostly correct, and that's what I'll be bookmarking this for… I don't think I've seen any elsewhere that are this extensive (in both axis).
  1. egberts1 · 1789644646 · focus · HN ↗
    [delayed]
2. skavi · 1789641521 · focus · HN ↗
  yup and the characterization of each allocator is so fuzzy, with zero methodology provided.
  allocators are so simple to just swap into your program. if you can put together a few representative workloads, you should just try out a few allocators and profile whatever metrics you care about.
  1. imp0cat · 1789645118 · focus · HN ↗
    And finally end up with either jemalloc or possibly mimalloc. ;)
    egberts1 · 1789646296 · focus · HN ↗
    Invariably so but I'm mulling over malloc()s on embedded topic now.
    skavi · 1789651558 · focus · HN ↗
    we actually ended up with (new) tcmalloc.
    for us, tc was among the fastest in runtime while being very space efficient [0]. large rust application using far too many threads.
    we’ve since also had great success with tc’s built in profiling tools.
    [0]: <a href="https://news.ycombinator.com/item?id=47403847">https://news.ycombinator.com/item?id=47403847
    imp0cat · 1789713502 · focus · HN ↗
    Interesting, is there an accompanying article?
    We've tried tcmalloc, too. I don't remember the exact details, but we basically ended using jemalloc because it was using way less memory.
    Same story with mimalloc - it usually provided a tiny bit more speed, but required more cpu and memory.
    skavi · 1789729267 · focus · HN ↗
    no article, sorry, grabbed the numbers from an old PR.
    to confirm, you were using tcmalloc from <a href="https://github.com/google/tcmalloc" rel="nofollow">https://github.com/google/tcmalloc and not from <a href="https://github.com/gperftools/gperftools" rel="nofollow">https://github.com/gperftools/gperftools, right?
    the latter is a lot worse iiuc.
    imp0cat · 1789734812 · focus · HN ↗
    Good point. It was from the <a href="https://packages.debian.org/trixie/google-perftools" rel="nofollow">https://packages.debian.org/trixie/google-perftools Debian package, which points to the gperftools project - so it was the worse one I guess.
    skavi · 1789753285 · focus · HN ↗
    yeah that’s a common mistake when evaluating tcmalloc. gperftools tcmalloc diverged quite a while ago. doesn’t have a lot of the fancier features of modern tcmalloc [0].
    [0]: <a href="https://github.com/google/tcmalloc/blob/master/docs/gperftools.md" rel="nofollow">https://github.com/google/tcmalloc/blob/master/docs/gperftoo...
  2. zX41ZdbW · 1789647810 · focus · HN ↗
    ClickHouse has been tested with jemalloc, mimalloc, tcmalloc (both variants), rpmalloc, lfalloc, hualloc, and ended up using jemalloc after a few patches and bug fixes.
    egberts1 · 1789651610 · focus · HN ↗
    [delayed]
    zX41ZdbW · 1789786587 · focus · HN ↗
    lfalloc: <a href="https://github.com/ClickHouse/ClickHouse/pull/62826" rel="nofollow">https://github.com/ClickHouse/ClickHouse/pull/62826 hualloc: <a href="https://github.com/ClickHouse/ClickHouse/pull/31376" rel="nofollow">https://github.com/ClickHouse/ClickHouse/pull/31376
    egberts1 · 1789845796 · focus · HN ↗
    [delayed]
    skavi · 1789651693 · focus · HN ↗
    a while back, our tests led us to tcmalloc (new).
    <a href="https://news.ycombinator.com/item?id=47403847">https://news.ycombinator.com/item?id=47403847
3. egberts1 · 1789644710 · focus · HN ↗
  [delayed]
4. adrian_b · 1789650132 · focus · HN ↗
  Yes, I do not know what this paragraph wants to say:
  > "The first memory allocation scheme started with a stack-based memory allocation. Next came the dynamic-based memory allocation scheme where linked-list and bucket-heap mechanism are used to divide the private-heap using size class approach. Soon, garbage collection algorithm introduced the initial backend of the memory allocation scheme."
  Since no specific operating system is mentioned, these sentences appear to refer to the general history of dynamic memory allocation, in which case they are wrong.
  "malloc" is a late comer in this history. It has appeared as the statement "ALLOCATE", together with the statement "FREE", in the programming language PL/I of IBM, by the end of 1964.
  At that time many other techniques of managing memory had already been used for a few years.
  Dynamic allocation of memory has started with allocation without ever freeing the allocated memory before the termination of the process.
  Then, in 1960, 3 methods of handling dynamic memory allocation were published: the use of garbage collectors in April (John McCarthy), the use of stacks in May (E. W. Dijkstra), and the use of reference counts in December (George E. Collins @ IBM).
  So the use of garbage collectors is actually the oldest published method for handling dynamic memory allocation, not a newer method.
  1. egberts1 · 1789658843 · focus · HN ↗
    [delayed]
    adrian_b · 1789665129 · focus · HN ↗
    To help you with the citations:
    Garbage collectors: "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", John McCarthy, Communications of the ACM, pp. 184-195, 1960-04.
    Stacks and stack pointers: "Recursive Programming", Edsger Wybe Dijkstra, 1960-05-11.
    Reference counts for memory allocation were introduced in "A Method for Overlapping and Erasure of Lists", George E. Collins (IBM), Communications of the ACM, Volume 3, Issue 12, 1960-12, pp. 655–657.
    egberts1 · 1789682231 · focus · HN ↗
    [delayed]
AnimalMuppet · 1789648920 · focus · HN ↗
Couldn't read the article (ERR_SSL_VERSION_OR_CIPHER_MISMATCH, Chrome on Windows). But I'm remembering something a coworker told me some time around... 1991 to 1993, maybe? Forgive me if I repeat some of what the article says - I did try to read it!
While he was at the university, they were experimenting with different kind of mallocs. One was called the "buddy" malloc. It kept a list of free blocks of various sizes, and when you asked for a block and it didn't have one, it asked the OS for twice as much as you asked for. From the rest, it made another block (identical to yours, called the "buddy" block), and put it on the free list of that size.
Well, they experimented with a similar algorithm, but the idea was that most requests were small. So it took the buddy block and broke it into smaller pieces, one half the size of the request, one a quarter the size, and so on, and put those on their respective free lists. They called this the "donner" malloc, because you carved up your buddy.
From the way my coworker smiled, I think he thought it was amusing, but I don't think he was making it up.
1. egberts1 · 1789650656 · focus · HN ↗
  D. S. Hirschberg, A Class of Dynamic Memory Allocation, CACM 16(10) 1973 covered this variants of halving Buddy Allocator.
brcmthrowaway · 1789665274 · focus · HN ↗
What malloc does macOS use in userspace? How about kernel?
1. egberts1 · 1789682703 · focus · HN ↗
  [delayed]
  1. ddcc7 · 1789729527 · focus · HN ↗
    NanoV2 was only used for smaller size classes. The current allocator is xzone malloc: <a href="https://github.com/apple-oss-distributions/libmalloc/blob/main/doc/xzone_malloc.md" rel="nofollow">https://github.com/apple-oss-distributions/libmalloc/blob/ma...
    egberts1 · 1789741274 · focus · HN ↗
    [delayed]
D2OQZG8l5BI1S06 · 1789687270 · focus · HN ↗
Every time I tried to replace the allocator in an app, the speedup was negligible.
1. egberts1 · 1789845942 · focus · HN ↗
  [delayed]

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.