7 ms·

One malloc to rule them all

33 points by parenthesis 17y ago

scott_s 17y ago
The title is inaccurate. It's a memory allocator specifically design for real-time systems. This is an important and difficult problem, but it in no way makes it an allocator "to rule them all." In particular, I'm thinking about multithreaded allocation, which I think will become increasingly important. Academic papers: http://rtportal.upv.es/rtmalloc/node/71 http://rtportal.upv.es/rtmalloc/node/71
- nkurz 17y ago
  I think the title is fine. He's not suggesting that this new malloc is the one "to rule them all". It sounds like he hasn't even tried it yet. Instead, he's wishing that there was such a malloc: That’s the crazy thing about malloc implementations. They all claim to be awesome in every way. So the burning question is: is this better than what I’m using today? I don’t know, but I’d sure like to! I like the article, but I'm not sure that there needs to be a single winner. Different programs have different needs. Right now, I'd love to find a malloc that can work within shared mmap segments, sort of as described here: http://blog.directededge.com/2009/02/27/on-building-a-stupidly-fast-graph-database/ http://blog.directededge.com/2009/02/27/on-building-a-stupid...
- haberman 17y ago
  nkurz is right about the intention of the title, but if TLSF is only intended for real-time systems, then why does it claim that it is general-purpose, and not include any caveats of the sort you do? Like all memory allocators I've encountered, none of them say "if you're doing X, you're probably better off using a different allocator." The closest it comes to a caveat is: > Although TLSF works rather well in many scenarios, it stands out in applications with hard/soft real-time application which uses explicit memory allocation with high flexibility requirements due to a high variability of the data size or adaptability to new situations. Or paraphrased: "TLSF is great, but is especially great when..."
  - scott_s 17y ago
    It was designed for real time systems, and evaluated in the context of real time systems. (Check out the academic papers.) "General purpose" just means it implements the malloc/free interface, and can be used in place of the standard on your system. In the case that most people care about, I think something like TCMalloc (http://goog-perftools.sourceforge.net/doc/tcmalloc.html http://goog-perftools.sourceforge.net/doc/tcmalloc.html) is more appropriate.
liuliu 17y ago
In my experience, the DSA took extensive use of x86 instruction ffs/fls which is fairly slow in several CPU chips (slower than maintain a free-list).
ComputerGuru 17y ago
I'm looking at nedmalloc atm (http://www.nedprod.com/programs/portable/nedmalloc/ http://www.nedprod.com/programs/portable/nedmalloc/) and I'm really impressed by what I'm seeing there. Has anyone here had the opportunity to test nedmalloc in real life? What sort of performance benefits did you see? Any problems you ran into? I'm currently designing embedded systems in C, and am looking to get the most performance out of strained resources as possible... I'm wondering if this'll compile for AVR or not.....
alexgartrell 17y ago
Two TA tricks to make people not use malloc: 1) Have them write it 2) Force them to check the return value of all system calls. Static arrays aplenty will arise Also) punish them for excessively large static arrays
vicaya 17y ago
It's impossible. Baiting titles are annoying.
- aminuit 17y ago
  This article will make you dumber. At least he linked to the jemalloc whitepaper, which he clearly didn't read. http://people.freebsd.org/%7Ejasone/jemalloc/bsdcan2006/jemalloc.pdf http://people.freebsd.org/%7Ejasone/jemalloc/bsdcan2006/jema... I especially like the part near the end of the post where it says, "It could be that different implementations excel in different scenarios" as if that wasn't completely obvious for anyone who has thought for more than a few minutes about a malloc implementation.
  - haberman 17y ago
    Article author here -- apologies for making you dumber. I would love to hear any data you have about when I should choose one malloc() implementation over another; the theory that malloc implementations have trade-offs is basic enough, but I've never come across a memory allocator that says "here are situations where you shouldn't use this allocator, and should use allocator Y instead." And since the malloc() that ships with any given libc is going to be used by 100% of applications that do not explicitly override malloc (and I have never come across an application that does), understanding which is the best all-around allocator seems like quite the worthwhile exercise. I also don't necessarily buy the jemalloc paper's assertion that allocators cannot be benchmarked in isolation. It's true that you can't measure the effects that locality will have on the rest of the application, but you surely can measure locality of allocations.
    - vicaya 17y ago
      General purpose malloc/free cannot "rule" in all situations due to its limited interface hence any particular understanding of resource management constraints. It's obvious that no malloc/free package can possibly outperform an arena scheme when it makes sense.

33 points by parenthesis 17y ago

The title is inaccurate. It's a memory allocator specifically design for real-time systems. This is an important and difficult problem, but it in no way makes it an allocator "to rule them all." In particular, I'm thinking about multithreaded allocation, which I think will become increasingly important. Academic papers: http://rtportal.upv.es/rtmalloc/node/71 http://rtportal.upv.es/rtmalloc/node/71

nkurz 17y ago
I think the title is fine. He's not suggesting that this new malloc is the one "to rule them all". It sounds like he hasn't even tried it yet. Instead, he's wishing that there was such a malloc: That’s the crazy thing about malloc implementations. They all claim to be awesome in every way. So the burning question is: is this better than what I’m using today? I don’t know, but I’d sure like to! I like the article, but I'm not sure that there needs to be a single winner. Different programs have different needs. Right now, I'd love to find a malloc that can work within shared mmap segments, sort of as described here: http://blog.directededge.com/2009/02/27/on-building-a-stupidly-fast-graph-database/ http://blog.directededge.com/2009/02/27/on-building-a-stupid...
haberman 17y ago
nkurz is right about the intention of the title, but if TLSF is only intended for real-time systems, then why does it claim that it is general-purpose, and not include any caveats of the sort you do? Like all memory allocators I've encountered, none of them say "if you're doing X, you're probably better off using a different allocator." The closest it comes to a caveat is: > Although TLSF works rather well in many scenarios, it stands out in applications with hard/soft real-time application which uses explicit memory allocation with high flexibility requirements due to a high variability of the data size or adaptability to new situations. Or paraphrased: "TLSF is great, but is especially great when..."
- scott_s 17y ago
  It was designed for real time systems, and evaluated in the context of real time systems. (Check out the academic papers.) "General purpose" just means it implements the malloc/free interface, and can be used in place of the standard on your system. In the case that most people care about, I think something like TCMalloc (http://goog-perftools.sourceforge.net/doc/tcmalloc.html http://goog-perftools.sourceforge.net/doc/tcmalloc.html) is more appropriate.

liuliu 17y ago

In my experience, the DSA took extensive use of x86 instruction ffs/fls which is fairly slow in several CPU chips (slower than maintain a free-list).

ComputerGuru 17y ago

I'm looking at nedmalloc atm (http://www.nedprod.com/programs/portable/nedmalloc/ http://www.nedprod.com/programs/portable/nedmalloc/) and I'm really impressed by what I'm seeing there. Has anyone here had the opportunity to test nedmalloc in real life? What sort of performance benefits did you see? Any problems you ran into? I'm currently designing embedded systems in C, and am looking to get the most performance out of strained resources as possible... I'm wondering if this'll compile for AVR or not.....

alexgartrell 17y ago

Two TA tricks to make people not use malloc: 1) Have them write it 2) Force them to check the return value of all system calls. Static arrays aplenty will arise Also) punish them for excessively large static arrays

vicaya 17y ago

It's impossible. Baiting titles are annoying.

aminuit 17y ago
This article will make you dumber. At least he linked to the jemalloc whitepaper, which he clearly didn't read. http://people.freebsd.org/%7Ejasone/jemalloc/bsdcan2006/jemalloc.pdf http://people.freebsd.org/%7Ejasone/jemalloc/bsdcan2006/jema... I especially like the part near the end of the post where it says, "It could be that different implementations excel in different scenarios" as if that wasn't completely obvious for anyone who has thought for more than a few minutes about a malloc implementation.
- haberman 17y ago
  Article author here -- apologies for making you dumber. I would love to hear any data you have about when I should choose one malloc() implementation over another; the theory that malloc implementations have trade-offs is basic enough, but I've never come across a memory allocator that says "here are situations where you shouldn't use this allocator, and should use allocator Y instead." And since the malloc() that ships with any given libc is going to be used by 100% of applications that do not explicitly override malloc (and I have never come across an application that does), understanding which is the best all-around allocator seems like quite the worthwhile exercise. I also don't necessarily buy the jemalloc paper's assertion that allocators cannot be benchmarked in isolation. It's true that you can't measure the effects that locality will have on the rest of the application, but you surely can measure locality of allocations.
  - vicaya 17y ago
    General purpose malloc/free cannot "rule" in all situations due to its limited interface hence any particular understanding of resource management constraints. It's obvious that no malloc/free package can possibly outperform an arena scheme when it makes sense.