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

Beating the Compiler

mattkeeter.com

Post reply on HN
Print view View original

51–60 of 78 posts

Re: Beating the Compiler

#51

Post by phire »

aengelke wrote: post #49
phire wrote: post #41

Earlier quoted context omitted.

Modern Out-of-order CPUs (like the M1), they can't see branches until far too late. The M1's frontend at least 24 instruction past the unconditional branch before the early possible moment it can even see it. So the branch predictor isn't just responsible for predicting which way conditional branches go. It must remember where all branches are, and their target so that the front end can follow them with zero cycle de…

Side note: Intel CPUs since Skylake and also recent AMD CPUs (since Zen 3 or so?) store a history for indirect branches. On such processors, using threaded jumps does not really improve performance anymore (I've even seen 1-2% slowdowns on some cores).

Pretty sure it's Haswell and Zen 2. They both implement IT-TAGE based branch predictors.

I just assumed the M1 branch predictor would also be in the same class, but I guess not. In another comment (https://news.ycombinator.com/item?id=40952404), I did some tests to confirm that it was actually the threaded jumps responsible for the speedup.

I'm tempted to dig deeper, see what the M1's branch predator can and can't do.

Re: Beating the Compiler

#52

Post by [deleted] »

gumby wrote: post #43
BeeOnRope wrote: post #25

Earlier quoted context omitted.

Modern compilers are not doing much searching in general. It's mostly apply some feed-forward heuristic to determine whether to apply a transformation or not. I think a slower, search based compiler could have a lot of potential for the hottest parts you're willing to spend exorbitant time on a search.

I understand the compiler Microsoft uses to build release versions of Windows, Office etc is like this and can take days to run.

[deleted]

Re: Beating the Compiler

#53

Post by anonymoushn »

pjmlp wrote: post #50
Validark wrote: post #45

I wish you wouldn't broadcast the sentiment contained in the first paragraph. Compilers lack the ability to consistently perform many basic optimizations to an embarrassing extent. Including even the ones you would think would be the first optimizations you'd implement when writing a compiler. Open up Godbolt and tell me if you still think the compiler knows best. I try to submit at least one issue to LLVM every time…

"Any sufficiently advanced technology is indistinguishable from magic." When people call themselves engineers, without placing their feets on an engineering school, with compiler development degrees, rather a six weeks bootcamp, their compilers feel like a sufficient advanced technology.

You really don't need a degree for this stuff. A typical degree has 1 class about this, and half of it is dedicated to formal language theory or the unfortunate practice of using parser generators.

Re: Beating the Compiler

#54

Post by fooker »

kaba0 wrote: post #46
jonjojojon wrote: post #28

Earlier quoted context omitted.

I have heard search based compiler optimization called "superoptimization"[1]. It seems interesting, but as far as I know has not seen much industrial use. 1. https://blog.regehr.org/archives/2578

It simply doesn’t scale. You can only superoptimize very short runs of code, nowhere anywhere close to even smaller code bases, let alone big ones.

It scales well enough. You can apparently run Souper on SQLite in 24 hours with a beefy machine, according to a talk I recently attended, by one of the developers.

Re: Beating the Compiler

#55

Post by pjmlp »

anonymoushn wrote: post #53
pjmlp wrote: post #50

Earlier quoted context omitted.

"Any sufficiently advanced technology is indistinguishable from magic." When people call themselves engineers, without placing their feets on an engineering school, with compiler development degrees, rather a six weeks bootcamp, their compilers feel like a sufficient advanced technology.

You really don't need a degree for this stuff. A typical degree has 1 class about this, and half of it is dedicated to formal language theory or the unfortunate practice of using parser generators.

Then my degree was atypical, as we had several classes about this, scattered around two years of other stuff.

The theoritical stuff, history and evolution of programming languages, compiler and language design, the actuall toy language implementation all the way to native code.

30 years ago, maybe the quality of teaching went down, I guess.

Re: Beating the Compiler

#56

Post by phire »

phire wrote: post #48

> The dispatch loop takes a single indirect branch to the opcode-specific implementation. This means that the branch will be nigh unpredictable! Modern branch predictors can actually predict indirect branches with multiple destinations, because they hash recent branch history into the prediction. The exact same indirect branch will end up with multiple BTB entries, based on previous control flow. I was curious where…

Ok, I spent quite a bit of time looking at performance counters, trying to understand what the M1's branch predictor was doing.

The branch predictor is really accurate with a common dispatcher, it predicts those indirect branches correctly 99.25% of the time. Switching to threaded jumps improves this slightly to 99.75%, but not because the indirect branches are at different addresses. This improvement in accuracy is entirely because of the unconditional branch back the dispatcher that was removed as a side effect. With that gone, the branch predictor can now track branch histories that are about twice as many VM instructions long.

My modified version with a dummy branch in the threaded dispatcher negates this longer history and (according to the performance counters) results in the exact same 99.25% correctly predicted branches as the common dispatcher, yet it's still significantly faster, only 20% slower than threaded jumps.

-------------------

Why are threaded jumps faster on the M1, if it's not increasing branch prediction accuracy?

Well, the M1 essentially has two branch predictors[1]. The faster one can return a prediction in one cycle, but it's not checking branch history it all, and it's almost always wrong for these unpredictable indirect branches. The slower predictor does take branch history into account, but takes three cycles to produce the correct result.

Which means there is a short pipeline stall when the second prediction comes in. This stall doesn't show up as a BRANCH_INDIR_MISPRED_NONSPEC, because the branch was correctly predicted. Instead, it seems to show up in the FETCH_RESTART counter.

So while threaded jumps doesn't improve overall branch prediction accuracy (except because of the longer history), it does slightly improve the accuracy of the faster branch predictor. With a common dispatcher, it predicts wrong almost 100% of the time, but with threaded code, the accuracy improves to 40%.

[1] Or at least that's a decent mental model. I suspect it's actually be a single ITTAGE branch predictor that returns the zero-history result in 1 cycle

Re: Beating the Compiler

#57

Post by the8472 » 

      0x100002ec0: b 0x100002d1c       ; jump back to the dispatch loop
I'd expect tail call based control flow - i.e. computing the jump destination at the end of each opcode function - to be nicer to the branch predictor because it could track targets separately.

Currently that's hard to achieve in Rust. There's an experiment in progress to see if guaranteed tail calls can be added to the language

https://github.com/rust-lang/rust/issues/112788

Re: Beating the Compiler

#58

Post by phire »

phire wrote: post #51
aengelke wrote: post #49

Earlier quoted context omitted.

Side note: Intel CPUs since Skylake and also recent AMD CPUs (since Zen 3 or so?) store a history for indirect branches. On such processors, using threaded jumps does not really improve performance anymore (I've even seen 1-2% slowdowns on some cores).

Pretty sure it's Haswell and Zen 2. They both implement IT-TAGE based branch predictors. I just assumed the M1 branch predictor would also be in the same class, but I guess not. In another comment ( https://news.ycombinator.com/item?id=40952404 ), I did some tests to confirm that it was actually the threaded jumps responsible for the speedup. I'm tempted to dig deeper, see what the M1's branch predator can and can't…

too late to edit

Turns out that M1 can track the history of indirect branches just fine, but it takes 3 cycles for a correct prediction. With threaded jumps, the M1 gets a slightly higher hit rate for the initial 1 cycle prediction.

https://news.ycombinator.com/item?id=40953764

Re: Beating the Compiler

#59

Post by flamedoge »

gumby wrote: post #43
BeeOnRope wrote: post #25

Earlier quoted context omitted.

Modern compilers are not doing much searching in general. It's mostly apply some feed-forward heuristic to determine whether to apply a transformation or not. I think a slower, search based compiler could have a lot of potential for the hottest parts you're willing to spend exorbitant time on a search.

I understand the compiler Microsoft uses to build release versions of Windows, Office etc is like this and can take days to run.

and well worth the cost

Re: Beating the Compiler

#60

Post by tucnak »

almostgotcaught wrote: post #39
ashton314 wrote: post #35

Earlier quoted context omitted.

I am going to be the token programming language researcher and say that what you really want is a dependently typed assembly language that your dependently typed higher level language lowers to. One school of thought that has yet to bear fruit in “mainstream“ programming, but gives tantalizing hints of what is possible, is expressing increasing amounts of your programs constraints in the type system, thereby informin…

> want is a dependently typed assembly language Doesn't make any sense. The "type constraints" on assembly operands (registers and numbers) is the ISA and thus those constraints are combinatorial not logical

There's the reason "token programming language researchers" are incapable of understanding modern computer architectures: a huge gap where would have been EE education.
Post reply on HN