Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Print(“lol”) doubled the speed of my Go function

medium.com

Post reply on HN
Print view View original

31–40 of 130 posts

Re: Print(“lol”) doubled the speed of my Go function

#31

Post by tylerhou »

fmstephe wrote: post #30
tylerhou wrote: post #25

Earlier quoted context omitted.

"Conditional move is slow" is not the right takeaway. (In fact, conditional move can be much /faster/ than a branch in certain circumstances (e.g. hard-to-predict branches, like binary search).) The reason why this code is slow is because the conditional move is on the critical path for resolving a loop-carried data dependency. In other words, to execute the assignment `maxV = (v if (v > maxV) else maxV)`, the CPU ha…

So would you say in the general case, i.e. the compiler obviously doesn't know how predictable a branch may be, using conditional move is a poor choice when writing to an address which is repeatedly written to inside the loop? What I am trying to get a feel for, is whether this represents a bad choice of assembly in general for this kind of loop.

Nit: If a variable/object is only being written, that’s fine. There is a data dependency here because there is a read after a write.

I don’t have enough compiler knowledge to be able to definitively answer your question, but I think it would be a reasonable heuristic to favor emitting a branch over a cmov in cases where the cmov participates in a loop-carried data dependency.

The other advantage of emitting a branch is that branch prediction can better adapt to runtime conditions. Branch prediction tends to struggle when data is perfectly random, but most data is not. So in general it’s also reasonable for compilers to default to emitting branches.

Re: Print(“lol”) doubled the speed of my Go function

#32

Post by Syrail_ »

I 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!

Re: Print(“lol”) doubled the speed of my Go function

#33

Post by masklinn »

ludiludi wrote: post #18
zhzy0077 wrote: post #15

Earlier quoted context omitted.

Sorry. My bad. But looking at ARM64 https://godbolt.org/z/YEjGKce1Y The difference is CSEL and BLT. The question still stands. Does CSEL have no branch predication?

It appears so. 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.

CSEL 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).

Re: Print(“lol”) doubled the speed of my Go function

#34

Post by masklinn »

perryizgr8 wrote: post #21

Why 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.

The 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 :
        Mov
    Else:
        Noop
Considering these branches unpredictable, it generates a CMOV.

With

    If :
        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/

Re: Print(“lol”) doubled the speed of my Go function

#35

Post by _cenw »

Go 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

Re: Print(“lol”) doubled the speed of my Go function

#36

Post by dmurray »

Syrail_ wrote: post #32

I 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…

Yes, 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.

Re: Print(“lol”) doubled the speed of my Go function

#38

Post by vsnf »

Kind 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.

Re: Print(“lol”) doubled the speed of my Go function

#39

Post by Smaug123 »

vsnf wrote: post #38

Kind 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 Eng…

There 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".

Re: Print(“lol”) doubled the speed of my Go function

#40

Post by distcs »

vsnf wrote: post #38

Kind 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 Eng…

I 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.
Post reply on HN