Hacker News Reader

Comment by stevekemp | Hacker News Reader

On that theme, collapse-OS has a discussion:

“Forth isn't particularly fast either. As an interpreted language, it is blazing fast, but the speed tax of the threaded model still has to be paid, so it will generally be slower than code produced by a C compiler.”

Not being familiar with this sense of “thread,” I found a good explainer here: https://www.complang.tuwien.ac.at/forth/threaded-code.html

And, as always, Wikipedia: https://en.m.wikipedia.org/wiki/Threaded_code

There are a few issues here. Running threaded code interacts badly with branch prediction. Essentially every "word" (operation) is followed by a branch to the next word, and those seem hard to predict (or at least with 2010-era hardware they were very hard to predict, maybe more modern branch prediction can do better?). The reason is that a popular word, say, +/add, might be called from all over the program. Only one copy of the word exists and the indirect jump to the next word could go anywhere.

However Forth does allow you to "inline" words, basically form a new word by chaining together existing words, which avoids this overhead. This doesn't optimise adjacent words, but it still gets semi-reasonable performance. (Inlining in JONESFORTH: https://github.com/nornagon/jonesforth/blob/d97a25bb0b06fb58...)

Modern Forths just have regular optimising compilers so none of this stuff applies, but they don't have the simple purity of one that you write and fully understand yourself.

Just an anecdotal experience, but I’m currently writing a JVM in Rust with a naive, interpreter loop. OpenJDK’s interpreter is a so-called template interpreter which looks at the method’s byte code and generates a given machine code snippet for each instruction, puts them serially next to each other and executes this buffer. The advantage of the latter is that in the interpreter loop model, one jumps back to the switch statement which will jump to the next instruction’s implementation, etc, while OpenJDK’s solution just continues execution serially, taking advantage of the branch predictor.

In my benchmarks that are definitely not suitable to infer much, OpenJDK without JIT can perform 1.5-8x better, though of course the whole implementation is different so don’t read too much into that.

It's amazing to me in general how much of a divergence in expectations of performance vs reality that branch prediction misses causes in modern software.

So many techniques that would improve performance on a 1980s processor can be woefully inefficient on a 21st century one. It's so easy to be still holding the computing model of the former in your head.

What is absolutely crazy is that many “primitive computation” is basically free. Like, there is more than likely some memory stalls either way and they just happen in the pauses not causing longer execution time.

I learned it the hard way when I was writing an emulator for a retro machine. Say you're blitting sprites to the screen. As you're drawing a line, each pixel either has some portion of a sprite, or doesn't. Your instinct is to do just like the hardware and 'chase the beam' and check at each pixel, or even just for each line, whether a sprite is present.

Super wrong. You're far better off precomputing the whole sprite bitmap -- even if you don't end up using it and doing a bulk operation to display it or not display it. Because doing that "if sprite is here?" in a loop is super super expensive, more expensive than just blitting the splits and not using them.

Most efficient ended up being precomputing things into boolean bitset vectors and using SIMD operations to do things based on those.

Even if not doing GPU stuff, the fastest way to compute these days is to think of everything in bulk bulk bulk. The hardware we have now is super efficient at vector and matrix operations, so try to take advantage of it.

(After doing this I have a hunch that a lot of the classic machine emulators <VICE, etc.> that are out there could be made way faster if they were rewritten in this way. )

Theaded code always interests me, but there definitely is a price to it. Should be noted though that a lot of newer Forths diverge from the classic threaded code model. Because it is a concatenative language, it is possible to have one that compiles native code by copying inlined subroutines (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56...).

For example to compile : SQUARE DUP + ; all the compiler has to do is copy the machine code of DUP to the place where SQUARE is being compiled, remove the ret instruction at the end of it, and copy the machine code of + after it. It can also do some small optimizations to remove redundant instructions.

You can do this with other languages, but concatenative languages can make it as simple as literally concatenating bits of code.

Yeah, that's pretty much how Ur-Scheme compiles, inspired by bigForth: http://canonical.org/~kragen/sw/urscheme

kragen, I emailed you on the 28th, can you please check it?

Not finding anything with from-address containing "j6a". Sorry, I'm not doing very well, so I apologize if I should recognize you.

here's a hint: you sent me this link a while ago. also, i sent you something and am trying to make sure you get it.

https://news.ycombinator.com/item?id=28936057

no reason you'd recognize this account that i just made, but I just resent the email and added j6a to the subject, so can you please check again.

It would be nice if the compiler could tell you:

    ERROR: DUP + is not SQUARE. Did you mean DOUBLE?

Yeah, that was a mistake. Changed it from * to + at some point when writing it and forgot to update it.

It's like the compiler becomes the CPU you wanted in the first place.

As with all languages, the compiled/interpreted distinction is a thing of convention/existing tools. Interpreted Forth is small, and tolerable speed-wise for tiny systems. But Forth can also be compiled directly to native machine code.

Relatively easily, you can get rid of the interpreter overhead by writing blocks of machine code that do each Forth word's action, instead of bytecode to dispatch the interpreter to each of those routines. Forth can be adapted for that easily enough, and some Forths do support this on a per-word basis, allowing you to pick how you want your words compiled.

Forth can also get the whole optimizing compiler treatment. Some optimizing Forth compilers have been released, but I don't know how good they were/are. Certainly never needed that kind of speed myself. I don't know if any Forth yet benefited from it, but a lot of work was put into Java, on approaches for optimizing stack machine-style code to reasonably fast native code for register machines.

Reply on news.ycombinator.com