Commodore BASIC: why was the PET's GOTO so slow?

Question

Received wisdom has it that Commodore didn't want to pay Microsoft extra for updated BASIC interpreters, and thus very little changed in Commodore BASIC v2 from the PETs to the C64. But consider the following program:

5 PRINT
10 PRINT "FOR:"
20 T=TIME
30 FOR I=1 TO 7138
40 NEXT I
50 DT=(TIME-T)/60
60 PRINT I;"LOOPS IN";DT;"S:";INT(I/DT);"/S"
70 PRINT "GOTO:"
80 T=TIME
90 FOR I=1 TO 4588
100 GOTO 110
110 NEXT I
120 DT=(TIME-T)/60
130 PRINT I;"LOOPS IN";DT;"S:";INT(I/DT);"/S"
135 PRINT

Run on an NTSC C64, it outputs:

FOR:
 7139 LOOPS IN 10 S: 713 /S
GOTO:
 4589 LOOPS IN 10 S: 458 /S

But on a PET (almost any model), the results are:

FOR:
 7139 LOOPS IN 9.93333334 S: 718 /S
GOTO:
 4589 LOOPS IN 13.3166667 S: 344 /S

So while the FOR loops run about the same speed on both machines, the PET's GOTO is roughly ⅓ slower than the C64's.

So my question: what changed in the code to improve this performance? (And perhaps a secondary question: was this improvement made by Microsoft and reflected in other MS 6502 interpreters?)

---

Further to WimC's comment I renumbered the test as suggested to ensure that the high byte of the GOTO target was higher than that of the current line:

5 PRINT
10 PRINT "FOR:"
20 T=TIME
30 FOR I=1 TO 7138
40 NEXT I
50 DT=(TIME-T)/60
60 PRINT I;"LOOPS IN";DT;"S:";INT(I/DT);"/S"
70 PRINT "GOTO:"
80 T=TIME
90 FOR I=1 TO 4588
100 GOTO 310
310 NEXT I
320 DT=(TIME-T)/60
330 PRINT I;"LOOPS IN";DT;"S:";INT(I/DT);"/S"
335 PRINT

The C64 results stay the same, but on an emulated PET the GOTO rate is faster:

FOR:
 7139 LOOPS IN 9.93333334 S: 718 /S
GOTO:
 4589 LOOPS IN 9.95 S: 461 /S

Answer 1

PET basic v2 only starts scanning from the current line if the high byte of the goto line number is greater than the high byte of the current line number. Otherwise it starts at the beginning of the program. What happens if you renumber lines 110 up so that they start from 310 (and the goto on line 100 of course)?

Answer 2

Further to WimC's explanation, here's perhaps the worst-case example that's possible on an 8K PET 2001.

This code runs in 2.2 seconds:

10 REM AA
  ... 762 MORE LINES LIKE THIS ...
7640 REM AA
7650 T=TI
7660 FOR I=1 TO 1000
7670 GOTO 7680
7680 NEXT I
7690 PRINT(TI-T)/60

while this code, with one line fewer, takes over 45 seconds:

10 REM AA
  ... 761 MORE LINES LIKE THIS ...
7630 REM AA
7640 T=TI
7650 FOR I=1 TO 1000
7660 GOTO 7670
7670 NEXT I
7680 PRINT(TI-T)/60

The issue is clearer if the line numbers are shown in hex:

7670 GOTO 7680  →  $1DF6 GOTO $1E00 : fast, as $1E > $1D
7660 GOTO 7670  →  $1DEC GOTO $1DF6 : slow, as $1D = $1D

The fast code only has to search for the next line, while the slow code (due to the bug) has to search through > 750 lines from the start of the program to find the target line.

Answer 3

If memory serves, the BASIC in the C64 and VIC-20 checks whether a GOTO line number is greater than or equal to the present line number and will scan from the start of the current line if so, and otherwise start from the beginning of the program. I wouldn't be surprised if the PET BASIC is always starting from the start of the program. It looks like the code is taking about 720 extra cycles per goto, to scan 11 lines, so about 65 cycles/line. It's too bad 6502 versions of MS-BASIC didn't store the length of each line at the start, rather than an address link, since that would have saved a byte per line, reduced scanning time (to about 26 cycles/line), and eliminated the need to fix up line links when code gets relocated.

Answer 4

It is more likely counting from the beginning. In 8bit basic, the line lengths are stored, and to find the beginning of a line, it must, look at each line.

I had the same with the Tandy 100.