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

51–60 of 130 posts

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

#51

Post by mcv »

distcs wrote: post #40
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.

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

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

#53

Post by mcv »

bakul wrote: post #4

Processor "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…

I 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

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

#54

Post by BiteCode_dev »

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…

The HN bubble doesn't have only disadvantages.

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

#55

Post by teddyh »

totetsu wrote: post #44
buro9 wrote: post #41

Earlier quoted context omitted.

This feels semi-normal to me... just have the curiosity to ask "why?" and the bias-to-action to move to "I'm going to find out". You encounter far far more dead-ends than anyone ever says, and every unsolved mystery is a mild nerd snipe, an open case, that years from now you'll see someone else explain something you realise it answers that question from years prior. For me, the hard bit is not over-indexing on this..…

https://imgs.xkcd.com/comics/ten_thousand.png for those who haven't heard of it.

Canonical link: https://xkcd.com/1053/>

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

#56

Post by spuz »

masklinn wrote: post #34
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…

Thank you. I was struggling to understand what was going on after reading the article. Your explanation is much better.

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

#57

Post by mcv »

tylerhou wrote: post #25
dataflow wrote: post #16

Earlier quoted context omitted.

Ah there you go, that's the conditional move on ARM. Yeah, those are slow.

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

But why does the print statement matter in how the compiler decides this? In both cases, the execution still depends on the vMax value calculated in the previous iteration.

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

#58

Post by secondcoming »

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…

It’s not all that uncommon outside of web stuff

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

#59

Post by James_K »

tylerhou wrote: post #25
dataflow wrote: post #16

Earlier quoted context omitted.

Ah there you go, that's the conditional move on ARM. Yeah, those are slow.

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

How exactly does that change anything? It's being run on an increasing array, so the data is assigned every loop. Surely the comparison creates a dependency on the value of the variable which was assigned in the last loop.

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

#60

Post by mcv »

dataflow wrote: post #23
littlestymaar wrote: post #22

Earlier quoted context omitted.

> and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it). Would you mind expanding? If the conditional move isn't needed, and given that it's costly in terms of perfs, how is that “totally sensible” to have one here?

The performance of branches is data-dependent. The performance of conditional moves is data-independent. In this case the branches are predictable, so they perform better here. In general, though, the compiler has no idea whether that's the case, so it makes sense to insert a conditional move to avoid branch misprediction penalties.

But still, why the difference? With or without the "lol", the data dependence is identical, the predictability is identical. Yet with the "lol" it optimises differently.

My best guess is that it's because of the added cost to the other branch: printing is expensive, so the compiler really doesn't want to do that, and would prefer to incorrectly predict not-printing than to incorrectly predict printing.

If that tradeoff is what causes the difference in behaviour here, then I understand. But I don't like it, because it's ridiculous and we shouldn't have to con the compiler into doing what's right. If we're going to have to do this, I'd rather have the language provide a way for us to make explicit what we expect here.

Post reply on HN