4 ms·

It should be obvious that a lot of 8 byte mallocs will give bad performance and horrible memory use. This article and in particular the benchmarks in it would b

by exDM69 13y ago

It should be obvious that a lot of 8 byte mallocs will give bad performance and horrible memory use. This article and in particular the benchmarks in it would be a lot more informative if the test case was more realistic. Please add at least 32 or 64 bytes of payload to the linked list structure and re-run the benchmarks. Even that is a very small allocation block, but is on the lower end of realistic allocation sizes although not a good practice.

barrkel 13y ago
8-byte mallocs are expensive because most mallocs have per-allocation memory overhead to track things. This is exactly why you may want to use a different allocator. IOW, you're angle is that instead of finding a solution to the problem, instead choose a different problem. You don't always have that luxury. My background on this problem is compilers. Compilers allocate lots of little structures that represent tree nodes, values, tokens, etc. Forcing them all to be a minimum of 32 or 64 bytes in size on the basis that would justify using malloc for them, would be more than a little bizarre. Arena allocation - both per module (for structures that need to persist for the whole compilation) and stack based (for structures that are discarded after e.g. evaluation or codegen) - makes far more sense than contorting the problem so that malloc makes sense.
- exDM69 13y ago
  > 8-byte mallocs are expensive because most mallocs have per-allocation memory overhead to track things. This is exactly why you may want to use a different allocator. I guess if the objective of the article is to point out the obvious fact that mallocing 8 bytes at a time is a bad idea, then showing up some actual numbers from actual malloc implementations is a good idea. However, even small objects in practical problems are usually bigger than 8 bytes, so making the allocation size a bit bigger would give more realistic figures. Overall I think the article was informative and well written but more realistic test case would better point out when to write a custom allocator and what allocator to choose for a particular usage pattern.
  - fruneau 13y ago
    The objective of the article wasn't to stress the specific case of the 8-bytes allocation pattern, it was about showing that malloc behavior depends on the context. The size of 8 bytes had been chosen because it was small enough to allow a large number of allocation to be performed so that timing were quite accurate in the results, however the main goal was to show the difference between was are called the "contended" and the "uncontended" case: your program may perform properly with single-threaded workload, but poorly in a multi-threaded environment, not because of explicit locking in your code but because some resource sharing is hidden behind the allocator. Also, the choice of lot of allocations + lot of deallocations pattern was chosen because this is an issue we ran into quite recently: we allocated a huge tree structure progressively and sometimes we flushed it to disk. The flush was quite efficient, but the deallocation blocked the program during approximatively 30s. As a quick fix, we put the deallocation in background, but this slowed the tree construction down by approximatively 50% because of the contention of the allocator. Even if the size of the chunks in the article were not realistic, the results were near-realistic enough to be considered publishable. I provided (in a separate comment) the result of the benchmarks with a 32-bytes payload (in that benchmark, all the allocators had the same 12% overhead in term of memory, but we clearly see the same performance pattern as with the 8-bytes payload).
  - jbooth 13y ago
    I kinda see it more as "we're using an unrealistic workload to emphasize the per-malloc overhead". A program that was written to minimize and batch allocations wouldn't be as demonstrative.
    - tptacek 13y ago
      Contra "exDM69", there's nothing unreasonable or "unrealistic" about allocating 8 bytes at a time; it's in fact extremely convenient to be able to do that. I think it's telling that someone would call that workload unrealistic; it indicates to me that they've never even really considered alternatives to malloc. It's a little like those C programmers who try to use 256 byte static arrays for all their strings because they don't quite grok malloc/realloc.
- tomlu 13y ago
  > 8-byte mallocs are expensive because most mallocs have per-allocation memory overhead to track things As you say, most mallocs have this overhead. But with a bit of alignment trickery and bit masking you can put the header storage at the start of a page, bringing per-allocation overhead down to just a few bits.
fruneau 13y ago
I ran the test with a payload of 32 bytes. Here are the results: Non-Contented test: * ptmalloc: alloc 39M/s, free 49M/s * tcmalloc: alloc 42M/s, free 40M/s * jemalloc: alloc 21M/s, free 21M/s * t_stack: alloc 110M/s Contended test: * ptmalloc: alloc 6.1M/s, free 6.4M/s * tcmalloc: alloc 25M/s, free 11M/s * jemalloc: alloc 18M/s, free 6.5M/s Note that the results are less accurate that those provided in the article since the number of allocations per batch is smaller (due to the limited amount of RAM available on my desktop). That's said, the article does not pretend benching realistic patterns.
tptacek 13y ago
The post starts out by explaining that malloc is a generic allocator and is thus less performant. Your comment seems premised on the idea that the author is suggesting a replacement for malloc in all its use cases, which he pointedly is not doing. Instead of him re-running his benchmarks, you should give the post a closer re-read.
- mmatants 13y ago
  I hate to go meta, but that last sentence in your post could have been omitted with no detriment to the post's message and great improvement to the tone.

by exDM69 13y ago

barrkel 13y ago

8-byte mallocs are expensive because most mallocs have per-allocation memory overhead to track things. This is exactly why you may want to use a different allocator. IOW, you're angle is that instead of finding a solution to the problem, instead choose a different problem. You don't always have that luxury. My background on this problem is compilers. Compilers allocate lots of little structures that represent tree nodes, values, tokens, etc. Forcing them all to be a minimum of 32 or 64 bytes in size on the basis that would justify using malloc for them, would be more than a little bizarre. Arena allocation - both per module (for structures that need to persist for the whole compilation) and stack based (for structures that are discarded after e.g. evaluation or codegen) - makes far more sense than contorting the problem so that malloc makes sense.

exDM69 13y ago
> 8-byte mallocs are expensive because most mallocs have per-allocation memory overhead to track things. This is exactly why you may want to use a different allocator. I guess if the objective of the article is to point out the obvious fact that mallocing 8 bytes at a time is a bad idea, then showing up some actual numbers from actual malloc implementations is a good idea. However, even small objects in practical problems are usually bigger than 8 bytes, so making the allocation size a bit bigger would give more realistic figures. Overall I think the article was informative and well written but more realistic test case would better point out when to write a custom allocator and what allocator to choose for a particular usage pattern.
- fruneau 13y ago
  The objective of the article wasn't to stress the specific case of the 8-bytes allocation pattern, it was about showing that malloc behavior depends on the context. The size of 8 bytes had been chosen because it was small enough to allow a large number of allocation to be performed so that timing were quite accurate in the results, however the main goal was to show the difference between was are called the "contended" and the "uncontended" case: your program may perform properly with single-threaded workload, but poorly in a multi-threaded environment, not because of explicit locking in your code but because some resource sharing is hidden behind the allocator. Also, the choice of lot of allocations + lot of deallocations pattern was chosen because this is an issue we ran into quite recently: we allocated a huge tree structure progressively and sometimes we flushed it to disk. The flush was quite efficient, but the deallocation blocked the program during approximatively 30s. As a quick fix, we put the deallocation in background, but this slowed the tree construction down by approximatively 50% because of the contention of the allocator. Even if the size of the chunks in the article were not realistic, the results were near-realistic enough to be considered publishable. I provided (in a separate comment) the result of the benchmarks with a 32-bytes payload (in that benchmark, all the allocators had the same 12% overhead in term of memory, but we clearly see the same performance pattern as with the 8-bytes payload).
- jbooth 13y ago
  I kinda see it more as "we're using an unrealistic workload to emphasize the per-malloc overhead". A program that was written to minimize and batch allocations wouldn't be as demonstrative.
  - tptacek 13y ago
    Contra "exDM69", there's nothing unreasonable or "unrealistic" about allocating 8 bytes at a time; it's in fact extremely convenient to be able to do that. I think it's telling that someone would call that workload unrealistic; it indicates to me that they've never even really considered alternatives to malloc. It's a little like those C programmers who try to use 256 byte static arrays for all their strings because they don't quite grok malloc/realloc.
tomlu 13y ago
> 8-byte mallocs are expensive because most mallocs have per-allocation memory overhead to track things As you say, most mallocs have this overhead. But with a bit of alignment trickery and bit masking you can put the header storage at the start of a page, bringing per-allocation overhead down to just a few bits.

fruneau 13y ago

I ran the test with a payload of 32 bytes. Here are the results: Non-Contented test: * ptmalloc: alloc 39M/s, free 49M/s * tcmalloc: alloc 42M/s, free 40M/s * jemalloc: alloc 21M/s, free 21M/s * t_stack: alloc 110M/s Contended test: * ptmalloc: alloc 6.1M/s, free 6.4M/s * tcmalloc: alloc 25M/s, free 11M/s * jemalloc: alloc 18M/s, free 6.5M/s Note that the results are less accurate that those provided in the article since the number of allocations per batch is smaller (due to the limited amount of RAM available on my desktop). That's said, the article does not pretend benching realistic patterns.

tptacek 13y ago

The post starts out by explaining that malloc is a generic allocator and is thus less performant. Your comment seems premised on the idea that the author is suggesting a replacement for malloc in all its use cases, which he pointedly is not doing. Instead of him re-running his benchmarks, you should give the post a closer re-read.

mmatants 13y ago
I hate to go meta, but that last sentence in your post could have been omitted with no detriment to the post's message and great improvement to the tone.