line-lookup
BASIC programs normally run by stepping through the program line-by-line. A small number of instructions, generically known as branches, interrupt this flow and direct the program to continue at some other location. The new location, or target, is indicated by a line number. Branches are common instructions, found in GOTO, GOSUB, IF...THEN and the ON statements. All of these branch instructions use a global line-lookup routine to find their target.
To find the target, the routine examines the line number stored at the front of each line of code in memory. If it does not match the target, it follows a pointer to the next line and tries again. This process becomes increasingly expensive as the program size grows. Most versions of Commodore BASIC include a simple optimization to improve performance. Being aware of how this system works allows you to improve the performance of your programs, sometimes by a considerable amount.
In Commodore BASIC (and similar vintage MS versions, including AppleSoft), line numbers are stored in the form of a 16-bit number, encoding a value between 0 to 63999. These are normally presented to the user in their original decimal format, but internally these are binary numbers and normally displayed in hexadecimal format in printed works. In hex format each set of 4-bits is represented by a single "digit", and thus the complete 16-bit address consists of four such digits. You can convert the decimal version of the line number, say "10000", to its hexadecimal format, in this case, "2710", using a hexadecimal calculator.
The optimization is this:
- In BASIC 1.0 (early PET), if the upper 8-bits of the target are greater than the current line's upper 8-bits, searching will take place from the current line. If the target line's upper 8-bits are lower or equal to the current line number, it searches from the start of the program. Taking advantage of this tweak can significantly improve performance by eliminating the search through all of the lines of a program. This is especially noticeable in longer programs.
- In BASIC V2 (C64/VC20), the whole 16 bits line number is compared correctly ($A8A6, explanation of the 16 bits comparison), and searching will take place from the current line if the target line is higher than the current one.
Slowdown bug on early PETs[edit | edit source]
Here is an example of how the slowdown bug works. Consider the following program:
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
This program runs in 2.2 seconds on a 8k SuperPET. Now consider the same program but having removed a single line:
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
This version runs much slower - it will take 45 seconds to run - on the same SuperPET (but it will run with same speed as the previous version with the fixed BASIC V2 of the VC20/C64).
To understand why, consider the GOTO statement in line 7670 and 7660. When you convert numbers on those lines to hex we see:
7670 GOTO 7680 → $1DF6 GOTO $1E00 7660 GOTO 7670 → $1DEC GOTO $1DF6
In the first example, the target line number's upper 8-bit value is $1E, while its own line number is $1D. This triggers the optimization, so it begins looking for the target line starting at the next line and immediately finds the target. In the second case, both the target and the current line numbers have the same upper 8-bits, so in this case, it starts from line 10 and has to search all 768 lines before it finds the target.
To make the best use of this optimization, you should cluster commonly used code, especially GOSUBs, in line numbers just beyond the end of the code that might call it. Check the starting number of each one to ensure that the upper 8-bits of the line number is greater than the line calling it to ensure this will trigger on all machines. Since 8-bits encodes 256 values, and BASIC programs generally number lines by 10s, this means the optimization will generally trigger for every 26th line of code, although one might want to separate them by slightly more than that to ensure it triggers.
Alternatively heavily used (small) subroutines are better placed at the beginning of a program because lower line number are always searched from the beginning (not depending on the position the call has came from) with the additional advantage that the smaller line number saves space an parsing time.
Unfortunately, the code is far from optimal in one particularly common case, when a small loop is constructed in a single line:
500 IF X < 10 THEN X=X+1:GOTO 500
In this case, the target line number is "equal or lower" so it search for line 500 from the start of the program. Properly handling this common case would significantly improve performance of many programs.
A further complication involves routines that contain backward branches, which is especially common in certain types of loops. The backward branch will always cause it to search from the top of the program. In this case, the best option is to place the routine at the top of the program instead, thereby making the backward branch find its target more rapidly. The only drawback to this approach is that you have to GOTO past the routines so that the code isn't run when the start the program with RUN.
