Reading for 11/7: Tracing

[Enochen]

Hi everyone! The discussion on 11/7 is about JIT via tracing. The reading can be found here.

[vivianyyd]

Note: We believe there is a typo in the caption of Figure 1; it should say "100 true values", not false.

[willwng]

And for the second loop, the condition should be k < 100

[yxd97]

As a hardware person, I see lots of similarities between tracing-based dynamic compilers and hardware acceleration: both identify hot spots in the program and optimize (specialize) them. While this paper focus on leveraging run-time type information to optimize a trace into specialized machine codes, I wonder if any compiler could also make use of the structure of the CFG of the trace?

For example, many linear algebra operations naturally incur nested loops (Figure 7 in the paper could come from a matrix-vector multiplication where the branch in the inner loop handles overflows). The compiler could detect such structure and map a large portion of the trace to especially optimized libraries.

[sampsyo]

Really good point! Here are two bits of related work that fall into this paradigm.

• Transmeta, where a trace-based JIT compiles x86 to a custom VLIW ISA.
• Trace caches are structures in superscalar processors that use tracing to speed up instruction fetch.

[evanmwilliams]

Yeah I found these connections very interesting! Especially when they started talking about future prevalence of multicore systems and how they were anticipating needing to provide support for it (the paper came out in 2009 so it was probably a wise choice)

[rcplane]

While searching around for any more concrete specification of Mozilla Javascript Ion LIR (lower level than MIR) which seems to be related to the trace-flavored SSA LIR described on page 468 in which the paper's traces are recorded, I came across an interesting retrospective from 2011 regarding the costs and benefits of implementing and supporting tracing for Javascript JIT compilation as progress marched on.

[keikun555]

I wonder whether it's against Python's philosophy to have an opt-in feature that use their type hints feature to make trace optimizations.

Currently type hints are used for static analysis with tools such as mypy. Maybe the CPython compiler can benefit from these types, given that the type check passes.

[sampsyo]

It is also worth considering what marginal value type annotations provide beyond JIT-style observation of run-time types.

[keikun555]

Whenever we're passing in a y: Any to a function with type annotation T, would it be possible at type checking/runtime to constrict y's type to T?

[SanjitBasker]

If I remember correctly, the type annotation Any is an "escape hatch" for the programmer to basically revert to untyped Python. Here's a full example.

from typing import Any

def f(x: int) -> int:
    return x + x

if __name__ == '__main__':
    y: Any = 3
    print(f(y))
    y = input("input a string: ")
    print(f(y))

It passes mypy version 1.5.1, and if you input yo it prints yoyo. A Python runtime that uses type information would have to maintain this by compiling f in a way which works for non-int inputs.

[sampsyo]

Also, run-time checking at the "typed/untyped boundary" is a good idea, and it's exactly what research on sound gradual typing attempts to do. It just turns out to be pretty darn expensive.

[NgaiJustin]

Interesting question! I think there's also a practical argument when transitioning a large codebase towards using types annotations. Static analysis tools are only effective with sufficient type coverage, but going from 0 to this critical point becomes an arduous endeavor when we are talking about a scale of millions of files. As mentioned above, gradual typing is an awesome way to gradually add annotations over time. Gradual type checkers, such as Pyre, do so by

• only reporting errors on functions that have an explicit return or parameter type annotation,
• introducing an escape hatch: a special type Any that has all possible attributes and is both sub- and super-type of any other type,
• and assuming that all untyped fuctions implicitly return Any.

[obhalerao]

I drew a lot of parallels between this paper and the current assignment we're working on; I found many of the ideas that this paper presents to be quite compelling; the idea of blacklisting a section of the program for which tracing often aborts is quite an interesting one as well. All this primarily goes to show that even without explicit static type information, the use of dynamic compilation can still enable speedups to be made upon execution.

[collinzrj]

I agree. A lot of optimizations they mention in section 3 is also what I thought about when I implement the optimizations for trace in bril. Moreover, I'm interested in how can we efficiently trace the program. In a previous paper of this semester, we talked about Efficient Path Profiling, can we draw any similarities between path profiling and tracing to reduce the overhead of tracing?

[jdroob]

One of the more interesting parts to read about for me was how tracing nested loops was handled. Equally interesting for me was reading about the problem that their implementation solved - since inner loops will become hot before outer loops, without intervention, the trace will look like: inner_loop_header -> inner_loop_body -> outer_loop_header - which is no big deal for a nesting depth of 2 but it's easy to see how this can get out of control as nesting depth increases. For example, with a nesting depth of just 3, the sequence becomes: inner_loop2_header -> inner_loop2_body -> inner_loop1_header -> outer_loop_header. The authors' approach feels much more natural and easier to reason about (i.e. inner_loop_header -> inner_loop_body is a single trace and, outer_loop_header -> outer_loop_body_mod_inner_loop -> inner_loop_header is another unique trace. I hadn't really considered what the loop traces in this week's task would look like so this paper really helped illustrate the variety of possible loop traces.

[matth2k]

I was surprised by how many heuristics the authors needed to add in order make the dynamic compiler behave more predictably:

• External functions called within traces that modify global variables or the call stack need to be marked as such and handled separately.
• The overhead of compiling short traces can cause performance degradation unless they are properly filtered out.
• Memory limitations can cause a trace to be abandoned. Then, those code segments need to be blacklisted.
• Variables that are not initialized until the first loop iteration make the loop appear to be "type unstable." The interpreter then needs to find the "type equilibrium" without wasting too many resources on tracing.

The paper was a good way to learn how dynamic compiler implementations diverge from the theory, without having to go through the great effort of creating such a compiler.

All these ad-hoc fixes make me wonder if it makes sense to research a uniform approach to dynamic compilation for all programming languages.

[bcarlet]

On a somewhat related note, I wonder about the burden that an unpredictable compiler places on programmers trying to optimize their code. Ideally, the compiler would transparently optimize programs in a predictable, somewhat uniform manner. But it seems like the realities of trace-based compilation lead to many pathological cases that could cause severe degradations in performance if a programmer were to accidentally stumble into one of them. It feels a bit like how CPU caches are intended to be invisible, but in reality one needs to be acutely aware of them in order to achieve good performance.

[sampsyo]

Yeah, it's definitely a tricky thing. I think that JITs, and especially tracing JITs, inevitably end up with a lot of these special cases where they need to remain conservative—i.e., just give up and fall back to "slow mode" if the program does anything unexpected. Another case like this from a very different-looking language is introspection in Java… it is a very reasonable strategy to just give up on compiling anything fast at all in code that imports java.lang.reflect.*.

[he-andy]

Super interesting paper, especially since up to now (including 4120), we've primarily only discussed statically typed languages. Something I found odd was that there are an absurd number of optimizations for these dynamically typed languages that are all extremely complicated (and probably intractable without heuristics/approximations). I wonder if the benefits of dynamically typed languages (their ease of use) really merits this amount of work to achieve what I would assume to be outperformed by a statically typed language with a well-written compiler. I feel like a good compromise would just to have a good type inference system (with type hints) to avoid all of this...

[xalbt]

While I agree that the optimizations for dynamically typed languages are cumbersome to both formulate and implement correctly, I definitely do think the benefits of dynamically typed languages merit this work. For one, Javascript is the most used language in the world. It is run in nearly all web browsers and a decent amount of node.js backends as well. Directly running un-jitted, un-optimized Javascript bytecode in all browsers and node.js implementations would certainly diminish our web browsing experience and non-insignificantly increase carbon emissions. As for usability, I would say most people would, for example, rather use Javascript to build out a full-stack application from scratch than use a combination of Javascript and Java or C++, because of the usability and fast iteration that Javascript is able to provide. This also applies to using Python for machine learning experiments rather than directly using something like Jax or Aten directly. Perhaps in an ideal world, the most popular programming languages would be statically typed and have a range of relatively easily implemented optimizations, but people gravitated toward dynamically-typed Javascript and Python for a reason—their ease of use.

[sampsyo]

Pulling in a thread from our conversation next week, the world does not need to decide between fast, static languages and slow, dynamic ones. In practice, both are used a lot, in different contexts. And they are two great tastes that go great together, as articulated in Ousterhout's dichotomy.

[MelindaFang-code]

Totally agree that the flexibility has made Javascript super popular and allow users to mangle code pretty fast and render cool effects, but at the same time makes it super hard to optimize. I wonder if some day Javascript is made simpler by means of other languages compiling into a subset of it, would it enjoy major speedups.

[evanmwilliams]

I really enjoyed this paper! Dynamically compiled languages are pretty complicated to implement, but this paper did a good job breaking down the main methods. I'm most curious about where the future work of this paper went actually. It's been a long time since it came out and we've had a lot of advancements in hardware acceleration and language development among other things. Is this tracing interpreter used in industry, or did people find better ways to implement JavaScript (I guess better means more performant here). Like Andy said above, the optimizations for languages like JavaScript get pretty complex, and one can argue that it's not worth trying to optimize the heck out of a language that is not meant to be running in super high-performance settings. Some people above also talked about opt-in optimizations, which is also interesting food for thought.

[sampsyo]

It’s hard to assess the whole landscape of contemporary similar compilers, but as one data point, I’m pretty sure SpiderMonkey does not use tracing anymore (it is more of a method JIT).

Dynamically compiled languages

I think you mean “dynamic languages”. 😂

[AliceSzzze]

The paper helped clear up some confusion I had on the topic and in this week's assignments. I was surprised to see that many of the benchmarks were running almost entirely in native code, despite being written in a dynamic language. I liked that the authors constructed a trace tree that tracks not only hot loops but also hot exits, which helps the compiler covers more hotspots and deal with loops of arbitrary depths. Some other thoughts I had:

• Is there a reason why a greedy register allocator is used other than simplicity?
• TraceMonkey did not trace recursion (p.475), resulting to little to no speedup on recursion-heavy benchmarks. I thought this led to an uneven improvement which might not be expected by the programmer. I read that recursion tracing was added in a later version, but eventually TraceMonkey was replaced by JägerMonkey, a method JIT (which was itself replaced by a newer Monkey). I haven't delved too deep but it would be cool to know what the newer ones are better at doing.
• SunSpider, the benchmark suite used in the paper, consists of 26 short-running (less than 250ms, average 26ms) JavaScript programs. It would be interesting to know how it performs on longer programs.
• The paper does a good job of analyzing where the VM spends its time (figure 12), but it would be interesting to know how much space overhead there is too

[stephenverderame]

I think the main reason for choosing the register allocator they did was more for compilation speed. I think they mentioned they only wanted optimizations that run in O(n), and even made the point to run all the forward passes while recording the trace. So I think the linear register allocation rather than the typical graph coloring approach was really to fit this constraint.

I also found it interesting they chose short programs, especially since they roughly need something like 270 trace runs to break even on the cost of tracing. They would have more promising results for showing longer programs. I agree it would have been nice to see both, but I suspect they chose short programs since being able to outcompete the other engines on benchmarks they could have a disadvantage on is pretty impressive.

[sampsyo]

I wish I had a good answer to this question, but I think it’s a really interesting question: what makes method JITs seemingly a better/more natural fit for recursion than tracing JITs? (And why is this difference different from the difference for loops?)

[zachary-kent]

This was super interesting! I had a couple questions/thoughts:

• I'm not sure that the test suite is exactly representative of most (client-side) JavaScript programs; I would hope that most frontend code doesn't spent a lot of time in loops. From what I can tell, SpiderMonkey was the JIT that powered FireFox and not a JIT for server-side JS code (but maybe it could be used as a server-side runtime, I'm not sure). I wonder how TraceMonkey affected the "average" performance of Firefox.
• Because JS is single-threaded, it seems like taking advantage of multicore architectures could be a massive win, beyond even parallel trace-tree recompilation mentioned in the paper. You can imagine the main "interpreter" thread executing the actual byte code and logging it to some shared memory region. A separate thread could then handle the logic for trace recording and compilation, possibly allowing traces to be more heavily optimized without a performance penalty. When the main interpreter thread reaches a loop header, it can then check if the "JIT" thread has compiled a trace for that loop. Has any work been done towards this end?

[sampsyo]

SunSpider is indeed deprecated/disused for a reason. It was the main driving benchmark suite behind the JavaScript engine wars of the 2000s, but the industry eventually outgrew it. It is, in general, really hard to say what would make a benchmark suite representative of real-world web browsing, since this is such a shifting target---and was even more so at the time.

That is, it would have seemed unreasonable back in the day that people would ever run particle simulations written in JavaScript. But that was in part because JS compilers were not great at the time. But then the compilers improved, and therefore the workloads people wanted to run expanded. Now it is not surprising at all when people do hardcore computational kernels in JavaScript so they can run in browsers. (WebAssembly’s growing market share notwithstanding.)

Putting the JIT compilation on a separate thread (hopefully to exploit a different physical CPU core) is indeed interesting, and I don’t think it’s uncommon to do today. Here is one paper about this:
https://dl.acm.org/doi/10.1007/978-3-642-00722-4_16

[keikun555]

I wonder if the nested tree idea can be used to solve the recursion problem in the paper.

[stephenverderame]

• One thing I found interesting was their "two-level" approach to JITing. The paper describes how for something like an object lookup, the trace will first replace the general instructions, taking complex inheritance relations into account, into a few bytecode loads to get the exact property being accessed. On its own, this feels like something that an interpreter, not compiling to native code, could take advantage of. In practice, I'm not sure if stopping here makes any sense since the tracing cost and machinery might very well be similar to a full JIT, but it is interesting to consider. It seems reasonable that this could have a smaller "compilation" cost than a full JIT and could be another point in the design space between interpreter and compiler.
• I wish the authors discussed how they came up with their "hotness" threshold of 2. One of the problems they discuss in their evaluation section is the "two programs which trace well but have a long compilation time." It would be interesting to know if increasing the hotness threshold to reduce the number of traces helps with this.
• It was cool to see how all their optimization passes on the compiled trace basically amount to dead code/store elimination and what sounds like something that can be implemented in a souped-up LVN since a trace effectively becomes a giant basic block.

[sampsyo]

To your first point, here is a really cool blog post I liked recently about getting some similar JIT-like efficiency out of an interpreter:
https://cfallin.org/blog/2023/10/11/spidermonkey-pbl/

The setting there is running an JS interpreter under WebAssembly, where JIT compilation is not allowed. Squeezing performance out of polymorphic inline caches in that setting is hard but possible!

---

It’s a good point about mysterious heuristics. Mysterious, seemingly-arbitrary thresholds are everywhere in JITs. For a long time, I have thought it would be a really fun project to try replacing all of these heuristics with parameters for a machine learning model, and then train them based on real executions of a corpus of programs. Maybe it would be possible to do a lot better than hand tuning.

[alifarahbakhsh]

The paper mentions that traditional static type inference is way too expensive for the highly interactive environment of a web browser. Echoing Zach's point above, their test suite does not seem to be representing this highy interactive environment. Moreover, I am a bit confused as to why static type inference is not suitable. If we could guess most of the types that can show up on runtime, all we have to do is to pay a one-time heavy price of static type inference for all possibilities, and then use it alongside some jitting techniques to execute the appropriate piece of code when types are finally revealed at runtime. Since the cost is one-time only, this could potentially be plausible. It would be great to see some explanation about this in the paper.

[sampsyo]

I actually don't think the problem is that static type inference is too expensive---it's that it's not precise enough. That is, taking an unannotated JS program and soundly inferring specific-enough types to enable practical optimizations is only possible in very restricted cases.

[Enochen]

Here's the PR for our blog post: #416