7 ms·

Lots of performance mysteries, particularly in micro-benchmarks, are explained by how either code or data aligns to memory cache lines. A seemingly unrelated c

by dzdt 6y ago

Lots of performance mysteries, particularly in micro-benchmarks, are explained by how either code or data aligns to memory cache lines. A seemingly unrelated change will cause memory locations to move. No idea if that is the case here or not but it looks like a possibility.

codezero 6y ago
Yep, I'm not even a hobbyist in this area, and immediately wondered if there was an alignment change because of it. With that said, it sounds like at least with GCC, a global constant would go in the TEXT section of the binary and I can't think of why that would affect performance, especially since the variable was seemingly unused. Neat, I hope someone finds the thread to pull here :)
- kijiki 6y ago
  > ...a global constant would go in the TEXT section of the binary... Wouldn't it go into the .rodata section, not .text?
  - codezero 6y ago
    I'm not sure, I am parroting what I thought I read on SO - so you are much more likely to be right, sorry about that!
    - vivekseth 6y ago
      clang seems to work this way, and macOS aliases gcc -> clang by default. Wrote more about this here: https://news.ycombinator.com/item?id=23634495 https://news.ycombinator.com/item?id=23634495
      - codezero 6y ago
        Thanks! Glad there's an explanation for my confusion :)
- tom_mellior 6y ago
  > it sounds like at least with GCC, a global constant would go in the TEXT section of the binary I don't know why you think it sounds like that, but GCC (on Linux) puts global constants into the .rodata section (read-only data) and other global variables into the .data section. > I can't think of why that would affect performance, especially since the variable was seemingly unused. I'm guessing data alignment and corresponding changes in cache hits and misses. But I wonder if there's a scenario where this change changes the offsets of other variables from the base of the data section, which changes the encodings and therefore the sizes of the instructions accessing those variables, which overall changes code size and might cause code alignment issues. Probably too far-fetched.
  - vivekseth 6y ago
    On macOS, "gcc" puts strings that don't include a null byte in the TEXT section. I put quotes around gcc, since it seems that by default macOS aliases gcc to clang. You can run the program I built here to see for your self: https://github.com/vivekseth/blog-posts/tree/master/Jump-Address-Hacking-to-Execute-Code-Stored-as-a-String https://github.com/vivekseth/blog-posts/tree/master/Jump-Add... Since the string in the TEXT section, we can actually execute it as if it were code! After you build the program you can run `otool -t ./a.out` to verify that the string `execString` is indeed in the TEXT section.
    - tom_mellior 6y ago
      Interesting. And if you put a null byte at the end of that character array, it would put it in a different section? I don't have access to MacOS, but I would be interested in seeing the output of clang -S on that code (with and without a null byte), maybe you could add it to the repository?
      - vivekseth 6y ago
        If I'm remembering correctly (this was from 3 years ago), the string was moved to a different section if it had a null byte in the middle of the string. That's why coming up with the assembly I used was kinda tricky. Here's the output as-is: https://gist.github.com/vivekseth/20f319d2a9978af57d926b649adc0bde https://gist.github.com/vivekseth/20f319d2a9978af57d926b649a... Here's the output with a null byte in the middle: https://gist.github.com/vivekseth/fc50319aaac24588bcf568209bf6df8e https://gist.github.com/vivekseth/fc50319aaac24588bcf568209b... From what I can tell, it seems like both strings are in the TEXT section now. Maybe something changed, or I'm remembering incorrectly.
muth02446 6y ago
here is a related paper: https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13....
nwallin 6y ago
This is probably the answer. I watched a great talk about this, and how to avoid problems that result from it. The presenter built a framework that made random changes to alignment of various blocks of code with two different versions of the same microbenchmark until it had high statistical confidence that either one was faster than the other, or it would eject and say that the difference between the two was statistically insignificant. Or something along those lines. I'm looking for the video now, but I can't find it. Pretty sure it was CppCon but I'm not positive.
- kristjansson 6y ago
  https://news.ycombinator.com/item?id=23634519 https://news.ycombinator.com/item?id=23634519 :)
- moonchild 6y ago
  Possibly 'Performance Matters'? (https://www.youtube.com/watch?v=r-TLSBdHe1A https://www.youtube.com/watch?v=r-TLSBdHe1A)
  - dkersten 6y ago
    This was the very first thing I thought of when I saw this submission title! Great talk, well worth watching.
  - Twirrim 6y ago
    My team watched this several months ago now. "Eyeball statistics" he mentions at one stage has been a phrase that has particularly stuck for us from it. So many metrics dashboards etc rely on it to a disturbing degree, if you step back and really think about what it's _actually_ showing you. I almost want to put a warning banner on most of ours. "Beware Eyeball Statistics!"
    - nwallin 6y ago
      The other one is 99th percentile latency. Lots of people think of 99th percentile latency as the latency that 1% of their users will encounter. But if your site loads 200 assets, almost every site load will hit 99th percentile latency.
kristjansson 6y ago
This[1] talk from Emery Berger at last year's Strange Loop does a good job discussing the impact of alignment and other 'small' changes on performance, and how to estimate the actual impact of changes on performance [1]: https://www.youtube.com/watch?v=r-TLSBdHe1A https://www.youtube.com/watch?v=r-TLSBdHe1A
userbinator 6y ago
This is one of the reasons why I think microbenchmarks are either not very useful or completely misleading --- they'll favour things like insanely unrolled loops or aligned data with lots of padding, when in fact on a macro-scale those things will certainly affect performance negatively due to cache misses. My preferred approach when optimising is to go for size first; then if more speed is desired, carefully apply size-increasing optimisations to areas which may benefit, testing with a macro benchmark to judge any improvement.
- jhallenworld 6y ago
  I've found an interesting converse with macro benchmarks: small improvements to any of the top functions shown in your profiler output will have a relatively larger than expected effect on the overall speed. I mean you make a change that improves just one function by a little bit on its own (within the benchmark), but the overall is better than this. I think you end up freeing resources used by everything else. The trick is to optimize the right macro benchmark- one that matches your customer's key use case I suppose.
- YZF 6y ago
  If the macro scale is dominated by the code you're optimizing, which is often the case, let's say some inner loops of a codec, signal processing, etc. then the cache misses that may follow aren't really a concern. Obviously(?) taking some random code that doesn't run frequently and trying to optimize it won't make a difference. Microbenchmarks are pretty useful in this context since they let you iterate faster. More generally the question is what is the bottleneck, if the bottleneck is fetching stuff into caches then that's what you optimize for, if the bottleneck is some computation that is running from caches then that's what you optimize...
  - jeffbee 6y ago
    The big cautionary tale of microbenchmarking is memcpy. If you look at the Gnu memcpy, it's ridiculously long and obviously been guided by extensive benchmarking. And memcpy often shows up in profiles, so it is a big target. But in real systems a small simple loop will perform better due to icache pressure.
staycoolboy 6y ago
That was my first thought. Not sure what compiler OP is using but I would put "#pragma align" all over the place and see if the absence still makes a difference.
- guerrilla 6y ago
  That wouldn't help if they're generating ELF files as .rodata is a string table, meaning it's tightly packed and as far as I know neither clang nor gcc pads it.
  - staycoolboy 6y ago
    Ah, I didn't think of that.
guerrilla 6y ago
I'm pretty sure this is it. Changing the number of pointers shouldn't matter as they're already aligned but the string is an odd number of characters, which would change the offset of pretty much every other constant string and thus the performance of the respective lookups. They were probably just very lucky that it was aligned so well before removing it.
albertzeyer 6y ago
But if this is the reason, does it make sense to leave it in then? I.e. to unroll this here: https://github.com/google/wuffs/commit/6537a817b7f8351cded8771fc574f7f7484c99fa https://github.com/google/wuffs/commit/6537a817b7f8351cded87... I guess, maybe once another global constant is introduced somewhere else, this might have exactly the same effect. But also, once there are more unrelated changes, everything will change anyway again. It seems strange then to keep this in because right now this seems to help.
lmilcin 6y ago
I have worked on algorithmic trading where you basically stare at instructions and try to ensure the CPU does not stall on branches, that memory is accessed in a strided pattern recognizable to the CPU and that there are no more concurrent patterns that CPU can coordinate, that memory written does not by accident belong to another core, etc. What is "mystery" in the article is actually bread and butter of anybody who tasked to seriously optimize a piece of non-trivial code.

by dzdt 6y ago

codezero 6y ago

Yep, I'm not even a hobbyist in this area, and immediately wondered if there was an alignment change because of it. With that said, it sounds like at least with GCC, a global constant would go in the TEXT section of the binary and I can't think of why that would affect performance, especially since the variable was seemingly unused. Neat, I hope someone finds the thread to pull here :)

kijiki 6y ago
> ...a global constant would go in the TEXT section of the binary... Wouldn't it go into the .rodata section, not .text?
- codezero 6y ago
  I'm not sure, I am parroting what I thought I read on SO - so you are much more likely to be right, sorry about that!
  - vivekseth 6y ago
    clang seems to work this way, and macOS aliases gcc -> clang by default. Wrote more about this here: https://news.ycombinator.com/item?id=23634495 https://news.ycombinator.com/item?id=23634495
    - codezero 6y ago
      Thanks! Glad there's an explanation for my confusion :)
tom_mellior 6y ago
> it sounds like at least with GCC, a global constant would go in the TEXT section of the binary I don't know why you think it sounds like that, but GCC (on Linux) puts global constants into the .rodata section (read-only data) and other global variables into the .data section. > I can't think of why that would affect performance, especially since the variable was seemingly unused. I'm guessing data alignment and corresponding changes in cache hits and misses. But I wonder if there's a scenario where this change changes the offsets of other variables from the base of the data section, which changes the encodings and therefore the sizes of the instructions accessing those variables, which overall changes code size and might cause code alignment issues. Probably too far-fetched.
- vivekseth 6y ago
  On macOS, "gcc" puts strings that don't include a null byte in the TEXT section. I put quotes around gcc, since it seems that by default macOS aliases gcc to clang. You can run the program I built here to see for your self: https://github.com/vivekseth/blog-posts/tree/master/Jump-Address-Hacking-to-Execute-Code-Stored-as-a-String https://github.com/vivekseth/blog-posts/tree/master/Jump-Add... Since the string in the TEXT section, we can actually execute it as if it were code! After you build the program you can run `otool -t ./a.out` to verify that the string `execString` is indeed in the TEXT section.
  - tom_mellior 6y ago
    Interesting. And if you put a null byte at the end of that character array, it would put it in a different section? I don't have access to MacOS, but I would be interested in seeing the output of clang -S on that code (with and without a null byte), maybe you could add it to the repository?
    - vivekseth 6y ago
      If I'm remembering correctly (this was from 3 years ago), the string was moved to a different section if it had a null byte in the middle of the string. That's why coming up with the assembly I used was kinda tricky. Here's the output as-is: https://gist.github.com/vivekseth/20f319d2a9978af57d926b649adc0bde https://gist.github.com/vivekseth/20f319d2a9978af57d926b649a... Here's the output with a null byte in the middle: https://gist.github.com/vivekseth/fc50319aaac24588bcf568209bf6df8e https://gist.github.com/vivekseth/fc50319aaac24588bcf568209b... From what I can tell, it seems like both strings are in the TEXT section now. Maybe something changed, or I'm remembering incorrectly.

muth02446 6y ago

here is a related paper: https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13....

nwallin 6y ago

This is probably the answer. I watched a great talk about this, and how to avoid problems that result from it. The presenter built a framework that made random changes to alignment of various blocks of code with two different versions of the same microbenchmark until it had high statistical confidence that either one was faster than the other, or it would eject and say that the difference between the two was statistically insignificant. Or something along those lines. I'm looking for the video now, but I can't find it. Pretty sure it was CppCon but I'm not positive.

kristjansson 6y ago
https://news.ycombinator.com/item?id=23634519 https://news.ycombinator.com/item?id=23634519 :)
moonchild 6y ago
Possibly 'Performance Matters'? (https://www.youtube.com/watch?v=r-TLSBdHe1A https://www.youtube.com/watch?v=r-TLSBdHe1A)
- dkersten 6y ago
  This was the very first thing I thought of when I saw this submission title! Great talk, well worth watching.
- Twirrim 6y ago
  My team watched this several months ago now. "Eyeball statistics" he mentions at one stage has been a phrase that has particularly stuck for us from it. So many metrics dashboards etc rely on it to a disturbing degree, if you step back and really think about what it's _actually_ showing you. I almost want to put a warning banner on most of ours. "Beware Eyeball Statistics!"
  - nwallin 6y ago
    The other one is 99th percentile latency. Lots of people think of 99th percentile latency as the latency that 1% of their users will encounter. But if your site loads 200 assets, almost every site load will hit 99th percentile latency.

kristjansson 6y ago

This[1] talk from Emery Berger at last year's Strange Loop does a good job discussing the impact of alignment and other 'small' changes on performance, and how to estimate the actual impact of changes on performance [1]: https://www.youtube.com/watch?v=r-TLSBdHe1A https://www.youtube.com/watch?v=r-TLSBdHe1A

userbinator 6y ago

This is one of the reasons why I think microbenchmarks are either not very useful or completely misleading --- they'll favour things like insanely unrolled loops or aligned data with lots of padding, when in fact on a macro-scale those things will certainly affect performance negatively due to cache misses. My preferred approach when optimising is to go for size first; then if more speed is desired, carefully apply size-increasing optimisations to areas which may benefit, testing with a macro benchmark to judge any improvement.

jhallenworld 6y ago
I've found an interesting converse with macro benchmarks: small improvements to any of the top functions shown in your profiler output will have a relatively larger than expected effect on the overall speed. I mean you make a change that improves just one function by a little bit on its own (within the benchmark), but the overall is better than this. I think you end up freeing resources used by everything else. The trick is to optimize the right macro benchmark- one that matches your customer's key use case I suppose.
YZF 6y ago
If the macro scale is dominated by the code you're optimizing, which is often the case, let's say some inner loops of a codec, signal processing, etc. then the cache misses that may follow aren't really a concern. Obviously(?) taking some random code that doesn't run frequently and trying to optimize it won't make a difference. Microbenchmarks are pretty useful in this context since they let you iterate faster. More generally the question is what is the bottleneck, if the bottleneck is fetching stuff into caches then that's what you optimize for, if the bottleneck is some computation that is running from caches then that's what you optimize...
- jeffbee 6y ago
  The big cautionary tale of microbenchmarking is memcpy. If you look at the Gnu memcpy, it's ridiculously long and obviously been guided by extensive benchmarking. And memcpy often shows up in profiles, so it is a big target. But in real systems a small simple loop will perform better due to icache pressure.

staycoolboy 6y ago

That was my first thought. Not sure what compiler OP is using but I would put "#pragma align" all over the place and see if the absence still makes a difference.

guerrilla 6y ago
That wouldn't help if they're generating ELF files as .rodata is a string table, meaning it's tightly packed and as far as I know neither clang nor gcc pads it.
- staycoolboy 6y ago
  Ah, I didn't think of that.

guerrilla 6y ago

I'm pretty sure this is it. Changing the number of pointers shouldn't matter as they're already aligned but the string is an odd number of characters, which would change the offset of pretty much every other constant string and thus the performance of the respective lookups. They were probably just very lucky that it was aligned so well before removing it.

albertzeyer 6y ago

But if this is the reason, does it make sense to leave it in then? I.e. to unroll this here: https://github.com/google/wuffs/commit/6537a817b7f8351cded8771fc574f7f7484c99fa https://github.com/google/wuffs/commit/6537a817b7f8351cded87... I guess, maybe once another global constant is introduced somewhere else, this might have exactly the same effect. But also, once there are more unrelated changes, everything will change anyway again. It seems strange then to keep this in because right now this seems to help.

lmilcin 6y ago

I have worked on algorithmic trading where you basically stare at instructions and try to ensure the CPU does not stall on branches, that memory is accessed in a strided pattern recognizable to the CPU and that there are no more concurrent patterns that CPU can coordinate, that memory written does not by accident belong to another core, etc. What is "mystery" in the article is actually bread and butter of anybody who tasked to seriously optimize a piece of non-trivial code.