34

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?

15
  • 3
    This question is asked in counterpoint to BBC/Acorn BASIC, what made it so fast?
    – scruss
    Sep 14, 2022 at 23:26
  • 2
    The other question already mentions terrible floating point math implementation for the Atari version (presumably when compared to the Microsoft BASIC used by most 8-bit systems). It wouldn't surprise me if Sinclair's BASIC also suffered for this too.
    – Brian H
    Sep 14, 2022 at 23:34
  • 1
    I've read Atari BASIC has to search from the beginning of the program every time any GOTO or GOSUB is executed. They seemed to be focused on getting the required features into 8KB by the deadline and didn't have time to optimize for speed.
    – Tim Locke
    Sep 15, 2022 at 0:07
  • 4
    While there are exceptional slow BASIC, I would think this question is not very focused - one could go in quite lengthy discussions about details without having any real result - just opinions. Especially when repeating assumed speed from back then.
    – Raffzahn
    Sep 15, 2022 at 0:25
  • 1
    @MichaelHarvey: definitely. I translated Fortran FFT functions to it, and used it to learn about DSP. I also wrote a program to calculate the Mandelbrot set, and added a selection system to zoom in on it. Its mathematical routines were fairly fast.
    – chthon
    Sep 15, 2022 at 10:17

8 Answers 8

33

"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.

7
  • 3
    I don't think the ROM media was really the problem with patching. There was no internet back then, so "patches" for home PC software weren't really A Thing. However your software was initially delivered to them, bugs and all, was how the customer was going to use it.
    – T.E.D.
    Sep 15, 2022 at 14:40
  • 2
    Oh hacks really * were * a thing. Software might have been on tapes and on old floppy disks with software controllers, but teenagers were disassembling copy protection and modding games as early as Apple II and BBC model B, because I remember it from 1980-82 ish. The difference was they circulated between friends, by hand, not online. (Perhaps BBs but I wasn't around those). So yes, patches and mods were rampant, and modded software to remove bad features and limits, as well as copy protection was an established scene. Systems that only took Roms sometimes had modded Roms, but rarer.
    – Stilez
    Sep 15, 2022 at 16:05
  • 1
    @T.E.D.: Many versions of BASIC included hooks to change certain aspects of behavior, and tweaks to do so were quite commonplace, with some being supplied by system vendors.
    – supercat
    Sep 15, 2022 at 16:46
  • 1
    In the early 80s, user groups, computer dealers, and fellow enthusiasts were surprisingly efficient at getting updates distributed. I was always using the latest version of Atari's disk-based DOS as it arrived, but never upgraded the BASIC cartridge that came in the box with the machine.
    – Jim Nelson
    Sep 15, 2022 at 17:15
  • 2
    @T.E.D. your "local computer shop" who had a relationship with a sales rep at the manufacturer was a thing, and fixes could be (and were) distributed that way if the company had an interest in doing so.
    – hobbs
    Sep 16, 2022 at 2:58
27

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.

36
  • 10
    Wow, that's last bullet ... that's just appalling. Floating point math back then had no CPU support whatsoever, and was so slow that programs used to move heaven and earth to avoid it. I have a tough time believing anyone would have been so profligate as to do loop increments with it.
    – T.E.D.
    Sep 15, 2022 at 14:46
  • 2
    @T.E.D.: It may seem absurd, but that's how things were done. The fact that stuff worked at all was sufficiently magical that there was no perceived need to make things faster. I don't think one would have needed to add very much code to a typical MS BASIC to make it so that numeric constants would be parsed as integers unless they exceeded 65535 or a decimal point was seen, nor to say that if the exponent byte of a number was zero, its value would be expressed by a two-byte integer and the sign bit, addition, subtraction, and comparisons of such values would operate...
    – supercat
    Sep 15, 2022 at 16:44
  • 2
    Also, some interpreters allowed the use of arbitrary numeric expressions as GOTO/GOSUB targets, e.g., GOTO 1000+N*100. This provided a compact way of implementing a switch statement, if you set up your line numbers correctly. But it may have impeded optimization, as you then can't distinguish lines that are potential jump targets from lines that aren't.
    – dan04
    Sep 15, 2022 at 16:56
  • 2
    @T.E.D. that’s how the original BASIC was designed. It had no other numeric type than floating point, to not bother beginners with such things. Everything else is a non-standard extension…
    – Holger
    Sep 16, 2022 at 8:10
  • 4
    "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.". Sooo... just like Javascript is still doing it in 2022? Sep 16, 2022 at 14:36
11

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.

3
  • 1
    In many MS dialects of BASIC, if one writes A%=B%+C%, the interpreter would convert both variables to floating-point format, then perform the addition, and then convert the result back to an integer. This sequence of operations would take much longer than simply using floating-point variables. Arrays of integers would take less storage than arrays of floating-point values, but that was the only time when integer types would offer any advantage.
    – supercat
    Sep 15, 2022 at 21:57
  • there is also euclidian division... but that can be achieved with rounding too Sep 16, 2022 at 6:16
  • I feel like that's incredibly difficult to do since the BASIC interpreter used the zero page liberally to increase speed, meaning that you have to know exactly what memory locations are safe to use, which can get confusing fast. Meanwhile if you stick to pure assembly you can just do whatever. Dec 7, 2022 at 13:59
6

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).

5
  • 1
    And that's why the ZX81 had FAST and SLOW modes. Not that FAST mode was that fast, it was just fast by comparison with SLOW mode.
    – Neil
    Sep 16, 2022 at 21:59
  • Sinclair BASIC was on the ZX80, ZX81 and Spectrum but the latter used the ULA to display the screen, not the Z80. Sinclair BASIC just wasn't written for speed, it was to be compact in the small ROMs of the ZX80 and ZX81 while Nine Tiles weren't given the opportunity to speed it up for the Spectrum and its 16 KB 90%-full ROM.
    – TonyM
    Sep 21, 2022 at 23:23
  • 1
    Didn't the Sinclair skip text parsing altogether by storing each BASIC instruction (e.g. PRINT,GOTO,etc) as a single byte, meaning that you had to press the specific PRINT or GOTO key to actually use those commands, but in return saving the interpreter a ton of hassle? Dec 8, 2022 at 15:51
  • I disagree. Algorithmic shortcomings were a real problem with BASIC interpreters. Retro BASIC implementations had serious memory and development time constraints. It was very time consuming to implement and debug anything fancy, thus simple linear algorithms prevailed, and a lot of subroutines were reused in as many places as possible. Thus eg. only integer or only floating point numbers but not both, floats stored as text, etc. The only BASIC from back then that had excellent performance was ABC 800 BASIC II from Luxor In Motala, Sweden. That was good enough for serious business applications! Dec 10, 2022 at 19:41
  • And speaking of BASIC II: I'm reverse engineering it right now and it's a tour-de-force of interpreter design. It was a structured basic with functions, while loops, "business strength" file I/O, solid type conversion functions (floats/ints/strings), BCD arithmetic in addition to integer and floating point, and the language was extendable - hardware extensions could include new commands and I/O routines in their EPROMS. Stay tuned :) Jan 2 at 15:02
6

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.

12
  • It's even worse when you consider the fact that the 6502 has no hardware support for 16-bit integers. You have to work with each half separately! (But I'm sure you knew that.) Dec 7, 2022 at 14:01
  • 1
    @puppydrum64: Worse than that, the BASIC interpreter would, for each digit of a decimal constant, increment the floating-point exponent of the value processed thus far, make a copy with the exponent two higher, and then use a floating-point addition to compute the new value (original times ten).
    – supercat
    Dec 8, 2022 at 15:42
  • @supercat Good grief. I couldn't figure out how to do software floating point in assembly, and these guys flex by using it for everything. Not a good thing though! Dec 8, 2022 at 15:49
  • @puppydrum64: I should have specified that Microsoft's BASIC interpreter in particular does that. But it has the part of the CHRGOT routine (retrieve next byte of BASIC code) which is stored in RAM include logic to check whether each character is a digit--a placement which saves at most three cycles in cases where calling code would actually care, when the scenarios where the number is a digit are processed abominably slowly.
    – supercat
    Dec 8, 2022 at 15:59
  • 1
    @MauryMarkowitz: In the 8-bit era, silicon cost was dominated not by transistors, but by routing. The Z80 used a 4-bit ALU internally, which would have had one input and one output that could be attached to bits 0, 4, 8, or 12 of any register, one that could be connected to bits 1, 5, 9, or 13, etc. so a 4-bit shift could have been handled efficiently (and some instructions exist for that). On most other 8-bit CPUs, adding a 4-bit shift instruction would have required adding a fair amount of extra wiring.
    – supercat
    Dec 11, 2022 at 19:53
5

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.

12
  • How feasible would it be to just create a BASIC compiler that turns it into ARM7TDMI code? Dec 8, 2022 at 15:54
  • 1
    BASIC Four (MAI) microcomputers did most of this - in microcode. But BASIC-only computers for commercial 3rd-party software development was their entire thing and they had a good engineering staff for it.
    – davidbak
    Dec 10, 2022 at 18:24
  • 1
    One extra trick I’ve seen done was variables stored in the token stream. After all, if a variable is referenced in the token stream, it exists, so fixed size values could be stored right there. For variable sized stuff (strings, variable arrays) a pointer would be stored. The symbol table was stored in a Huffman coded format. After all, runtime is time-critical, editing/listing can be at “human” speeds. Dec 10, 2022 at 19:44
  • 1
    @davidbak -- that's interesting, certainly not the typical BASIC found on home computers though Dec 13, 2022 at 22:59
  • 1
    Otherwise all the points in this answer are spot on. Especially the last one!
    – davidbak
    Dec 13, 2022 at 23:44
2

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.

2
  • On the base console, the Basic program was not stored in CPU addressable RAM but in the Video-RAM of the display processor -- note that there was a good reason for this: the machine had 256 bytes of CPU RAM and 16K of Video RAM.
    – occipita
    Mar 11, 2023 at 20:36
  • Indeed, there was a reason for it, but I'm not sure it was a "good" one. ;-) Mar 13, 2023 at 7:07
1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .