How fast were BASIC interpreters in the 80s? (Is this optimization for speed really necessary?)

Question

I have a client who wants me to analyze a BASIC program from Umberto Eco's Foucault's Pendulum. I have never written a line of BASIC in my life as I was born in 1995 and started programming around 2010. The program isn't difficult to understand though, all it does is generate all permutations of the 4 letter input. I was able to execute it with vintage BASIC on a modern PC. While the program works flawlessly it seems unnecessary difficult to read to me. I was able to create a (in my opinion) easier to read program that generates exactly the same output.

Here is the original program from the book:

10 REM ANAGRAMME
20 INPUT L$(1), L$(2), L$(3), L$(4)
30 PRINT
40 FOR I1 = 1 TO 4
50 FOR I2 = 1 TO 4
60 IF I2 = I1 THEN 130
70 FOR I3 = 1 TO 4
80 IF I3 = I1 THEN 120
90 IF I3 = I2 THEN 120
100 LET I4 = 10-(I1+I2+I3)
110 LPRINT L$(I1); L$(I2); L$(I3); L$(I4)
120 NEXT I3
130 NEXT I2
140 NEXT I1
150 END

And here is my (better readable) version of the program:

10 REM ANAGRAMME
20 INPUT L$(1), L$(2), L$(3), L$(4)
30 PRINT
40 FOR I1 = 1 TO 4
50 FOR I2 = 1 TO 4
70 FOR I3 = 1 TO 4
80 FOR I4 = 1 TO 4
90 IF (I1 = I2) OR (I1 = I3) OR (I1 = I4) OR (I2 = I3) OR (I2 = I4) OR (I3 = I4) THEN 115
110 LPRINT L$(I1); L$(I2); L$(I3); L$(I4)
115 NEXT I4
120 NEXT I3
130 NEXT I2
140 NEXT I1
150 END

The difference between the two versions aside from the readability is obviously that my program will take more instructions to execute. But other than that there is no difference. So I assume that the original program is optimized for speed. I counted the number of instructions that the original program and my program executed to reach the goal and these are the numbers I came up with:

• Book program: 238 instructions executed
• My program: 710 instructions executed

Which doesn't seem to me that much of a difference. The book clearly states that it is a one purpose program that is only used a few times and not on a regular basis. So this seems to be a poor trade off to me.

The character in the book later tries to adjust his program so that it works with 6 characters as input and it takes him over 30 minutes to do so and he makes multiple mistakes doing so. In contrast to that I was able to adjust my program to work with 6 characters in under 2 minutes and on the first try.

However my 6 characters program needs to execute 112698 instructions to reach its goal. The version for the 6 letter program is not given in the book, so I have no numbers to compare that with.

So here is my question. How fast would BASIC interpreters work on typical home computers in the 80s. Would you feel a noticeable difference between the two programs in execution time. I would assume that the primary bottleneck in performance would be the printer and both programs execute the exact same printer instructions.

How long would it take for it to execute a ~100000 instructions. Does it matter that every ~4th instruction is a jump?

Answer 1

The speed of BASIC interpreters has been discussed elsewhere on this site, see How can you measure time using BASIC on Atari XL computers? for example. They were slow, in many cases very slow; bear in mind that micros in the 80s had slow CPUs, small amounts of memory, and most BASIC implementations were interpreted. Even BASIC on PCs was slow (at least, BASICA and GW-BASIC). Worse, many manufacturer-provided BASIC interpreters were even slower than they had to be, e.g. because they performed all arithmetic using floating point, with poor implementations of floating point algorithms at that, or because all searches were done linearly, with no indexing of any kind.

Regarding your readability question, readability (and by extension, maintainability) is to some extent in the eye of the beholder. Short-circuiting loops makes a huge difference, and was second nature to programmers in the 80s; the program you show could well have been written like that from the beginning, not as a result of optimisation. You determined yourself that the short-circuiting version of the program uses three times fewer instructions than your “more readable” version; that’s an enormous difference! The fact that the fictional character takes so long to adjust the program to six characters isn’t representative, it’s fiction after all.

How long a typical micro would take to execute 100,000 machine instructions would depend on what those instructions were. For a typical mix on a typical 1MHz 8-bit micro, a time getting on for a second wouldn’t be surprising. BASIC instructions are another matter entirely, 100,000 BASIC instructions would take far longer to run.

The cost of jumps, when there is one, is dwarfed by the cost of the extra loops. In any case an interpreted program is going to involve lots of jumps at the machine level...

Answer 2

They were awfully slow.

And not just because the CPUs they ran on were slow; the interpreters themselves tended to use some terribly inefficient implementation techniques that certainly wouldn’t pass for good practice today:

• Where a modern programming language interpreter might use a just-in-time compiler or convert the program into bytecode before running it, a BASIC interpreter of the time would merely convert the source code into a token sequence, and otherwise re-parse the syntax every time a line of code was run. With home computer BASIC, bytecode was barely even heard of (though there were some language implementations based on it, including Blitz BASIC), and you could forget about JIT compilation entirely.
• Number literals were represented as character sequences instead of native machine words, so again, they had to be parsed every time they were evaluated.
• Some dialects (like variants of Microsoft BASIC, which was fairly widespread) offered only the floating-point number type and used floating-point arithmetic internally, slowing programs down. This was made even worse by the fact that those computers usually had no dedicated FPU, meaning the interpreter had to rely on a slow software implementation. (Take a look, for example, at Microsoft’s 6502 BASIC ANDOP, OROP and NOTOP routines, which convert the number to an integer, perform the bitwise operation, then convert it back to floating-point.)
• Line numbers had to be looked up every time a GOTO jump was performed, using linear search instead of an index or storing the direct target address next to the jump instruction. This meant jumps became slower as the program grew larger.

This all added up to some pretty large overheads. There were no fancy UB-driven optimisers either: all operations were executed exactly as written. (Though to be fair, language implementations of the time didn’t have much compile time to spare on optimisations either, never mind the theory behind them not being as developed as it is today.)

To get a rough estimate of how much performance was lost to interpretation overhead, we can take The 8-Bit Guy’s demo (taken from his video about machine language) comparing a BASIC program that updates the colour of the screen border to an equivalent program written in assembly. The host didn’t perform any timing measurements himself, but we can recover them simply by looking how large a fragment of the screen was displayed between the colour switches.

First the BASIC version:

The C64 runs at a resolution of 320×200 (without the border). In the screenshot above, I measured the width of the colour band as about 516 pixels, where the screen area without the border is 660 pixels high. This gives a speed of roughly one colour switch per 516 ÷ 660 × 200 ≈ 156 scanlines.

Now the assembly version:

The assembly program manages to switch the border colour about 4.5 times per scanline. We can thus calculate that the BASIC program is 4.5 ÷ (1 ÷ (516 ÷ 660 × 200)) ≈ 703 times slower, almost three orders of magnitude. When this was their point of comparison, no wonder people thought you needed assembly to have code perform well.

Now, you may of course say this measurement is not particularly rigorous or representative, but even this should give you a pretty good idea how rough things were back then. When the CPU barely ran at 1 MHz, while writing code in BASIC made things run 700 times slower even than that, every optimisation was worth it.

Answer 3

You can actually try out these programs on a real-speed computer of that vintage using jsBeeb or, for a more convenient program editing environment, bbcmic.ro.

To make the above programs compatible with BBC BASIC, change LPRINT to just PRINT, and add a line at the beginning reading DIM L$(4).

I found that the published program took less than a second to run, while yours took about 3 seconds.

Answer 4

For a program as small as this, optimization doesn't matter. But ...

IMO the main reason the first version is hard to read is not the optimization, but keeping track of the statement numbers in the GOTO statements. Every more modern programming language has some type of "IF ... THEN ... ELSE ... END IF" statement which makes the labels unnecessary.

Think about what happens to your version if you want to create an anagram with more than four letters. Let's count the number of times you execute the logic in line 90, compared with the number of lines of output:

Number of letters	line 90	line 110
3	3 × 3 × 3 = 27 times	3 × 2 × 1 = 6 times
4	4 × 4 × 4 × 4 = 256 times	4 × 3 × 2 × 1 = 24 times
5	3,125 times	120 times
6	46,656 times	720 times
7	823,543 times	5,040 times
...
10	10,000,000,000 times	3,628,800 times

It should be clear that you need to do something to reduce the number of times you get to line 90, not to mention that with 7 letters, line 90 would need 720 separate comparisons joined by OR.

This first version meets both of those objectives. It only needs n − 1 IF statements for n letters, and it "weeds out" the unnecessary work at the earliest opportunity. It is not only more efficient, but easier to extend to more letters.

Of course the "really optimal" way to program this for a longer anagram (say 10 or 20 letters) is not a set of nested loops like version 1. The big problem with version 1 is that you need a different program for every different number of letters.

An algorithm that used recursion, and/or one based on the mathematics of group theory (and specifically on permutation groups) would not have that limitation, and you could write a single "readable" program that would (given enough time) create anagrams of any length.

The algorithm would generate each new anagram by swapping the position of two letters in the previous one, in such a way that it cycled through every possible anagram before returning to the original order of the letters. It would not "waste" any time at all generating things that were not anagrams and then discarding them.

Answer 5

BASIC interpreters on 8 bit microcomputers are miraculously performant within their context.

You might think it sounds crazy to take a 1 or 2 MHz machine and bog it down with an interpreter, and one that doesn't even translate code into byte code! These BASICS were just tokenize for more compact storage, but otherwise interpret at the token level; the interpreters are parsing statements and expressions over and over again.

Yet, BASICS are fast enough for simple video games with animated action for a small number of objects, and useful applications such as dial-up bulletin boards with decent text editing, or custom scientific or business applications.

The practice of identifying performance hot spots in BASIC programs and using machine language further helps the usability of BASIC on these micros.

Speaking of which, BASIC interpreters also were developed with the capabilities and use cases of their respective host machines, and included some of the right kinds primitives for those use cases. In a game ostensibly written entirely in BASIC, graphic primitives are used, like drawing a line, or putting an entire shape on the screen. A statement like PLOT X1, Y1 TO X2, Y2, though taking time to scan and dispatch, calls a machine language routine that gets right down to the business to putting pixels onto the screen. The routine is hard-coded to one kind of display hardware and not go through any driver layers.

Get this: the Applesoft BASIC found in Apple II computers has both floating-point variables/arrays as well as integers. All unsuffixed variables like A, TX, I, are floating-point; integers are denoted by a trailing % sigil like K% or X%. Yet, it is common for programs in this dialect to use floating-point numbers for loops. This Applesoft tutorial doesn't even mention integers, and it is reflective of the historic programming practice. In the heyday, users of Applesoft BASIC were cheerfully oblivious to the fact that they were writing loops that subscript over arrays using floating-point, which is implemented in expensive floating-point routines executing on a 1Mhz processor with 8 bit registers. A big reason for this is that the FOR/NEXT looping construct of Applesoft BASIC only supports floating-point numbers! Yikes!

BASIC programs were written using techniques that squandered performance; the interpreters and the programs were nowhere near as fast as was possible for an interpreted BASIC. It's as if people thought they had gobs of cycles to burn.

Steve Wozniak's original Integer Basic ran something like five times faster due to using integers for everything but it came to be disused as newer machines shipped with Applesoft ROMs. Usability was favored over speed; Applesoft was useful for a wide range of applications, including scientific calculations.

Speaking of implementation techniques, it's worth mentioning that BASIC compilers exist; they were used by people trying to get even more oomph out of their machines.

Anyway, I suspect that a major reason why 8 bit BASICS have useful performance in their context is that the memories are so small. This means that if halfway decent algorithms are used for everyday problems, you simply don't run into big enough input sizes N.

You really feel the pain, though, if you do anything that takes higher order polynomial (even quadratic), not to mention exponential time, whether accidentally or necessarily.

For a time I went to a highs chool that used a some in-house-developed BASIC program running on Apple II's for course scheduling: assigning students to class times based on what they are enrolled in. This algorithm would run for several hours. I have no idea what it was doing, but I'm guessing it was doing a brute force search of all the non-conflicting ways for the student to take those courses.

A common problem with BASIC interpreters of this era is that to maximize memory utilization, they allow character strings to fill up almost the entire heap and then run a garbage collection routine that must execute in a fixed amount of space. Often the algorithm is "find the highest-addressed string in the entire heap that has not yet been moved, and move it as high as possible in memory. Then repeat". This can create garbage collection pauses which run for seconds or minutes. Here, we're not talking about the speed of execution of BASIC per se, but an aspect of its performance entirely coded in inefficient assembly code.

I ran a BBS which is an application that naturally does a fair bit of text processing, with large arrays of long strings. The GC pauses were hurting. I used a replacement GC assembly routine which kicked in at a lower threshold and used more memory to run faster: it identified and moved the N highest addressed strings in a single pass, for N being like 50. Each pass placed these into an array using simple insertion, and then compacted them together. GC went from long pauses to a fraction of a second.

Some of the BBS's text processing code was time consuming enough that a user typing through it would experience character loss. There was a workaround for that: the BASIC interpreter used an indirect function call for invoking the code for fetching the successive tokens of the program being interprted. This indirect address was stored at a well-known location and that provided an important hook: by pointing that hook at your own machine language routine, you could get "background processing" to happen while BASIC is interpreting. I used this to poll the modem for characters and transfer them to the I/O buffer. Presto: the BBS had decently working type-ahead, in spite of a total lack of interrupt-driven serial processing.

Answer 6

Your version is dramatically slower.

I did minor changes to get it to run on Atari BASIC simply because I can cut and paste code into my Atari 800 emulator. I added an internal timer, that's the PEEKs at the top and bottom. Here is my version for the first example:

9 ST=PEEK(18)*65536+PEEK(19)*256+PEEK(20)
10 REM ANAGRAMME
15 DIM A$(4)
20 INPUT A$
30 PRINT 
40 FOR I1=1 TO 4
50 FOR I2=1 TO 4
60 IF I2=I1 THEN 130
70 FOR I3=1 TO 4
80 IF I3=I1 THEN 120
90 IF I3=I2 THEN 120
100 LET I4=10-(I1+I2+I3)
110 PRINT A$(I1,I1);A$(I2,I2);A$(I3,I3);A$(I4,I4)
120 NEXT I3
130 NEXT I2
140 NEXT I1
680 ET=PEEK(18)*65536+PEEK(19)*256+PEEK(20)
690 PRINT "T=";(ET-ST)/60

That runs in 3.5 seconds. Here is the code for the second example:

9 ST=PEEK(18)*65536+PEEK(19)*256+PEEK(20)
10 REM ANAGRAMME
15 DIM A$(4)
20 INPUT A$
30 PRINT 
40 FOR I1=1 TO 4
50 FOR I2=1 TO 4
70 FOR I3=1 TO 4
80 FOR I4=1 TO 4
90 IF (I1=I2) OR (I1=I3) OR (I1=I4) OR (I2=I3) OR (I2=I4) OR (I3=I4) THEN 115
110 PRINT A$(I1,I1);A$(I2,I2);A$(I3,I3);A$(I4,I4)
115 NEXT I4
120 NEXT I3
130 NEXT I2
140 NEXT I1
680 ET=PEEK(18)*65536+PEEK(19)*256+PEEK(20)
690 PRINT "T=";(ET-ST)/60

That takes 8.7 seconds.

Note that Atari BASIC has absolute scandalously poor performance in FOR loops, so the difference is likely to be smaller on other platforms.

I was actually a bit surprised by the outcome; even with AB's poor looping constructs, the program is small which would minimize the effect, and moreover, the I/O of the PRINT should absolutely overwhelm loop performance. But here you have it, never assume what you can easily test!

Of course, by any practical measure, there's no real difference, it takes longer to type in a single line of code than run the program to completion.

Answer 7

Interpreters were slow and programs like this that you typed in were not expected to be fast. It's doubtful the program was optimized for speed.

You were trained to think of readability in terms of structured programming on a large screen. No gotos allowed.

In this era, gotos were expected and ubiquitous. They feel unreadable to you, but I still see questions online from people who have trouble thinking without them.

One small thing per line was also expected and ubiquitous, because you might have only 40 or even 32 characters per line. Your refactor has 89 characters, which would wrap across 3 lines and be super annoying to read on a small screen. Even here, I had to scroll to the right to read it.

Also, I might be remembering incorrectly, but I personally didn't learn about short-circuit evaluation until learning C. If BASIC interpreters commonly short-circuited, I don't know if that was common knowledge.

Answer 8

When you ran these two programs, did you do it on actual, vintage hardware (or same emulated at vintage clock speeds) or did you run the BASIC on modern gigahertz CPUs?

The very poor performance of CPUs of the day forced you to redefine your definition of "elegance".

Your concept of "elegance" is "CPU is cheap/free, especially if it's someone else's CPU, so waste CPU to make easier-to-read code". As a programmer of that earlier age, I could not possibly disagree more.

That is why stalwart programs like Microsoft Word are actually slower and more clunky on brand new PCs than they were on 1990s era machines. That is because programmers have lazily "expanded into" the glut of CPU power readily available on newer machines - for every doubling in CPU power, their code gets triply sloppier.

That said, your feelings about opaqueness are entirely valid. Here is what I call elegant:

 100 REM since our four numbers sum to 10, we
 101 REM don't need to iterate on the last 
 102 REM number... we can derive it! 
 103 LET I4 = 10–(I1+I2+I3)

Commenting is hardly an inconvenience. Some people think "I don't need comments, I know what I just did there"... but "Just" is perishable and when you come back the next day/year, you have no idea what you did lol.

That huge bolles of six comparisons is very awkward, and much harder to read than the original, so that is no improvement in elegance at all. In fact, making the L1 to L2 compare in the inner loop makes me think the programmer is foolish, since it could have been done in the outer loop much more efficiently, and spreading the compares out increases clarity and readability: "Oh, that's what they're doing there!"

You are doing six compares, and if the interpreter is non-optimizing, six compares per inner loop - very wasteful of cycles. (FYI An optimizing interpreter will suss out the entire "if" statement and on an outer "or", stop computing when it finds the first "1" value; yes, early interpreters did not do that so it was on you to hard-code it, as was done in the book). That is why the original did two IF statements instead of one with an "or".

No modern optimizer is smart enough to fix your "L1 = L2 compare in the inner loop" blunder.

---

---

A final note: I preserve stuff that's 100-120 years old, and the tech there seems primitive and simple at first glance, but it's not. There's a lot going on that is not apparent to us, and you find that out if you try to simplify something in a 100 year old design.

It's easy to "look back" at the work product of yesteryear and go "they were ignorant savages". No they weren't! They were putting the very best of themselves into their work, as you do now. That is the definition of elegance.

Answer 9

I don't think that this is fundamentally a question about BASIC interpreter design: it is fundamentally a question about math. Your code is very slightly easier to understand, but at the cost of a ton of extra work.

You code goes through all 4⁴ = 256 possible values of I1, I2, I3, I4. Only 4! = 24 are actually permutations, so in some sense your code is only 10% efficient – a bunch of the looping doesn't do anything.

The Eco code is not perfectly efficient but it does a much better job since it doesn't do all of the inner loops if two outer indices are equal.

A couple of things to note: for 6 things your code is looping through all 6⁶ = 46656 values of I1, ..., I6. Only 6! = 720 of these are valid permutations, so only about 1.5% of the values of I1, ..., I6 result in an output. Your version gets exponentially less efficient as the number of symbols increases.

I think that the programmer's difficulty with coding the version for six things is more for narrative purposes than due to any real difficulty. For each loop you check all of the indices for the outer loops, and if any of them are the same you bug out.

Finally it isn't that hard to code up a version that requires three loops, one from 1 to 4, one from 1 to 3, and one from one to 2, but the math to go from these to a permutation might look a bit opaque if you haven't thought about permutations in a while.

In general, with 80s computers whose clock speed was in single digit MHz, it was very important to do things efficiently, as many other have commented.

Answer 10

“… many professionals and computer enthusiasts criticized BASIC for its simplicity, how it handled tasks, and the way in which it did not maximize or fully utilize the power of the computer itself. However, those criticisms missed the point completely.”

(from Rankin, Joy Lisi. A People’s History of Computing in the United States Harvard University Press, 2018. Chapter 3, p.66–7)

Yes, the BASICs on home computers were terribly slow and limited when viewed by modern users. But compared to working out word problems with a pencil and paper, they were lightning fast. They were interactive, you could solve problems through trial and error, you could save your work and reuse it later, no formal knowledge of algorithms required!

This, of course, gave rise to millions of lines of entirely terrible code that barely worked. As long as it was faster than manual solutions and was marginally reliable, it was often deemed worth keeping and using.

As to your comment that you were “… able to adjust my program to work with 6 characters in under 2 minutes and on the first try”, remember:

1. you're an experienced programmer: the fictional character wasn't supposed to be;

2. the character in the book used alcohol to assist in writing the code. While this might help the time pass during manual drudge-work, it's really not conducive to clear or efficient programming. I speak from the unfortunate experience of having to debug a seldom-sober former manager's code.

---

With interpreted BASIC on 8-bit computers, knowledge of the particular interpreter you were running could make almost as much difference as optimizing the algorithm. For example, on the BBC Micro:

• as written, the four letter anagram code runs in 0.44 s and the six letter version posted elsewhere in this thread in 22.7 s

• altering the loop variable names to use BBC BASIC's fast single-letter integer variables A%, B%, C% and D% (etc.) reduces the run times to 0.29 and 14.93 s. That's a speed increase of over ⅓!

• using integer variables and packing the program into a few long lines with all unnecessary spaces removed further reduced the run times to 0.27 and 13.76 s. This can be done automatically, and I did it with basictool. So even spaces in the source mattered!

Unfortunately, after using such a packing tool, the code is unreadable. Here's the 6-letter version:

1DIML$(6):INPUTL$(1),L$(2),L$(3),L$(4),L$(5),L$(6):PRINT:T=TIME:FORA%=1TO6:FORB%=1TO6:IFB%=A%THEN15
2FORC%=1TO6:IFC%=A%THEN14
3IFC%=B%THEN14
4FORD%=1TO6:IFD%=A%THEN13
5IFD%=B%THEN13
6IFD%=C%THEN13
7FORE%=1TO6:IFE%=A%THEN12
8IFE%=B%THEN12
9IFE%=C%THEN12
10IFE%=D%THEN12
11F%=21-(A%+B%+C%+D%+E%):PRINTL$(A%);L$(B%);L$(C%);L$(D%);L$(E%);L$(F%)
12NEXTE%
13NEXTD%
14NEXTC%
15NEXTB%:NEXTA%:PRINT(TIME-T)/100:END

LPRINT would have added some overhead, as printers of the time might typically print at anywhere between 10 - 80 characters per second.

Answer 11

Different versions of BASIC supported different control structures. The program was most likely written to be understandable by anyone who understood any dialect of BASIC, regardless of which particular dialect it was. There are many ways the program could have been written that would be more readily understandable to people familiar with some dialects, but that might have made it more difficult to understand for people who weren't familiar with those particular dialects.

That having been said, I think that the versions of BASIC which would allow code to write strings into an array without dimensioning it first tended to offer better constrol structures than Dartmouth BASIC, but I don't think there would be any nice way to write the code that would be compatible with both Dartmouth, HP BASIC, and Atari BASIC, all of which handle strings as somewhat quirky arrays of characters, and and other variations which support arrays of strings.

Answer 12

So here is my question. How fast would BASIC interpreters work on typical home computers in the 80s. Would you feel a noticeable difference between the two programs in execution time.

I typed both programs into my Mattel Aquarius, which is a fairly typical 80's 8 bit home computer with a 3.58MHz Z80 and Microsoft BASIC. I don't have an RS232 serial printer so I changed the LPRINT statement to PRINT to print the words on the screen.

The first program took just under 1 second to execute according to my stopwatch. The second program took 6 seconds. Not only was the difference very noticeable, the second program ran much less smoothly which made it seem even worse.

I would assume that the primary bottleneck in performance would be the printer and both programs execute the exact same printer instructions.

That would depend on the printer and interface. The Aquarius printer runs at 1200 baud using bit-banged serial, so it would take at least 1.2 seconds to print 24 lines of 4 characters. A parallel printer with reasonable sized buffer should not slow the program down much, possibly less than having to scroll the 1000 character screen 24 times.

Does it matter that every ~4th instruction is a jump?

Jumps don't incur much penalty on these old machines because the CPUs don't have instruction caches. What really slows them down is that most had a version of Microsoft BASIC which was optimized for size rather than speed. All variables are floating point even when 8 bit integers would do, which takes hundreds of instructions to do what might have only needed tens. Commands are tokenized but their arguments are parsed 1 character at a time.

But despite all the inefficiency these machines could still do useful calculations much faster than you could by hand, and the interpreted BASIC was much easier to work with than a compiler or assembler. They were also very robust. With BASIC in ROM there was no chance of corrupting the OS, and crashes almost never occurred (unless you used the POKE command) because the interpreter had comprehensive error checking.

Answer 13

I ran your code in the VICE Commodore 64 emulator. I only added two lines 25 TI$="000000" and 145 PRINT TI/60 to display the execution time in seconds (not including the time the program sits there waiting for user input). Also I changed LPRINT to plain PRINT (as C64 BASIC has no LPRINT command) and removed some spaces from line 90 of your version, to make it fit into the 80 character (two screen lines) maximum BASIC line length of the C64 screen editor.

The original version took 1.1 seconds to run. Your version took 8.23 seconds. I'd say the difference is quite stark.

Answer 14

The theory

To me, just like to several other responders to your question, this is first and foremost the question about algorithmic complexity. The program from Eco's book generates all permutations of the 4 letter input. There are actually two types of permutation generators: with and without repetitions. The difference matters because there are much fewer permutations without repetitions:

         No of permutations         No of permutations
N        without repetitions        with repetitions
1        1! = 1                     1^1 = 1
2        2! = 2                     2^2 = 4
3        3! = 6                     3^3 = 27
4        4! = 24                    4^4 = 256
5        5! = 120                   5^5 = 3125
6        6! = 720                   6^6 = 46656
7        7! = 5040                  7^7 = 823543

You probably know that both N^N and the factorial function N! grow very rapidly, so rapidly in fact that as N grows both will quickly overwhelm the processing capabilities of any specific computer, even a modern one. From the table above you can also see that N^N grows quite a bit faster, although the difference for small values of N can be not very dramatic.

How does this relate to the presented programs? Both of them output the number of permutations without repetitions. For 4 input letters, both programs need to produce 24 outputs, but they approach it very differently. The program from Eco's book tries to exclude invalid combinations as early as possible. E.g. once it identifies that I1=I2, it skips all possible values for I3 and I4, because they are deemed to be irrelevant. How successful is this strategy? Maybe it can be assessed by thinking about how many times the innermost IF statements are executed, see lines 80 and 90. It is easy to check that they are executed only 36 times, i.e. they only result in a GOTO executed once out of every 3 iterations.

The program that you wrote actually generates all permutaions with repetitions and then selects from them the ones without repetitions. This means that your innermost loop runs much hotter: your IF statement is executed 256 times, which is particularly important because the condition that you are testing is also quite a bit more expensive computationally compared to the condition in Eco's program. For large enough N the inner loop tends to dominate the computation cost and you will be able to a large extent ignore the cost of everything else. For smaller N your mileage will vary. Crudely speaking, your inner loop is up to 256/36 times slower, i.e. slower by the factor of 7.

The computational experiment

How does the theory compare to the actual practice of computations on a small 1980s micros? Well, this thread already contains plenty of evidence:

• @TeaRex run the test on the Commodore 64 and reported that Eco's program run in 1.1 sec, whereas your program run in 8.23 sec. Your program is factor of 8.23/1.1 ~ 7.5 slower, quite close to our estimate.
• @BruceAbbott run the test on Mattel Aquarius and reported that Eco's program executed in just under 1 sec, whereas yours run in 6 sec. Once again, this is pretty close to the factor of 7 difference.
• @Chromatix did a test on BBC Micro and reported that Eco's program executed in under a sec and that your program executed in 3 sec. While not exactly confirming our prediction, this does not directly contradict them either.

I am not including measurements by Maury Markowitz because he included the user input time into his results, which makes them unreliable, esp. given how quickly the programs run. I also did a quick run of both programs on ZX Spectrum 48K, and found that Eco's program runs in 1.48 sec and your program runs in 7.84 sec (clearly, the inner loop estimate is a bit less accurate in this case, but not dramatically so).

However, these tests do not really answer the interesting question: was it worth it for Eco's characters to spend half-an-hour writing their efficient permutations generator, if they could implement a brute-force solution, like yours? To test this, I wrote two new programs for ZX Spectrum BASIC.

The first program generalizes the algorithm from Eco's book to the case of 6 letter permutaions:

  10 REM ANAGRAMME
  20 DIM A$(6): INPUT A$(1),A$(2),A$(3),A$(4),A$(5),A$(6)
  30 POKE 23672,0: POKE 23673,0: POKE 23674,0: POKE 23672,0
  40 FOR I=1 TO 6
  50 FOR J=1 TO 6
  60 IF J=I THEN GO TO 180
  70 FOR K=1 TO 6
  80 IF K=I OR K=J THEN GO TO 170
  90 FOR L=1 TO 6
 100 IF L=I OR L=J OR L=K THEN GO TO 160
 110 FOR M=1 TO 6
 120 IF M=I OR M=J OR M=K OR M=L THEN GO TO 150
 130 LET N=21-I-J-K-L-M
 140 POKE 23692,0: PRINT A$(I);A$(J);A$(K);A$(L);A$(M);A$(N);"  ";
 150 NEXT M
 160 NEXT L
 170 NEXT K
 180 NEXT J
 190 NEXT I
 200 PRINT "T = ";65536*PEEK 23674+256*PEEK 23673+PEEK 23672

Just in case you are wondering: POKEs in line 30 re-set the internal timer, and PEEKs in line 200 read its state after running the code (this allows me to measure the execution time to within 1/50th of a sec). POKE in line 140 is necessary because the number of outputs is quite large, so the POKE ensures that outputs just scroll asross the screen (without the POKE I'd be given a prompt to scroll the results every time the screen gets full, which will make my measurements less accurate).

On my ZX Spectrum 48K this program executes in 4685 frames, i.e. in 4685/50 ~ 93.7 seconds. This is a link to my program, so that you can try running it yourself. Therefore, the characters in Eco's book, who just spent half an hour writing this code, will have to wait for another 1.5 minutes to get the result they needed.

I also implemented your approach for 6 letter inputs, with the same instrumentation. The code looks as follows:

  10 REM ANAGRAMME
  20 DIM A$(6): INPUT A$(1),A$(2),A$(3),A$(4),A$(5),A$(6)
  30 POKE 23672,0: POKE 23673,0: POKE 23674,0: POKE 23672,0
  40 FOR I=1 TO 6
  50 FOR J=1 TO 6
  60 FOR K=1 TO 6
  70 FOR L=1 TO 6
  80 FOR M=1 TO 6
  90 FOR N=1 TO 6
 100 IF I=J OR I=K OR I=L OR I=M OR I=N OR J=K OR J=L OR J=M OR J=N OR K=L OR K=M OR K=N OR L=M OR L=N OR M=N THEN GO TO 120
 110 POKE 23692,0: PRINT A$(I);A$(J);A$(K);A$(L);A$(M);A$(N);"  ";
 120 NEXT N
 130 NEXT M
 140 NEXT L
 150 NEXT K
 160 NEXT J
 170 NEXT I
 180 PRINT "T = ";65536*PEEK 23674+256*PEEK 23673+PEEK 23672

It outputs all of the necessary permutations in 137118 frames, i.e. in 137118/50 ~ 2742 sec ~ over 45 minutes. Run it in your favourite emulator, to verify my findings. So, even if you were to write this program in two minutes, as you claimed in your post, you'd still have to wait for quarter an hour longer than Eco's characters just to get the necessary outputs computed.

Summary

Interpreted BASIC on the 1980s microcomputers was slow enough to justify having to use the correct approach to generating permutations without repetitions, esp. in the case of 6 letters.

Fundamentally, the difference in the number of permutations with and without repetitions is so large that it would make a difference even on the modern desktop PC. You won't notice this difference for a small number of letters, but for larger values of N, the computational complexity will once again dominate the proceedings.

Answer 15

While the interpreters were generally quite slow, even relative to the platforms they ran on, this optimization would not help things much.

The reason is that the PRINT statements would dominate this program's running time on typical machines of the age. The implicit formatting of the output already takes a fair few cycles, and then they would hook into screen-management routines that would typically shift small but numerous chunks of memory.

If the output was redirected to a file, the screen routines would be skipped, but the program would wait much longer for the moving parts of a printer or (typically) floppy disk.

Answer 16

The main issue is that back then, everything about computers felt very limited (and, obviously, also was limited).

It was easy for a kid to run out of RAM for their BASIC programs. I wrote several programs back then on an Atari 800 XL which ended up with simply not being able to add more lines.

On the assembler level, memory was paged in 256 byte pages - so for the easiest way to do on-the-fly assembler chunks to run alongside a BASIC program, you had 256 bytes before it became complicated.

The machines had an address space (!) of 64KB - they could not address more. At the end of my 8 bit carreer, I purchased a 256KB RAM extension, which gave me a whopping total of 320KB. It was not easy to use - inidividual chunks of that extension had to be swapped in since the CPU could not actually address more than 64KB.

Speed, as well, was always too slow. To give you a feeling - more intense graphics used the time when the electron beam in the monitor moved from one edge of the screen to the other (while switched off), or from the bottom back to the top, for calculations; time was so precious.

This all lead to a feeling of optimizing everything you did. BASIC was easy to program, but after a while you just naturally wrote stuff in a way that was "automatically" tuned to be either CPU or RAM optimal in whatever way you needed. You did not have todays luxury of virtually unlimited RAM/storage resources and almost unlimited processing speeds.

Doing the loops like shown in the example from your book has a major benefit over your example: it exits the loops as soon as possible. It avoids plenty of the inner loops. Line 60 alone shaves off 25% of processing further down the line (give or take) as it skips 4 out of 16 combinations, with the further skips adding more to that.

TLDR: Yes, it would have made a very noticeable difference; and more importantly, people would do it the way the original example shows out of pure habit. Writing code efficiently always had higher priority than doing it "beautiful" by some standard (or to put it differently, efficient code was beautiful).

Answer 17

TL/DR computer speed didn't really matter as it was still order of magnitude faster than no computer.

---

BASIC interpreters in 8 bit computers were slow. There are already enough answers explaining why, mainly because they traded space for performance, the interpreter had to fit in less that 16 KiB. Most machines had either Basic in ROM (Apple II, CBM, TRS-80, etc.) or loaded into RAM (Sharp MZ-80, CP/M machines etc.) which constrained the size more than the performance.

The performance was not that important as you have to realize what computers were replacing: scientific and programmable calculators and slide rules.

While games were the motor of progress in the 80s, the pioneers of computers were engineers that needed computations for their work and school teachers to do calculations. These were the people than also used programmable calculators etc. Magazines at that time would present computers more as an extension to programmable calculators that a category of itself (my late brother started his career in 1981 as engineer with a slide ruler and a scientific calculator). It was only later, when people realized computers could also function as a programmable game console that the speed of basic became inadequate. For calculation purposes it was plenty enough for the requirements of the time.

So even a slow interpreter was leagues ahead of what could be processed "by hand" at that time.

It is only a bit later that the competition and the benchmark mentality pushed (dubious) optimizations for the sake of performance. IMHO binary floats were one of these dubious optimizations (I grew up on TI-99/4A and Sharp Pocket computer Basic, both using decimal floats, and was shocked how bad Applesoft floats were. They were fast, but barely usable for my needs in school).