Prime Cruncher - a Basic benchmark from 1980

Here’s a benchmark, and some results from various 1980s machines. It’s from the June 1980 issue of Interface Age:

LISTING 1—Prime Number Cruncher
100 REM  INTERFACE AGE’s benchmark program to
110 REM  ‘discover’ the first 1000 Prime numbers
120 REM
130 PRINT "Starting:"
140 FOR N = 1 TO 1000
150 FOR K = 2 TO 500
160 LET M = N/K
170 LET L = INT(M)
180 IF L = 0 THEN 230
190 IF L = 1 THEN 220
200 IF M > L THEN 220
210 IF M = L THEN 240
220 NEXT K
230 PRINT ;N;" ";
240 NEXT N
250 PRINT CHR$(7)
260 PRINT "Finished."
270 END

We’re encouraged to walk into a “computer factory” - or in the 80s perhaps a “computer shop” and now perhaps a “computer museum” to type this in and see what we get.

On a 1981 BBC Micro it takes just under 473 seconds - not “under four minutes” as the article holds as a measure of wonderfulness, but would have earned fourth place in the rankings.

We should note that this prime number program - perhaps by Mike Simmons - is not written for best performance. In the case of BBC Basic, and i suspect many others, the GOTOs will be relatively expensive, as they always search from the start of the program.

At the top of the league table from the article, we see

  • 65 seconds, Digital Equipment PDP-10 running Basic on TOPS-10
  • 143 seconds, Digital Microsystems HEX29 (3MHz bit sliced CPU) running HBASIC+ on HOST
  • 317 seconds, Alpha Micro’s AM-100/T (with WD16 processor at 3MHz) running AlphaBASIC on AMOS
  • 573 seconds, the similar AM-100 at 2MHz
  • 585 seconds, Technico SS-16 with 9900 microprocessor at 3MHz, Super BASIC 3.0 on DOS
  • 680 seconds, Ohio Scientific’s C4-P with a 2MHz 6502, running Level I BASIC on OS65D
  • 955 seconds, Radio Shack TRS-80 Model II with Z80 at 4MHz running Level III BASIC on TRSDOS
  • 960 seconds, Apple II+ with 2MHz 6502 running Applesoft II BASIC on DOS3.2
  • 1020 seconds Rexon RX30 with 8086 at 5MHz running Business BASIC on RECAP
    and so on…

(We notice the TRS-80 is described as “the most widely produced computer in the history of the world”.)

The article does encourage us to improve the performance by any specific coding tricks, so long as we leave the algorithm unchanged… I can’t resist.

I’ll time my efforts using a lower limit of 100 for the results. The original program runs in 9.37s and I got that down with a little crunching to 6.69s and this version runs the full 1000 test in a hair under 340s - still leaving the Beeb in 4th place. But a 1986 BBC Master with Basic 4 runs in just under 256s, which bumps up into 3rd place. The Master Turbo with the 4MHz 65C02 second processor runs in just under 124s which bumps up to 2nd place.

A few more results have been published:

  • In 1981, Convergent Technology’s CT-2100 with 5MHz 8086+8087 posted 752s with Basic, but 9s with a Pascal port.
  • Later in 1981, System Group’s System 2800 with a 4MHz Z80 and Microsoft Basic posted 699s.
  • Also in 1981, a port to FORTRAN running on an 80MHz Cray ran in 33 milliseconds
  • In 1982, Fortune’s 5.5MHz 68000-based machine 32:16 posted a disappointing 1010 seconds.

Hardly surprising, of course, that compilers do better than interpreters here.

via mmruzek on anycpu

7 Likes

Looks like that code will claim that 1 is a prime, no?

1 Like

Sadly, yes, and I don’t find that entirely excellent! (But even Hardy at one point allowed 1 to be prime, although it seems to have gone out of fashion.)

BTW there are a couple of not-entirely-unrelated threads over on Stardot
Short and sweet prime numbers in Basic
Factorising to give prime factors

And at least one over on 6502.org:
A coding challenge: prime numbers
slightly OT: a simple Benchmark

(Edit: citation added for Hardy fact!)

I’ve another data point: Commodore PET 2001 (ROM 2.0, emulation) at a modest 1132 seconds (18 m 52 s).
While this may be rather depressing, it’s just about 120% of the Beeb, taking the 1Mhz clock speed of the PET’s 6502 into account (versus 2MHz on the Beeb).

Have a nice cup of tea (or two) and try it here:wink:

1 Like

In the same vein:

1 Like

About the TRS-80 being the most produced computer by 1980, that would be the Model I. I don’t think we can lump the Model II that was used in that benchmark with the I, though the Model III can certainly be considered a version of the I.

1 Like

(That nice graphic, and many more, can be seen in the 10 part article Total share: 30 years of personal computer market share figures)

My Cambridge Z88 is under 11 minutes.

I did have a thought: those early microcomputer Basics were written for small ROMs and interpreted programs in small RAMs. (ZX80 had 1k RAM and 4k ROM as an extreme example.) So, when machines with 32k, 48k, nearly 64k of RAM came along, with ROMs of 16k or more, one wonders why a little RAM wasn’t used in some tradeoffs for performance: in particular, for this case, speeding up GOTO references. (Other tradeoffs would include precalculating the binary values of constants, even perhaps pre-digesting expressions for evaluation, perhaps speeding up variable lookup.)

Edit: see this comment elsewhere and the thread below it…

On most machines, I suspect the video buffer was placed just below the roms,
and you can’t move that for more rom. As for slower basic runtimes are we
compareing the same floating point formats? A spread sheet would work better
with a bcd floating point, than a faster binary one.
Ben.

Binary constants versus literals would be huge. Having to parse a number each time it’s accessed is very expensive. However, there’s what may be called “literal value fetishism” going on in BASIC. Users expect that when they enter A + 1 it will also list as this and not as A + 0.1E1 (or whatever). You could probably insert a few extra bytes before the constant in the BASIC text (e.g., a binary constant marker including a format mark, 2 or 4 bytes for the binary value, and another byte for the skip offset, so you wouldn’t have to parse the constant again to find its end). Optimizations for GOTO may be also doable, but would require about the same effort as renumbering the entire program on each edit (which may be quite unbearable with longer programs).

Another quite remarkable factor is white space parsing, esp. in MS BASIC. (The performance difference with/without white space is quite remarkable.)
I guess, for a high performance, but still convenient version of BASIC, there’s nothing short of retokenizing the entire program in a close-to-binary shadow version at program start (RUN), in other terms, precompiling, like with Perl, etc. But this should be adverse to the dialog-like philosophy, which is crucial to BASiC. In other words, BASIC is slow, because it allows its users to add or re-edit program text anytime without re-evaluting the entire program. (Hence, there is no consistent structure in memory, lines may be linked lists without consistent sequence, there may be even dead code, etc.)

(P.S.: I really don’t know the internals of Atari BASIC. The description reads interestingly, but, I guess, there must be some trade-offs, as well.)

1 Like

Yes, for me it would be important for LIST always to return the exact typed text. Perhaps I’m thinking along the lines of storing a parsed version of each line - perhaps on the heap - the first time it’s encountered. There’d be room in that parsed version for storing pointers to lines which are mentioned as line numbers - but perhaps those pointers need only be set when that line number is first used as a target. That would avoid searching the program text, I think, other than the first time it needs to be searched for execution.

BASIC 09 for the 6809 under O/S9 was a nice BASIC. You could compile your program
for speed or just run the tokenized version.

This.

When I wrote my own BASIC interpreter I tokenised everything. Numeric constants were the biggest hassle, so they were converted into binary, stored as a token in the code - the token is a token value that says “constant” plus an index into the symbol table - the entry in the symbol table contains the string representation of the number as well as the binary value.

It was cumbersome and made LIST perform precisely.

Also only relevant for people using the traditional line-number entry system - move over to the editor and it’s plain text all the way (but the conversion still applies as the system reads your edited text file to convert to internal format - it’s effectively a sort of one-pass compiler with a de-compiler).

But it was aimed at a modern Linux PC, not a memory constrained 8-bit micro, so I got away with it.

-Gordon

1 Like

Storing a fully tokenized/binary version of a line just-in-time on the heap as we go along has its charms. But we’d need some modern variable management with hashes – and garbage collection may be an issue.
But GOTO/GOSUB is an absolute show-stopper. Consider the following lines:

80 H = H/C : GOSUB 2500 : A=A+1 : B=B*2 : C=(A+B)/2
90 IF C =< 100 THEN GOTO 120 ELSE PRINT A
100 ON X GOTO 200, 220, 250

In line 80, we’d never come to store the entire tokenized line, because we exit on GOSUB, leaving the rest untokenized, process the subroutine, and as we return, we’ve probably exhausted our buffers. Quite the same with any IF-ELSE clauses (if our dialect supports this) as in line 90. We may introduce a restriction that any jumps must be the very last statement in a line (similar to strict tail recursion), but this would put any kind of ON… statements (as in line 100) out of question.

A double-headed BASIC, which supports both an interpreted and a compiled mode, as suggested by @oldben, may be the best way to go.

Edit: Maybe, the GOTO problem could be overcome with linked lists, like with text editors, so that any jump would mark the end of an internal “paragraph” and the code must link to another list entry after this. But, if we use this in a dialog-like fashion, our heap will become a mess pretty soon. (Meaning, there had to be a hash list, linking to line entries, which are a linked list, each. I’m not sure how feasable this would be with a 16-bit address space, with ROM, hardware interfaces, etc, included. This leaves about 32-36 K for BASIC text, heap, and any variable stores and we’d run out of resources with anything larger than 8K of program text pretty soon.)

Been there, not in actual code, but in drafting mode. I couldn’t see, how this would be manageable.
(That is, you could store the literal constant along with the binary representation, but then you would still have white space and style related issues. It just wont be BASIC.)

Now, here’s my own take on this: Have a normal, tokenized BASIC, but with jump vectors for constant parsing and variable lookup routines and a mode marker at the very beginning of the program. Now we may optionally save a program in a compressed (white space excluded) and fully tokenized format. With regard to the mode mark, we’d now use binary constants and indices into a variable store instead of names. We could even list the binary format (with some caveats.) And this should be a rather simple modification, too. Leaving GOTO/GOSUB, which may be sped up by using doubly-linked lists for the lines. (So we may have an educated guess, from which end to tackle our search best.)
Considering all, anything more fancy is probably more costly than it may be worth.

*) Edit: Rather obviously, the other, default mode is interpreted BASIC as usual.

I suppose one question would be: how large is the text of a Basic program, and how much additional memory is needed by the program as it runs?

Obviously, programs can be as large and as hungry as we like - and we know Acorn pursued, in sequence, HIBASIC for a 64k second processor, BAS128 to use 64k of mapped RAM on the Master, and the in-house 256k Turbo machine (which might have had a Basic angle?)

But any program written for a machine with say 16k RAM would have lots of room for a semi-compiled data structure on a machine with say 32k or more RAM - wouldn’t it?

That’s a nice idea - it also allows for a program so large that it can’t be compiled but can still be interpreted.

The whitespace issue is easy - you remove them all once you’ve tokenised the line. Applesoft (and I suspect other MS derived BASICs) does this. (Obviously you preserve spaces in strings and comments. This makes for some odd listings in Applesoft - e.g. if you don’t use LET then that line is one space to the left of the lines above/below if they do use LET or start with another keyword. It’s just one of those things we got used to/ignored back in the 70’s …

When I started mine, I thought I could simply strip spaces then “as if by magic” have variables names with spaces. Not being an expert in parsing, etc. this was going to take more of my time than I wanted it to, so I quietly dropped that idea. I still strip spaces once the line is tokenised, so the LIST function lists the program as I want it listed (complete with keywords capitalised as I want them capitalised, indentation as I want it indented and so on. If others don’t like this, then they can use the screen editor which is just a simple nano-like text editor).

-Gordon

True, you should be fine with double the RAM. I’m a bit worried about the performance of line look-up. Say, we have a hash list with 8-bit hashes and named arrays for lines with hash-collissions, where each entry points to a binary line on the heap. We’d had to go through the process of hashing and probably still comparing a few literals for each single line executed. I’m not sure, if this wouldn’t be performing worse for normal execution, even offsetting any other gains.

(E.g., MS BASIC with line numbers stored as binary 2-byte integers and storing lines as a linked list should be pretty performant even when searching for lines as a jump target, since the comparison is trivial. Much like variable lookup, actually. And advancing to the next line in normal flow is more than trivial, since there is already a binary pointer with the very address in memory.)