What made some 8-bit BASIC interpreters especially slow?

Question

Most 8-bit systems had a BASIC interpreter that ran at a rate roughly commensurate with the CPU type, speed, memory bandwidth and interrupt status. Some systems, however, had interpreters that ran at a fairly dismal speed: I'm particularly thinking of Atari BASIC and Sinclair BASIC.

What design decisions contributed to making these interpreters so inefficient compared to contemporary competitors?

Answer 1

"Atari BASIC: The Good, the Bad, and the Ugly" is an excellent summary Atari BASIC's advantages and weaknesses. To answer the Atari half of your question:

How did it get so slow? Basically because of two problems – a poor implementation of line number lookups in loops and jumps, and a poor implementation of multiply and divide.

Because Atari distributed their standard BASIC as a ROM cartridge (and later in system ROM with the XL line), it was difficult and expensive to distribute a patched version that could have fixed these problems.

Atari BASIC's designers discuss the language's internals in The Atari BASIC Source Book.

Answer 2

Commodore BASIC suffered from four major performance issues:

• It stored numbers as text in the source, and had to parse numbers every time they were used.
• Program lines are stored as singly-linked lists, so if it branched back to a line earlier in the program, goto and gosub had to start at the top of the program and find the target line, one line at a time. Forward branches searched one line at a time, starting from the executing line.
• Variables were stored in a singly linked list, so it would iterate through the list, one by one, until it found the referenced variable.
• All computations are done as software floating point. Integer variable updates would be converted to floating point, have the computation performed, then converted back to integer.

Other than those severe performance issues, it was pretty good.

Answer 3

Oric BASIC was slow for several reasons I can think of

• like most interpreted BASIC flavours, it used floating point for numeric variables by default. One could use integer types (ex: A%) but in practice that was rarely used.
• In so-called "high resolution" mode, graphical operations were limited to point, line, circle. There was no flood fill or ellipses for instance, you had to roll your own (better in assembly!)
• the language doesn't provide array copy. You have to use basic loops.
• the keyboard hardware doesn't trigger interrupts, so the BASIC (using the 100Hz interrupt) scans each key of the keyboard a lot of times per second. It has to, when you have to type text. In games, reading the keyboard without any tricks results in a 20% performance loss (even in pure assembly loops, as the interrupt was active all the time, unless shut down and replaced by custom poll of just a few useful keys, or reduced frequency of the polling (L'Aigle d'Or used the latter).

(I would be tempted to add that it was running in ROM, and that ROM memory is slower than RAM memory, but I'm not sure if it applies to this case)

Despite those issues, it was able to store a lot of instructions. Each basic token (FOR, CLS, ...) was stored as 1 byte token. Coding the same thing in assembly or in C took a lot of instructions, thus memory. It was very often that commercial games used BASIC for the non real-time parts of the game (hiscore, menu, intro, level init) for simplicity/quicker development but also for smaller size, and reserved pure assembly for the main game loop.

Answer 4

Don't blame the BASIC - blame the computer.

The ANTIC chip on Atari computers basically locks out the 1.79MHz 6502 for the entirety of each visible scan line in text mode, so the CPU gets maybe 40% of the available cycles (horizontal and vertical blanks).

The Sinclair uses its Z80 to do screen refresh and again, that leaves little for BASIC (or anything else).

Answer 5

Someone linked to my earlier article on the problems in Atari BASIC, but that was written long ago and I can offer some additional insights. Curiously, by all rights Atari BASIC should have been quite fast, but a couple of decisions nuked it.

This is going to be long...

To understand where this is going, we need to consider some other examples of early microcomputer BASIC. To do so, we'll consider the following program:

10 A=A+1
20 IF A<1000 THEN 10

When one thinks of "an interpreter" one may think of a system that reads the source line by line (or statement by statement), interprets it, and runs the result. Such systems are rare, but we can consider one example, Tiny BASIC. When the user types the second line in and presses return, you would get something like this in memory:

$14 IF A<1000 THEN 10 $13

At runtime, the interpreter has to read this character by character, figure out each of the keywords, and then run them. Now compare the same line in MS:

$0014 $xx $8B A $B3 1000 $A7 10

MS tokenized the keywords, and at runtime, it can separate them easily because tokens have their high bit set. This short-circuits having to read the text and parse it, at least partially. It still has to parse and lookup variables and convert the numeric constants, 1000 times each. Note the $xx which is a pointer to the next line, allowing it to do line lookups much faster than in Tiny.

Now finally, consider Atari BASIC:

$0014 $xx $xx $07 $80 $20 $0E $430100000000 $1B $410100000000

The line has been completely converted into the form that it will be when it is run. For instance, the $80 indicates the location in memory for the A variable, so there is no need to search for it. The two numeric constants have been converted to their internal format, so again, nothing has to be done at runtime, they just copy it directly into the registers. Additionally, it stores the location of the next line, as well as the next statement, which may or may not be on the same line. This allows IF statements to jump to the next statement without having to search the source for the colon.

So at this point, it would seem AB should run circles around MS. But in fact, it is about 1/3rd the speed on most benchmarks. As I noted in my earlier article, there are two main reasons for this.

The first is that they store all numeric constants in a BCD form. However, the line numbers themselves are in 16-bit int format. This means the line number has to be converted from BCD to a 16-bit int every time through the loop. Had they either (A) provided a second format for storing line numbers, or (B) stored the line numbers in BCD format, all the line lookups would immediately have improved.

Now a GOTO here and there is not going to be too bad, they are not always found in loops. But here's where it goes from bad to worse: they also stored the return line in FOR/NEXT loops as a line number. So every time through a FOR/NEXT, it has to search the entire program for the matching line. This was absolutely brain-dead. There was a patch that came out sometime in the 1980s that made the change to store the address in loops, and it results in an average 50% speedup for about 30 bytes of code.

To a lesser degree, another issue is that the BCD code was complete pants. It's possible to make performant BCD code on the 6502, although multiply and divide will always be slower. But simple stuff like A=A+1 should not be too much different than in binary. Not so in AB, where the code was almost always much slower than the equivalent in MS's binary code. For instance, that BCD-to-int could take some god-awful amount of time.

So in the real world, does the basic idea behind AB - and Sinclair worked the same way BTW - actually improve performance? Well for that we can look at TurboBASIC. TB was a (significantly) patched version of AB which removed some of this dumbness and added a new math package.

The results can be seen here.

Note the faicuai tests, where 100 = 100% of the performance of a C64 - as you can see Turbo runs about 65% faster in this large battery of tests.

Answer 6

I'll add my $0.02 since I've written a few performant BASIC-like interpreters for work for the S08, ColdFire and ARM7TDMI. Everything below is generally NOT what BASIC interpreters did in the 80's.

• tokenize everything into a token/direct/subroutine threader
• tokenize all values into the smallest, most 'native' format
• move line numbers into a list of pointers (out of the token stream)
• move variables to their own region and use pointers
• move strings and comments to their own region and use pointers
• use the string table as the base for the string heap
• binary search the list of line numbers on GOTO/GOSUB
• do not use line numbers for function-calls and loops
• lean on your parser to do all the heavy lifting, not the interpreter

What it should have been is something more like a "Shunting-Yard FORTH with Line Numbers" and it should have been able to perform close to that as well.

Answer 7

I will add the special case of TI-99/4A TI-basic which is probably one of the worst offender in the category of slow interpreters.

• TI-Basic (and also TI-Extended Basic) are especially slow because the interpreter was not written in TMS-9900 machine language as one would suppose, but was written in GPL (Graphic Programming Language) which was a kind pseudo-code (a bit like Java bytecode or UCSD P-Code or Apple II's Sweet16) to add a level of abstraction to the system.

• On the base console, the Basic program was not stored in CPU addressable RAM but in the Video-RAM of the display processor. Each byte read or written required I/O commands.

• As all other interpreters, everything is done in floating point. The peculiarity of the TI machine is that the floating point routines implemented were at the same level of sophistication as their FP routines in the TI calculators, i.e. 8 byte for storage, 13 digits precision with -99 to +99 range for the exponent (decimal storage). This had the advantage of nice calculation capacity without the precision issue with the binary floating points of other machines but cost quite some performance.

• Syntax and semantic check at start. When invoking RUN command the interpreter analyses the whole program to see if there are still some errors in the code. For big programs this can take a lot of time (minute).

All the other issues listed for the other interpreters apply also here: linear search for line numbers and for variables. Garbage generating string functions with stop the world garbage collection from time to time.

Answer 8

There are many things that could slow an interpreter to death, I can list them but here are a few:

1. How it does manages the variables in memory - if the access method is fast or slow, and the number of times the program accesses them.
2. In case of numeric variables, if and how differs between different types (bytes, words, ints, decimals).
3. In case of having decimal support, how long they are and how are implemented (fixed vs floating point). Fixed point are always faster than floating point, but have both fewer range and resolution.
4. If the computer has a math co-processor in the form of a floating-point unit or similar, or by the other hand if they have to operate them with a software library. Software implementations are always slower than hardware ones when using the same system. You can check it even without an interpreter if you take an old PC with 8086/8088+8087 and make a program that list the result of a large set of operations in floating point numbers first in software, then with the coprocessor.
5. In case of microcomputers with banking systems, how efficient is it. For instance, TA Alphatronic P2U had 16KB RAM on top of the system ROM and for every single access to screen had to disable the lower RAM to access it, then enable it again.
6. The number of checks every command of the interpreter does at run-time. This may be the most problematic factor when building an interpreter. Unnecessary checks not may, but will slow the interpreter; but the problem not only lies with unneeded comprovations but also with necessary ones placed wrongly and, when in masse causing significant overhead.
7. Basic specs of the computer: the frequency at which the processor operates, if the computer has slow dram which has to wait for...
8. How many accesses the I/O devices have and if it has to wait for them.
9. If the block operations are executed with a DMA or if the CPU takes responsibility. A couple of clock cycles per operation may not seem a lot, but when you have hundreds or thousands of transfers it pays back.
10. Specifically to timers, if they are implemented with an interrupt-driven clock or are implemented using cycle-counting