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

CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

cs.cornell.edu

Post reply on HN
Print view View original

41–50 of 63 posts

Re: CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

#41

Post by panick21_ »

titzer wrote: post #40
mikemike wrote: post #39

Earlier quoted context omitted.

Trace compilation is NOT a dead end. LuaJIT works just fine. On big programs. On hundreds of millions of servers and devices. I find it deeply saddening that even scholars keep repeating this trope. Ignorance is bliss.

Hi Mike, I think your work on luajit is really cool. I worked on JavaScript for some time and among all of the JS engines out there, a lot of ideas were tried. TraceMonkey in particular did explore trace compilation for JavaScript and benefited from a lot of fundamental research into trace compilation from Michael Franz's group and others. I've talked to many of those people. It just didn't work out for JS as there a…

Didn't you guys have this discussion like 10 years ago in Lambda the Ultimate comments?

Re: CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

#43

Post by afdbcreid »

saghm wrote: post #28
afdbcreid wrote: post #18

Earlier quoted context omitted.

I've never heard about that and I'm pretty sure it's incorrect (although "machine learning" is a wide term), do you have a source for that?

I've also never heard this before. The closest I can think of is fuzzing test suites used to find panics in various crates, but that's neither machine learning nor in the compiler itself. I know that datalog is used for the borrow checking logic, so I could also maybe imagine someone describing something like that in some hand wavy way like "proof by machine to detect up front whether the program is safe or might cra…

Datalog is not used for borrow checking. It was used in old versions of the experimental next-gen borrow checker, Polonius. Current versions of Polonius (which is still experimental) are coded in Rust.

Re: CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

#44

Post by mikemike »

titzer wrote: post #40
mikemike wrote: post #39

Earlier quoted context omitted.

Trace compilation is NOT a dead end. LuaJIT works just fine. On big programs. On hundreds of millions of servers and devices. I find it deeply saddening that even scholars keep repeating this trope. Ignorance is bliss.

Hi Mike, I think your work on luajit is really cool. I worked on JavaScript for some time and among all of the JS engines out there, a lot of ideas were tried. TraceMonkey in particular did explore trace compilation for JavaScript and benefited from a lot of fundamental research into trace compilation from Michael Franz's group and others. I've talked to many of those people. It just didn't work out for JS as there a…

I'm not sure one can infer anything from a single failed Mozilla project.

'Real-world' JavaScript is a challenge for any compiler, no matter the underlying technology.

The technical debt in SpiderMonkey (at that time, anyway) was eye-watering. Grafting anything on top of that was hard. They haven't even gotten to the point of implementing the crucial pieces of a trace compiler before the project folded.

Trace compilers make nice textbook exercises. Getting them into production is a different matter: region selection, side-exit handling, trace graph evolution, deep VM integration, code generation adapted to all of this … far from trivial, but doable.

Neither is it trivial to create a production-quality method-at-a-time JIT compiler and VM for a dynamic language.

Ceterum censeo: The fundamental papers on trace compilation are from Fisher (1981) and the teams around Multiflow (1990) and Dynamo (1999). Franz, Gal, et al can be credited for later re-popularizing the idea, but they haven't added anything of note.

Re: CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

#45

Post by saghm »

afdbcreid wrote: post #43
saghm wrote: post #28

Earlier quoted context omitted.

I've also never heard this before. The closest I can think of is fuzzing test suites used to find panics in various crates, but that's neither machine learning nor in the compiler itself. I know that datalog is used for the borrow checking logic, so I could also maybe imagine someone describing something like that in some hand wavy way like "proof by machine to detect up front whether the program is safe or might cra…

Datalog is not used for borrow checking. It was used in old versions of the experimental next-gen borrow checker, Polonius. Current versions of Polonius (which is still experimental) are coded in Rust.

Oh interesting, I'm not sure why I misunderstood that. Thanks for the correction!

Re: CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

#46

Post by vsmenon »

titzer wrote: post #9
samps wrote: post #4

Earlier quoted context omitted.

Thanks, Ben. I admit I mostly think tracing is just a mind-expanding concept to learn about, even if history has proven it’s not very practical as an organizing principle. But as you say, I’d love to offer more context on “what actually seems to work” industrially.

Yeah, it is conceptually interesting. I like giving students perspective and in 770 ( https://www.cs.cmu.edu/~wasm/cs17-770/fall2025/ ) I might spend half or less of a lecture on tracing and I don't pull punches on how I think it ends up not really working well in real systems. It's a good opportunity to talk about program behavior and the cost/benefit of speculation. We spend a lot more time on type feedback, ICs, a…

To be fair, the listed Self paper did age quite well!

Re: CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

#48

Post by nwallin »

titzer wrote: post #20
jlebar wrote: post #14

Earlier quoted context omitted.

> Generally, trace compilation is a dead end and has been abandoned repeatedly. JAX is a tracing compiler! (I know, I know, it sits in an extremely different part of the problem space than TraceMonkey or LuaJIT. Still.)

Interesting. I think numerical computing is a narrow enough domain where programs have very well-behaved control flow, which avoids most of the problems of trace compilation. Loops over branchy code, which are really common in general programs, are very difficult to make work well with tracing. Numerical programs being very stable in terms of control is what enables GPU parallelization and loop optimizations in the l…

My feeling about JavaScript is statistically speaking, random JavaScript code is more likely to be spaghetti nonsense than, say, the equivalent Python code. This feeling isn't based on empirical data, tbh it's probably as much anti-JS bias as it is experience with poorly written JavaScript.

Is your criticism of tracing specific to messy, confusing code, with lots of edge cases in the main loop, or does it also hold true for well written code?

I have no experience with compiler design, didn't even take a compilers course in college.

Re: CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

#49

Post by ebiederm »

mrkeen wrote: post #38
ebiederm wrote: post #26

Earlier quoted context omitted.

The academic literature on register allocation is scary. First is presented a linear time optimal algorithm for graph coloring then it is claimed better can be done by a O(N^2) algorithm that uses a heuristic. I do believe the dragon book got caught with the emperor's new register allocator and the literature hasn't really recovered yet.

I didn't believe the optimal algorithm is linear time, so I checked the source: a simple register allocation algorithm can achieve most ot the performance of the more complex algorithms: linear-scan register allocation, developed by Poletto and Sarkar "Most of the performance" is not optimal. Were you referring to a different source?

The big caveat in what I was saying is that it is only the pure graph coloring portion that has an optimal linear time algorithm.

Take code in static single assignment form, or another form where it is values that are tracked with live ranges. For a single basic block the interference graph of the live ranges is an interval graph. As the live ranges are just intervals from the instruction that produces the value to the last instruction that consumes the value.

It is annoying but totally doable to follow this into graph theory and see that interval graphs, are a subset of chordal graphs, and these graphs have an algorithm that colors the graph optimally in linear time.

Poke a little more and it turns out that algorithm is the same algorithm as linear-scan register allocation.

Add multiple basic blocks and it is trickier to see, but there are proofs in the academic literature that the interference graph remains an interval graph. Something about phi functions not counting.

Which is what I meant when I said a linear time algorithm.

Compare that to the O(N^2) heuristic from the paper register allocation by graph coloring.

The big change is going from a linear time optimal algorithm to a quadratic time heuristic and proclaiming the quadratic time heuristic is better. (What???)

In practice there are a lot of complications that are not accounted for by graph coloring. Instructions and function calls that take fixed registers. Spilling registers when you need more values alive then there are registers. Deliberately keeping a non-minimal number of values in registers to increase instruction level parallelism.

To the best of my knowledge all of those problems are very tractable if you start with a linear scan register allocator, as the code can be changed without requiring the register allocation to restart.

Code based on computing the interference graph has to reconpute the interference graph and restart whenever the code has to be changed. Making it much worse time wise. If for no other reason than computing the interference graph is O(N^2).

So yes more complications but only because the model described is overly simplified.

Re: CS 6120: Advanced Compilers: The Self-Guided Online Course (2020)

#50

Post by foobazgt »

nwallin wrote: post #48
titzer wrote: post #20

Earlier quoted context omitted.

Interesting. I think numerical computing is a narrow enough domain where programs have very well-behaved control flow, which avoids most of the problems of trace compilation. Loops over branchy code, which are really common in general programs, are very difficult to make work well with tracing. Numerical programs being very stable in terms of control is what enables GPU parallelization and loop optimizations in the l…

My feeling about JavaScript is statistically speaking, random JavaScript code is more likely to be spaghetti nonsense than, say, the equivalent Python code. This feeling isn't based on empirical data, tbh it's probably as much anti-JS bias as it is experience with poorly written JavaScript. Is your criticism of tracing specific to messy, confusing code, with lots of edge cases in the main loop, or does it also hold t…

Nah, as titzer said, it's really about general-purpose code being branchy (a good match for CPUs) vs numeric code being heavily parallelized and non-branchy (a good match for SIMD/GPUs). Only a small subset of very specific languages / instructions target the latter (e.g. CUDA and SSE4).
Post reply on HN