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

101–110 of 130 posts

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

#101

Post by pohl »

ColinWright wrote: post #99
pohl wrote: post #95

Earlier quoted context omitted.

A compiler from what to Z80? (I think there’s a word missing in what you wrote.) I started on a Model I and I’m curious about your compiler. I miss some aspects of those old machines. It was great, as a learner, that the ROM and a DOS like L-DOS was small enough to fit in your head. It can be intimidating how large everything is today.

Now edited ... thank you. The compiler was from a limited subset of TRS-80 BASIC to Z80. It was written in its own subset, so it could compile itself. I had 16K of RAM, and that had to fit the BASIC source, the compiled version, and then that compiled version compiled the BASIC source to another compiled version in a different location, which could then be saved on tape. Interesting times, and so foreign to today's e…

That sounds like a valuable exercise. I wrote a word processor. There was an issue of 80 Micro that had a simple buffer in assembly (I think they called it Scripy) and I wrote some BASIC around it for various other functions, so that I could keep a journal and write essays for school. A compiler sounds ambitious in comparison.

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

#102

Post by pjc50 »

mcv wrote: post #48
keyle wrote: post #47

Earlier quoted context omitted.

They're a dying breed. We're forgetting how to look under the hood and understand "why something works". Case in point, I'm slowly being replaced by Salesforce muppets for all my projects at work. They're little code monkeys with amazon ebook type knowledge, projects cost 20x more and I look like the mad scientist for speaking the truth. The products are worse in every possible metrics, I'm not crazy. The politics at…

> We're forgetting how to look under the hood and understand "why something works". Partly because that's often not what we're supposed to do; the stuff under the hood "just works" and we're meant to use it to write features, not worry about optimising the stuff that happens under the hood. And partly it's because the stuff under the hood is increasingly weird and bizarre. Branch prediction is weird, and I still don'…

> I still don't understand why that extra print statement changes the branch prediction.

The article is under-informing you: they should have shown the full disassembly for both loops, not just the bit in question. I suspect the explanation as given is slightly wrong, but there's no way to disprove it without replicating the setup myself.

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

#103

Post by [deleted] »

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…

[deleted]

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

#104

Post by Majromax »

mcv wrote: post #57
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…

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.

The version with the print statement requires the branch because it's conditionally executed; the 'continue' statement in the if-block will skip it if the loop finds a new maximum.

Since the function-with-if version requires a branch, there's no advantage (regardless of predictability) in using a conditional move for the assignment to maximum.

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

#106

Post by Majromax »

Zinu wrote: post #72
mcv wrote: post #53

Earlier quoted context omitted.

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

It'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.

The 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'.

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

#107

Post by anentropic »

smcl wrote: post #79
grose wrote: post #64

Earlier quoted context omitted.

Seems like the answer is no[1] and profile-guided optimization is recommended instead, 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

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

Not giving you nice things because "Your average programmer may mess that up" is the whole philosophy of Go though

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

#108

Post by vlovich123 »

anonymoushn wrote: post #73
James_K wrote: post #59

Earlier quoted context omitted.

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.

For branch instructions but not for conditional move instructions, the processor will happily execute the next instruction before the values are actually ready, then invalidate the work it has done later if it turns out retrospectively to have been wrong. This is called branch prediction.

Technically my understanding of terminology is that the branch predictor is responsible for determining which branch to take when speculative execution encounters a branch. Speculative execution is the thing that will invalidate work if the branch predictor was wrong.

Also my understanding based on reading this thread is that a conditional move is harder to speculate across because of the data dependency carried across iteration loops, preventing speculation. With a conditional branch, speculation can keep executing the next loop and most of the time the branch predictor will guess correctly how to execute the next iteration for this problem.

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

#109

Post by gv83 »

MrYellowP wrote: post #90
gv83 wrote: post #68

Earlier quoted context omitted.

> We're forgetting how to look under the hood and understand "why something works". But under the hood there is a hood. And under that hood there is another hood. And under that hood there is a brand new car you don't know how to open the hood, and so on. I cannot devote my life to know everything or I won't be able to provide for my family.

No. Flat out wrong. There is only a small amount of fundamental understanding that needs to be acquired to actually know what your code is actually doing. Knowing how things work fundamentally is what matters the most, as everything else can be inferred and deduced from that. This is universally true. When you know how something works, you can build up on that. There's no value for a programmer below how processors w…

I never had the chance to work at the lower levels you seem to have worked with; in any case I don't disagree in principle with your points (and understand some part of the fundamental understanding you mention), but less dependency leads to wheel reinventing which is completely unsustainable in the long run, specially if you need to maximize the value you bring to the table. It has been like this for every field; how can we call this, industrialization?

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

#110

Post by tallanvor »

trolan wrote: post #9
dataflow wrote: post #6

I 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

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

No, this is not true.

There is branch prediction around the length of loops. This is a case where the processor is not able to accurately predict how long it needs to stay in the loop. The BLT instruction changes the prediction model, causing the processor to be more likely to assume the loop will continue.

Honestly, though, worrying about this level of optimization is generally silly. If you're looping through an array often enough that optimizing the code this way is worth your time, you should use a data structure that automatically maintains the max (and min) values for fast retrieval.

Post reply on HN