C performance mystery: delete unused string constant

https://github.com/google/wuffs/commit/49023afd48aab68febc55a3561b2e8a0e2635533

by dolmen • 6 years ago

153 105 6 years ago

dzdt• 6 years 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.

codezero4• 6 years 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• 6 years ago

...a global constant would go in the TEXT section of the binary...

Wouldn't it go into the .rodata section, not .text?

tom_mellior4• 6 years 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.

muth02446• 6 years ago

here is a related paper:

https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13....

nwallin3• 6 years 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.

kristjansson2• 6 years ago

https://news.ycombinator.com/item?id=23634519 :)

moonchild3• 6 years ago

Possibly 'Performance Matters'? (https://www.youtube.com/watch?v=r-TLSBdHe1A)

kristjansson2• 6 years 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

userbinator2• 6 years 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.

YZF• 6 years 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...

jhallenworld• 6 years 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.

GuB-42• 6 years ago

My preferred approach when optimising is to go for size first

Agreed, in my experience, more often than not, size is speed. Small memory usage mean less cache misses, smaller memcpys, more chance of having data fit a single word, etc...

staycoolboy3• 6 years 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.

guerrilla3• 6 years 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.

guerrilla3• 6 years 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• 6 years 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/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• 6 years 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.

AdmiralAsshat• 6 years ago

Isn't this usually where someone sufficiently versed in Assembly would look at the generated assembler code and figure out what changed?

pascal_cuoq• 6 years ago

You need to look at the disassembly of the generated binary to make sense of this sort of performance variation (paying attention to line cache boundaries for code and data), and even so, it is highly non-trivial. The performance counters found in modern processors sometimes help (https://en.wikipedia.org/wiki/Hardware_performance_counter ).

https://www.agner.org/optimize/microarchitecture.pdf contains the sort of information you need to have absorbed before you even start investigating. In most cases, it's not worth acquiring the expertise for 5% one way or the other in micro-benchmarks. If you care about these 5%, you shouldn't be programming in C in the first place.

And then there is this anecdote:

My job is to make tools to detect subtle undefined behaviors in C programs. I once had the opportunity to report a signed arithmetic overflow in a library that its authors considered, rightly or wrongly, to be performance-critical. My suggestion was:

… this is not one of the subtle undefined behaviors that we are the only ones to detect, UBSan would also have told you that the library was doing something wrong with “x + y” where x and y are ints. The good news is that you can write “(int)((unsigned)x + y)”, this is defined and it behaves exactly like you expected “x + y” to behave (but had no right to).

And the answer was “Ah, no, sorry, we can't apply this change, I ran the benchmarks and the library was 2% slower with it. It's a no, I'm afraid”.

The thing is, I am pretty sure that any modern optimizing C compiler (the interlocutor was using Clang) has been generating the exact same binary code for the two constructs for years (unless it applies an optimization that relies on the addition not overflowing in the “x + y” case, but then the authors would have noticed). I would bet a house that the binary that was 2% slower in benchmarks was byte-identical to the reference one.

voldacar• 6 years ago

If I may ask, what was the use case for this code that they cared so much about a 2% difference in benchmarks? Aerospace? Game engine? Packet routing?

gnufx• 6 years ago

Performance counters are vital, and you don't need to grovel the disassembly yourself in association with profiling, even if it's feasible. Get a tool to do it for you; MAQAO is one in that area (x86-specific, and unfortunately part-proprietary).

Anyway, yes, measurements are what you need, rather than guesses, along with correctness checks, indeed.

saagarjha3• 6 years ago

I've had this exact situation happen to me as well :/ It's frustrating.

cybervasi• 6 years ago

I am guessing your tool was source based to even detect this, let alone the fact that the code change would have produced the identical code.

moonchild3• 6 years ago

The presence (or absence) of a global variable has no effect on the rest of the generated code. Nothing changed. You could possibly look at the alignment of the in-memory representation generated by the relocator,runtime dynamic linker. Likely, some bits of code are now on the same cache line that were previously separate, and vice versa.

ufo2• 6 years ago

When weird performance things like this happens, it can be helpful to test in other environments. If the performance change does not happen in other operating systems or hardware then it suggests that the weird performance you are observing could be due to an unusual coincidence in your particular system.

That said, if you do want to figure out why deleting that global variable made a difference then using Linux's perf tool might give you more informationto work with. One time I had a weird program where inserting a NOP instruction in a certain location made it run twice as fast. After investigation we found out that the difference was with branch prediction. The presence or absence of that NOP instruction affected the addresses of the jump targets the inner loop's switch statement. For some reason, the version without the NOP instruction those addresses resulted in lots of branch mispredictions. Perhaps because of a collision in the branch predictor's hash tables.

MauranKilom• 6 years ago

Are you sure it wasn't just instruction alignment? Inserting nops before loop jump targets to align the first loop body instruction to 8 or 16 bytes is a very common x86 thing most compilers do. See e.g. https://reverseengineering.stackexchange.com/a/2930.

ufo2• 6 years ago

Would that explain the large difference we observed in the "branch-misses" statistic when we ran it under "perf stat"?

SomeoneFromCA2• 6 years ago

I remember changing a _constant_ int into a volatile global variable, and my code became 4 times faster. It was on Ubuntu 16.04. I might actually find code and post here later.

sfblah• 6 years ago

I worked on some code once for an app that would crash if you added a comment in a specific place. We removed the comment and then added a comment asking developers not to re-add the comment.

IAmLiterallyAB• 6 years ago

Was it a language where the comment would be compiled out ahead of time? Or still present at runtime like JS

a_t48• 6 years ago

It didn't happen to end with a '\' did it? :)

gaogao• 6 years ago

Oh nice, we had a load bearing comment too at work.

staycoolboy3• 6 years ago

Interesting. Were you writing a kernel driver? I've only ever used 'volatile' in embedded code where an ISR is touching a variable outside the scope to prevent the compiler from optimizing the code away. What were using 'volatile' for?

SomeoneFromCA2• 6 years ago

No it was some random debugging of Leet Code style excercise, some useless math computation. I just was throwing every possible change, till one worked. I knew that code had to be fast than it was, because with PGO it was very fast.

acqq3• 6 years ago

As far as I see, the source code of the library is not plain C but .go, which is then transpiled to .c

Anyway, even if what we see in the resulting .c is "just some missing string" it's not necessarily obvious how the strings are supposed to be handled in the whole .c domain. Specifically, it can be that some other constants (even not necessarily sting constants, but the constants in the same segment where the string constants are!) are being used very frequently by the code which is measured (let's call them "hotter" constants), and the removal of that one string constant simply affected the placement of the "hotter" constants).

In short, I suspect that the deletion of the constant is not the only way to get different results, but that the different results would also happen even when changing the order of the definition of constants, without removing any of them.

So the way I would attack that problem, if it would be desired to fix the performance issues, is: I'd measure the access of all the constants in the same segment, and identify which are used during the whole run of these benchmarks -- those are "hot." The solution is then to modify the code to be less dependent on such constants inside of the "hot" loops. Often the number of these that have to be fixed is low, but it's also possible it's otherwise.

So I believe it's not that much a mystery as it appears to be. (I have even more specific experiences and also suggestions. And I'm also looking for a new dream remote job. Anybody needs this kind of expertise, for some reasonable longer term, or shorter term but seriously paid?)

terminalcommand• 6 years ago

Watching used constants and trimming them to fit the cache seems like a good idea. I'm a total noob PC-architecture wise so apologies beforehand, but doesn't the CPU handle the caching of most used memory locations itself? If there are an equal number of hot constants, how does changing the order of them help performance? CPU is going to cache the most used locations anyway. In this example, the constant was never used, so there is no reason for the CPU to cache it.

BTW, adding some contact info to your HN profile could help in the job search. Best of luck!

acqq3• 6 years ago

doesn't the CPU handle the caching of most used memory locations itself?

Yes but caches aren't "never failing magic". You can imagine them as the mechanisms that allow saving some work in some scenarios. If the work thrown at them is different from their limitations, worse results aren't surprising.

If there are an equal number of hot constants, how does changing the order of them help performance? CPU is going to cache the most used locations anyway.

The caches have some limitations by design. It's easy to construct the code which stresses the caches more, and sometimes just the position of elements accessed can influence the "congestion" points due to the changed mapping between the addresses and the elements accessed.

adding some contact info to your HN profile

Thanks. I still hope that if there's a real interest the contact happens in spite of not being exceptionally easy -- also a kind of filter.

rurban• 6 years ago

He should experiment with shortening his ENV vars one byte by one, to see similar benchmarking effects. It process affects alignment, and if you unlucky bad alignment can cost a few percent.

moonchild3• 6 years ago

deleting this one line of code can have a dramatic effect on seemingly unrelated performance micro-benchmarks. Some numbers get better (e.g. +5%), some numbers get worse (e.g. -10%). The same micro-benchmark can get faster on one C compiler but slower on another

There's a fundamental disconnect that makes it difficult for humans to reason about performance in computer programs. Because the speed of light is so slow, computer architecture as we know it will always rely on cache and OoO to be fast. The human brain does seem to work out of order, but it's only used to thinking about a world that runs in order. When we use theory of mind, we don't model other people's minds, we use our own as a model for theirs; see mirror neurons[1].

Because of this, standard code benchmarks are not very useful, unless they can demonstrate order-of-magnitude speedups. Even something like a causal profiler[2][3][4], which attempts to control for the volatile aspects of performance, is of limited use; it cannot control for all variables and its results will likely be invalidated by the same architectural variation it tries to control for. Instead (with respect to performance) we should focus on three factors:

- Code maintainability

- Algorithmic complexity

- Cache coherency

Everything else is a distraction.

1. https://en.wikipedia.org/wiki/Mirror_neuron

2. https://www.youtube.com/watch?v=r-TLSBdHe1A

3. https://arxiv.org/pdf/1608.03676v1.pdf

4. https://github.com/plasma-umass/coz

dleslie• 6 years ago

There's a major caveat: if you know the hardware won't change and you control the software stack throughout.

Game consoles, unikernels and the like apply here.

viraptor2• 6 years ago

I'm not sure I understand why they revert the change. You get random small +/- changes in performance with the change, but you get slightly cleaner code. What's the reason not to want that?

d_tr• 6 years ago

I wondered the same. These are microbenchmarks after all and it does not even seem like a clear win.

rybosworld• 6 years ago

They might be hesitant to check in a change that causes a behavior they don't understand. This is a good mindset imo.

viraptor2• 6 years ago

I feel like there's a (sometimes blurry) line between being hesitant about dangerous changes (good thing) and hoping that if you ignore something you don't understand, it will keep working as you expect (not a good thing).

Purely leaving an unused variable in place due to weird impact on performance is in the second category for me. But maybe there are other aspects - that's why I'm curious and asking about it

nigeltao6• 6 years ago

Sorry that the commit message wasn't clearer.

Letting "foo" denote "wuffs_base__note__i_o_redirect", it wasn't really that "foo was unused", it was that "foo was unused, after the previous (artificial) commit renamed all-but-one of the foo references to another existing string constant". That previous commit set it up so that this commit, which exhibits the performance difference, has a trivially small diff. But the two commits combined to remove a "foo" that was actually in use, so the combination was rolled back.

The previous commit is https://github.com/google/wuffs/commit/844fc9b5eeef46edab49c...

thrownaway954• 6 years ago

I have to admit... I get a "geek on" whenever I read C programmer commit messages. I don't know what it is but those people know how to write detailed, interesting and often entertaining commit messages. This one was a perfect example of all 3.

kjgkjhfkjf• 6 years ago

Removing `const char* wuffs_base__note__i_o_redirect = "@base: I/O redirect";` removes not only the literal string, but also a global non-constant pointer. This perhaps affects various optimizations.

They should have used `const char* wuffs_base__note__i_o_redirect const =` or (preferably) `const char wuffs_base__note__i_o_redirect[] =`.

tom_mellior4• 6 years ago

I can't think of a plausible way in which an unused global would affect compiler optimizations. Could you elaborate?

HelloNurse2• 6 years ago

The pointer probably precedes interesting variables in the same data segment, which therefore shift to a different address that is cached differently.

munro• 6 years ago

I've never heard of this "wuffs" project before, apparently it's a programming language. It looks like a wild project, does anyone have any details what this is?

nigeltao6• 6 years ago

Start at https://github.com/google/wuffs/tree/master/doc

nigeltao6• 6 years ago

I am the commit author.

I wrote that commit on my laptop. I was unable to reproduce this on my desktop.

Re "why does this happen?", it certainly looks like an alignment thing. A more interesting question for me is "what should I do about it?" If future non-trivial changes affect the micro-benchmark numbers, how do I ensure that it's signal and not noise? Do I sprinkle some alignment directives throughout my code and hope for the best? Once the immediate symptoms are gone, how do I know that I've added enough?

Somebody suggested (off-list): "use compiler flags like the combo `-ffunction-sections -falign-functions=N` for values like 16, 32, 64 to help diagnose these issues quickly. You can also look at perf counters to find the problems, but each problem has a different counter so that can be hard. Once you know you have a problem, you can usually write code defensively against the issue. But it requires knowing a lot about the micro-architecture. Things like minimizing branch density, data dependency graph height, etc."

That's all very well (and better suggestions than nothing), but I'm hesitant to hill-climb using different compiler flags from what my users generally do. I also want to avoid over-fitting to my primary (day-to-day) machine or to a particular version of a particular C compiler.

I've also been pointed to https://github.com/ccurtsinger/stabilizer but it sounds tied to LLVM 3.1 and hasn't had any substantial updates since 2013.

mritun• 6 years ago

If you’re only able to reproduce the problem on your laptop, check heat, throttling and power saving.

secondcoming• 6 years ago

Indeed, micro-profiling code on a laptop is generally not that useful

Twirrim2• 6 years ago

It's mentioned elsewhere in this HN discussion, but I think I'd encourage watching this talk: https://www.youtube.com/watch?v=r-TLSBdHe1A. It's particularly relevant to what you're seeing.

nigeltao6• 6 years ago

Yeah, I've watched that video. That's the source of my "I've also been pointed to https://github.com/ccurtsinger/stabilizer but it sounds tied to LLVM 3.1 and hasn't had any substantial updates since 2013."

DougBTX• 6 years ago

How consistently reproducible is it on your laptop? Do the same benchmarks change in the same way every time?

acqq3• 6 years ago

I wrote that commit on my laptop. I was unable to reproduce this on my desktop.

Then please modify the comment in the source to state that.

The described behavior (the speed results unpredictably slightly changing in both directions) of the measurements is actually "normal" on the notebooks with most of the possible thermal configurations and is not something that should be even tried to be "fixed" until the observed effects are actually consistent and big enough to be repeatable without the tight thermal controls.

Edit: of course the pushed commit can't be changed. But the comment (if it is visible in the source -- haven't checked that) can. There should be some kind of a visible "resolution" of the question in the repo.

saagarjha3• 6 years ago

Then please modify the comment to state that.

Please don't modify a commit you've pushed!

nigeltao6• 6 years ago

I haven't written a comment in the source yet, as I haven't further investigated and implemented a work-around yet to hang the comment on. It's low on the priority list.

abetusk• 6 years ago

I'm no expert, but if it is a memory alignment issue, isn't this undefined behavior?

If the string is unused, isn't the compiler free to allocate or not allocate it (unless it has some 'volatile' directive or something)? This means that doing things like turning off/on optimization could yield inconsistent results across machines, across compilers and even across versions of the same compiler.

Is this used for security so that side channel timing attacks can be used to glean information about private data? Is the speed differential noticeable such that someone has created an issue for it? Is exact consistency in speed across different compilers, architectures, etc. a priority of the project?

If the answer is no to all of those, then I find it difficult to justify 'fixing' the issue.

From what I understand, isn't this what GUIX is trying to do? Create consistent byte-for-byte compiled programs? There has to be a trade off between consistency an speed. I also don't know how usable GUIX is or how valuable it is for your use case.

HelloNurse2• 6 years ago

The compiler knows how it's aligning variables, It's a pure performance issue: location of things in memory affects alignment to caching unit boundaries (accessing one more cache line for the same data) and cache pressure (data ends up cached in the same location as something else, causing unnecessary evictions while other cache locations remains underused)

kev009• 6 years ago

VTune will help

gomijacogeo• 6 years ago

Looks like other people are onto the same thing - alignment.

Especially if this is threaded code, what's probably happened is something (likely with some sort of locking primitive) that fit on one cache-line, now straddles two. The reverse is also possible where two items were landing on different cache lines and are now creating a false sharing problem.

It's likely a global and likely in the .bss (which comes immediately after .data, which is why it has alignment troubles when static strings change). It's usually pretty easy to binary search your way to the problematic module and variable.

nigeltao6• 6 years ago

It's single-threaded.

robalni• 6 years ago

This reminds me of when I made a program faster by adding a print statement to it. I am not able to find the program but I was able to create a new one as similar to it as I remember and it seems that this weird trick works in this program too.

When I uncomment the puts("hi") line in the code below, the time it takes to run the program consistently changes from 5.6 to 5.4 seconds on my machine if I compile without optimizations.

#include <stdio.h>

int main() { long tri_side = 1; long tri_area = 1; long sq_side = 1; long sq_area = 1; while (sq_side < 1000000000) { if (sq_area == tri_area) { printf("tri:%ld sq:%ld area:%ld\n", tri_side, sq_side, sq_area); //puts("hi"); } if (sq_area < tri_area) { sq_area += sq_side * 2 + 1; sq_side += 1; } else { tri_area += tri_side + 1; tri_side += 1; } } }

guerrilla3• 6 years ago

I wasn't able to reproduce this but I'm wondering if it could have to do with buffer flushing. puts may implicitly do whatever fflush(stdio) does. [1]

[1]. https://linux.die.net/man/3/fflush

C performance mystery: delete unused string constant

Related Stories