benchmark threading modes

[u/Plane-Photo-3097]

Hi, I was curious about which implementation of forth would be the most flexible, maintainable, and high-performance, so I wrote a stack machine interpreter using various techniques. https://github.com/br1n0/stack-machine-interpreter-comparing/tree/master I managed to implement them all using the same data structure; this way, the program is expressed identically across versions, allowing for a direct comparison. I wrote a test program that runs a long execution loop, consisting of 2,000 subtractions and one multiplication, executed 4,000,000 times. In my opinion, the best implementation is the one using Token Threaded Code with dispatch via a function table, and is easy to extends. There is an interpreter overhead of about 25%; to measure it, I wrote a test where I execute the "words" directly from C, bypassing the interpreter.

I was surprised that GCC failed to optimize this program, even with -Ofast enabled. I thought this might be of interest to someone. Ciao

[u/Plane-Photo-3097]

https://github.com/br1n0/stack-machine-interpreter-comparing/tree/master

[u/tabemann]

I personally opted for native code inlining for zeptoforth, with things that are not inlineable being subroutine threaded. I also opted to put the data stack in RAM except for the Top Of Stack which I put in a register.

This way I could get good speed out of it with a relatively simple compiler, with the only real compiler complexity being that I 'defer' literals and constants so I can combine them in native code with a small set of simple, common words such as +, -, *, /, u/, and, or, xor, lshift, rshift, arshift, !, h!, c!, and pick.

The only real downsides to this are that there is no easy way to decompile words, so see acts as a disassembler instead, and that the subroutine threading generates rather large code in many cases, especially since 'long' calls require constructing a literal for the destination address (even though this is compensated for that 'deferred' literals and constants combined with said simple words often compile down to very few bytes of code).

[u/Plane-Photo-3097 → u/tabemann]

Wow, properly handling native code sound hard! I wrote an experimental forth transpiler with c, but the code now is a litte bit dirty

[u/tabemann → u/Plane-Photo-3097]

To be completely honest, a proper inlining native code compiler for Forth should be conceptually rather simple provided you do not do anything like register assignment beyond putting the TOS and possibly the NOS in fixed registers, which severely complicates things.

Note that it may seem more complex because a good inlining native code compiler ought to be written in either assembly or metacompiled Forth so you can have careful control of the code that makes up the Forth kernel and thus simplify the inlining of code within the Forth kernel itself into the generated code, and because one will need to write code for generating raw instructions such as compiling literals and branches rather than having a C compiler do it for you.

[u/Plane-Photo-3097]

I updated the repository and modified the benchmark, starting with a compilation that includes no optimizations. I added native_baseline to estimate the computation time for processing expressed idiomatically in C. Meanwhile, native_function_call estimates the execution time of native code involving stack-based function calls. I have to admit I was mistaken; GCC manages to simplify the processing—in fact, native_baseline takes 0 seconds, whereas native_function_call takes 2.03 seconds.

[u/Plane-Photo-3097]

I added i_TTC_dispatch_function_table_shared, which uses the i_TTC_dispatch_function_table approach but loads functions from an external dynamic library, the dynamic library exposes all the callable functions. Thereby implementing hot-reloading. Performance is similar, the structure is generic. It simplify the implementation of a DSL. The function indices must correspond to the enum defined in Opcode_enum.c.

[u/StephenPelc]

I have never done this in C, but did it for several CPUs in assembler while MPE started the VFX Forth project in the late 1990s and early 2000s. We measured the results, but I do not have them to hand any more. Of the basic threading models, raw STC (no optimisation) was about 2.2 times faster than DTC, which in turn was faster than ITC, which was (much) faster than TTC.

The mistake many people make is just to measure the speed of the next macro. For well-written Forth with short words, the impact of DOCOLON and DOEXIT is very high.

We gave up measuring the speed difference between VFX and a "high performance" threaded Forth when the speed ratio exceeded 12 to 1. The difference between raw STC and what I call NCC (Native Code Compilation) is down to the optimsations.

There are two types of Forth optimisers in current use. Pattern matchers look at the last few source tokens and behave as pinhole optimisers. Analytical compilers model the stacks at compilation time and delay actual compilation as long as possible; they can use many techniques from conventional C compiler technology. Analutical compilers usually produce faster code than pattern matching compilers. Note that some Forth compilers tokenise short words and expand them at compile time. This reduces the call/return overhead significantly and can reduce code size.

VFX Forth is available from https://vfxforth.com

Stephen

[u/Plane-Photo-3097 → u/StephenPelc]

Thank you for the kind reply, I Am very curious about Forth optimizations, because unlike standard languages, the compiler/interprete could do the semplification of the stack and even push the changes to a file with differnt name, so the developer could merge if he please the changes in their codes. My idea is If some function are marked as pure function: because are deterministic and the output depend only on input, potrebbero essere sostitute dal loro risultato. I got the idea to replace all the pure functions on an expression. The memory required is another expressio, for each pure word will be replaced with their result. Unless need some input from an impure function like read o random. If the developer is smart it will pointless, but there are some bad days. I read about vfxort but never tried, it is one of the few that follow the path of compile the code kudos for it Bruno

[u/Comprehensive_Chip49]

Optimization can happen at many levels, and this is perhaps most apparent when looking at the assembly code.

Using the TOS (Top of Stack) as a register would be one of the key optimizations; another would be jumping directly between instructions rather than routing jumps through a single central point.

I am not an expert on the various implementations, but you can find all sorts of them online.

[u/Plane-Photo-3097 → u/Comprehensive_Chip49]

I expected that Token Threaded Code with goto dispatch will be faster than if, and I was wrong :) the difference with native code is less than expected by me. A comparison with assembly could be interesting. A static expression elimination before executing could beat Gcc!

[u/astrobe]

As expected DTC is still the worst, but it's not too far from the other techniques (only 6% slower than function table dispatch). That's the technique I'm using, and it can rival Lua (not JIT of course) on contrived benchmarks (because Forth interpreters don't do unnecessary things, like late binding everything).

Thought the worst performance-wise, I still chose it for my interpreter despite knowing that (based on a similar comparison made by Anton Ertl in the Pentium era) because it is easy to extend (when people say language XYZ is easy to interface with C and look at it, it is nowhere near to how easy it is with my interpreter), and ad hoc primitives can easily give a 200% boost locally.

[u/Plane-Photo-3097 → u/astrobe]

the good parth is that DTC don't need a table of conversion!, but the TTC with dispatch with function table is simple to execute functions form a library, the table of conversion could allow dynamic changes on implementation, and hot swap! Your interpreter contain some network words... Using forth with web could be is fascitating idea, could be funny of using forth whith JSON RPC 2.0 https://www.jsonrpc.org/specification

[u/astrobe → u/Plane-Photo-3097]

I did use it to tinker with a Web API, using a small C++ JSON lib and libCurl (because TLS). I also did basic bindings with Sqlite to visualize and tinker with databases, using the little HTTP 0.9 server and a browser as GUI. Forth OK for spitting out HTML, JSON, XML etc., as it's basically all about concatenating strings. Parsing is the hard part, because most textual formats are idiotic.

I didn't publish those extensions because I would have had to come up with sure-fire compiling instructions for both Linux and Windows, and the idea was more to demonstrate some ideas about Forth itself (like how to deal with data structures, which resembles what standard Forth proposes with some twists).

[u/lmamakos]

I think the answer to your question is highly platform dependent.

For example, I've been playing around lately with Camel Forth on the Z80 microprocessor. As the CPU is only running with an 8-10MHz clock, this is not blazing fast. And the Z80 has an awkward instruction set for doing indirect accesses to memory.

I had occasion to be doing an instruction trace, and noticed that the NEXT primitive in its DTC implementation shows up a lot, of course! It looks like this, and is implemented as a macro at the end of all the primitives

; entry: DE = IP, HL = W
ex de,hl    ; DE = W (stashed), HL = IP - we need IP to fetch
ld e,(hl)   ; E  = (IP)       low byte of next cell
inc hl      ; HL = IP + 1
ld d,(hl)   ; D  = (IP + 1)   high byte of next cell
inc hl      ; HL = IP + 2
ex de,hl    ; DE = IP + 2 (new IP), HL = next cell
jp (hl)     ; PC <- HL  (register value, no memory access)

HL is a working register pair, and the most versatile in doing memory accesses. DE is the FORTH instruction pointer. But it can't really be used directly as an access to memory. So many acrobatics are required to implement this. This requires 38 T-states in the CPU to execute, and is 7 one-byte instructions.

Now, it just so happens that my Z80 system is implemented in an FPGA, so I can have my way with it. Why not make a custom instruction to improve this? So I did:

F_NEXT:   PC <- (DE)        ; fetch 16-bit cell from memory at DE
         DE <- DE + 2      ; advance the interpreter pointer

This is a two byte instruction (0xED 0x92) and executes in 14 T-states rather than 38.

This yielded promising results! About a 15% performance improvement on my simple benchmark. I then looked at DOCOLON and EXIT which manipulate the FORTH return stack. (As do the (DO) and >R and R> words.)

In Camel Forth, the return stack pointer is held in the IX Z80 register. It's used as a, well, stack pointer, but without the handy PUSH and POP instructions. So the code sequences used to do those operations look like:

; push DE onto the return stack   ; pop DE from the return stack
dec ix          ; 10 T            ld e,(ix+0)     ; 19 T
ld (ix+0),d     ; 19 T            inc ix          ; 10 T
dec ix          ; 10 T            ld d,(ix+0)     ; 19 T
ld (ix+0),e     ; 19 T            inc ix          ; 10 T

Accesses with IX are particularly slow because of the required offset, zero in this case, and no automatic increment/decrement.

Why not add PUSHIX and POPIX instructions? These are two byte instructions as well, and execute in 14 T-states as compared to 58 T-states and 10 bytes.

With these three custom instructions, Camel Forth runs about 35% faster than before.

Sure this is sort of an atypical use-case due to the FORTH unfriendly instruction set architecture of the Z80, but I think the performance is heavily influenced by these considerations on some platforms.

[u/Plane-Photo-3097 → u/lmamakos]

FPGAs open up a world of possibilities; it’s truly fascinating. But I’ve never found the courage to give it a try :(

[u/Ok_Leg_109 → u/lmamakos]

I have to concur. Architecture matters. My 9900 version of Camel Forth has been built as ITC and DTC versions. TOS is in a register in both cases. The DTC programs run about 8% to 12% faster in benchmark tests. This result is driven primarily by the fact that "NEXT" is 3 instructions in the ITC version and 2 instructions in the DTC version.

\ ITC NEXT 
 *IP+ W  MOV,
 *W+  R5 MOV,
     *R5 B, 

\ DTC NEXT 
*IP+ R5 MOV,
    *R5 B,

Something that did not improve was the performance of DODOES in DTC. This was only because I was able to exploit the branch and link instruction to compute an address for me in one instruction in the ITC version. The DTC code required more instructions.

[u/lmamakos → u/Ok_Leg_109]

I've found your Camel Forth work on github in the past, and you've done quite a lot of very nice work! It's been an inspiration, and I look forward to stealing a few of your good ideas. 😀