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

31–40 of 78 posts

Re: Beating the Compiler

#31

Post by 256_ »

Why does making the FETCH part of the cycle a macro make it faster? Surely the branch predictor is fine with unconditional immediate branches. What am I missing here?

Also, it has jump-to-register immediately after the instruction that sets that register. Wouldn't it be faster if it went like:

  get jmp address
  execute VM opcode
  jmp to next instruction
So the pipeline can fetch it ahead of time?

Re: Beating the Compiler

#32

Post by drpixie »

almostgotcaught wrote: post #29
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.

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

Can you give an example?

In general, searching any significant space is very slow, applying heuristics is much quicker.

Re: Beating the Compiler

#33

Post by interpunct »

> I've proven to my satisfaction that writing an interpreter in assembly is both fun and performant!

Fun maybe/maybe not, but define "performant". I might drop into assembly for 1 or 2 orders of magnitude faster for a non-toy project. Even then, what are my requirements? What is the bus factor of LuaJIT again? Try getting support for s390x, or your patch accepted.

Look at the speedup of Lua v. LuaJIT (C language VM v. C/Lua VM with JIT code gen):

https://web.archive.org/web/20180430211146/https://luajit.or...

Re: Beating the Compiler

#34

Post by azakai »

drpixie wrote: post #32
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.

Can you give an example? In general, searching any significant space is very slow, applying heuristics is much quicker.

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 quality of a solution - how big the binary size is with an order - but the space of possible orders is huge (every permutation that keeps every global after its dependencies). What we do is a targeted search of that space using some heuristics using parameters that work well enough and aren't too slow in practice.

Re: Beating the Compiler

#35

Post by ashton314 »

gumby wrote: post #3

IMHO the best way to think of it (well, it's how I have long thought of it) is two lemmas: 1 - The compiler has more "fingers" than a human does. Back when I wrote programs in assembly I would use printout to keep track of what I was doing and for debugging, and so would often put a finger on the paper to mark where a jump was and then go to the destination to see if it matched up, etc. This process isn't at all scal…

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 informing the compiler precisely about your intent.

Re: Beating the Compiler

#36

Post by almostgotcaught »

drpixie wrote: post #32
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.

Can you give an example? In general, searching any significant space is very slow, applying heuristics is much quicker.

I don't know what you're asking for - this isn't some kind of controversial topic - any iterative algo that isn't polynomial time (or is approximate) is search.

In the context of compilers there are many. Look at this block diagram for Chaitin's register allocator:

https://en.wikipedia.org/wiki/Register_allocation#Principle_...

That's a search because it tries an allocation, possibly incurs a spill, tries again.

Re: Beating the Compiler

#37

Post by almostgotcaught »

azakai wrote: post #34
drpixie wrote: post #32

Earlier quoted context omitted.

Can you give an example? In general, searching any significant space is very slow, applying heuristics is much quicker.

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 heuristics are really that good.

Re: Beating the Compiler

#38

Post by abbeyj »

201984 wrote: post #13

Very cool! I enjoy seeing people writing asm, and letting us get the most out of our CPUs. I see you already tried what I thought of, which is getting rid of the jump table and making each instruction handler the same size. Do you think that could still work if you limited each instruction handler to 64 or 32 bytes instead of 256, and then for longer handlers jumped to a larger body of code somewhere else?

This is how Dalvik (the old Android Java interpreter) worked, with 64 chosen as the size of an instruction handler. See https://wladimir-tm4pda.github.io/porting/dalvik.html (search for "computed goto").

Re: Beating the Compiler

#39

Post by almostgotcaught »

ashton314 wrote: post #35
gumby wrote: post #3

IMHO the best way to think of it (well, it's how I have long thought of it) is two lemmas: 1 - The compiler has more "fingers" than a human does. Back when I wrote programs in assembly I would use printout to keep track of what I was doing and for debugging, and so would often put a finger on the paper to mark where a jump was and then go to the destination to see if it matched up, etc. This process isn't at all scal…

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

Re: Beating the Compiler

#40

Post by WalterBright »

almostgotcaught wrote: post #29
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.

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

Post reply on HN