10 ms·
Print(“lol”) doubled the speed of my Go function
- schemescape 3y agoWhy is there a "continue" at all in the first code sample? Edit to add: does removing it make any difference?
- ludiludi 3y agoGood question. As you can see in the comment in the github repo, it has no effect. https://github.com/ludi317/max/blob/master/blog/max_test.go#L12 https://github.com/ludi317/max/blob/master/blog/max_test.go#... It is there only to match the continue in the second code sample, where it is needed.
- schemescape 3y agoThanks! In that case, I have to say I'm surprised. I assumed the code generated for the loop would have an instructions that branches, so adding another branching instruction could only hurt (edit: not necessarily a lot), but apparently my intuition is wrong. I'm curious if the performance difference noted in the article happens on Intel/AMD as well...
- fmstephe 3y agoAccording to the godot compiler explorer removing the `continue` makes no difference to the generated assembly. https://godbolt.org/z/ds1raTYc9 https://godbolt.org/z/ds1raTYc9 https://godbolt.org/z/rbWsxM83b https://godbolt.org/z/rbWsxM83b The `print("lol")` output looks remarkably different. https://godbolt.org/z/c3afrb6bG https://godbolt.org/z/c3afrb6bG
- rep_lodsb 3y agoIt is there to skip the print("lol") in the second version if the condition is true. Since the array is sorted in ascending order, it will be true for every value, and that print is never be executed.
- nemetroid 3y agoThe inclusion of ”continue” in the non-lol version is pointless and obscures the actual reason for the difference: the addition of the non-pointless ”continue” in the lol version. As other comments point out, this construct can be replaced by a cmov instruction: if a > b: b = a The following construct however, cannot be replaced by cmov: if a > b: b = a continue Only by first eliminating the pointless "continue" is this replacement valid. But by including it, you can make it look like it's the 'print("lol")' is what makes the difference, which is only true lexically.
- ahazred8ta 3y agounrelated: a few months ago you were asking about small language runtimes https://docs.micropython.org/en/latest/ https://docs.micropython.org/en/latest/
- bakul 3y agoProcessor "optimizations" can produce surprising effects. The problem is these optimizations are not programmatically accessible to C (or most modern programming languages) given their simple memory model. Deterministic performance is not easy to obtain. My view is to not bother with such tricks unless absolutely necessary (and be prepared that your changes may actually pessimize performance on a future processor or a compatible processor by a different vendor). If you are interested in this sort of thing, check out comp.arch!
- mcv 3y agoI would agree, but it's hard to argue with a factor 2 performance boost. But these kind of tricks feel like we need to con the compiler into optimising this correctly, which is of course ridiculous. What we probably need instead is if-statements that we can tell what's most likely the correct prediction. Something like: if v > maxV predict true maxV = v continue
- deleted 3y ago[deleted]
- Zinu 3y agoIt's only factor 2 with an increasing array though. At which point you can just take the last element, that's way faster. So really you end up having to make assumptions about the input to get the performance boost.
- Majromax 3y agoThe text does point out that the branch is somewhat predictable even for a random array. In that case, the odds of having seen the array-maximum increase as you scan through the array. For example, on a random array I would predict the first iteration to take the branch 1/2 of the time, but the last iteration to take the branch only 1/N of the time. The CPU's branch predictor won't be able to perform that kind of algorithmic analysis, but patterns like the above also work reasonably well for simpler heuristics like 'predict the same outcome as the last time the branch was taken'.
- dataflow 3y agoI read it and I still don't get it, can someone (re-)explain what the presence of the print() is doing that is helpful for branch prediction (or any other aspect of the CPU)? Update: It seems to be the conditional move, see https://news.ycombinator.com/item?id=37245325 https://news.ycombinator.com/item?id=37245325
- trolan 3y agoI'm in school, so this may be oversimplified, but if the processor/assembly code is predicting the next result, it gets the result faster. The processor only does this prediction with conditional branches. The extra if for printing or finding the min invoke the prediction with the accuracies stated.
- dataflow 3y ago> The processor only does this prediction with conditional branches This sounds... wrong? Unless ARM64 is designed in an absurd way? I'd love to see the full disassembly; something seems funny here. If it was x86 I would say it's a conditional move causing this, but I don't know what's going on on ARM.
- fmstephe 3y agoIt's interesting that you say conditional move here. I am confused by this behaviour, and although I definitely don't know what the answer is here; the non-lol version does have a CSEL (https://developer.arm.com/documentation/dui0802/b/CSEL https://developer.arm.com/documentation/dui0802/b/CSEL) which is totally missing from the lol version. Non-lol https://godbolt.org/z/ds1raTYc9 https://godbolt.org/z/ds1raTYc9 lol https://godbolt.org/z/c3afrb6bG https://godbolt.org/z/c3afrb6bG
- dataflow 3y agoAh there you go, that's the conditional move on ARM. Yeah, those are slow.
- cyphar 3y agoIn the Linux kernel, there are unlikely() and likely() macros which indicate to the compiler whether or not a condition is likely using __builtin_expect (which then influences the output assembly into producing code that should make the branch predictor do the right thing more of the time). Unfortunately, the issue here is that the performance depends on the input and so such hints wouldn't help (unless you knew a-priori you were dealing with mostly-sorted data). Presumably the min-max (and lol) versions perform worse for descending arrays?
- nomel 3y agoIt's nice using these to mark less-likely, but latency sensitive, paths, which is something that profiler guided optimization can't do.
- zhzy0077 3y agoI'm a noob. Looking at the disasm: https://godbolt.org/z/766aPTPc3 https://godbolt.org/z/766aPTPc3 It turns a CMOVQLT to a JLT. Is the blog saying CMOVQLT don't have branch predication? I don't get it.
- ludiludi 3y agoYour disasm is for x86-64. The benchmarks in the blog were run on an M1 MacBook Pro, which is an ARM64.
- zhzy0077 3y agoSorry. My bad. But looking at ARM64 https://godbolt.org/z/YEjGKce1Y https://godbolt.org/z/YEjGKce1Y The difference is CSEL and BLT. The question still stands. Does CSEL have no branch predication?
- ludiludi 3y agoIt appears so. https://developer.arm.com/documentation/102374/0101/Program-flow---conditional-select-instructions https://developer.arm.com/documentation/102374/0101/Program-... "So far, we have seen examples that use branches to handle decisions. The A64 instruction set also provides conditional select instructions. In many cases, these instructions can be used as an alternative to branches." Seems CSEL is not a branch.
- masklinn 3y agoCSEL is a conditional move, they’re usually used to avoid branches (and branch predication) entirely. Here it turns out to be a very bad choice, because it creates unnecessary data dependencies. But a cmov would be a fine choice if the branch was impossible to predict (e.g. if the input was random, well even then I’d expect the limit to mostly creep up so it should be predicated as mostly cold).
- perryizgr8 3y agoWhy would an unconditional print have any effect on whether the branch predictor is invoked or not? The if statement is there in both cases, so branch prediction should kick in for both. I didn't find an explanation for this behaviour in the article.
- projektfu 3y agoIt has to make a decision to jump over the print sequence or not, whereas without the print it can eliminate the branch with a conditional move and only have to predict the loop variable. It just makes a bad guess as to whether branch prediction or conditional move will be faster, as explained above by tylerhou.
- masklinn 3y agoThe go compiler might have a heuristic where a branch with IO is considered cold compared to a branch without. In the original, it essentially faces If <cond>: Mov Else: Noop Considering these branches unpredictable, it generates a CMOV. With If <cond>: Mov Else: Print It now considers the first branch hot and the second cold, and thus branch predication valuable, and generates a branch instead. Turns out for the use case choice (1) is a misfiring, as the branch is extremely predictable, so all the conditional move does is create an unnecessary data dependency. It’s not necessarily the wrong choice in general, as for unpredictable branches cmov will usually be a huge gain, they’ll incur a cycle or two of latency but save from 15+ cycles of penalty on a mispredicted branch (which if the prediction only works half the time is an average 7.5 cycles per iteration). You can find older posts which demonstrate that side of the coin e.g. https://owen.cafe/posts/six-times-faster-than-c/ https://owen.cafe/posts/six-times-faster-than-c/
- Someone 3y ago> Turns out for the use case choice (1) is a misfiring, as the branch is extremely predictable Happens to be extremely predictable for this data. In general, over all possible inputs, it’s not extremely predictable. If you assume all inputs are different (not something the compiler can assume, of course) the probability of having to update the max value goes down from 1 for the first iteration to 1/n for the last, so, possibly, the loop should be split into two halves. Go through the start of the sequence assuming the value needs updating more often than not, and switch to one where it doesn’t at some point. For truly large inputs you could even add heuristics looking at how much room there is above the current maximum (in the limit, if you’ve found MAX_INT, you don’t have to look further) Sorting programs used to have all kinds of such heuristics (and/or command line arguments) trying to detect whether input data already is mostly sorted/mostly reverse sorted, how many different keys there are, etc. to attempt avoiding hitting worst case behavior, but I think that’s somewhat of a lost art
- Syrail_ 3y agoI think this is a case of mis-assigned blame (on the tool’s part, not the author’s). My semi-educated guesswork follows: Looking at the disassembly screenshots in the article, the total runtime for the benchmark doesn’t appear to have decreased by very much. “Time per op” has decreased by half in max_lol(), but the total number of ops being performed has likely increased, too - Specifically, extra work was done “for free” (As was shown in min_max). This experiment is showing us that the compiler is in fact doing exactly what we want - maximizing throughput in the face of a stall by pipelining! In this experiment, maxV is potentially being written to with each iteration of the loop. Valid execution of the next iteration requires us to wait on that updated value of maxV. This comparison and write takes longer than just running an instruction - it’s a stall point. In the first profile, the compare instruction gets full credit for all the time the CPU is stalled waiting on that value to be written - there’s nothing else it can be doing at the time. In the other profiles, we see a more “honest” picture of how long the comparison takes. After the compare instruction is done, we move on to other things which DON’T rely on knowing maxV - printing “lol”, or doing the other compare and write for minV. I propose that the processor is doing our added work on every iteration of the loop, no matter what (And why not? Nothing else would be happening in that time). That BLT instruction isn’t making things faster, it’s just deciding whether to throw away the results of our extra work or keep it. Throughput is important, but not always the same thing as speed. It’s good to keep that in mind with metrics like ops/time, particularly if the benchmarking tool tries to blame stuff like cache misses or other stalls on a (relatively) innocent compare instruction!
- dmurray 3y agoYes, this part seems wrong > Following standard practice, I use the benchstat tool to compare their speeds That tool (at least as used here) would be suitable for comparing execution of the same code between two processors with the same architecture. For comparing different programs on the same architecture, you need a different tool that focuses on total execution time.
- _cenw 3y agoGo can have unexpected performance differences way higher up in the stack. Ask me about that one time I optimized code that was deadlocking because the Go compiler managed to not insert a Gosched[1] call into a loop transforming data that took ~30 minutes or so. The solution could've been to call Gosched, but optimizing the loop to a few seconds turned out to be easier. I assume the inverse - the go compiler adding too many Goscheds - can happen too. It's not that expensive - testing a condition - but if you do that a few million times, things add up. [1]: https://pkg.go.dev/runtime#Gosched https://pkg.go.dev/runtime#Gosched
- morelisp 3y agoThe Go scheduler is now (well, for years) preemptive.
- smcl 3y agoDoes Go have any facility for providing hints to the optimiser (like how some C compilers support #pragmas) that could cause the branch-predicted instruction to be used rather than the slower one?
- grose 3y agoSeems like the answer is no[1] and profile-guided optimization is recommended instead, https://go.dev/doc/pgo https://go.dev/doc/pgo. I would be curious to see if pgo helps with the author's use case. [1] https://groups.google.com/g/golang-nuts/c/1erdKe3aV5k https://groups.google.com/g/golang-nuts/c/1erdKe3aV5k
- smcl 3y agoAh thanks! That's interesting but a bit weird to me. That response sounds a little bit like someone who feels like they shouldn't do something and is thinking on-the-fly for reasons they can use to justify that feeling. > We don't want to complicate the language So I can understand if this complicates the implementation but I don't know if totally optional pragmas or annotations complicates the language itself. Like C has this but I don't think people say "Ah C is alright but the pragmas are a bit confusing and make things complicated". > experience shows that programmers are often mistaken as to whether branches are likely or not Your average programmer may mess that up, but those who would give optimisation hints aren't quite your average programmer. And insisting on introducing PGO to your build process (so build, run-with-profile, rebuild-with-profile) for some cases where someone isn't mistaken as to whether branches are likely (or whether some loops run minimum X times, etc) feels a bit needless. Please remember though that I'm neither a Go programmer nor contributor so I'm really just an outsider looking in, it could be that this is a total non-issue or is really low-priority.
- anentropic 3y agoNot giving you nice things because "Your average programmer may mess that up" is the whole philosophy of Go though
- vsnf 3y agoKind of tangential, but who are these people who are so comfortable with disassembling a high level language binary, reading assembly, and then making statements about branch prediction and other such low level esoterica? I've only ever meet people like that maybe two or thee times in my career, and yet it seems like every other blog post I read in certain language circles everyone is some kind of ASM and Reverse Engineering expert.
- Smaug123 3y agoThere are many ways you can get to this point (e.g. I just sort of picked this kind of thing up), but an example of a course which is designed precisely to give you these skills is Casey Muratori's "Performance-Aware Programming".
- distcs 3y agoI don't think I'd call "branch prediction" as "low level esoterica". It is a basic fact about how CPUs are implemented since many decades now. I learnt these things in my university coursework. Any module on CPU or computer system architecture is going to teach you all this stuff. But I'm sure you could learn these things from books on this topic too.
- mcv 3y agoI didn't, and frankly, half of the articles I read about it make me think branch prediction is a bug. I mean, I know it's meant to improve performance, which is great, but it has to make assumptions about what's going to happen before it knows it, and those assumptions are going to be wrong. How wrong? How can we con it into making better assumptions? Suddenly programming becomes about second guessing the compiler. And remember Spectre and Meltdown? Security vulnerabilities caused by branch prediction. If I recall correctly, the pipeline was executing code it wasn't meant to execute because it's executing it before it knows the result of the check that decides if it has to execute it. Programming is a lot easier if the actual control flow is as linear as I'm writing it. My broad takeaway of the whole ordeal is that I'm basically avoiding if-statements these days. I feel like I can't trust them anymore.
- zerr 3y agoNo explanation whatsoever. Why the branch predictor is not "invoked" in the first version of the function?
- MauranKilom 3y agoBecause it's most likely using a conditional move.
- distcs 3y agoBut I don't see the post going into investigating this at all. Yes, most likely that is what is going on but I don't understand the point of the OP post is if the real reason of the difference in the branch predictor behavior is not explained.
- Exuma 3y agoThere’s a go course that was really good about this level of nuance. He talks a lot about mechanical sympathy and how to dig in detail with this. I think it’s called ultimate go?
- AshleysBrain 3y agoMost languages have a `max` function, so the core of the loop could be written with just something like: `maxV = max(maxV, v)` That could be entirely branchless, right?
- assbuttbuttass 3y agoA max function still compiles down to some kind of branch
- AshleysBrain 3y agoI thought there were specific assembly instructions for this kind of thing, such as MAXSS in x86 [1], plus vector variants like SSE4 PMAXSD. Presumably it's possible the CPU can handle those with special branchless logic, depending on the compiler and CPU implementation. I guess you'd have to know about the CPU internals to know if the instruction is truly branchless, but it is branchless in the sense there is no conditional jump made in the assembly instructions. [1] https://stackoverflow.com/questions/40196817/what-is-the-instruction-that-gives-branchless-fp-min-and-max-on-x86 https://stackoverflow.com/questions/40196817/what-is-the-ins...
- tjalfi 3y agoclang compiles all three of these functions to use max instructions (https://godbolt.org/z/9z7hGfdhq https://godbolt.org/z/9z7hGfdhq). #include <algorithm> using std::max; int max_array_func(int values[], size_t values_count) { int max_value = values[0]; for (size_t j = 0; j < values_count; j++) { max_value = max(max_value, values[j]); } return max_value; } int max_array_bittwiddling(int values[], size_t values_count) { int max_value = values[0]; for (size_t j = 0; j < values_count; j++) { int x = max_value; int y = values[j]; // http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax max_value = x ^ ((x ^ y) & -(x < y)); } return max_value; } int max_array_branch(int values[], size_t values_count) { int max_value = values[0]; for (size_t j = 0; j < values_count; j++) { if (max_value > values[j]) { max_value = values[j]; } } return max_value; }
- Liquid_Fire 3y agoI was curious what this strange assembly language was, as it looked like neither Arm nor x86. Apparently the Go toolchain has its own assembly language which partially abstracts away some architectural differences: https://go.dev/doc/asm https://go.dev/doc/asm I wonder what the advantages are? It feels like as soon as you move away from the basics, the architecture-specific differences will negate most usefulness of the abstraction.
- rob74 3y agoI guess it's for historical reasons. As the document you linked states, "The assembler is based on the input style of the Plan 9 assemblers". It's important to know that at least two of the "founding fathers" of Go (Rob Pike and Ken Thompson) are ex-Bell Labs guys and were involved with Plan 9. The Plan 9 compiler toolchain was available, they were familiar with it, so that's what they used for Go. Some parts of the toolchain (the linker, I think) have been swapped out in the meantime, but the assembly format has stayed. EDIT: found the document talking about changing the linker: https://docs.google.com/document/d/1D13QhciikbdLtaI67U6Ble5d_1nsI4befEd6_k1z91U/view#heading=h.g4m43nddv64t https://docs.google.com/document/d/1D13QhciikbdLtaI67U6Ble5d... . Favorite quote: > The original linker was also simpler than it is now and its implementation fit in one Turing award winner’s head, so there’s little abstraction or modularity. Unfortunately, as the linker grew and evolved, it retained its lack of structure, and our sole Turing award winner retired. ...which is referring to Ken Thompson I guess.
- yencabulator 3y agoIt's not just historical, it's more "the same justification as back then".
- yencabulator 3y agoRob Pike's talk The Design of the Go Assembler from GopherCon 2016: https://www.youtube.com/watch?v=KINIAgRpkDA https://www.youtube.com/watch?v=KINIAgRpkDA
- deschutes 3y agoThe explanation is not convincing. My guess is some kind of measurement error or one of the "load bearing nop" phenomena. By that I mean the alignment of instructions (esp branch targets?) can dramatically affect performance and compilers apparently have rather simplistic models for this or don't consider it at all.
- romshark 3y agoI tried to come up with the most efficient implementation of this rather simple function that I could think of with pure Go without going down to SIMD Assembly: https://go.dev/play/p/zHFxwvWOoeT https://go.dev/play/p/zHFxwvWOoeT -32.31% geomean across the different tests looks rather great. Any ideas how to make it even faster?