News for hackers. Stuff that matters.
Re:Squeezing a Little More Performance Out of Bytecode Inter... by astrobe_ on Sunday June 18, 2023 @03:29AM (#36378093)
> Our results suggest that it can give large improvements when training for a specific benchmark.

> improved the execution speed of the program for which the order was optimized between 0.8% and 23.0% with 7.7% on average.

Single-digit speedup is not worth it IMO, and the wide range (<1% - 23%) probably means that you specialize for some tasks at the expense of other types of tasks, which is not for everyone's interpreter.

One use I can see for it is to compile multiple inner loops and have the interpreter switch between them (probably manually), if that can get us the yummy 20% speedup. Core primitives and dispatchers are usually not the biggest part of interpreters, after all. Maybe in this scenario the core primitives could also benefit from small semantic changes, like no bounds checking for instance.

Re:Squeezing a Little More Performance Out of Bytecode Inter... by _a_a_a_ on Sunday June 18, 2023 @07:28AM (#36379195)
> Single-digit speedup is not worth it IMO

would you reject a single-digit pay rise? :)

Re:Squeezing a Little More Performance Out of Bytecode Inter... by 13of40 on Sunday June 18, 2023 @08:23AM (#36379591)
Well, to continue the analogy, they might be asking me to do 10% more work for 2% more pay.

Owning and maintaining a trainer in your build system would be a form of technical debt.

Re:Squeezing a Little More Performance Out of Bytecode Inter... by eldenring on Sunday June 18, 2023 @03:35AM (#36378113)
It would be cool to see this compared with a more simple bin packing technique, or even just stuffing the most commonly used instructions at the top and those ordered by size.
Re:Squeezing a Little More Performance Out of Bytecode Inter... by dvh on Sunday June 18, 2023 @04:00AM (#36378202)
Re:Squeezing a Little More Performance Out of Bytecode Inter... by dazzawazza on Sunday June 18, 2023 @06:08AM (#36378816)
wayback machine has a single cache for the curious: https://web.archive.org/web/20221030174643/http://spa.info.k...

interesting read.

Re:Squeezing a Little More Performance Out of Bytecode Inter... by smarr on Monday June 19, 2023 @10:58AM (#36391817)
Yeah, the serve seems to be temporarily down. The paper can also be found here: https://tugawa.github.io/ejs-comlan-preprint.pdf
Re:Squeezing a Little More Performance Out of Bytecode Inter... by runehol on Sunday June 18, 2023 @04:20AM (#36378302)
The key problems with this approach is not mentioned in the blog post, but is shown in figures 6 and 7 of the paper - https://stefan-marr.de/downloads/acmsac23-huang-et-al-optimi...

Basically, the code handler ordering does not generalise well across benchmark nor processor, so to get the speedup they see, you'd need a specialised interpreter for your specific benchmark and processor. That puts this into the "interesting, but not very practical" category.

Re:Squeezing a Little More Performance Out of Bytecode Inter... by CmdDot on Sunday June 18, 2023 @05:33AM (#36378644)
From the post: «In the context of resource-constraint embedded devices, it may make sense to tailor an interpreter to a specific applications to gain best performance.»

The «key problems» are also discussed in the introduction of the paper at the top of page 2 - including why it’s practical in their context.

Also in the paper, they say speedups based on optimizing a subset of benchmarks generalize to other benchmarks as well, but not across environments.

Last I checked, starting with an «optimizing your environment» task, is far from being considered «not very practical»

Re:Squeezing a Little More Performance Out of Bytecode Inter... by _a_a_a_ on Sunday June 18, 2023 @09:07AM (#36379952)
Come on man, they literally say that, and acknowledge hardware may differ in behaviour, that difference too to be subsumed by the training/optimising.
Re:Squeezing a Little More Performance Out of Bytecode Inter... by jonstewart on Sunday June 18, 2023 @09:09AM (#36379972)
I wish there was a bit more analysis of the properties/qualities of reorderings that improved performance. Also, how do the improvements intersect with profiler-guided optimization?
Re:Squeezing a Little More Performance Out of Bytecode Inter... by _a_a_a_ on Sunday June 18, 2023 @09:36AM (#36380172)
This is my area of interest and I know a little about interpretation/compiling. I'm a little dubious about this (which I shouldn't be because the benchmarks speak for themselves). But a couple of doubts.

1. "it avoids an extra jump to the top of the loop at the end of each bytecode" – but the top of the loop is a known, hardcoded value, so the prefetcher should be able to take the unconditional jump at little or no cost.

2. "we have multiple dispatch points instead of a single one" which is supposed to assist branch prediction - I made a big "oooh!" at that, but thinking it over, the target of the GOTO is computed each time eg.

   push_local:
      void* target = targets[index];
      index += /* ... */
      goto *target;
So I don't see how the branch predictor has that much to work on. I suppose it cuts down on the possible number of targets so it's more likely to predict correctly, and reading again, that's exactly what they say "we may only see a subset of bytecodes, which increases the chance that the processor can predict the jump correctly". Hmm, I'm a bit surprised that makes that much of a difference but a quick look at the benchmarks suggest they are really pretty small. I'd expect the technique to lose its speedup as the amount of code grows.

Perhaps if you wanted speed then picking out common bits of code and inlining it would cut down on the branches and possibly make the code more compact, for better cache use. (that's a bit petty though, it's clearly not the target of their research).

I suppose if you had some spare byte codes left over and you have a commonly used instruction, perhaps 'add', you might have a few different versions of add (add1, add2, add3) which behaved identically but were scattered through the 'source' code, to help the branch predictor even more.

Re:Squeezing a Little More Performance Out of Bytecode Inter... by CmdDot on Sunday June 18, 2023 @11:35AM (#36381194)
I don’t see why it would be dependent on the amount of code - the amount of bytecodes is constant, and the likelyhood of bytecode B following bytecode A should remain fairly stable. Adding the bytecode equivalent of fused madd if there’s unused space would be an interesting extension - but maybe a bit unintuitive in the heuristics of how to choose good candidates - if it’s really the mispredictions that cause stalls, you’d want the ones where the split of A -> B and A -> C is fairly even, not the most common combinations. Almost worth a paper of its own to explore :)
Re:Squeezing a Little More Performance Out of Bytecode Inter... by superdimwit on Sunday June 18, 2023 @03:04PM (#36383265)
On 1: this small amount of overhead matters because the amount of work you do on each opcode can be tiny. The extra jump could be 20% of your runtime! On 2: yes, this helps the indirect branch target predictor. In a real program you’ll often get repeated sequences of opcodes (increment, then compare) that can be predicted. These branch predictors can be pattern based.
Re:Squeezing a Little More Performance Out of Bytecode Inter... by kaba0 on Sunday June 18, 2023 @06:31PM (#36385204)
So you are questioning the effect of direct threading code? Because I assure you, that has a significant impact compared to the naive switch-eval loop, on the order of 2-4x from my experience.

(Source: have written a JVM interpreter with the naive approach that is approximately that much slower than the OpenJDK with disabled JIT compiler. It was later also confirmed by people working on the actual JVM that that’s roughly the order of difference between the two approaches. Unfortunately I can’t find a great article on the topic right now (google is beyond useless recently)).

The article is about a further small improvement over this much larger and commonly implemented one.

Re:Squeezing a Little More Performance Out of Bytecode Inter... by hinkley on Monday June 19, 2023 @12:03AM (#36387209)
The last new information I had on this was that direct threading stopped being a distinct perf advantage when branch predictors got more sophisticated (able to predict indirect branches).

Do you have benchmarks on current gen hardware that suggest that the code complexity results in a measurable difference in outcomes?

Re:Squeezing a Little More Performance Out of Bytecode Inter... by kaba0 on Monday June 19, 2023 @12:48AM (#36387412)
I wrote that interpreter roughly a year ago — my computer is definitely not the most up-to-date (the CPU is an intel i5-4690), but I would be surprised if the difference would have disappeared.

Also, I don’t think that it could even in principle be efficiently branch predicted — you are basically doing a memory read, jump conditionally based on that, jump back, do another memory read vs memory read, jump there, memory read, jump there. There is one less jump involved here, so any form of improved branch prediction would also enhance this second form as well.

I found this, you might be able to benchmark it yourself if you have better hardware: https://github.com/vshymanskyy/interp

Re:Squeezing a Little More Performance Out of Bytecode Inter... by ghusbands on Monday June 19, 2023 @01:01AM (#36387473)
Even if it were only the same speed on current gen hardware, most users are on older hardware, anyway, so it would still be a win unless it actually reduced performance.
Re:Squeezing a Little More Performance Out of Bytecode Inter... by hinkley on Monday June 19, 2023 @03:40AM (#36388358)
That was pre COVID news, if not more on the order of five years ago. Although now that I think of it, with Spectre and Meltdown mitigations perhaps the clock has been turned back on those improvements.
Re:Squeezing a Little More Performance Out of Bytecode Inter... by _a_a_a_ on Monday June 19, 2023 @03:54AM (#36388444)
> So you are questioning the effect of direct threading code?

No, cos I said "the benchmarks speak for themselves". But I am trying to understand why it's better and under what circumstances.

Re:Squeezing a Little More Performance Out of Bytecode Inter... by kaba0 on Monday June 19, 2023 @05:13AM (#36388942)
I meant it in terms of whether your question is about the reordering or the direct threading vs naive switch-loop.
Re:Squeezing a Little More Performance Out of Bytecode Inter... by _a_a_a_ on Monday June 19, 2023 @05:10PM (#36396508)
The direct threading is what interests me. From a link provided above by ghusbands https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...

"...and the goto version is 25% faster than the switch version...

Comments inside the CPython implementation note that using computed goto made the Python VM 15-20% faster"

(Which isn't the 2-4x speed up that you found).

In that link they say that part of the reason is because of the bounds checking which is automatically done by the switch statement.

What I'm struggling with which is no doubt down to my lack of knowledge, is why it should be significantly faster (if you take out or disable the bounds checking added by the switch). I can see there would be some advantage in spreading out the jumps so the branch predictor could work a bit better, but I am surprised at the speed up. I guess mispredicted branches are so expensive that doing just a little bit better could account for the difference, but I am trying to understand it.

Re:Squeezing a Little More Performance Out of Bytecode Inter... by ghusbands on Monday June 19, 2023 @12:59AM (#36387461)
It's odd that this is your area of interest and yet you don't know of the commonly-used direct/indirect threading techniques. Many interpreters, including a famously fast one [1], use them, and benchmarks have repeatedly shown it to be a significant gain [2].

[1] http://lua-users.org/lists/lua-l/2011-02/msg00742.html

[2] https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...

Re:Squeezing a Little More Performance Out of Bytecode Inter... by _a_a_a_ on Monday June 19, 2023 @04:59PM (#36396383)
My interest is in compilers much more than interpreters, I haven't come across this threaded style before, my interest in languages and compilers is something I've barely used at work, and everything after university that I've learnt has been self-taught. There are inevitably going to be holes.

Anyway, great pair of links, much appreciated!

Re:Squeezing a Little More Performance Out of Bytecode Inter... by dddnzzz334 on Sunday June 18, 2023 @01:05PM (#36382073)
Didn't know goto labels can be treated as values.

TIL: https://stackoverflow.com/q/1777990

Re:Squeezing a Little More Performance Out of Bytecode Inter... by superdimwit on Sunday June 18, 2023 @03:05PM (#36383280)