line-lookup

From C64-Wiki
Jump to navigationJump to search

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, 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: if the upper 8-bits, or leftmost two hex digits, of the line number, are greater than the current lines 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.

Here is an example of how the system 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 takes 45 seconds to run. 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.

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.