3 ms·

Not a good article, IMO. FTA: “When multiple threads simultaneously allocate or deallocate memory from the allocator, the allocator will serialize them. Progra

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 (http://jemalloc.net/ http://jemalloc.net/), the idea of arenas is from the 1960s, and Wikipedia claims the term was coined in 1990 (https://en.wikipedia.org/wiki/Region-based_memory_management#History_and_concepts https://en.wikipedia.org/wiki/Region-based_memory_management...), and the linked paper (https://www.cs.princeton.edu/techreports/1988/191.pdf 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.

eqvinox 9d ago
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, total allocators covered & details per allocator).
- egberts1 9d ago
  Thank you. I got tired of reading AI prose so I compiled and wrote it from my collections of others' whitepapers. As a "For Reference Only", at the very least, for me. As usual, anyone is welcome to improve upon it under CC BY-NC-SA.
skavi 9d ago
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.
- imp0cat 9d ago
  And finally end up with either jemalloc or possibly mimalloc. ;)
  - egberts1 9d ago
    Invariably so but I'm mulling over malloc()s on embedded topic now.
  - skavi 9d ago
    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]: https://news.ycombinator.com/item?id=47403847 https://news.ycombinator.com/item?id=47403847
    - imp0cat 8d ago
      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 8d ago
        no article, sorry, grabbed the numbers from an old PR. to confirm, you were using tcmalloc from https://github.com/google/tcmalloc https://github.com/google/tcmalloc and not from https://github.com/gperftools/gperftools https://github.com/gperftools/gperftools, right? the latter is a lot worse iiuc.
        imp0cat 8d ago
        Good point. It was from the https://packages.debian.org/trixie/google-perftools https://packages.debian.org/trixie/google-perftools Debian package, which points to the gperftools project - so it was the worse one I guess.
egberts1 9d ago
Thank you for the critique. Compilations are hard to get 100% right.
adrian_b 9d ago
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. The C programming language has inherited these 2 functions from IBM PL/I, together with several other features. At that time (1964-12), many other techniques of managing memory had already been used for a few years. Dynamic allocation of memory has started during the fifties, with allocation without ever freeing the allocated memory before the termination of the process. Then, in 1960, 3 methods of handling dynamic memory allocation and implicit freeing were published, which have remained important until today: 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, being used in LISP I about 5 years before the first release of PL/I with explicit allocation and freeing (mid 1965).
- egberts1 9d ago
  Thank you for the insightful aspect. This too should be in the lore of memory allocations as well Will research that, citations and all
  - adrian_b 9d ago
    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, 1960-04, pp. 184-195 (open access at ACM). Stacks and stack pointers: "Recursive Programming", Edsger Wybe Dijkstra, 1960-05-11 (available at the Dijkstra Archive). Reference counts for memory allocation: "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 (open access at ACM). The first "malloc", i.e. the statements "ALLOCATE" and "FREE" appeared in "NPL Technical Report" at IBM in 1964-12 (available at bitsavers.org). "NPL" was a provisional name for the new programming language of IBM, which was rebranded as "PL/I" when it was launched officially, a half of year later. IBM did not document what kind of algorithm was used by their "malloc" implementation, but it already had to handle multi-threaded programs and it was specified that when a new thread was spawned, it could still access any variable that had been dynamically allocated in the parent thread, before the launching of the new thread, but the variables that were allocated in the new thread were private to that thread. The C "malloc" became compatible with multi-threading only many decades after its ancestor from PL/I.

eqvinox 9d ago

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, total allocators covered & details per allocator).

egberts1 9d ago
Thank you. I got tired of reading AI prose so I compiled and wrote it from my collections of others' whitepapers. As a "For Reference Only", at the very least, for me. As usual, anyone is welcome to improve upon it under CC BY-NC-SA.

skavi 9d ago

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.

imp0cat 9d ago
And finally end up with either jemalloc or possibly mimalloc. ;)
- egberts1 9d ago
  Invariably so but I'm mulling over malloc()s on embedded topic now.
- skavi 9d ago
  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]: https://news.ycombinator.com/item?id=47403847 https://news.ycombinator.com/item?id=47403847
  - imp0cat 8d ago
    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 8d ago
      no article, sorry, grabbed the numbers from an old PR. to confirm, you were using tcmalloc from https://github.com/google/tcmalloc https://github.com/google/tcmalloc and not from https://github.com/gperftools/gperftools https://github.com/gperftools/gperftools, right? the latter is a lot worse iiuc.
      - imp0cat 8d ago
        Good point. It was from the https://packages.debian.org/trixie/google-perftools https://packages.debian.org/trixie/google-perftools Debian package, which points to the gperftools project - so it was the worse one I guess.

egberts1 9d ago

Thank you for the critique. Compilations are hard to get 100% right.

adrian_b 9d ago

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. The C programming language has inherited these 2 functions from IBM PL/I, together with several other features. At that time (1964-12), many other techniques of managing memory had already been used for a few years. Dynamic allocation of memory has started during the fifties, with allocation without ever freeing the allocated memory before the termination of the process. Then, in 1960, 3 methods of handling dynamic memory allocation and implicit freeing were published, which have remained important until today: 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, being used in LISP I about 5 years before the first release of PL/I with explicit allocation and freeing (mid 1965).

egberts1 9d ago
Thank you for the insightful aspect. This too should be in the lore of memory allocations as well Will research that, citations and all
- adrian_b 9d ago
  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, 1960-04, pp. 184-195 (open access at ACM). Stacks and stack pointers: "Recursive Programming", Edsger Wybe Dijkstra, 1960-05-11 (available at the Dijkstra Archive). Reference counts for memory allocation: "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 (open access at ACM). The first "malloc", i.e. the statements "ALLOCATE" and "FREE" appeared in "NPL Technical Report" at IBM in 1964-12 (available at bitsavers.org). "NPL" was a provisional name for the new programming language of IBM, which was rebranded as "PL/I" when it was launched officially, a half of year later. IBM did not document what kind of algorithm was used by their "malloc" implementation, but it already had to handle multi-threaded programs and it was specified that when a new thread was spawned, it could still access any variable that had been dynamically allocated in the parent thread, before the launching of the new thread, but the variables that were allocated in the new thread were private to that thread. The C "malloc" became compatible with multi-threading only many decades after its ancestor from PL/I.