4 ms·

> malloc and free are still the two hottest functions in most benchmarks. Avoiding heap allocations can be a win. This is a non-sequitur. If you see a hot func

by eridius 10y ago

> malloc and free are still the two hottest functions in most benchmarks. Avoiding heap allocations can be a win. This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can. But it does not mean that you should try to reduce calls to that function elsewhere (unless you can cut out a lot in one go). As a trivial example, if you have a super-fast function that cannot be optimized any further, but it's called millions of times, that function may appear hot, but any individual invocation of the function might be taking just a few microseconds. Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good. I guess another way of saying this is, if you're trying to optimize a hot function by reducing the number of times it's called, you need to reduce it by a significant percentage of the total calls rather than reducing it by a specific number of times. No matter how many times it's called, if you reduce the number of calls by 50%, the overall time taken by the function drops by 50%. But if you reduce the number of calls by 50, then whether that's meaningful or not depends entirely on how long each individual call to the function takes. Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why.

MaulingMonkey 10y ago
> Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why. Didn't downvote you, and considering you're currently on the top of the replies list, I wouldn't worry about potential misclicks. But I'll bite. > This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can. This is just as much of a "non-sequitur" - maybe you can optimize that function further, but if it's reached the point of diminishing returns it may not be worth it even if it's technically possible. In-context, there has already been a lot of optimization work put into malloc and free, lots of low hanging fruit is gone. Further, malloc and free are very generic allocation strategies that generally do a lot of work to try and handle many different cases with OK efficiency. I challenge you to make them as fast as, say, stack allocation - go ahead, I'll wait. Sure, you can't replace all use of a heap with a stack, but most programs I've seen have at least some cases where you could. And there is actually a way to make malloc and free as fast as a stack - turn your malloc implementation into a pointer increment, and free into a noop. Not appropriate for all tools, but a short lived compiler pass might be able to get away with it! Although it'd possibly cause problems for large 32-bit builds. Regardless - this is also technically no longer a heap. As such, "Avoiding heap allocations can be a win" seems to be a very true and straightforward reply. Confusingly, you seem to agree with this in your next paragraph despite labeling it a "non-sequitur"? Perhaps you're interpreting this as claiming that avoiding a single heap allocation call site is going to be a significant win? Because that's reading far too much into the statement, IMO. > Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good. An important note here: Cutting the number of calls in half could, in theory, involve eliminating one call site (because e.g. the calling code itself is very hot) although this probably isn't the case in the Rust codebase or it'd have been optimized already. Even if we pessimistically assume that we need to eliminate N% of call sites to eliminate N% of calls, the first step to eliminating N% of call sites is to eliminate one call site. The second step is to eliminate a second call site.
- eridius 10y ago
  > Didn't downvote you, and considering you're currently on the top of the replies list, I wouldn't worry about potential misclicks. But I'll bite. Thank you for your reply. At the time I added that edit, I was at -2 points. And I'm only at 1 point right now (and aren't showing up at the top of the stack when I look at the comments page). In any case, the edit did seem to do what I wanted, which was to get replies. > As such, "Avoiding heap allocations can be a win" seems to be a very true and straightforward reply. Confusingly, you seem to agree with this in your next paragraph despite labeling it a "non-sequitur"? Perhaps you're interpreting this as claiming that avoiding a single heap allocation call site is going to be a significant win? Because that's reading far too much into the statement, IMO. The way I read it was "malloc is a hot function, therefore you should try to avoid using it". And that's a non-sequitur because the conclusion does not follow from the premise. Whether or not it's a hot function has no bearing on what the cost of an individual call is. And when you identify a hot function in a profile, that doesn't mean you should remove calls to it, that means you should optimize it. If you can't optimize it, then you should charge it to its parent frame. If you take all your un-optimizable hot functions and charge them to their parent frame, then you can see if any new hot functions pop up that can be optimized. e.g. you can't optimize malloc, but if you find one function is calling malloc hundreds or thousands of times, and it doesn't have to, then you can optimize that function (or if it does need all those allocations, you can investigate using alternatives to malloc). > Even if we pessimistically assume that we need to eliminate N% of call sites to eliminate N% of calls, the first step to eliminating N% of call sites is to eliminate one call site. The second step is to eliminate a second call site. When talking about a function with many thousands of individual call sites, eliminating them one at a time isn't practical. You need to come with some way to systematically eliminate a lot of them. Of course, if you do the above and charge malloc to its callers then maybe you can identify a small number of call sites that are responsible for a high percentage of calls to malloc.
  - MaulingMonkey 10y ago
    > The way I read it was "malloc is a hot function, therefore you should try to avoid using it". We agree that's a non-sequiter in the more general case at least ("X is a hot function ...") - but even in the more general case, it's not an error to state that it may be worth avoiding, which would be a more accurate reading IMO. It's an avenue to investigate. > When talking about a function with many thousands of individual call sites, eliminating them one at a time isn't practical. I've done it before (refactoring logging macros, static_assert s due to macros conflicting with builtins on new compilers, even fixing up allocation interfaces to better trace call sites, etc.) It's painful and laborious, but sometimes worthwhile.
elihu 10y ago
The original statement isn't a non-sequitur. If the compiler is spending a lot of time in malloc, it makes sense to replace those heap allocations with stack allocations where possible. You are also correct that removing mallocs might not be much of a low-hanging fruit, since it might entail changing a lot of malloc calls rather than just a few, but that doesn't mean the original statement was wrong.
- eridius 10y ago
  Fair enough, but it's a good bet that most of those mallocs cannot be replaced with stack allocations.
  - MaulingMonkey 10y ago
    So grab an fixed-size pool allocator. Malloc is very generic, and faster alternatives aren't limited to stack allocators. EDIT: Or do what the article does, eliminate allocations that were straight up unnecessary (because they were unused, or over-eager deep copies)
  - nnethercote 10y ago
    My post indicates that I've already removed a large chunk of the existing mallocs. The remaining ones are harder, but I expect I'll be able to still remove a decent fraction.

by eridius 10y ago

MaulingMonkey 10y ago

> Edit: Why am I being downvoted for this? I'm speaking a factually correct statement. It's not like this is some sort of controversial opinion. If I'm wrong, please tell me why. Didn't downvote you, and considering you're currently on the top of the replies list, I wouldn't worry about potential misclicks. But I'll bite. > This is a non-sequitur. If you see a hot function in a profile, that is an indication that you should optimize that function if you can. This is just as much of a "non-sequitur" - maybe you can optimize that function further, but if it's reached the point of diminishing returns it may not be worth it even if it's technically possible. In-context, there has already been a lot of optimization work put into malloc and free, lots of low hanging fruit is gone. Further, malloc and free are very generic allocation strategies that generally do a lot of work to try and handle many different cases with OK efficiency. I challenge you to make them as fast as, say, stack allocation - go ahead, I'll wait. Sure, you can't replace all use of a heap with a stack, but most programs I've seen have at least some cases where you could. And there is actually a way to make malloc and free as fast as a stack - turn your malloc implementation into a pointer increment, and free into a noop. Not appropriate for all tools, but a short lived compiler pass might be able to get away with it! Although it'd possibly cause problems for large 32-bit builds. Regardless - this is also technically no longer a heap. As such, "Avoiding heap allocations can be a win" seems to be a very true and straightforward reply. Confusingly, you seem to agree with this in your next paragraph despite labeling it a "non-sequitur"? Perhaps you're interpreting this as claiming that avoiding a single heap allocation call site is going to be a significant win? Because that's reading far too much into the statement, IMO. > Getting rid of a handful of calls to this function (or even a few hundred) isn't going to make an appreciable difference. Of course, if you can cut the number of calls in half, then that would be good. An important note here: Cutting the number of calls in half could, in theory, involve eliminating one call site (because e.g. the calling code itself is very hot) although this probably isn't the case in the Rust codebase or it'd have been optimized already. Even if we pessimistically assume that we need to eliminate N% of call sites to eliminate N% of calls, the first step to eliminating N% of call sites is to eliminate one call site. The second step is to eliminate a second call site.

eridius 10y ago
> Didn't downvote you, and considering you're currently on the top of the replies list, I wouldn't worry about potential misclicks. But I'll bite. Thank you for your reply. At the time I added that edit, I was at -2 points. And I'm only at 1 point right now (and aren't showing up at the top of the stack when I look at the comments page). In any case, the edit did seem to do what I wanted, which was to get replies. > As such, "Avoiding heap allocations can be a win" seems to be a very true and straightforward reply. Confusingly, you seem to agree with this in your next paragraph despite labeling it a "non-sequitur"? Perhaps you're interpreting this as claiming that avoiding a single heap allocation call site is going to be a significant win? Because that's reading far too much into the statement, IMO. The way I read it was "malloc is a hot function, therefore you should try to avoid using it". And that's a non-sequitur because the conclusion does not follow from the premise. Whether or not it's a hot function has no bearing on what the cost of an individual call is. And when you identify a hot function in a profile, that doesn't mean you should remove calls to it, that means you should optimize it. If you can't optimize it, then you should charge it to its parent frame. If you take all your un-optimizable hot functions and charge them to their parent frame, then you can see if any new hot functions pop up that can be optimized. e.g. you can't optimize malloc, but if you find one function is calling malloc hundreds or thousands of times, and it doesn't have to, then you can optimize that function (or if it does need all those allocations, you can investigate using alternatives to malloc). > Even if we pessimistically assume that we need to eliminate N% of call sites to eliminate N% of calls, the first step to eliminating N% of call sites is to eliminate one call site. The second step is to eliminate a second call site. When talking about a function with many thousands of individual call sites, eliminating them one at a time isn't practical. You need to come with some way to systematically eliminate a lot of them. Of course, if you do the above and charge malloc to its callers then maybe you can identify a small number of call sites that are responsible for a high percentage of calls to malloc.
- MaulingMonkey 10y ago
  > The way I read it was "malloc is a hot function, therefore you should try to avoid using it". We agree that's a non-sequiter in the more general case at least ("X is a hot function ...") - but even in the more general case, it's not an error to state that it may be worth avoiding, which would be a more accurate reading IMO. It's an avenue to investigate. > When talking about a function with many thousands of individual call sites, eliminating them one at a time isn't practical. I've done it before (refactoring logging macros, static_assert s due to macros conflicting with builtins on new compilers, even fixing up allocation interfaces to better trace call sites, etc.) It's painful and laborious, but sometimes worthwhile.

elihu 10y ago

The original statement isn't a non-sequitur. If the compiler is spending a lot of time in malloc, it makes sense to replace those heap allocations with stack allocations where possible. You are also correct that removing mallocs might not be much of a low-hanging fruit, since it might entail changing a lot of malloc calls rather than just a few, but that doesn't mean the original statement was wrong.

eridius 10y ago
Fair enough, but it's a good bet that most of those mallocs cannot be replaced with stack allocations.
- MaulingMonkey 10y ago
  So grab an fixed-size pool allocator. Malloc is very generic, and faster alternatives aren't limited to stack allocators. EDIT: Or do what the article does, eliminate allocations that were straight up unnecessary (because they were unused, or over-eager deep copies)
- nnethercote 10y ago
  My post indicates that I've already removed a large chunk of the existing mallocs. The remaining ones are harder, but I expect I'll be able to still remove a decent fraction.