Why was BBC BASIC so fast?

[jay]

I've seen benchmarks showing that BBC BASIC as implemented on the Beeb was fast compared to micros not having BBC BASIC. Does anybody have any specific information about why that was so? What decisions about the language definition were important to this? Or was it all about implementation efficiency and good data structures & algorithms? I'm really interested in the details here.

[drfloyd]

Same question

I have tried lot of basic on 8bit : Amstrad, Atari XL, C64, TI99 (16 bit computer!), Spectrum, Apple 2... I have never seen a so fast basic (basic IV on Master 128)

[Coeus]

I think there are two aspects to this:

• The hardware is faster than you might expect from reading the spec. Although it is not a 1:1 comparison, it is generally accepted that a Z80 requires about twice as many clock cycles as a 6502 to do the same work so, all other things being equal, the BBC B with a 2Mhz 6502 would be about the same speed as machines with a 4Mhz Z80 which is where some of the other machines were at. What is possibly unique about the BBC micro, though, is that there is no contention in the memory access between the CPU and the video circuitry. That was achieved by using RAM that was twice as fast as the CPU needed to accesses from the CPU and the video output could be interleaved.
• Sophie Wilson clearly optimised the BBC BASIC for speed. For example:
  • The single letter integer variables (A% etc.) are stored in fixed locations for fast access.
  • The rest of the variable are stored in a series of linked lists, one for each possible starting letter. Another way to think of this is a hash table with a linked list as the means of collision resolution and the first character as the hash function. This makes it faster to search for variables compared to having them all in one long list.
  • When working with floating point numbers it is usual to normalise the result after a calculation. This involves shifting the mantissa left until the left-most bit is a 1 which can then be replaced by the sign before storing the number. In Steve Wozniak's implementation for Apple BASIC he shifts a three byte mantissa one bit at a time in a simple loop. In BBC BASIC the mantisaa is four bytes long and Sophie has coded this as two separate loops one to shift a whole byte at a time and then another to pick up the extra bits (always less than 7)
  • 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).
  There are no doubt more tricks to be discovered but I think this is a sufficient clue that Sophie quite deliberately set out to write a fast BASIC interpreter.

[tricky]

I didn't know about the multiple lists, so I assume that xPos, yPos, zPos is faster than posX, posY, posZ.
As far as I can tell from various z80 decapping videos it is a 4bit ALU and hence requires two cycles to do what the 6502 can do in one.
I assume memory access is "full speed", so some of the perf differences must be down to instruction set and z80 having extra reads fro extended instructions.
I think this is also where the nybble oriented instruction comes from (iirc it has been 40 years).

EDIT: To answer the question:
Sophie Wilson.
16K ROM.
Full speed RAM.
Built for the beeb.

[Coeus]

I didn't know about the multiple lists, so I assume that xPos, yPos, zPos is faster than posX, posY, posZ.

Yes. Although it was probably, even then, considered legacy practice, this was probably optimised for those coming from FORTRAN and used to single letter variable names.

As far as I can tell from various z80 decapping videos it is a 4bit ALU and hence requires two cycles to do what the 6502 can do in one.

I think that's probably part of why the Z80 needs the clock to be twice as fast for the same throughput but I am not sure if it's the only factor. Also, as I said, Z80A (4Mhz) CPUs were common. Even the Sinclair machines had them. So I think memory contention was the big thing, In the Sinclair ZX80, because the CPU was used as part of the video generation, no running of a user program happened during the period video was being displayed - only the flyback period was available for computation. That's an extreme case but a more general case, with RAM speed matched to the CPU, would be that the CPU would have wait states inserted during video generation so was probably running about half speed then, and full speed during flyback. On the BBC it ran full speed except when accessing the 1Mhz hardware

The other thing I forgot to mention in connection with the BASIC intrepreter was that just having integer variables was a speed-up as these were quicker to calculate with than floating point.
[/quote]

[ajcduggan]

Also, the input lines are tokenised and stored using binary token abbreviations, which makes interpretation faster.

[BigEd]

BBC Basic was a large Basic: a 16k ROM, and without the need to carry any OS functions (another 16k there) or filing system (another 16k, if not cassette.) I'm sure that helped, in making some space/time tradeoffs. And it was a second cut too, after Atom Basic.

Sinclair's Basic was very space-constrained, and a rush-job port from ZX80/81.

Microsoft Basic was not written by 6502 experts, more of a quick port that was readily available under license (or not under license, in the case of the UK101)

I'm not sure about Amstrad - I've a feeling they had quite a fast Basic?

But I'd say the Z80 4MHz is rather comparable to a 6502 at 1MHz - it has the same memory bandwidth, but a richer instruction set and register set. The ratio may not be 4:1 but I think it's better than 2:1.

The BBC Micro, then, has an unusually fast microprocessor, a very unusually fast memory, a lot of code space, is a second cut, and with great coding talent behind it.

[jgharston]

It's not just the CPU. Z80 BBC BASIC on a 3.5MHz Z80 on a ZX Spectrum is more than three times faster than Z80 ZXBasic on the same 3.5MHz Z80 on the same ZX Spectrum:

[Naomasa298]

It's witchery, I tell you!

[chinnyhill10]

I'm not sure about Amstrad - I've a feeling they had quite a fast Basic?

CPC Basic was produced by Locomotive software who had one eye on Beeb Basic as the gold standard when they wrote it. But it was time constrained in development.

The version of Basic Locomotive wrote for the PCW (Mallard) was speed optimised. Hence the name.Not sure how it benchmarks against BBC Basic though.

[jgharston]

I've got some notes that lists that Locomotive Basic on the 4MHz Z80 CPC is 1.5 times slower than BBC BASIC on the 2MHz 6502 doing exactly the same take. The CPC would need to be running at 6.5MHz for Z80 Locomotive Basic to run as fast as 2MHz 6502 BBC BASIC.

Luckily, we have Z80 BBC BASIC for the CPC as well, so ClockSp can give a direct comparison. Hold on a mo....

ClockSp reports that a 4MHz CPC128 is equivalent to a 1.18MHz BBC B.

[mr-macrisc]

Good hardware, very very well optimised basic etc etc

There were quite a few benchmarks where bbc micro could better the ST and Amiga. Especially ones designed to test how good the basic interpreter was.

I believe there was 1 other 8 bit machine with a well optimised basic in rom that was as fast if not faster than bbc for basic (maybe depending on task).

[mr-macrisc]

Luxor ABC 800m was the other one with very very quick basic performance

[Richard Russell]

Sophie Wilson clearly optimised the BBC BASIC for speed.

I'm sure this is the key reason why her BBC BASIC's are fast. BBC BASIC is not inherently a fast language at all, indeed there are features of its design which might be expected to make it slower than its contemporaries. 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. Whilst these are features that made BBC BASIC very powerful, and have helped it survive to today, they are not conducive to speed!

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! I'm pretty sure there was no cacheing, or using a binary chop, or other optimisations. Not even 'search forward from the current line if the destination line number is higher' as far as I know (I am happy to be corrected). Of course being a structured language there is no reason ever to use GOTO or GOSUB so that may be one reason why this aspect was neglected.

My versions of BBC BASIC aren't particularly fast, at least in part because I have always aimed for for minimum code size rather than maximum speed. For example my Z80 interpreter was less than 12K compared with 16K for Sophie's 6502 version, and ran more slowly than can be explained solely by the difference in the CPUs and clock rates. Because mine initially looked so bad in comparison, I even introduced an optimisation which cheated common benchmarks: variables without any suffix are (numeric) variants in my versions, not floats!

I don't think this was quite in the same league as Volkswagen's emissions cheating (!), variants are useful in their own right and all my versions of BBC BASIC to this day still use them, but it did have the valuable effect of those benchmark programs using integer calculations in my Z80 BASIC but floating-point calculations in Sophie's 6502 BASIC. Mine didn't look too bad at all then!

[BigEd]

Luxor ABC 800m was the other one with very very quick basic performance :)

Thanks - turns out I'd investigated that last year, and found

the Basic is tokenised and expressions are converted to an RPN format

and

partially compiled programs into machine code before running them

[BigEd]

Because mine initially looked so bad in comparison, I even introduced an optimisation which cheated common benchmarks: variables without any suffix are (numeric) variants in my versions, not floats!

That sounds quite handy to me: presumably the values are integers, up until the point where they can't be? So if the program only ever increments a variable, it'll be integer speed, but if it goes about dividing and taking square roots, the variable will become a float and stay that way?

[dominicbeesley]

the Basic is tokenised and expressions are converted to an RPN format

and

partially compiled programs into machine code before running them

Neither of these are true as far as I'm aware from doing a line-by-line port the expressions are evaluated in the order they are written (by a quite clever and fast evaluator) I suspect the partially compiled thing is a misunderstanding of the built in assembler or tokenizer?

One thing that is often overlooked is the 6502's zero-page which is quite handy in terms of speed and not having to constantly save any pointers. BBC BASIC uses the zero-page indirect to parse/scan the program and from my experience porting to other processors any mucking around with this can affect speed greatly. BASIC spends a good proportion of its time scanning the program so while the arithmetic and excellent FP support are a help a lot of the speed comes in the efficient parsing and dispatching of the tokens and expressions in the BASIC program.

D

[Richard Russell]

That sounds quite handy to me: presumably the values are integers, up until the point where they can't be? So if the program only ever increments a variable, it'll be integer speed, but if it goes about dividing and taking square roots, the variable will become a float and stay that way?

That's basically right, yes, although you have some control. You can force the value to be initially a float by including a decimal point; it won't subsequently be converted to an integer unless you use the INT() function:

Code: Select all

      myvariable = 5 : REM integer
      myvariable = 5.0 : REM float

BASIC (going right back to the Kemeny & Kurtz days) didn't traditionally have 'typed' variables, it just had numerics and strings (the latter being indicated by a $ suffix). In my view, and in the spirit of the Beginners' part of the acronym, the language should spare the programmer the need to choose between an integer for speed and a float when non-whole-numbers are needed. I've got nothing against extending the language with additional data types, but suffixless variables should be as 'universal' as possible.

[Richard Russell]

One thing that is often overlooked is the 6502's zero-page which is quite handy in terms of speed and not having to constantly save any pointers.

True, but of course the Z80 (unlike the 8080) is sufficiently register-rich that what the 6502 version would have stored in zero-page is quite likely to be stored in registers, with just as much - if not more - benefit in speed. This was typically the register allocation I used for numeric computations in BBC BASIC (Z80):

• A, A' General purpose temporary storage
• C H L H' L' Numeric operand 1 and result (C = 0 signifies integer, otherwise floating-point exponent)
• B D E D' E' Numeric operand 2 (B = 0 signifies integer, otherwise floating-point exponent)
• B' C' (e.g.) Additional 16-bits precision when needed for intermediate values
• IY Code pointer (addresses tokenised BASIC program in memory)
• IX General purpose pointer, e.g. to coefficient tables in memory for transcendental ops
• SP Stack pointer used by both the CPU (push/pop/call/return) and as BASIC's soft stack!

So even a quite complicated numeric expression could be evaluated with very few memory references.

[1024MAK]

So to sum up, it’s a combination of factors:

• The fast (compared to most other 6502 based systems) 2MHz processor.
• No (RAM) memory contention for program memory, display memory and no slowdown to read the ROM chips.
• A large amount of ROM space allowing it to be written for speed rather than being written to be as compact as possible.
• The OS is in a separate ROM and is also written for speed rather than being written to be as compact as possible.
• Being that there was enough space in the ROM, BBC BASIC supported integral variables as well as floating point variables (some other BASICs only used floating point variables for all numeric numbers).
• This was, as Ed says, the second generation, it having been developed from the Atom BASIC. Hence lessons would have been learned.
• A lot of Z80 systems may have used the Z80A rated at 4MHz, but rarely did they actually constantly run at this speed. The ZX Spectrum if running code in non-contented memory runs at 3.5MHz. The CPC range does clock the Z80A at 4MHz but the video system reduces the effective clock rate as it aligns the Z80 memory accesses to suit it, as the video system has priority. Where there are Z80 systems where the Z80A can run at full speed (4MHz) the video system is provided via a video display processor (VDP) that is accessed as I/O ports, and hence the video RAM is separate and not in the processor memory map.

In terms of comparing 8 bit processors, the clock speed is not a very good comparison. And some processors are better at some things than their competitors. There have been countless discussions on this over the years.

Remember both the 6502 and the Z80 were intended for embedded applications, not for home, business or ‘personal’ computers and were both designed to be as low cost as possible.

However a common and very appropriate guide goes like this:
Z80 running at 2.5MHz appropriately equivalent to a 6502 running at 1MHz
Z80A running at 4MHz appropriately equivalent to a 6502A running at 1.5MHz
Z80B running at 5MHz appropriately equivalent to a 6502B running at 2MHz
Z80B running at 6MHz appropriately equivalent to a 6502B running at 2.5MHz
(Unless anyone has any better comparisons to offer)

And yes, the Z80 does only have a 4 bit ALU (done to make sure that Intel could not legally challenge Zilog over IP rights compared to the 8080). But due to the larger range of instructions, Z80 code is generally considered to be more compact than 6502 code.

Mark

[Coeus]

I'm sure this is the key reason why her BBC BASIC's are fast...

Ok, so I didn't say in my reply that I was talking about Sophie's implementation in particular but I took that as read because the thread started with:

I've seen benchmarks showing that BBC BASIC as implemented on the Beeb was fast compared to micros not having BBC BASIC...

Also I would say that, in general, it is implementations that are either fast or slow, though there are features of a language specification that can help or hinder writing a fast implementation. For example, the EVAL statement may cause one implementer to conclude that BASIC cannot be compiled and thus the whole program should be interpreted, another might include an interpreter in a compiled program that uses EVAL for just those cases.

BBC BASIC is not inherently a fast language at all, indeed there are features of its design which might be expected to make it slower than its contemporaries. 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.

Were these part of the specification or just a design choice from Sophie that you have maintained compatibility with? I seem to remember that the outline specification from John Coll only called for at least the first two characters of variable names to be significant.

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! I'm pretty sure there was no cacheing, or using a binary chop, or other optimisations.

I assume we're talking about Sophie's implementation here? There is surely nothing in the language spec that says that line numbers should always be searched from the beginning. In Sophie's implementation, a binary chop would be hard as lines are variable length and stored in a linked list rather than there being an index. It's a singly linked list so searching backwards is also not possible.

Of course being a structured language there is no reason ever to use GOTO or GOSUB so that may be one reason why this aspect was neglected.

Indeed.

My versions of BBC BASIC aren't particularly fast, at least in part because I have always aimed for for minimum code size rather than maximum speed. For example my Z80 interpreter was less than 12K compared with 16K for Sophie's 6502 version, and ran more slowly than can be explained solely by the difference in the CPUs and clock rates.

So another part of this discussion is that things don't exist in isolation and are not designed in isolation. At the time the BBC micro was designed RAM was expensive so it didn't that much of it. That lead to there being plenty of space in the address map for ROM which was presumably not so expensive and ROM chips are a fixed size so there would be no benefit of making Sophie's implementation 12K rather than 16K.

On a CP/M machine, though, with programs loaded from disc, each 1K of space used by the interpreter is 1K less for the user's BASIC program so it's a different situation.

So some of the optimisation in Sophie's implementation may have come later. The loop unrolling, for example, is something that can be done without any design changes.

...variables without any suffix are (numeric) variants in my versions, not floats!

I don't think I'd call that a cheat. As long as these behaves as if they were floats, i.e. when you do FP-specific things with them they work then that's all that matters.

[Richard Russell]

Were these part of the specification or just a design choice from Sophie that you have maintained compatibility with?

I think it's true to say that most of what we know as BBC BASIC arose from Sophie's design choices, not anything mandated by the BBC; apart from the requirement to be a 'structured' language there were very few detailed constraints in the specification. 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 and I'm sure there were occasions when Sophie proposed something but the BBC asked for it to be changed, or vice versa.

There is surely nothing in the language spec that says that line numbers should always be searched from the beginning.

Indeed not, but nor is there anything that says variables should be accessed via linked lists indexed by the initial character, which is often quoted as one of the features of BBC BASIC that contributes to its speed. Inevitably certain aspects of the initial implementation have become linked with the 'language', and certainly all my versions have used the same approach.

On which point it has always surprised me that Sophie didn't take advantage of the variable linked lists to implement an 'obvious' optimisation: move the most-recently-accessed variable to the head of the list. My modern BASICs all do that, and it has a good cost-benefit tradeoff: manipulating the links to reorder the list is quite straightforward, and it means the variable will be found very quickly next time. For variables accessed in loops, particularly, it's very valuable, and helps the language scale well to very large programs.

In Sophie's implementation, a binary chop would be hard as lines are variable length and stored in a linked list rather than there being an index.

I don't necessarily think it would have been a drastic change to have, say, an index of line numbers and associated pointers to the program code. Rather than storing three bytes per line (length and number) embedded in the program, a separate table could have stored four bytes per line (two bytes for the line number, two as a pointer) so the overall cost in memory would have been only one byte per line, but with the potential for much faster GOTO, GOSUB and RESTORE.

there would be no benefit of making Sophie's implementation 12K rather than 16K.

Think of the additional features that could have been included with 4K spare! The language could have been much richer, for example with some of the features which have been added since (CASE..ENDCASE, WHILE..ENDWHILE, multiline IF..ENDIF etc.) being included from the start.

I don't think I'd call that a cheat. As long as these behaves as if they were floats, i.e. when you do FP-specific things with them they work then that's all that matters.

It was a cheat in the sense that it artificially manipulated benchmark results to make my Z80 BASIC look faster than it really was.

[BigEd]

It still doesn't feel like a cheat to me. Is there any program which would behave differently in the presence of this 'variant' optimisation?

[Richard Russell]

Is there any program which would behave differently in the presence of this 'variant' optimisation?

Only ones which depend on the internal representation of a variable. Even in the old 8-bit versions you could legitimately access a variable in memory by using CALL's parameter block to provide its address, and more recently I've added an explicit 'address-of' operator. You'll find a few of my programs containing code like:

Code: Select all

      a *= 1.0

which has the sole purpose of coercing it to be a float so that, for example, it can be passed 'by address' to an API function.

There was a cost in overall floating-point numeric range, however, because I reserved one value of the 8-bit exponent (zero) to signify that the 'mantissa' actually contained a signed 32-bit integer.

[Coeus]

It was a cheat in the sense that it artificially manipulated benchmark results to make my Z80 BASIC look faster than it really was.

Well it presumably had the effect of making the benchmark figure better but if the result of doing calculation on what you believe to be floating point variables is still correct and execution is just faster then that's fine as it will improve performance not just on the benchmark but on a class of programs ported from other BASICs where there was not concept of floating point and integer variables, just numeric variables, where the majority of numeric variable contain integer values.

The point about the VW emissions cheat is that they knew full well that the emissions test itself was the only place it would deliver the claimed performance and that in normal use it would be worse. I don't think that is the case with your variant variables.

[Richard Russell]

I don't think that is the case with your variant variables.

I did say it wasn't in the same league!

[Coeus]

It's not just the CPU. Z80 BBC BASIC on a 3.5MHz Z80 on a ZX Spectrum is more than three times faster than Z80 ZXBasic on the same 3.5MHz Z80 on the same ZX Spectrum.

I am not sure anyone was suggesting that it was all down to hardware, just that the hardware did have some effect and just looking at CPU clock speeds doesn't tell the whole story.

But these results are certainly interesting. Here's the obvious thing to try: Z80 BBC BASIC on an (emulated) Z80 2nd processor which runs at 6Mhz:

Unfortunately I can't slow the clock down to 4Mhz as it then it doesn't keep up with the tube. But according to 1024MAK's post that isn't so far off the equivalent of a 2Mhz 6502 but we'd need to scale the answers by 5/6 which gives an overall figure of 2.05Mhz, i.e. pretty close to the 2Mhz 6502.

So, far from being rather slow, Richard's implementation for the Z80 is actually pretty quick!

[Richard Russell]

So, far from being rather slow, Richard's implementation for the Z80 is actually pretty quick!

I'd need to look at the code which is being used for those measurements. If the "Real REPEAT loop" and "Real FOR loop" are using genuinely floating-point values then I would have to agree that the conclusion is valid. But if, as I suspect, they are using integer values held in suffixless variables then they aren't measuring what they purport to, but rather the speed of integer loops!

Edit: In what I believe to be the code you are running, the 'Real' loops are indeed nothing of the sort:

Code: Select all

   50 Z=0:B=1:C=100:D=510
   70 PRINT"Real REPEAT loop    ";:T%=TIME:A=Z:REPEATA=A+B:UNTILA>C:T%=TIME-T%
   90 PRINT"Real FOR loop       ";:T%=TIME:FORA=Z TO D STEP B:NEXT:T%=TIME-T%

Whoever wrote that program should have used non-integer values for B, C, D and Z for the measurements to be meaningful with any of my BASICs. See why I called the variant variables a cheat!?

[scruss]

Not yet mentioned is the complete lack of garbage collection in BBC BASIC. String heap cleanup on other BASICs could be a real slowdown. It did mean that a BBC BASIC programmer had to be a little careful about string allocation and memory management, though.

I've never tried one, but the rather rare DAI home computer is reputed to have an extremely fast BASIC, even for its not-great 2 MHz 8080A processor. I suspect the optional AM9511 floating point coprocessor had a lot to do with the speed.

[Richard Russell]

Not yet mentioned is the complete lack of garbage collection in BBC BASIC.

Later versions of BBC BASIC, from ARM BASIC 5 onwards, support the re-use of memory freed by strings. Admittedly they don't coalesce memory freed by two small strings so that it can be used by one larger string (there's an assemble-time option called COAL that Sophie added to implement this experimentally, but I don't think it's enabled in any released version).