personal ngaro vm news ;)

Some new words for an assembler

2009-08-21T03:54:00.000-07:00

Hello,

Ngaro mnemonics can now be uses like other words in colon definations:


: test swps + dup * ;

Immediate parameters are handled from within the interpreter:


: fib.n ins 
        adda 
        swps
        decd
        bnzd [ tail ], rts
; fib.n
  constant fib.n-trace

I'm now writing some documentation and will add mor compiler back-ends (x86-64 and ARM at first).

benchmarking

2009-08-19T05:02:00.000-07:00

A first, simple benachmark test:


TYPE: Machine-code generation test
OS:   XUbuntu 9.04
CPU:  Intel Pentium 4 rev 2
      1,6 GHz
MEM:  1024 Mbyte
------------------------------------------------------------------------------
GFORTH 0.7.0;

SOURCE:
: loop-test 1000000000 0 do 1+ loop ; 0 loop-test . bye

START:
time ./gforth --dynamic loop.fs

RESULT: 1000000000

TIMINGS: (at stable):
real 0m5.458s, user 0m4.280s, sys 0m0.036s
------------------------------------------------------------------------------
4P 3.1 LUXOR;

SOURCE:
: loop-test 1000000000 0 do 1+ loop ; 0 loop-test . bye

START:
time ./forth4p -j loop.fs

RESULT: 1000000000

TIMINGS: (at stable):
real 0m1.493s, user 0m1.308s, sys 0m0.012s
------------------------------------------------------------------------------
RETRO DEV (10.2), extended-ngaro:

SOURCE:
: loop-test ins [ inca , decb , bnzb , 11 , rts , ] ;
  loop-test constant loop-test-trace

: start ins [ lib , 1000000000 , lia , 0 , bi , loop-test-trace , rts , ] ;
  start constant start-trace

: test start-trace aot . ; test bye

START:
time ./retro --with loop-opt.fs

RESULT: 1000000000

TIMINGS (at stable):
real 0m2.606s, user 0m1.608s, sys 0m0.096s

is promising because the code generator doesn't use any optimations yet. As written before I'm not happy with the current assembler and try to make code generation simplier. Another work in progress is to integrate the native-code generator into retro's compiler so forth definations would generate traces instead of vm code.

all finished !

2009-08-09T06:10:00.000-07:00

The compiler interface is finsihed so all parts are now complete and can be used from within retro ! I'm now writing an assembler and think about a parser for compiling forth source-code into traces.

The first application for the assembler will be a port of these benchmark suite (just for fun and to oversee possible optimation demands):

http://shootout.alioth.debian.org/

Then there are some projects of me which wait for implementation...

Roadmap for next version:

- Writing an assembler.
- Finishing documentation of the compiler and extended-instruction set.
- Implement back-ends for x86-64, ARM, PowerPC and TMS320c60x
(how about using Retro on the beagle board ?)

For future releases:

- extend the port system for low-level accessing of block devices.
- writing an os for supporting easy file and data access.
- Implement an IDE for retro, a spreedsheed, database and text processor.

Compiler is finished

2009-08-05T15:16:00.000-07:00

The only thing left is implementing some new opcodes for interpreter integration and execution of generated instructions. At current there exist only a back-end for x86-32 class cpu's but work for x86-64, ARM, PowerPC and possibly MIPS and ez80 processors are under way.

By the way, here is a little benchmark of the new interpreter against gforth (please note, without using the compiler yet):

OS:
Ubuntu 2.6.28-14.47-generic

C compiler:
gcc-Version 4.3.3 (Ubuntu 4.3.3-5ubuntu4)

CPU:
Intel(R) Pentium(R) 4 CPU 2.40GHz stepping 07
Total of 1 processors activated (4782.53 BogoMIPS)

Mem:
492852k/516032k

Benchmark (FIB):

gforth 0.7.0 - retro 10.2.1


time ./gforth --dynamic fib2.fs

result: 102334155 

real | 0m9.418s 0m9.466s 0m9.297s
user | 0m9.365s 0m9.373s 0m9.273s
sys. | 0m0.012s 0m0.024s 0m0.012s

time ./retro < fib.f

result: 102334155

real | 0m9.042s 0m8.931s 0m9.651s
user | 0m8.873s 0m8.857s 0m9.565s
sys. | 0m0.056s 0m0.060s 0m0.060s

Source code:


fib2.fs -
: fib dup 2 < if exit then 1- dup recurse swap 1- recurse + ; 40 fib . cr bye

fib.f -
: fib dup 2 < if ;; then 1- dup fib swap 1- fib + ; 39 fib . cr bye

That's interesting because ngaro is a TTC vm and gforth uses DTC via GCC's label-value extension. It seams replicated-switch threading can be compiled to very efficient code (and is ANSI conform) !

Compiler is working !

2009-07-21T15:01:00.000-07:00

The compiler for ngaro now works as espected and I can translate and execute some little vm-code sequences at runtime by hand. Now, as the main work is done it's time to implement the full ngaro-instruction set and extend the new vm with some opcodes for compilation on demand.

New vm version

2009-07-06T09:57:00.000-07:00

The newer gcc-compiler suites drives me crazy because of some "optimations" which make it very hard to implement an indirect-threading interpreter without some deeper investigation of the generated assembler code (the version which uses gcc's first-class label extension).

So I implement a new method called replicated-switch threading which have some advantages:

- this method is ANSI conform.
- the performance seems to be equivalent to the older extended-vm.
- the code generator (gcc) produce better code without the need for using expensive optimation flags.
- the vm source code looks more simply yet.

The next step: Porting my little native-code compiler to this vm.

Status

2009-02-04T11:11:00.000-08:00

Baíran:

TTC and DTC part: works,
meta-code compiler: 3'th rewriting (the last one for sure)

summary: think the vm is finished the end of february.

Then I reanimate my GIT account and port retro to it. As I plan to use the current retro forth for the assembler I think abount the pro and contra of self compilation.

Baíran:

TTC und DTC interpreter: Fertig.
Metacode Compiler: Finale, dritte Version in Arbeit.

Zusammenfassung: Die VM wird Ende Februar fertig sein.

Ich werd dann meinen GIT Account reanimieren und beginnen Retro zu portieren. Hierbei plane ich die derzeitige Version für den Assembler zu nutzen weshalb ich gerade über die Vor und Nachteile philosophiere, das ganze irgendwann sich selbst kompilieren zu lassen.

a new year, a new approach

2009-01-07T10:13:00.000-08:00

First, I wish all who read this a happy new year !

I have lately experimented with concepts of functional programming, different vm dispatch routines, interpreter design and optimation. My conclusions from all these experiments are:

1.)
Indirect and direct threading interpreters written in C compile to very efficient code if one knows the right compiler flags (for GCC).

2.)
So a simple interpreter in C, with static or dynamic super instructions and caching of vm registers can have a low performance disadvantage in relation to a simple (JiT) native-code compiler, too small as it would be worth to give up platform independence for it. Interestingly enough, it's seems I'm not the only one who came to similarly conclusions. The author of the LuaJIT project describes in its roadmap for 2008 the following:

Preliminary benchmarks show that *the interpreter alone* is
already 2x-4x faster in most cases. Embarassingly this is better
than LuaJIT 1.x in a few benchmarks. Much higher speedups are
still to be expected from the trace compiler.

Similarly as I tried it with Vid, he had rewritten the Lua vm from a tree based to a indirect threading interpreter in assembler. To archive the high run-time performance:

the bytecode format has been redesigned. It's much more orthogonal, partially specialized and tuned for faster dispatch.

Ah, a déjà vue !

As I see it, a trace compiler can be realized with threaded code also (this would have the advantage of guaranteed platform independence), in fact the stream compiler of the extended Ngaro vm isn't a very different approach just a bit simplier !

2.)
For a high run-time performance, a simple opcode encoding can be much more important than the threading variant (so register based vm's has a disadvantage here).

3.)
A complex but efficient instruction set is better suited for interpretation because of reduced dispatch time per functionality.

Which follows from it ?

I write at present a new vm for retroforth which implements a new instruction set and a new opcode encoding. The vm is higly orthogonal, scalable and supports fine-gained, parallel execution of vm-code sequences. I expect a far better performance as of the old vm.

compiler details (ngaro)

2008-11-20T23:45:00.000-08:00

after discussing a bit, I had a nice idea to solve one little problem: Translate branch offsets form ITC to native code and back. My solution is simple to add an lenght field to the opcode table so for each instruction the start adress of the appropriate machine code is calculable. There, peep-hole optimation can be realized with some kind of opcode fusion (a vm-code sequence is replaced with a single one of identical functionality), I don't see any resolvable problems.

Another challange is calling to ITC from native code (that's not so relevant for forth but can be an issue for functional programming languages). The problem here is the next routine of the vm (no definable return point to native code). Adding a new instruction offers some benefits therefore I decided to inline ITC sequences. For this a new vm instruction is present (SINST_ITC).

my current work

2008-11-13T12:23:00.000-08:00

Vid Forth
Vid Forth is evolved to a hybrid threaded/native code generating forth written in assembler (yasm) for x86_64 class cpu's. The compiler decompose words to function primitives which consume one or two stack items. The resulting list is then compiled to native code. As the stack adressing can be directly mapped to register operations this way only a peep-hole optimation is needed for a good code quality.

Bu this method has also a drawbreak: Though each word defination results in a mostly large list of functional sequences the code size for compiled words can get large compared to itc or dtc (all dependencies are resolved though inlining). To compensate this, word definations can be compiled to itc also (and itc dependencies are resolved though calling the inner interpreter).

Why itc and not stc or dtc ? My benchmark test shows no significant performance advantages for x86_64 class cpu's and call sequences add the opcode lenght to the adress field independent of the adress-field size so the resulting code would be a bit larger.

By the way, this means I need a fast interpreter because performance can be an important issue for itc words also !

At the moment I implement the vm and compiler primitives and new features needed for functional processing, for example:

quotations:


2 
25 [dup * sin] ither

1 2 3 4 
3 [pi + 1.2436 *] map

locals:


: multi {a b} a b * ;

Strings, quotation and base prefixes can be used without a space as seperator !

extended ngaro vm

I work on a little native code compiler for at runtime generated opcodes and write a documentation.

benchmark results

2008-11-11T05:59:00.000-08:00

ok, i've finished a little benchmark test to compare different threading schemes and here are the results (based upon Anton Ertl's threading benchmark V2):

CPU:
AMD Athlon64 3000+
512 MB Ram
FreeBSD 7

Compiler:
gcc (GCC) 4.2.1 20070719 [FreeBSD]

compiler flags


subroutine.c :  
-O  -fomit-frame-pointer (°1)
direct.c :      
-O3 -fomit-frame-pointer
indirect.c :    
-O3 -fomit-frame-pointer
switch.c :      
-O  -fomit-frame-pointer (°1)
repl-switch.c : 
-O  -fomit-frame-pointer (°1)

1:
the -O3 flag would unrolling the loop in subroutine.c and result in
impressive bad code for switch constructs so in both cases the -O flag gives
better results for comparations.

Results:


Vid:            
0.548u 0.000s 0:00.57
subroutine :    
0.251u 0.000s 0:00.25
direct:         
0.429u 0.000s 0:00.46
indirect:       
0.517u 0.007s 0:00.56
switch:         
1.277u 0.000s 0:01.29
repl-switch:    
0.604u 0.000s 0:00.64
call:           
1.157u 0.000s 0:01.19

Results for subroutine.c, switch.c and repl-switch.c with -O3 flag


subroutine:     
0.010u 0.000s 0:00.01
switch:         
1.247u 0.000s 0:01.28
repl-switch:    
0.858u 0.000s 0:00.89

The replicating switch test shows a similar performance compared to indirect or direct threading dispatches:


0:00.64 (repl-switch) versus 
0:00.56 (ITC) versus 
0:00.46 (DTC).

The time difference is so small that one can ask about the avantage to implement threading though gnu's label extension. However, this result is surprising for me but don't forget: For other cpu's, the results can be quite different of course !

The current dispatch scheme of Vid Forth isn't optimated yet but shows equal results with highly optimated C Code and thats a good thing. If I insert 4 nops to the NEXT pattern, the executing time goes down to 0:00.46 ! (this is a AMD specific optimation).

Ich habe einen kleinen Benchmark Test durchgeführt um die einzelnen Threading Schemen besser einschätzen zu können. Hier sind die Ergebnisse:

Prozessor:
AMD Athlon64 3000+
512 MB Ram
FreeBSD 7

Compiler:
gcc (GCC) 4.2.1 20070719 [FreeBSD]

Compiler Flaggen


subroutine.c :  
-O  -fomit-frame-pointer (°1)
direct.c :      
-O3 -fomit-frame-pointer
indirect.c :    
-O3 -fomit-frame-pointer
switch.c :      
-O  -fomit-frame-pointer (°1)
repl-switch.c : 
-O  -fomit-frame-pointer (°1)

1:
Der -O3 Parameter führt zum exessiven "Loop-Unrolling" in subroutine.c und erzeugt beeindruckend schlechten Code für switch Konstrukte so das stattdessen in diesen Fällen mit "-O" kompiliert wurde um vergleichbare Ergebnisse zu erzielen.

Ergebnis:


Vid:            
0.548u 0.000s 0:00.57
subroutine :    
0.251u 0.000s 0:00.25
direct:         
0.429u 0.000s 0:00.46
indirect:       
0.517u 0.007s 0:00.56
switch:         
1.277u 0.000s 0:01.29
repl-switch:    
0.604u 0.000s 0:00.64
call:           
1.157u 0.000s 0:01.19

Ergebnisse für subroutine.c, switch.c und repl-switch.c mit -O3 Parameter:


subroutine:     
0.010u 0.000s 0:00.01
switch:         
1.247u 0.000s 0:01.28
repl-switch:    
0.858u 0.000s 0:00.89

Der repl-switch Test zeigt eine similare Performanz zu ITC und DTC:


0:00.64 (repl-switch) versus 
0:00.56 (ITC) versus 
0:00.46 (DTC).

Die Zeitdifferenz ist so gering, daß man bezweifeln könnte ob es wirklich Sinn machen würde, Threading über die proprietäre Labelerweiterung des GCC Compilers zu realisieren. Wie auch immer, dieses Ergebnis hat mich überrascht, man sollte allerdings nicht vergessen, daß es für andere Prozessoren natürlich nicht automatisch verallgemeinert werden kann.

Das derzeitige ITC Schema von VidForth ist noch nicht optimiert, liefert allerdings gleichrangige Ergebnisse mit hochoptimierten C Code (soweit schonmal nicht schlecht). Erweitere ich die NEXT Routine um 4 NOPs (allerdings eine AMD spezifische Optimierung) sinkt die Ausführungzeit auf 0:00.46 s ! Folglich ist eine weitere Verbesserung noch möglich.

benchmarking threading schemes

2008-11-05T05:43:00.000-08:00

I have spent a night with counting clock cycles and latencies of various threading schemes (and study a lot of assembler-optimization guides of course) to finalize my effort with a benchmark test today. Some things are generally interesting:

String opcodes for dispatch

The traditional way to implement threading for ia32 processors is to dispatch the next word via LODSx. I have found that these instruction is always a serialized, micro-coded instruction on all newer cpu's from Intel and AMD (including the VIA C7). This results in a huge latency. In combination with an indirect jump the NEXT routine can have a dependency of something between 5-7 clock states or greater ! As the advantage for older processors like the i386 of a shorter instruction length isn't important here (Pentium 4 and AMD Athlon class cpu's have a much larger level 1 cache) I think it's better to avoid string instructions for threading dispatch.

CALL versus JMP

A indirect call instead a indirect jump seems to have the advantage of a lesser branch mis-prediction ratio (AMD Athlon64) but I need some more testing because a sequence of variable length nops after a jmp have an effect also and I'm puzzled why (the AMD guides gives an example for this but don't explain the reason for these behavior).

Threaded and native code

2008-11-05T03:48:00.000-08:00

As the code grows, the token threaded code seems to me redundant so I switched to a kind of indirect threading so token threaded code can be implemented as addition (I named the class word DOCOL.TTC). As compiled, native code primitives are simply implemented in the classic way with a pointer to the code. Now, there exist three compiler-class words, one for TTC, one for ITC and one for native code generation and two words for colon definitions (DOCOL.ITC and DOCOL.TTC). A bit unorthodox but I'm quite happy with it !

Eine TTC basierte VM erscheint mir mitlerweile überflüssig, da entsprechender Code innerhalb einer ITC VM bei Bedarf ebenfalls ausführbar wäre (des entsprechende Interpreterwort habe ich DOCOL.TTC genannt). Da des weiteren, auf diesem Wege, die Ausführung von nativem Code in klassischer Weise implementierbar wird, was vieles vereinfacht, ist das Ergebnis ein ITC Forth mit 5 zusätzlichen Klassen, jeweils eine für die Generierung von TTC, ITC sowie nativen Code sowie zwei für Colondefinitionen (DOCOL.ITC sowie DOCOL.TTC).

A native code compiling forth system called Vid.

2008-10-26T00:34:00.000-07:00

To differentiate the native code compiler from Retroforth, I name it Vid Forth; Now working on the compiler. The resulting system becomes compatible with Retroforth 10, including an ANS modul.

Um mein System vom Retroforth Interpreter zu unterscheiden habe ich es Vid Forth genannt; Arbeite momentan am Compiler. Das fertige System wird zu Retroforth 10 kompatibel sein sowie einen einigermaßen vollständiges ANS Modul umfassen.

compiler strategy

2008-10-22T02:30:00.000-07:00

the smp detection is done. I'm searching now for a way to init long mode without needing to handle these obscure paging mechanism (who needs a 4 or 3 way ass. page table ?! For my propose, I don't need paging at all and if one study modern operationg systems like MS Singularity, Sharp OS and others, paging seems to be in general very redundant to me).

After discuss a bit on comp.lang.forth I had a nice idea related to my compiler strategy:

If the source of a forth word is simply interpretated as functional quotation, it's possible to decompose these to a reduced form in which each function adress only one or two stack items. In this case, the compiler can map all parameters to fixed register allocations with the chance to avoid stack accessing at all (this is possible because the first two stack items shoud be cached in registers anyway).

References to other words become in principle inlined bytecode fragments (so no problems with the optimation of inlined code blocks) and code optimation is done though a very simple peep-hole optimiser (no sophisticated compiler optimations are needed).

I have create a prototype compiler and the generated code is very good - Forthers should think functional I think !

Die SMP Detektion ist abgeschlossen. Ich versuche nun derart den "long mode" so zu initialisieren, daß ich um diesen obskuren Paging Mechanismus herumkomme (welches Betriebsystem benötigt eigentlich eine bis zu 4 fach assoziative Seitenbeschreibungstabelle ?! Meine VM benötigt eigentlich überhaupt keine und wenn man sich einmal moderne Betriebsysteme wie MS Singularity, Sharp OS und andere ansieht wird schnell deutlich, daß jeder Paging Mechanismus prinzipiell überflüssig ist).

Nach einer netten Diskussion unter comp.lang.forth kam mir eine gute Idee für meine Kompilerstrategie:

Wenn man den Code eines Wortes funktional auffasst, kann man jenen prinzipiell in eine reduzierte Form überführen deren Funktionen maximal zwei Parameter beanspruchen. Falls man nun diese, maximal zwei Parameter fest einzelnen Registern zuordnet und die ersten beiden Stapelelemente ebenfalls in Registern hält ist es möglich Stapelbezüge komplett in Registeradressierungen zu überführen.

Der so generierte Machinencode ist durch einen einfachen "peep-hole" Algorithmus optimierbar.

Ich habe nach dieser Strategie einen Kompilerprototypen erstellt und der so generierte Code ist mehr als zufriedenstellend - ich denke, Forth Programmierer sollten funktional denken !

I like to code in assembler for sure

2008-10-11T02:01:00.000-07:00

The new vm will get along without operating system. The bootstrap code is finished and I`m working now on smp detection and initialisation whereupon a small, retroforth compatible, forth kernel will be the basis for the vm compiler and other nice things. This have one big avantage: The engine can be implementated in forth ! I think it would no problem to port the assembler source code to other architectures like PowerPC based systems in one or two days because the kernel is small so it doesn't need to be really written in C (and you doesn't get crazy about compiler and "syntax" realated pitfalls of this great "language").

Die neue VM wird kein Betriebsystem mehr benötigen. Der Bootlader ist fertig und ich habe begonnen am Code für die SMP Erkennung und Initialisierung zu arbeiten. Dieser wird dann die Basis für einen kleinen, Retroforth kompatiblen, Forthkernel bilden welcher es wiederum zulässt den VM Kompiler komplett in Forth zu implementieren. Ich denke die Assembler Sourcen sind recht einfach auf andere Prozessorarchitekturen zu übertragen, der Kernelcode ist simpel und vor allem nicht derart umfangreich, das eine Implementierung in C sinnvoll wäre (endlich kein Herumärgern mehr mit syntaktischen und kompilerabhängigen Feinheiten dieser tollen "Programmiersprache").

A new Ngaro VM - die nächste Version

2008-09-11T23:36:00.000-07:00

The extended Ngaro VM implements new possibilities like the generation of new opcodes at runtime but is inconsequent in its architecture. That's the reason I'am working on a complete new instruction level design which offers much more possibilities for code optimations. The new VM implement a kind of cpu independant microcode for the generation of instruction level architectures (lots of fun with IA32, TMS9900 and 32 bit extended 6502 like ISA's on the same vm). In addition, it is now possible to stream generated opcodes conditionally to serialise loops, recursions and other flow dependant code. This way the new VM is scalable and opcodes can be executed generally parallel (ok, a compiler is needed that can be serialise code).

Die bisherige VM bietet zwar einige neue Möglichkeiten wie etwa die Generierung neuer Bytecodes zur Laufzeit, ist jedoch hierbei nicht konsequent und das ist ein grundlegender Nachteil. Daher arbeite ich zur Zeit an einer komplett neuen Instruktionsarchitektur welche Eigenschaften aufweist, die bisher meines Wissens in keiner etablierten VM Eingang gefunden haben. So implementiert die neue VM einen prozessorunabhängigen, jedoch sehr hardwarenahen, Mikrocode zur Implementierung beliebiger Instruktionsarchitekturen zur Laufzeit. Es ist möglich derart generierte Opcodes zu streamen, d.h. ihre Laufzeitverhalten von einzelnen Flaggen abhängig zu machen wodurch z.B. Rekursionen sowie Schleifen als serielle Codeabschnitte implementierbar sind. Hierdurch wird es wiederum möglich die Ausführung ohne zusätzlichen Aufwand zu parallelisieren da Datenabhängigkeiten aufgelöst bzw. auf die VM ausgelagert werden und seitens eines Compilers oder Interpreters nicht mher berücksichtigt werden brauchen. Die VM Architektur ist also in hohen Maße skalierbar (man beachte nur die Möglichkeiten, welcher sich im Hinblick auf moderne Mehrkernprozessoren heiraus ergeben).

Status update

2008-08-19T09:00:00.000-07:00

VM runs stably and I am about to accomplish a last test to check around one potential error. As preparation for the bench mark test I have in addition begun to write an assembler because Toka doesn't work under my present 64 bits Linux system and I urgently need a retro image which uses the possibilities of the extended ngaro version.

Die VM läuft soweit, ich führe gerade noch einen kleinen Test durch um eine potentielle Fehlerquelle abzufangen. In Vorbereitung auf den Benchmark habe ich desweiteren begonnen einen Assembler zu schreiben da Toka unter meinem derzeitigen 64 Bit Linuxsystem nicht lauffähig ist und ich dringend ein Retroabbild brauche welches die Möglichkeiten der erweiterten VM auch nutzt.

just more optimations - noch mehr Optimierungen

2008-07-07T01:26:00.000-07:00

It is now possible to nesting SINST bytecodes. Thereby Lambda functions can be e.g. realized á la LISP for example. Besides I have begun to optimize the vm primitives as well as begin to write a documentation. Everything should be finished soon. Charles Childers extends the RETRO compiler, therefore it will slowly time for a comprehensive benchmark test. I want to refer here also different C based interpreters (Pforth, Gforth, Ficl, Lua, Parrot and so on) in order to see, how the new VM lets itself arrange within the results.

Es ist nun möglich innerhalb einer neuen Instruktion per SINST beliebig weitere zu definieren. Hierdurch lassen sich z.B. Lambda Funktionen á la LISP realisieren. Nebenbei habe ich damit begonnen den Instructionscode zu optimieren sowie eine Dokumentation zur neuen VM zu schreiben. Sollte alles bald fertig sein. Charles Childers erweitert gerade den RETRO Compiler, folglich wird es langsam Zeit einen umfassenden Benchmarktest durchzuführen. Ich will hierbei auch andere C basierte Interpreter miteinbeziehen (Pforth, Gforth, Ficl, Lua, Parrot etc.) um zu sehen, wie sich die neue VM innerhalb der Ergebnisse einordnen läßt.

Performance

2008-06-29T07:08:00.000-07:00

Die neue VM ist nun soweit lauffähig und ich kann beginnen einen neuen Compiler für Retro zu konzipieren um die Möglichkeiten zur dynamischen Codegenerierung, direkten Rgisteradressierung etc. auch zu nutzen. Die bisherigen Benchmarktests zeigen eine weit höhere Performance als mit der alten Version allerdings musste ich mangels dynamischen Compiler den entsprechenden Bytecode selbst generieren. Ein zusätzlicher Vergleich mit GForth und Lina zeigte darüberhinaus einige interessante Ergebnisse, die ich bisher noch nicht sicher interpretieren kann bis auf die Aussage, der DTC Interpreter von GForth liegt von seiner Performance her im Grunde auf einem Niveau mit dem nichtoptimierten ITC Code von Lina (die Werte für Ngaro liegen 30-50% darüber) ?! Ich habe da einen gewissen Verdacht im Hinblick auf die Funktionsweise von TLB Caches ....

Auf ein neues

2008-06-26T02:53:00.000-07:00

Zur Zeit teste ich die neue VM aus. Aus meinen ursprünglichen Plan ging ein vollkommen neuer Ansatz hervor. Anstatt den VM Code in etwas performanteres umzuwandeln erweiterte ich einfach den Instruktionssatz um eine Instruktion welche eine beliebig lange Sequenz von seriellen Bytecodes in einen DTC Strom compiliert. Dies hat den Vorteil die bessere TLB Effizienz des TTC Interpreters bei Programmsprüngen mit der höheren Geschwindigkeit einer DTC Interpretation für serielle Codeabschnitte zu verbinden ohne prozessorspezifische Anpassungen vornehmen zu müssen. Des weiteren kann für weitere Optimierungen die entsprechende Routine einfach ersetzt werden ohne das der Interpreter weiter angepasst werden müsste. Es wäre z.B. möglich anstatt DTC die Bytecodesequenzen direkt in Maschinencode zu überführen.

Nachteilig ist allerdings, das der Retro Sourcecode angepasst werden muss um die neue Möglichkeit auch zu nutzen. Der Forth Interpreter kann theoretisch die Compilierung von Colon Definitionen ebenso wie ihre Ausführung zum Großteil an die VM delegieren. Entsprechende Wörter würden dann schlicht den Instruktionssatz der VM erweitern und die separate Interpretation (derzeit in Form von STC) könnte komplett entfallen...

At present I am debugging my new VM version. From my original plan followed a perfectly new beginning. Instead of compiling the VM code into something with a better performance I extended simply the instruction set by an instruction which convert serial sequences of byte codes into a DTC stream. This have the advantage to combine the better TLB efficiency of the TTC interpreter for jumps with the higher speed of DTC interpretation for serial code sections without processor-specific adjustments. Moreover the appropriate routine can be simply replaced without that the interpreter needs to be adapted for further optimizations. E.g. it would be possible for example to compile the byte code sequences directly in machine code without any side effect for the interpreter.

However,the retro source code need to be rewritten to use the new feature and I can't oversee the problems for Java and Javascript versions of ngaro to implementating a DTC compiler (is there any way? I doubt no).

2008-05-28T01:08:00.000-07:00

Die Strategie für den neuen Interpreter sieht folgendermaßen aus:

Dynamische Superinstruktionen:
Zunächst erweitere ich die NEXT Routine um die Generierung von Maschinencodesequenzen welche aus den vorhandenen Intruktionscodes bezogen werden. Dies erfolgt solange bis eine Sprunginstruktion erreicht wird. Anschließend wird noch der Maschinencode zur Ausführung eben des Programmsprungs zugefügt und die so generierte Superinstruktion ausgeführt. Als Folge gibt es nun zwei Klassen von Instruktionen: Stapelinstruktionen die den Programmzähler nicht verändern als Maschinencodevorlagen sowie Sprunginstruktionen die wie bisher interpretiert werden.

Stapellose Instruktionen:
Durch das cachen der beiden obersten Stapelelemente können alle bit, logischen sowie arithmetischen Operationen mit Varianten erweitert werden welche keine Stapeladressierung durchführen. Stapeladressierungen sind so minimierbar.

Statische Superinstruktionen:
Der Instruktionssatz wird erweitert indem jeweils zwei Instruktionen zu einer neuen zusammengeführt werden.

Die statischen wie nicht stapeladressierten Instruktionen müssen im Ngaro Image auch verwendet werden. Daher werde ich im letzten Schritt ein kleines Programm schreiben welches den Code in das neue Bytecodeformat transformiert. Bei der Gelegenheit kann dieser auch gleichzeitig auf mögliche Fehlerquellen überprüft werden.

2008-05-26T08:59:00.000-07:00

Nachdem nun die Benchmarksuite von Charles Childers fertig ist kann ich anfangen den Interpreter durch die dynamische Bildung von Superinstruktionen derart zu erweitern, daß die bisher notwendige Stapeladressierung minimiert werden kann. Der erste Schritt hierzu ist das cachen der obersten beiden Stapelelemente durch Prozessorregister. Die derzeitige Performance fällt nach dem neuen Test so aus:

With the new benchmark suite from Charles Childers i'am now prepared to extend the threading vm with the dynamic generation of super instructions. As a preparation of this the vm now caches the first two stack elements in registers. A side effect of this is the possibility to minimise stack accesses on the fly. The current state of the vm gives me the following performance hints:

CPU: AMD Athlon 64 3500
RAM: 512 MByte
GCC: 4.1.2

Switch based ngaro:

Recursive FIB (39)... 134.540261 seconds
Countdown Loop (1,000,000)... 8.096384 seconds
Next/Unnest (256 million pairs)... 7.197207

Threading version:

Recursive FIB(39)... 76.825494 seconds
Countdown Loop (1,000,000)... 4.962105
Nest/Unnest (256 million pairs)... 4.793791

I hope to reduce these times a lot more soon :D