Why was BBC BASIC so fast?

[Richard Russell]

there's an assemble-time option called COAL that Sophie added

Here's what Sophie herself wrote on the subject (I hope I'm not revealing anything confidential):

"COAL and FOAL are conditional switches inside BASIC: here are the SThrash performances:

Code: Select all

                                             bytes    entries       time
No contiguity check                         201284       1554        276
COAL                                        206740       1458        329
FOAL                                        200128       1589        267
COAL+FOAL                                   194724       1404        321

As can be seen, COAL makes fewer entries but they're bigger on average so more space got used. FOAL breaks things down: more entries but less space on average (and FOAL is quite quick in the steady state). COAL+FOAL wins out!"

[BigEd]

(No confidentiality problem: posted by Sophie to comp.sys.acorn.programmer in 2004)

[Richard Russell]

(No confidentiality problem: posted by Sophie to comp.sys.acorn.programmer in 2004)

Thanks, that's good to know. At the above link, Sophie asserts that the string allocation strategy I use in BBC BASIC for Windows and BBC BASIC for SDL 2.0 is "still not OK". Well, all my tests done then and since suggest otherwise; I believe my simple modification to her algorithm (prioritising allocating space from the string free list over expanding into the heap) completely solves the so-called Minerva problem without the disadvantages of her solution.

[Richard Russell]

Whoever wrote that program should have used non-integer values for B, C, D and Z

I've modified the program by adding 0.5 to C, D and Z (not B because that's the STEP value so changing it alters the number of loop iterations, which we don't want). As expected it runs at exactly the same speed as before on Sophie's interpreter (tested in BeebEm) but should give a more 'honest' report for mine:

Code: Select all

   10 REM > ClockSp 3.00 (RTR)
   20 REM Calculate CPU clock speed
   30 PRINT"BBC BASIC CPU Timing Program"
   40 A%=0:T%=TIME:REPEATA%=A%+1:UNTILTIME>T%+50
   50 Z=0:Z%=0:B=1.0:B%=1:F=1/10:C=100:C%=100:D=510:D%=510:F%=3
   60 REPEAT:C=C*10:C%=C%*10:D=D*10:D%=D%*10:F%=F%*10:F=F*10:A%=A%DIV10:UNTILA%<50
   65 Z=Z+0.5:C=C+0.5:D=D+0.5
   70 PRINT"Really real REPEAT loop ";:T%=TIME:A=Z:REPEATA=A+B:UNTILA>C:T%=TIME-T%:PROCp(F*41000/T%)
   80 PRINT"Integer REPEAT loop     ";:T%=TIME:A%=Z%:REPEATA%=A%+B%:UNTILA%>C%:T%=TIME-T%:PROCp(F*23900/T%)
   90 PRINT"Really real FOR loop    ";:T%=TIME:FORA=Z TO D STEP B:NEXT:T%=TIME-T%:PROCp(F*51200/T%)
  100 PRINT"Integer FOR loop        ";:T%=TIME:FORA%=Z% TO D% STEP B%:NEXT:T%=TIME-T%:PROCp(F*17800/T%)
  110 PRINT"Trig/Log test           ";:IFCOS0=0:PRINTSPC4"<none>"
  120 IFCOS0<>0:A=1:T%=TIME:FORJ%=1 TO F%:A=TAN(ATN(EXP(LN(SQR(A*A)))))+1:NEXT:T%=TIME-T%:PROCp(F*68800/T%)
  130 REM PRINT"Ackermann Recursion ";
  140 REM M%=3:T%=TIME:FORN%=1 TO 3:Z%=FNAck(M%,N%):NEXT:T%=TIME-T%:PROCp(F*255400/T%)
  150 PRINT"String manipulation     ";
  160 T%=TIME:A$="STRINGMANIPULATIONTEST":FORA%=0TOF%*4:A$=RIGHT$(MID$(A$,LENA$/2,LENA$/4+1)+RIGHT$(A$,LENA$/4)+MID$(A$,LENA$/2,2)+LEFT$(A$,LENA$/4)+MID$(A$,LENA$/4,LENA$/4+1),LENA$):NEXT:T%=TIME-T%:PROCp(F*72750/T%)
  170 PRINT"Procedure call          ";:T%=TIME:FORA%=Z% TO D%:PROCtest:NEXT:T%=TIME-T%:PROCp(F*80500/T%)
  180 PRINT"GOSUB call              ";:T%=TIME:FORA%=Z% TO D%:GOSUB300:NEXT:T%=TIME-T%:PROCp(F*90000/T%)
  190 PRINT"Combined Average        ";:PROCp(FNspeed)
  200 PRINT'"Compared with a 2.00MHz BBC B"
  210 END
  220 :
  230 DEFFNAck(M%,N%)
  240 IF M%=0:=N%+1
  250 IF N%=0:=FNAck(M%-1,1)
  260 =FNAck(M%-1,FNAck(M%,N%-1))
  270 :
  280 DEFPROCtest:ENDPROC
  290 :
  300 RETURN
  310 :
  320 DEFPROCp(T%):PRINTRIGHT$("     "+STR$(T%DIV100),6);".";RIGHT$("0"+STR$(T%),2);"MHz";CHR$8:ENDPROC
  330 :
  340 REM This is calibrated against a
  350 REM BBC model B with no second
  360 REM processor, running BASIC II
  370 REM and with almost all interupts
  380 REM turned off using:
  390 REM ?&FE4E=&3F
  400 REM This gives 2.00MHz.
  410 :
  420 REM Savage Floating Point test and
  430 REM Ackermann Recursion test added
  440 REM -Mar-1993, based on A&B Jan 90.
  450 :
  460 REM Version 2.00 recalibrates
  470 REM itself for faster systems
  480 REM 15-Mar-2002
  490 :
  500 DEFFNspeed:LOCAL A,B,C,D,F,Z,A%,B%,C%,D%,F%,Q%,R%,S%,U%,V%,W%,X%,Y%,Z%
  510 A%=0:T%=TIME:REPEATA%=A%+1:UNTILTIME>T%+50
  520 Z=0:Z%=0:B=1.0:B%=1:F=1/10:C=100:C%=100:D=510:D%=510:F%=3
  530 REPEAT:C=C*10:C%=C%*10:D=D*10:D%=D%*10:F%=F%*10:F=F*10:A%=A%DIV10:UNTILA%<50
  535 Z=Z+0.5:C=C+0.5:D=D+0.5
  540 T%=TIME:A=Z:REPEATA=A+B:UNTILA>C:T%=TIME-T%:U%=F*41000/T%
  550 T%=TIME:A%=Z%:REPEATA%=A%+B%:UNTILA%>C%:T%=TIME-T%:V%=F*23900/T%
  560 T%=TIME:FORA=Z TO D STEPB:NEXT:T%=TIME-T%:W%=F*51200/T%
  570 T%=TIME:FORA%=Z% TO D% STEPB%:NEXT:T%=TIME-T%:X%=F*17800/T%
  580 Y%=X%:IFCOS0<>0:A=1:T%=TIME:FORJ%=1 TO F%:A=TAN(ATN(EXP(LN(SQR(A*A)))))+1:NEXT:T%=TIME-T%:Y%=F*68800/T%
  590 T%=TIME:A$="STRINGMANIPULATIONTEST":FORA%=0TOF%*4:A$=RIGHT$(MID$(A$,LENA$/2,LENA$/4+1)+RIGHT$(A$,LENA$/4)+MID$(A$,LENA$/2,2)+LEFT$(A$,LENA$/4)+MID$(A$,LENA$/4,LENA$/4+1),LENA$):NEXT:T%=TIME-T%:S%=F*72750/T%
  600 T%=TIME:FORA%=Z% TO D%:PROCtest:NEXT:T%=TIME-T%:R%=F*80500/T%
  610 T%=TIME:FORA%=Z% TO D%:GOSUB300:NEXT:T%=TIME-T%:Q%=F*90000/T%
  620 =INT((Q%+R%+S%+U%+V%+W%+X%+Y%)/(78/10))
  630 REM Returns CPU speed*100

I don't have a real Z80 (or calibrated emulation) to try it on so if somebody could post the revised figures for BBC BASIC (Z80) it would be interesting to compare them with the previous values. Little did I think that my cheat (if you'll forgive me still calling it that) would be fooling people into thinking my BASICs are faster than they really are in 2020!

[scruss]

I don't have a real Z80 (or calibrated emulation) to try it on so if somebody could post the revised figures for BBC BASIC (Z80) …

I tried on my 8 MHz Zeta SBC V2, but completely forgot about the RTC patch/overlay. Without it, TIME always returns 0, and so ClockSp did a whole lot of not very much.

I also have a MinZ with a ~ 37 MHz Z180, but it yet again needs RTC patching magic. It's a very small machine indeed: about the size of a box of matches:

MinZ

worlds-smallest-retrocomputer2.jpg (29.29 KiB) Viewed 1898 times

(posted an image for BigEd: all this sort of thing is hatched on the RetroBrew Computers Forum. The designer has a 50 MHz one in development.)

[BigEd]

(Haven't heard of a MinZ - photos please, perhaps in a new thread?)

[CHRISJJ]

and I'm sure there were occasions when Sophie proposed something but the BBC asked for it to be changed, or vice versa.

Not intending to sound rude, but I'm sure that shows you weren't there.

For example when I queried the apparent blunder of placing the MOS ROM rather than the language ROM at top of memory map, pranging 6502SP full memory utilisation, Paul (Bond, BBC MOS architect) agreed. But said to switch it now was impossible because the usable MOS block was slightly smaller than the language block. Since the only language ROM was BASIC, and neither code was remotely final, I said er why, since Roger would just need to give up a few bytes from BASIC, for a huge benefit to this and all other languages. Paul replied with signature smile and dry wit. "As I said. impossible."

[CHRISJJ]

[*]Integer variables are four byte quantities. An obvious way to add/subtract/copy these would be to write a loop that goes round 4 times and accesses the bytes via an index register. In BBC BASIC it is written instead as four separate groups of instructions with no looping. In modern compiler-speak we would call this loop unrolling. The non-indexed instructions are faster than their indexed equivalents and it also saves time on the loop control (decrement, test, branch).

What's obvious to a modern compiler writer is here pretty much the opposite of what was obvious to a 1980s assembler coder. The good 6502 assembler coder doesn't unroll a loop. He doesn't start with a loop. The four instruction groups is the standard and obvious way to do it. A loop would be doubly costly because of the storage of the loop counter, whereas the standard solution gets that effect for free in the program counter.

Why was BBC BASIC so fast? It wasn't, considering its limitations such as e.g. the aforementioned mickey-mouse strings. Why did BBC BASIC programs run so fast? Because they were running on a fast machine!

[jgharston]

For example when I queried the apparent blunder of placing the MOS ROM rather than the language ROM at top of memory map, pranging 6502SP full memory utilisation, Paul (Bond, BBC MOS architect) agreed.

But the MOS has to be at the top of memory, because the hardware vectors are there.

[Rich Talbot-Watkins]

Yes, I was going to say the same thing.

Perhaps it would've been better to have the language ROMs paged over &C000...&FC00 (with the final 1k never paged out), but I think it would've been hard to lose 1k of code from the BASIC ROM.

Skip that, it would never have worked. I think the memory map was pretty well chosen, to be honest.

[1024MAK]

Before redesigning the ROM arrangements, what are you intending putting in the vacated memory map space? More RAM? Keep in mind that at the time the machine was designed, RAM was rather expensive.

So if you can put your hindsight aside, I think the memory map that Acorn used was not only reasonable for the time, but actually a good arrangement.

There are only a couple of things that I think they could have done better, but that is off topic, as it’s nothing to do with the speed of BBC BASIC.

Mark

[Coeus]

For example when I queried the apparent blunder of placing the MOS ROM rather than the language ROM at top of memory map, pranging 6502SP full memory utilisation...

I think this would have been quite disruptive. As JGH points out the 6502 reset IRQ and NMI vectors are at the very top of the memory map. If these were in the language ROM rather than the OS ROM it means they must be duplicated in every language ROM including those not released by Acorn. That means that either the addresses of these routines in the OS ROM can never change or there has to be another indirection. Would there be anything in the last 256 bytes that would be considered proprietary? Or there has to be extra complexity to the address decoding to map the OS ROM into the last 256 bytes of the the address space rather than the language ROM.

Would the I/O space have been moved too?

The 2nd processor also has ROM at the top of its memory map. The language would need to be shortened by either 256 bytes, or maybe 1K if the I/O space was not also moved, for the I/O processor but how big does the ROM on the 2nd processor need to be?

It would have been much easier, of course, if the code for the 6502 could be position independent but relocation of the language was solved later by a relocation table and an extension to the ROM header. That would surely have been possible right from the start if someone had thought of it, though I accept the table would have been bigger for an NMOS 6502 without the BRA instruction.

[Coeus]

What's obvious to a modern compiler writer is here pretty much the opposite of what was obvious to a 1980s assembler coder. The good 6502 assembler coder doesn't unroll a loop. He doesn't start with a loop. The four instruction groups is the standard and obvious way to do it. A loop would be doubly costly because of the storage of the loop counter, whereas the standard solution gets that effect for free in the program counter.

And what about the two loops for FP or the linked lists for variable names? Other BASICs of the time have cases where compact code was written despite being slower because space was short. As far as I can see that is entirely missing from BBC BASIC.

Why was BBC BASIC so fast? It wasn't, considering its limitations such as e.g. the aforementioned mickey-mouse strings. Why did BBC BASIC programs run so fast? Because they were running on a fast machine!

Mickey mouse strings? Is that a reference to the lack of garbage collection?

I think we all acknowledge that the hardware was unusually fast for the time but I don't think it was the only factor.

[Soruk]

and I'm sure there were occasions when Sophie proposed something but the BBC asked for it to be changed, or vice versa.

Not intending to sound rude, but I'm sure that shows you weren't there.

I think you will find that Richard Russell was very heavily involved with the BBC Microcomputer Project, on the BBC side of things.

[BigEd]

Richard only said that the BBC might have made a suggestion to Sophie, not that she would have accepted it! The usual trick with such a person is to make it seem like their idea.

[CHRISJJ]

Richard only said that the BBC might have made a suggestion to Sophie,

Er, no. "That's not to say the BBC (and others) had no say in how the language turned out, there was a close degree of liaison"

not that she would have accepted it!

I interpret "having a say in something" to mean a little more than having a chance to say stuff that's rejected.

[CHRISJJ]

on the BBC side of things.

We're not talking about the the BBC side of things.

[danielj]

I am aware this is getting a bit testy. I don't see that it needs to be

[Bobbi]

BASIC-rage?

[Kweepa]

These include having 40-bit floats, when most other BASICs had 32-bit floats, 32-bit integers when most others had 16-bit, arbitrarily long variable names etc.

Microsoft BASIC and Sinclair BASIC both use 40-bit floats. Microsoft BASIC allows you to define integer variables using the same % syntax but mainly to reduce storage requirements for arrays - they are converted to floats when doing math on them.

Indeed BBC BASIC is particularly slow in one regard: the way that GOTO and GOSUB find their destination line by a linear search starting at the beginning of the program every time!

Microsoft BASIC at least does the same thing (searching linearly that is -it does start from the current line if the destination is >= current). I would doubt any 8k BASIC works differently, given the minimal code size.

[BigEd]

Microsoft Basic had build-time options and offered either 32 or 40 bit floats. I've seen both, I think, on different machines.

[Kweepa]

Interesting. The variants used by Commodore and Apple are both 40-bit, though.

[julie_m]

Indeed BBC BASIC is particularly slow in one regard: the way that GOTO and GOSUB find their destination line by a linear search starting at the beginning of the program every time

Microsoft BASIC at least does the same thing (searching linearly that is -it does start from the current line if the destination is >= current). I would doubt any 8k BASIC works differently, given the minimal code size.

But I know from experience trying to read the names and values of variables that BBC BASIC definitely does make a database of PROCs and FNs, which were seen as the "proper" way to write programs. (The dreaded Bad program error means it can't make sense of a program when it tries to update that database.) Old-fashioned GOTO and GOSUB were really only provided for converting type-in listings from legacy systems. The expectation was for you eventually to replace GOSUB with PROC and infinite GOTO loops with REPEAT ..... UNTIL FALSE.

There are a few ways you could speed up GOTO/GOSUB a little bit compared to a linear search every time. You could enable two-way searching by storing another copy of the length of a line at the end of that line. Using BCD line numbers enables some optimisations to be made with respect to lines whose numbers are exact multiples of 100, but also restricts you to four digits. (It would work in decimal mode, too; but anyone who knows their 256 times table off by heart probably isn't going to be using much BASIC anyway .....) Or since BBC BASIC already tokenises line numbers referenced by GOTO, GOSUB and RESTORE, you could build up a table of target line numbers and their addresses. Even on non-BBC-like systems, you could make a table of targets you have already searched for, which at least would make subsequent calls to the same line quicker. But all of these cost memory; an extra byte per program line for the two-way searching, three bytes per entry in a table of "round hundred" addresses, and who knows how much for tables of targets (four bytes for each distinct target: two bytes for the line number, and two more for its address in memory). All in all, it probably would not be worth it for the minimal saving. You have to remember, the prevailing idea was that modern structured programming was the way forward, and GOTO and GOSUB were soon to be obsolete.

To be honest, the only time I really use GOTO is as a poor person's substitute for multi-line IF ..... THEN ..... ELSE ..... FI. Then the jumps are likely to be short, so Microsoft's optimisation of searching forward from the next program line rather than rewinding for every target might have been nice.

[BigEd]

Jeremy Ruston's notes and annotated disassembly in his BBC Micro Compendium are well worth looking through.

[Kweepa]

Old-fashioned GOTO and GOSUB were really only provided for converting type-in listings from legacy systems.

There's not really an efficient substitute for ON X GOTO/GOSUB though, so they still have their place.

[scruss]

Microsoft Basic had build-time options and offered either 32 or 40 bit floats. I've seen both, I think, on different machines.

It gets weirder: they also had 32 and 64-bit decimal float interpreters. I don't know if any of them hit the 6502, but MSX BASIC was perhaps the most widely-used MS BASIC with BCD floats. It was a few years later than the 6502 versions described on pagetable.com.

None of the BCD float interpreters would win speed contests, though

[1024MAK]

The best way to speed up GOTO and GOSUB is to treat the referenced line as a label. As the program is entered, a dummy offset address (in binary) from the start address of the program is allocated in a table. Then when run, the first thing that the interpreter does is search for and populate the table. After this it runs the program.

Even better if you can actually specify a label:

406 IF LIFE%<0 THEN GOTO #GAMEOVER
.
.
.
1078 #GAMEOVER
1079 CLS : PRINT “GAME OVER”

If you are going to stick to treating it as a number, why not allow the use of an expression that resolves to a number? Then you could use variables and expressions:

35 GAMEOVER%=1078
406 IF LIFE%<0 THEN GOTO GAMEOVER%
.
.
.
1078 CLS : PRINT “GAME OVER”

or

404 LIFE%=LIFE%-1
406 IF LIFE%<0 THEN GOTO GAMEOVER%
408 GOSUB LIFE%*100+1000
410 UNTIL FALSE
.
.
1100 REM code to show screen for one life remaining
.
.
1199 RETURN
1200 REM code to show screen for two lives remaining
.
.
1299 RETURN
1300 REM code to show screen for three lives remaining
.
.
1399 RETURN

Obviously if you allow expressions, you can’t have a lookup table for any GOTO or GOSUB that uses an expression or variable.

And yes, of course there are other ways of doing the examples that I give above. Some will say that other ways are better, but one of the objectives of a flexible language, is that it should allow the programmer to decide on the method that he or she prefers.

The real limiting factor, is of course, available ROM space for the code, the specification that was being worked to in creating the language code, how much RAM was to be used, and just as importantly, the time to produce bug free working code.

Generally speaking, maybe more could have been squeezed into the 16k byte ROM, but this would have meant making compromises elsewhere or writing slower but more compact code.

To be honest, the worst feature of BBC BASIC, is how unreadable it gets when all of the optional spaces are left out. That’s one area where ZX80, ZX81 and ZX Spectrum BASIC wins. It includes spaces when it expands the BASIC keyword tokens, but further, it handles cases where two expanded keyword tokens are next to one another without having two spaces consecutively. This massively improved readability without taking up excessive memory for spaces that the interpreter does not really need.

Mark

[julie_m]

I don't mind the lack of spaces; I got so used to living without them, my brain tends to put them there for me. You can even miss out more spaces than you would normally ever get away with, if you use a slight hack: insert a token directly into your program, either by VDUing its token code to the screen in MODE 7 and COPYing the character, or by defining a function key to insert it. Then an expression such as plotbuf MOD256 can be entered as plotbufMOD256 using the token directly.

This works because BBC BASIC programs are stored tokenised. When a line is entered into a program, any reserved words outside speech marks are replaced by single high-bit-set characters. When the program is LISTed, those characters are expanded back to the words wherever they appear outside speech marks. The tokeniser would not normally pick up on be a reserved word in the middle of a variable name, but entering it directly bypasses this behaviour. At RUN time, BASIC sees the MOD token immediately after the variable name plotbuf, and does not have to look in vain for a variable called plotbufMOD256. And it will SAVE and LOAD just fine, like any other tokenised program. Which it is; the MOD token you inserted directly indicates the end of the variable name just as surely as the space you would have had to put there in order for the tokeniser to pick up on the letters M O D.

HOWEVER

This technique will not survive editing using COPY, nor *SPOOL / *EXEC, because this involves a line being entered into the program which the interpreter could understand, but the tokeniser would never be able to produce. (Although emulator users could craft pre-tokenised files on the host to be imported into the target.)

[BeebMaster]

35 GAMEOVER%=1078
406 IF LIFE%<0 THEN GOTO GAMEOVER%
.
.
.
1078 CLS : PRINT “GAME OVER”

or

404 LIFE%=LIFE%-1
406 IF LIFE%<0 THEN GOTO GAMEOVER%
408 GOSUB LIFE%*100+1000
410 UNTIL FALSE
.
.
1100 REM code to show screen for one life remaining
.
.
1199 RETURN
1200 REM code to show screen for two lives remaining
.
.
1299 RETURN
1300 REM code to show screen for three lives remaining
.
.
1399 RETURN

Actually I have used this very method in my ADFS disc imager which I am developing and using to back up my old Winchester discs. It started all nice and neat in procedures and functions. However, because there is quite a bit of user input, such as suggesting new file names when the image file reaches maximum size, and at any where point you involve the user you can end up with an error being generated, or any number of other things could do wrong like a No clock or Not listening error if saving the image file to Econet, I had to take any part of the code which was within, or could be called from, a procedure or function, which could possibly result in an error, out of procedures and functions so I could trap the errors without breaking everything. Also the main REPEAT...UNTIL loop had to be replaced with IF NOT endofdisc GOTO doitagain type structures.

So now instead of PROCdothis I have R%=<current line+10> and GOTO <line for dothis> and at the end of "dothis" I have GOTO R%. That way I can at least return to the point the procedure is called, and it can be called from multiple different points by setting R% just before. It gets complicated when a procedure calls another procedure, so you have to save the old R% and restore it afterwards, and so on, and it gets very messy and also means I can never renumber the program which is running out of line numbers at various points now.

I wish I'd paid more attention to the thread on trapping errors within loops and procedures in 6502 BASIC. Eventually I think I am going to have to include that methodology to keep the thing afloat.

[Coeus]

Microsoft Basic had build-time options and offered either 32 or 40 bit floats. I've seen both, I think, on different machines.

Armed with that, just for interest I did a quick and dirty port of MS BASIC to the BBC*:

Then pasted in the primes by trial division benchmark from http://typewritten.org/Articles/Benchma ... esoft.html

then ran it:

There's no automatic timing but I timed it with a stopwatch and got 44s.
Now back to BASIC 2 and the equivalent program from http://typewritten.org/Articles/Benchma ... s/bbc.html

which ran to completion:

in 48.82s so very slightly slower than the Microsoft BASIC!

* A quick and dirty port in the sense that it assumes what memory it can use rather than dynamically adapting to screen mode and ROM usage, has no file I/O at all and doesn't handle OS errors.