5 ms·

My data says that perf of malloc/free in actual programs (not fake ass shit calling malloc in a loop) is never affected by the call overhead. Not by dynamic cal

My data says that perf of malloc/free in actual programs (not fake ass shit calling malloc in a loop) is never affected by the call overhead. Not by dynamic call overhead, not even if you write a wrapper that uses a switch or indirect call to select mallocs. Reason is simple: malloc perf is all about data dependencies in the malloc/free path and how many cache misses it causes or prevents. Adding indirection on the malloc call path is handled gracefully by the CPU’s ability to ILP, and malloc is a perfect candidate since it’s bottlenecks will be cache misses inside the malloc/free paths.

saagarjha 7y ago
Has per-thread arenas made locking less of an issues these days?
- pizlonator 7y ago
  Not everyone does per thread arenas as a way of solving this problem. And I don’t think any solution to locking in malloc is a silver bullet. Some schemes work exceedingly well for specific use cases. So, there will always be folks in the malloc space who think theirs is better or theirs completely solves the problem because it is better and does solve the problem for their use case.
s_kanev 7y ago
This was the case a few years back when the fastest pools were implemented with recursive data structures (e.g. linked lists for the freelists in gperftools). In the new tcmalloc (and, I think, hoard?) the fastest pools are essentially slabs with bump allocation, so the fastest (and by far, the most common) calls are a grand total of 15 or so instructions, without many cache misses (size class lookups tend to stay in the cache). Call overhead can be a substantial chunk of that.
- pizlonator 7y ago
  First of all, let’s be clear: for a lot of algorithms adding call overhead around them is free because the cpu predicts the call, predicts the return, and uses register renaming to handle arguments and return. But that’s not the whole story. Malloc perf is about what happens on free and what happens when the program accesses that memory that malloc gave it. When you factor that all in, it doesn’t matter how many instructions the malloc has. It matters whether those instructions form a bad dependency chain, if they miss cache, whether the memory we return is in the “best” place, and how much work happens in free (using the same metrics - dependency chain length and misses, not total number of instructions or whether there’s a call).
  - jlebar 7y ago
    > First of all, let’s be clear: for a lot of algorithms adding call overhead around them is free because the cpu predicts the call, predicts the return, and uses register renaming to handle arguments and return. This is only thinking at the hardware layer. There are also effects at the software layer. Function calls not known to LTO prevent all sorts of compiler optimizations as well. In addition, as Jeff says on this thread, not being able to inline free means you get no benefit from sized-delete, which is a substantial improvement on some workloads. (I'd cite the exact number, but I'm not sure Google ever released it.) Source: I literally worked on this.
    - pizlonator 7y ago
      Let’s be clear: even without LTO, the compiler knows what malloc and free do at a semantic level. I buy the sized delete win, I’ve seen that too, in some niche cases. But that’s a far cry from the claim that not inlining malloc is bananas. If that’s all you got then this sounds like a stunning retreat from the thesis of Jeff’s post. You’re just saying that you’ve got a free that benefits from size specialization, which has nothing to do with whether malloc got inlined.
      - jlebar 7y ago
        > even without LTO, the compiler knows what malloc and free do at a semantic level. int *a = ...; int b = *a; malloc(42); b = *a; printf(b); If malloc is an opaque function, can the compiler nonetheless eliminate the second `b = *a` load as dead because it "knows what malloc does"? Certainly not, right?
        jepler 7y ago
        https://godbolt.org/z/z-92qR https://godbolt.org/z/z-92qR Interestingly, the compiler emits no call to malloc, even. What!?
        gpderetta 7y ago
- nightcracker 7y ago
  You are not wrong but also missing the point of the person you're replying to.
jlebar 7y ago
> My data says that perf of malloc/free in actual programs (not fake ass shit calling malloc in a loop) is never affected by the call overhead. Your data is legitimate, but you've got to ask yourself, would Jeff specifically and Google more generally care so much about it if it were also true for their use-cases?
- pizlonator 7y ago
  I don’t consider appeals to authority when thinking about technical issues.
  - jlebar 7y ago
    This isn't an appeal to authority. It's a suggestion that we consider the possibility that they are not wasting their time on make-work. This is Bayesian logic (our prior is that the systems engineers at Google are not incompetent), not an appeal to anything.
    - pizlonator 7y ago
      Just because someone isn’t incompetent doesn’t mean that we should assume they are right. Highly competent people are often wrong. Questioning things is good.
      - jlebar 7y ago
        > Questioning things is good. HN could indeed use more epistemic uncertainty and gray (vs black-and-white) thinking.
username90 7y ago
Runtimes often uses a lot of small malloc/free calls in quick succession. Since I worked with implementing a runtime at Google I've seen the function call overhead go up to 20% of the cost of it in real programs, since the actual memory needed was very small. You might argue that we should have done that optimization on our own, but we are just a small team doing an inhouse thing so we don't have those kind of resources, so to us it helps a lot that the the default malloc is very optimized.
ckennelly 7y ago
The cost in applications really does add up. "Profiling a warehouse-scale computer" (by S. Kanev, et. al.) showed several % of CPU usage allocating and deallocating memory. While a malloc and free does have some data dependencies, the indirect jump (by dynamically linking) is an avoidable cost on the critical path by statically linking.
- wahern 7y ago
  Since Haswell indirect jumps have negligible additional cost. See, e.g., "Branch Prediction and the Performance of Interpreters - Don't Trust Folklore", https://hal.inria.fr/hal-01100647 https://hal.inria.fr/hal-01100647 Perhaps Spectre mitigations have changed things, but we're still talking about a fraction of a fraction. As others have said, the best way to improve malloc performance is to not use malloc. Second best would be avoid allocations in critical sections so the allocator doesn't trash your CPU's prediction buffers.
w0utert 7y ago
>> My data says that perf of malloc/free in actual programs (not fake ass shit calling malloc in a loop) is never affected by the call overhead. I have thought the same for a long time until I ran some benchmarks on some of our 3D modeling code that uses Open CASCADE, and found out that in some cases allocation overhead was over 20% of total time spent in the CAD kernel...
- alexhutcheson 7y ago
  pizlonator is saying that the overhead of the function call itself (the “call” instruction itself) doesn’t matter relative to the body of that function. The body of the function still matters a lot.

saagarjha 7y ago

Has per-thread arenas made locking less of an issues these days?

pizlonator 7y ago
Not everyone does per thread arenas as a way of solving this problem. And I don’t think any solution to locking in malloc is a silver bullet. Some schemes work exceedingly well for specific use cases. So, there will always be folks in the malloc space who think theirs is better or theirs completely solves the problem because it is better and does solve the problem for their use case.

s_kanev 7y ago

This was the case a few years back when the fastest pools were implemented with recursive data structures (e.g. linked lists for the freelists in gperftools). In the new tcmalloc (and, I think, hoard?) the fastest pools are essentially slabs with bump allocation, so the fastest (and by far, the most common) calls are a grand total of 15 or so instructions, without many cache misses (size class lookups tend to stay in the cache). Call overhead can be a substantial chunk of that.

pizlonator 7y ago
First of all, let’s be clear: for a lot of algorithms adding call overhead around them is free because the cpu predicts the call, predicts the return, and uses register renaming to handle arguments and return. But that’s not the whole story. Malloc perf is about what happens on free and what happens when the program accesses that memory that malloc gave it. When you factor that all in, it doesn’t matter how many instructions the malloc has. It matters whether those instructions form a bad dependency chain, if they miss cache, whether the memory we return is in the “best” place, and how much work happens in free (using the same metrics - dependency chain length and misses, not total number of instructions or whether there’s a call).
- jlebar 7y ago
  > First of all, let’s be clear: for a lot of algorithms adding call overhead around them is free because the cpu predicts the call, predicts the return, and uses register renaming to handle arguments and return. This is only thinking at the hardware layer. There are also effects at the software layer. Function calls not known to LTO prevent all sorts of compiler optimizations as well. In addition, as Jeff says on this thread, not being able to inline free means you get no benefit from sized-delete, which is a substantial improvement on some workloads. (I'd cite the exact number, but I'm not sure Google ever released it.) Source: I literally worked on this.
  - pizlonator 7y ago
    Let’s be clear: even without LTO, the compiler knows what malloc and free do at a semantic level. I buy the sized delete win, I’ve seen that too, in some niche cases. But that’s a far cry from the claim that not inlining malloc is bananas. If that’s all you got then this sounds like a stunning retreat from the thesis of Jeff’s post. You’re just saying that you’ve got a free that benefits from size specialization, which has nothing to do with whether malloc got inlined.
    - jlebar 7y ago
      > even without LTO, the compiler knows what malloc and free do at a semantic level. int *a = ...; int b = *a; malloc(42); b = *a; printf(b); If malloc is an opaque function, can the compiler nonetheless eliminate the second `b = *a` load as dead because it "knows what malloc does"? Certainly not, right?
      - jepler 7y ago
        https://godbolt.org/z/z-92qR https://godbolt.org/z/z-92qR Interestingly, the compiler emits no call to malloc, even. What!?
        gpderetta 7y ago
nightcracker 7y ago
You are not wrong but also missing the point of the person you're replying to.

jlebar 7y ago

> My data says that perf of malloc/free in actual programs (not fake ass shit calling malloc in a loop) is never affected by the call overhead. Your data is legitimate, but you've got to ask yourself, would Jeff specifically and Google more generally care so much about it if it were also true for their use-cases?

pizlonator 7y ago
I don’t consider appeals to authority when thinking about technical issues.
- jlebar 7y ago
  This isn't an appeal to authority. It's a suggestion that we consider the possibility that they are not wasting their time on make-work. This is Bayesian logic (our prior is that the systems engineers at Google are not incompetent), not an appeal to anything.
  - pizlonator 7y ago
    Just because someone isn’t incompetent doesn’t mean that we should assume they are right. Highly competent people are often wrong. Questioning things is good.
    - jlebar 7y ago
      > Questioning things is good. HN could indeed use more epistemic uncertainty and gray (vs black-and-white) thinking.

username90 7y ago

Runtimes often uses a lot of small malloc/free calls in quick succession. Since I worked with implementing a runtime at Google I've seen the function call overhead go up to 20% of the cost of it in real programs, since the actual memory needed was very small. You might argue that we should have done that optimization on our own, but we are just a small team doing an inhouse thing so we don't have those kind of resources, so to us it helps a lot that the the default malloc is very optimized.

ckennelly 7y ago

The cost in applications really does add up. "Profiling a warehouse-scale computer" (by S. Kanev, et. al.) showed several % of CPU usage allocating and deallocating memory. While a malloc and free does have some data dependencies, the indirect jump (by dynamically linking) is an avoidable cost on the critical path by statically linking.

wahern 7y ago
Since Haswell indirect jumps have negligible additional cost. See, e.g., "Branch Prediction and the Performance of Interpreters - Don't Trust Folklore", https://hal.inria.fr/hal-01100647 https://hal.inria.fr/hal-01100647 Perhaps Spectre mitigations have changed things, but we're still talking about a fraction of a fraction. As others have said, the best way to improve malloc performance is to not use malloc. Second best would be avoid allocations in critical sections so the allocator doesn't trash your CPU's prediction buffers.

w0utert 7y ago

>> My data says that perf of malloc/free in actual programs (not fake ass shit calling malloc in a loop) is never affected by the call overhead. I have thought the same for a long time until I ran some benchmarks on some of our 3D modeling code that uses Open CASCADE, and found out that in some cases allocation overhead was over 20% of total time spent in the CAD kernel...

alexhutcheson 7y ago
pizlonator is saying that the overhead of the function call itself (the “call” instruction itself) doesn’t matter relative to the body of that function. The body of the function still matters a lot.