ZXSimulator

[tofro]

Actually, the fastes parsing is not comparing string by string.

Instead, an algorithm that sorts keywords in a tree is the fastest possible: If you have seen the keyword starts with a "P", you don't need to check for "LET" or "SIN", but rather only for "PRINT", "POKE", and "PEEK". This is what lex and yacc (parser generators on Unix) do, ending up with a lot less comparisons.

Tobias

[bwinkel67]

Actually, the fastes parsing is not comparing string by string.

Instead, an algorithm that sorts keywords in a tree is the fastest possible: If you have seen the keyword starts with a "P", you don't need to check for "LET" or "SIN", but rather only for "PRINT", "POKE", and "PEEK". This is what lex and yacc (parser generators on Unix) do, ending up with a lot less comparisons.

Tobias

Yup, that's what Norm and I have been discussing and is a method also used in a recursive descent parser. BTW, lex/yacc fall under table-driven parsing so their parse structure is a bit different and then build up an internal parse-tree to parse once and then you run the parse-tree when executing (recursive descent parsers do not and would need either a pre-processing stage to tokenize or somehow build it up on the fly and replace on next time through).

I've written a bunch of languages using lex/yac (or flex/bison which are the free ones) so I have experience with them. Haven't used other tools such as ANTLR that much. With lex/yacc, it does add overhead in the size of the generated code base and you lose some control over the parsing. One issue with the above approach of sorting keywords into its parts is the reliance of a well implemented switch statement and I fear Digital 'C' SE doesn't do that well. I'm looking into the idea of hashing keywords for quick lookup. With that approach, I don't actually need to hash the entire keyword as likely only the first 2 or so characters differentiate all of the BASIC keywords and so you only lose computing power by going through 2 or 3 characters.

That being said, the ZXSimulator doesn't have to run at fully optimal speed, just realtime. What I've already seen is that the BASIC portion seems to run faster in some cases than the ZX81 and only the graphics output is slower. Since space (i.e. memory size) is also a huge concern, I may give up optimizing parts of the interpreter to keep the footprint small.

[bwinkel67]

BTW, below is an outline of how yacc does its parse so I'm not sure how it would take advantage of the nested switch structure.

First it takes a context free grammar, say a simple expression one like this that only implements addition and multiplication. It's in standard BNF format though yacc uses its own variant where it gets rid of < and >:

Code: Select all

<expr> ::= <expr> + <expr>
<expr> ::= <expr> * <expr>
<expr> ::= ( <expr> )
<expr> :: id

It then transforms it by left factoring it (note that e is the empty symbol).

Code: Select all

<expr> ::= <term> <plus>
<term> ::= ( <expr> )
<term> ::= id <mult>
<plus> ::= + <expr>
<plus> ::= e
<mult> ::= * <term>
<mult> ::= e

Then the following table is generated internally (the algorithm for that is not difficult but a bit involved):

Code: Select all

        +-----------------+-------------+------------+------------------+---------+--------+
        |       id        |      *      |     +      |        (         |    )    |   $    |
--------+-----------------+-------------+------------+------------------+---------+--------+
<expr>  |  <term> <plus>  |             |            |   <term> <plus>  |         |        |
--------+-----------------+-------------+------------+------------------+---------+--------+
<term>  |    id <mult>    |             |            |    ( <exp> )     |         |        |
--------+-----------------+-------------+------------+------------------+---------+--------+
<plus>  |                 |             |  + <exp>   |                  |    e    |    e   |
--------+-----------------+-------------+------------+------------------+---------+--------+
<mult>  |                 |  * <term>   |     e      |                  |    e    |    e   |
--------+-----------------+-------------+------------+------------------+---------+--------+

The main parsing algorithm in yacc is pretty simple (given in pseudo code). Note that getToken is the lexical analyzer provided by lex:

Code: Select all

0) initialize algorithm
   a) push "S $" onto stack where S is grammar start and $ is EOF (S on top of stack)
   b) input = getToken()

1) if stack[top] == input  &&  input == $
   a) ACCEPT, no errors

2) if stack[top] == input
   a) pop(stack)          // pop top of stack
   b) input = getToken(); // next input symbol
   c) goto 1

3) if stack[top] == non-terminal   && TABLE[ stack[top] , input ] == production-rule  // entry not blank
   a) stack[top] = production-rule         // replace top of stack with production-rule
   b) goto 1

4) else SYNTAX ERROR

To see a parse, given the following input:

Code: Select all

id * id

The states of the parse using the table looks like this:

Code: Select all

<-top-of-stack             <=string           action
------------------------------------------------------------------------------------------
<expr> $                   id * id $          (0) push( <expr> $ ), getToken -> input = id
<expr> $                   id * id $          (3) pop, push( <term> <plus> )
<term> <plus> $            id * id $          (3) pop, push( id <mult> )
id <mult> <plus> $         id * id $          (2) pop, getToken -> input = *
<mult> <plus> $            * id $             (3) pop, push( * <term> )
* <term> <plus> $          * id $             (2) pop, getToken -> input = id
<term> <plus> $            id $               (3) pop, push( id <mult> )
id <mult> <plus> $         id $               (2) pop, getToken -> input = $
<mult> <plus> $            $                  (3) pop, push( e )
<plus> $                   $                  (3) pop, push( e )
$                          $                  (1) ACCEPT

[bwinkel67]

Latest version.

zx.zip

(19.27 KiB) Downloaded 266 times

Tested it and it runs about 50% slower than the original ZX81 so not too bad. Timings for TEST6.BAS:

• JTYOne (online ZX81) - 18.75 seconds
• ZXSimjlator - 28.41 seconds

Changes:

• Added the AT command
• Fixed print command formatting so "," work
• Added rudimentary EDIT command (only puts cursor at end and lets you delete
• Changed SAVE/LOAD/LRUN to require quotes around file names
• Fixed power function to use ** and not ^
• Removed lots of unused BASIC commands
• Conformed FOR and IF to be like ZX81's (so made it simpler)

No speed fixes just wanted to implement the AT command to get some graphics. The code shrunk by about 2.5K to 38K which gives me room as I will have to add a bunch more commands to get it fully functional so that's why I'm stripping out all the non-matching BASIC stuff. I want to leave as much of the 96K RAM the unexpanded QL offers to loading up to 16K programs (since I don't tokenize they will be slightly larger than 16K). String subscripting is implemented but I don't as yet have DIMensions (I don't think I ever did for the Mac version) so that will be new.

Here is the test program (TEST6_BAS) that uses AT to print characters using subscripting. This example was originally built on ZX81 emulator and then moved to ZXSimulator.

Code: Select all

10 LET A$="QL ZXSIMULATOR"
20 FOR I=20 TO 1 STEP -1
30 FOR J=1 TO 14
40 PRINT AT I,J*2;A$(J)
50 NEXT J
60 NEXT I

Next, I think I'll write a simple game to see how animation fares now that I have the AT command. Will see if that's enough. May need to implement RAND next.

[bwinkel67]

Another update...

zx.zip

(19.89 KiB) Downloaded 296 times

• This implements the graphics characters in a string (not easy since the format is multi-character)
• Fixed a bug in AT to make it work like in a true ZX81
• I broke my IF/THEN in last one that is now fixed
• Did I mention that space now breaks a run

This program does a cool message printing. about 2-3 times slower than realtime it seems:

Code: Select all

10 LET A$="QL ZX-SIMULATOR"
20 FOR I=11 TO 1 STEP -1
30 FOR J=1 TO 8
40 PRINT AT I+10,30-J*2;A$(3);A$(16-J)
50 PRINT AT 11-I,1+2*(J-1);A$(J);A$(3)
60 PRINT AT 11-I,30-J*2;A$(3);A$(16-J)
70 PRINT AT I+10,1+2*(J-1);A$(J);A$(3)
80 NEXT J
90 NEXT I
92 IF A$(1)="%Q" THEN GOTO 10
94 LET A$="%Q%L% %Z%X%-%S%I%M%U%L%A%T%O%R"
96 GOTO 20

Here is what it looks like in JtyOne (online ZX81 emulator):

I think I have enough implemented now to write a simple graphics game in it so I'll post the BASIC file when done. sometime this week.

[NormanDunbar]

You have a bug. And Digital C is not telling you about it.

Code: Select all

/* BASIC commands */
BASICcmds (cmd)
   char cmd[];
{
   char *val_s, *vl2_s, arg[LINELEN], var[VARLEN], *val_s, *vl2_s;
   int  val_i, vl2_i, vl3_i, i, doLF;
   ...

You have *val_s and *vl2_s declared twice.

C68 doesn't like it at all, and errors out. Digital C doesn't seem to mind. This is a bad thing.


Cheers,
Norm.

[bwinkel67]

Hi Norm,

Yes, I saw that while fixing a memory leak this morning. It's been in there for 30 years. Hopefully I took it out in the Mac product.

I must say, as I'm re-learning what I did in the BASIC interpreter, there are things I like and there are things I don't. It's actually supposed to be a recursive descent parser but nowhere am I doing a recursive call (i.e. I should be calling BASICcmds somewhere within BASICcmds). The best place would have been with the THEN but I just had a if_nst variable that I incremented. I'm surprised it works as well as it does :-/ I've not tried to change it but conform to my own 90's standards but in present day this would look a bit different had I to re-write it. I guess I've learned a lot in 30+ years.

So it had a memory leak so here is the latest. Didn't show up in QLAY2 but right away on my unexpanded QL. Been running it now for a while and seems to be fixed.

zx.zip

(19.81 KiB) Downloaded 256 times

It still has a bug where 3 digit BASIC line numbers cause it to do silly things so I need to track that down. This was just a prototype so it was never fully debugged. The Mac version was but I don't want to try and port it backwards. You'll note that there are lots of limits in number of variables and nestings that are hard-coded vs being dynamic.

Latest speed run for TEST7_BAS running through a full screen of normal and a full screen of inverse is

• EightOne - 51 seconds
• ZXSimulator - 1:42 seconds(on unexpanded QL)

So about 1/2 speed. The inverse and graphics characters take up twice as much space since they are in ASCII format using % and \.

[stevepoole]

Hi Bwinkel67,

You have mentioned that assignments are slow.

I have timed the main SMSQ/E operators, which all return roughly similar speed timings, (including coercions).
Printing with AT or CURSOR barely slow timings, and BORDER width has little effect.
But assigning x=y then x=y+y*y-y/y only slows by 30%, so piling up operators in assignments is VERY advantageous...

This is I think the point you were making ?
Regards,
Steve.

[bwinkel67]

Hi Steve,

Hi Bwinkel67,
You have mentioned that assignments are slow.

I am referring to assignments on the ZX81 BASIC and how they are slower than in my ZXSimulator BASIC interpreter and how that is helping the ZXSimulator to catch up since currently printing characters on the ZXSimulator is about 3 times slower then what the ZX81 does. I'm not updating the QL character set, but instead using block() calls which is why it is slower.

I have timed the main SMSQ/E operators, which all return roughly similar speed timings, (including coercions).
Printing with AT or CURSOR barely slow timings, and BORDER width has little effect.
But assigning x=y then x=y+y*y-y/y only slows by 30%, so piling up operators in assignments is VERY advantageous...

The AT I was referring to was implementing the ZX81 AT command in my ZXSimulator BASIC interpreter and comparing the two (so I'm not comparing it to QL's SuperBASIC -- I'm not sure from your post what timings you were doing under SMSQ/E).

This is I think the point you were making ?
Regards,
Steve.

To reiterate, my timings are between the ZXSimulator BASIC and the ZX81 BASIC as they compare on the unexpanded QL vs the original ZX81. Note that for the ZX81 I'm using the EightyOne and JtyOne emulators which have been shown to be 1 to 1 (or close to that) realtime. I need to actually boot up my old ZX81/TS1000 to get a completely accurate timing.

Of course I may be misunderstanding your question so apologies, just wanted to be clear we are on the same page since there are three BASICS we could be talking about :-/

[stevepoole]

Hi Bwinkel69,
You may be interested in some more timing figures for the QL :

CONFIGURATION CYCLES/SEC +/- % SPEED REMARKS
Ql 128ko JS : ? : ? : ? : I don't wish to unplug my SuperGoldCard !
SGC QL under QDOS : 1864 : .25 : x1 : No extra multitasking from me.
SGC QL with SMSQ/E : 8440 : .11 : x4.5 : " " ROMdisc and Hermes.
Compaq, 1core, QPC2, 2.8Ghz : 173894 : 37.2 : x93 : Very variable timings due to monocore multitasking.
Asus, 3core, QPC2, 1.9Ghz : 138683 : 4.0 : x90 : Triple core means better variability when multitasking.
" " " " ? ? ? C++ code runs 400 times faster than superbasic version !
Here is the program I used for the timings :

100 ::
110 REMark Code_timer_bas by S.Poole, v25mar2020
120 REMark empty=168316 on QPC2 3core at 1.9Ghz...
125 CLEAR: overhead=93195: REMark {if d<>date: end if}...
130 CLS: y=PI: sum=0: Max=0: min=1E15: secs=10
135 z='3.141592654': BORDER 0
140 d=DATE: FOR wait=0 TO 1E9: IF d<>DATE: d=DATE: EXIT wait
150 :
160 FOR COUNTs=1 TO secs
170 FOR cycles=0 TO 1E9
180 IF d<>DATE: d=DATE: EXIT cycles
190 REMark
200 END FOR cycles
210 sum=sum+cycles: AT 1,1: PRINT secs-COUNTs!!!
220 IF cycles>Max: Max=cycles
230 IF cycles<min: min=cycles
240 END FOR COUNTs
250 dif=Max-min: hlf=dif/2: pc=(hlf*100)/Max
260 PRINT INT(sum/secs)!!'+/-'!pc;'%': BEEP 3276,1
270 ::
280 DEFine FuNction pie
290 RETurn 3.141593
300 END DEFine

I tested each basic operator for 600 seconds, to avoid bias from mutitasking, several times, with and without web access....
Usually, figures are fairly OK using 10 seconds !
The code to test, for example x=0, is placed between lines 180 and 200. The overhead is a constant and is best ignored.
You may wish to compare the timings with your QL configuration ...
The C++ speed was obtained using the transcribed 'QPC2 Travelleing Salesman Program', some 80ko long...
How does the bare 128ko QL fare ?
Regards,
Steve.