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

61–70 of 78 posts

Re: Beating the Compiler

#61

Post by almostgotcaught »

tucnak wrote: post #60
almostgotcaught wrote: post #39

Earlier quoted context omitted.

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

Correct - most of them think the goal is an infinite tower of sophisticated "abstractions" not realizing there's nothing abstract about a finite piece of silicon.

Re: Beating the Compiler

#62

Post by almostgotcaught »

WalterBright wrote: post #40
almostgotcaught wrote: post #29

Earlier quoted context omitted.

> Modern compilers are not doing much searching in general. This is false. Any compiler that does register allocation and instruction scheduling (all of them) is searching for an optimal (or just good enough) solution to an optimization problem.

Where things get fun is when two optimizations combine to make things worse. They never tell you about that in compiler class! It's like designing a house. If you want the master closet bigger, the master bath has to shrink. Everything is a tradeoff.

You have this exact issue in VLIW and it's exactly where you can't cheat by using heuristics:

Combinatorial Register Allocation and Instruction Scheduling

https://dl.acm.org/doi/10.1145/3332373

Re: Beating the Compiler

#63

Post by intelVISA »

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.

Any good 2 week bootcamp for mastering PLT??

Re: Beating the Compiler

#64

Post by pjmlp »

intelVISA wrote: post #63
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.

Any good 2 week bootcamp for mastering PLT??

Get Modern Compiler Implementation in C [0] (with Java and ML versions also available),or the Kaleidoscope LLVM tutorial [1], and do the whole thing in 2 weeks, as starting point.

[0] - https://www.cs.princeton.edu/~appel/modern/c/

[1] - https://llvm.org/docs/tutorial/

Re: Beating the Compiler

#66

Post by [deleted] »

almostgotcaught wrote: post #37
azakai wrote: post #34

Earlier quoted context omitted.

I'm not sure there is a clear separation between applying heuristics and searching a space. Often in compilers you search a subset of a space using heuristics, and you can adjust those to control how much of the space you cover. For example, here is a pass that reorders WebAssembly globals in the Binaryen optimizer: https://github.com/WebAssembly/binaryen/blob/main/src/passes... We have a simple criteria for the qual…

> I'm not sure there is a clear separation between applying heuristics There is and it's quite simple: if your heuristic reduces the size of your search space faster than it takes to perform the search (ie try solutions) then you have a real algo on your hands. Otherwise you're just searching. This is basically the border between P and NP and it's just that in compilers most of the problems are NP hard so none of the…

[deleted]

Re: Beating the Compiler

#67

Post by gumby »

almostgotcaught wrote: post #37
azakai wrote: post #34

Earlier quoted context omitted.

I'm not sure there is a clear separation between applying heuristics and searching a space. Often in compilers you search a subset of a space using heuristics, and you can adjust those to control how much of the space you cover. For example, here is a pass that reorders WebAssembly globals in the Binaryen optimizer: https://github.com/WebAssembly/binaryen/blob/main/src/passes... We have a simple criteria for the qual…

> I'm not sure there is a clear separation between applying heuristics There is and it's quite simple: if your heuristic reduces the size of your search space faster than it takes to perform the search (ie try solutions) then you have a real algo on your hands. Otherwise you're just searching. This is basically the border between P and NP and it's just that in compilers most of the problems are NP hard so none of the…

I disagree with this part of your comment:

> then you have a real algo on your hands

To me an algorithm is closed, while a heuristic (aka rule of thumb) is just a fast way to probably get a better solution / subset of the solution space at the cost of possibly missing the optimal result or even ending up in a pessimal corner case.

With an NP complete problem you'd rather have some solution rather than use up your lifetime searching for the best.

Re: Beating the Compiler

#68

Post by almostgotcaught »

gumby wrote: post #67
almostgotcaught wrote: post #37

Earlier quoted context omitted.

> I'm not sure there is a clear separation between applying heuristics There is and it's quite simple: if your heuristic reduces the size of your search space faster than it takes to perform the search (ie try solutions) then you have a real algo on your hands. Otherwise you're just searching. This is basically the border between P and NP and it's just that in compilers most of the problems are NP hard so none of the…

I disagree with this part of your comment: > then you have a real algo on your hands To me an algorithm is closed, while a heuristic (aka rule of thumb) is just a fast way to probably get a better solution / subset of the solution space at the cost of possibly missing the optimal result or even ending up in a pessimal corner case. With an NP complete problem you'd rather have some solution rather than use up your lif…

> To me an algorithm is closed

i dunno what "closed" means here? converges? lots of things with heuristics converge...

most things people think of as algorithms are just heuristics codified. take for example unit propagation in DPLL (fairly modern SAT approach); quoting wiki[1]

> In practice, this often leads to deterministic cascades of units, thus avoiding a large part of the naive search space.

that *in practice* there means there's no guarantee because ofc not - otherwise they would've proven something about NP. but they didn't, they just came up with a way to search that's sometimes/often not bad. a lot of people call this an algorithm ("... is a refinement of the earlier Davis–Putnam algorithm") because it fits the dictionary definiton (a repeatable process) but i do not because it's a repeatable process that isn't proven to produce anything (ie faster than brute force). and the intuition i'm proposing for why it doesn't is because it doesn't actually shrink the search space fast enough.

note, my definitions/intuitions don't translate/have the same force elsewhere (especially in continuous/differentiable spaces) but they're a pretty standard/obvious perspective in combinatorial optimization (np-hard/np-complete problems).

[1] https://en.wikipedia.org/wiki/DPLL_algorithm#The_algorithm

Re: Beating the Compiler

#69

Post by mkeeter »

phire wrote: post #56
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…

Very cool, thanks for digging into this!
Post reply on HN