Hacker News Reader

Comment by pcwalton | Hacker News Reader

> I reckon performing a hashtable lookup during every single method call has a bigger effect on performance than garbage collection.

Well, a high-performance Ruby VM will perform inline caching to mitigate this. And if the VM isn't a high-performance VM (i.e. it's interpreted), then the overhead of the interpreter dispatch loop dominates everything.

View on HN

The notion that the overhead of interpreter dispatch dominates everything else (and thus the most focus should be placed on optimizing dispatch) was formed with experiments against microarchitectures that are fairly primitive by current standards.

Earlier indirect branch predictors didn't take much execution history into account, mostly associating a predicted branch target with the address of a branch instruction. With a predictor of this kind, using a distinct branch instruction for distinct execution paths dramatically improves the amount of context available to the branch predictor. The same remains true if you add a small amount of context to the predictor.

Over time, conditional branch predictors incorporated more branch history, e.g. the various designs like OGEHL / TAGE based on associating a branch instruction with multiple branch histories whose lengths form a geometric series. The same trick was quite successful when applied to indirect branches, although it is more difficult to implement because the result of a prediction is an address rather than a single bit indicating the branch direction.

You can see evaluations of various benchmarks against both actual Intel processors and simulations of the leading academic branch predictor designs here:

https://hal.inria.fr/hal-01100647/document

On Haswell and later (and with their model of ITTAGE) the mispredictions encountered by a switch-based interpreter loop are negligible.

That being said, I would still write an interpreter in assembly myself, because the code generators found in traditional compilers do a poor job of generating code for interpreters, and you can do a better job of deciding what work goes on the inline fast path and what goes on a slow path. When you're writing an interpreter by hand, you might as well use separate indirect branches for dispatch because there's no impedance mismatch like there is in C/C++.

"because the code generators found in traditional compilers do a poor job of generating code for interpreters,"

Are you referring to the assembler in the GNU toolchaine or? Could you elaborate on this sentiment? Thanks.

I mean "code generator" as in the backend of a compiler that comes after most optimizations have been done. In particular, most common register allocators and schedulers are designed to optimize code that looks much different than an interpreter loop, and they generally do a poor job on interpreters.

I'm admittedly not very familiar with compiler backends - especially not JIT compilers. But how does this optimization even work if I'm constantly modifying the method tables of objects at runtime? If I understand correctly, ORMs and Web frameworks for dynamic languages do this sort of thing all the time.

In a JIT for a dynamic language, you generally have to predicate your more aggressive optimizations on some runtime condition, e.g. "this variable is actually an integer", or "this object has the same method layout as other objects did before". These conditions are checked before relying on the optimization, and if they fail, the generated code jumps into a runtime that may decide to use an interpreter, generate deoptimized code, etc.

This actually sounds more complicated thank thinking ahead how to define your abstraction in more precise terms. (So that you don't need to perform optimistic optimizations that you might later need to roll back.)

I don't understand, who should define such abstractions? If you're the JIT developer and you define a value encoding that supports all possible values (so that the JITed function never has to be rolled back), then you can't really optimize.

For example, if the JIT has the code "function(a, b) { return a+b; }", and it sees that the function has been called 50 times with a and b as integers, it can generate a machine code implementation that is just a couple of instructions adding two registers.

If you keep the abstractions wide enough to support other values, you can never achieve this efficiency.

> I don't understand, who should define such abstractions?

The language designer.

> If you're the JIT developer and you define a value encoding that supports all possible values (so that the JITed function never has to be rolled back), then you can't really optimize.

Obviously, the solution is to know the types of values ahead of time. This is precisely where a language with more precise abstractions can make the lives of implementors easier.

Well, yes, but the whole point is to make the lives of the end programmers easier, not of the language implementors. If you want to avoid forcing people to manually tag each variable, the implementors either need to write an optimistic JIT or a really good type inference engine.

More precise abstractions benefit end programmers too:

(0) They increase the effectiveness of code as a communication medium between programmers. To use an analogy: If I tell you a story, you don't need to hire actors to enact it, just to understand the plot. You can just use your knowledge of the English language, right? Imagine if we could do the same with code: programmers conversing in code, because they understand it natively, without having to “interpret” it (in a REPL, using a test suite, etc.).

(1) They decrease the burden of anticipating, preventing and handling things that may go wrong. Again, to use an analogy: Defensive programming in a language with imprecise abstractions is like spending 75% of a construction project's budget on buying insurance.

The fact that precise abstractions usually lend themselves to simpler and more elegant implementations than imprecise abstractions, well, it is just a nice additional benefit.

Clearly there are millions of end programmers who disagree with you, since they could be using a language with more precise abstractions and yet they choose not to. As one of them, my claim is that you need to eliminate the burden of manually tagging each value, because that effort usually isn't worth it. And eliminating that burden while keeping precise abstractions is not an easy task for implementors.

They're generally operating on the assumption that there's some amount of setup that you do initially, maybe the first time you try to call methods on your magic ORM object, that will set up the inheritance for that class and inject the appropriate methods, and then this will mostly stay static for the remainder of the process lifetime. This seems to me like a generally reasonable assumption.

I don't think this scales to systems with more than, say, 50 tables. In an ERP system with dozens of thousands of tables and views, and which supports adding new functionality to a running application server, you can't assume that the database schema will remain fixed throughout the lifetime of the application server process.

Reply on news.ycombinator.com