Comment by MindSpunk | Hacker News Reader

Comment by MindSpunk | Hacker News Reader

Parent Full thread

I'm not convinced the performance benefits are entirely the result of the more compact object representation. It definitely would help, but looking at the code snippets the author provides for the add instruction there's an important structural change that would be making a huge difference.

The old, enum based value type used a single big match statement to dispatch between all possible type combinations. Their assembler output looks like the match gets compiled to something like a big stack of nested if statements.

The new code uses an explicit fast path check with a dispatch into a tagged 'cold' path when the common case isn't hit. The generated code is a single upfront branch for the fast path that exits immediately, with a dispatch into the slow path in a separate function.

This would be contributing significantly to the performance improvements. The old path requires taking several branches even on the hot path. The new code has a single, highly predictable branch that skips all the messy dispatch for the other types.

This could have been implemented for the enum based value type, and I would expect to see a jump in performance there too even without the new compact value type. There will be a much higher branch predictor hit rate with the explicit fast path.

Author here. The disassembly for the old enum handling had many spills, simply because the old value enum can't fit in a single register. If you have an instruction that two operands with two of those big value enums, it needs 4 registers instead of 2. That, coupled with better cache-friendliness, explains a lot.

Absolutely, I agree. I suspect that explicit branch for the hot path is doing a lot too.

Separating the hot path into a prefix before calling into a separate cold function should still generate better code. Your prefix only needs to allocate registers and stack space for just that single path. You would only pay the spilling costs in the old code off the hot path rather than every instruction. And I would expect the branch prediction accuracy of that prefix check to be higher than having the hot and cold paths all dispatching through the same tree of branches.

However it's speculation until you measure so I could be wrong.

Good article in any case, I enjoyed reading along.

100% agreed (see my sibling comment), this all accumulates for in-language function calls,etc since code at runtime often spends a surprising amount of time just moving around values instead of doing useful work, having them just as singular register values really helps a ton.

This was probably 15-20 years ago at this point but I was doing a lot of micro-tests in terms of dynlang->C/C++ transpilers (in relation to my MsC thesis) to see the effects of different value-models, GC strategies and the win of compiled code vs interpretation/JIT (Some might say that a transpiler via C skews the result but it did more or less optionally generated code without delving into writing a good lowlevel codegen).

Don't remember exact results but you could clearly see the stages that made up the raw computation performance differential (12x at the time iirc) between CPython and V8(JS).

Each of the above steps made up for a 2x-4x differential (don't remember the ratios exactly but combined about 12x or the V8 / CPython differential).

- Interpretation vs JIT (surprisingly a smaller than expected benefit)

- Memory model, moving from naive referece counting (very frequent per-operation bookkeeping operations) vs GC (GC does work, but compared with a GC doing small/incremental work it's miniscule compared to a naive ref-counter)

- Moving to tagged primitive integers from a "fat" tagged type (ie tag+ptr/value), biggest surprise to me, a bit like in this article.

Like the article mentions in the end, you have twice the number of values to move around, with singular values they just ride along in registers but also the fatter representation will make it far harder for the compiler to manage register allocations, remember a dynamic runtime doesn't only move around values, there's often GC or other context objects being kept around that contribute to register pressure.

On top of that, I don't remember the exact author, probably referenced in the old 90s Agesen type inference papers, but a very high percentage of operations in compiler code is just related to moving around values (think function arguments,etc), every instance of those becomes moving around 2 values instead of just a single register.

Tl;Dr; If it's not your first rodeo in compilers, IMHO just design your runtime primarly for register-passable values from day one, it might feel like premature optimization, but since the value model will permeate so much of the runtime, the knock-on effects once you do decide to fix it probably makes it worth to go with it from day 1.

Strongly agree. Ironwood (https://github.com/ironwood-lang/ironwood) takes that to the limit by throwing away the JVM :) The static type is the tag, so nothing is tagged at runtime. Primitives are machine-width values, references are one pointer, and generics specialize in the closed world, so the language has no boxing at all.

> If it's not your first rodeo in compilers, IMHO just design your runtime primarly for register-passable values from day one, it might feel like premature optimization, but since the value model will permeate so much of the runtime, the knock-on effects once you do decide to fix it probably makes it worth to go with it from day 1.

Day one, definitely. Those were cheap to fix only because the value model never had to change.

Umm, Java/JVM has mostly static typing (if you discount the generic mess) but regardless Java/JVM computations has no type-tags for values (vtables for object types however).

This discussion is mostly in relation to dynamically typed languages such as JS (Not Java), Python,etc.

And unless the language was initially designed for static typing it's not always applicable to mix in discussions of static typing (I literally wrote my thesis on the subject of type inference).

But CPU branch predictor should have figured out hot paths in the original implementation?

Reply on news.ycombinator.com