Faster Programming Using Indirection Operators

By C. Francis

Originally published in EUG #53

If you have tried writing anything but the most simple Basic game, the chances are that you will have tried using arrays. This causes two problems: arrays use up a lot of memory, and they are relatively slow. Fortunately, both problems can be solved without resorting to machine code by the use of the so-called indirection operators provided by BBC Basic. The full description of indirection operators lies in the part of the manual that most of us don't read (pages 129, 130 and the section on assembly language programming), but in fact they are remarkably easy to use.

An indirection operator allows a Basic program to use any memory location directly; on many micros the actions involved are known as 'peeks' and 'pokes'. The simplest way to use indirection operators applies to integer arrays when it is known that all the numbers to be stored are positive integers less than 256. For example, two arrays could be used to store the X and Y co-ordinates of user defined characters within a game, with one for the X values, and the other for the Y values. In this case, the two arrays can be replaced directly. Consider the following short program, which loops round setting an array to a specific value:

      10 DIM A%(999)
      20 TIME=0
      30 FOR I%=0 TO 999:A%(I%)=1:NEXT
      40 PRINT TIME
In Mode 6, this took 1.38 seconds on my Electron. Now replace A%(999) by A% 999 and A%?I% (? is pronounced as 'query'). With this replacement, the loop takes 1.02 seconds: a saving of 25%. This can be a very major saving in a game in which you may access a number of arrays hundreds of times whenever the main loop of the program is executed.

DIM A% 999 assigns 1000 bytes of memory from A% to A%+999. To find out where in memory this might be, type PRINT A% after the above program has been run. A%?I% gives the contents of memory location A%+I%, but this could also be accessed with ?(A%+I%). This gives a clue to an even greater saving. Replace line 30 above with:

      30 FOR I%=A% TO A%+999:?I%=1:NEXT

This accomplishes exactly the same thing, but the program now runs in 0.92 seconds, a total saving of around 33%.

This is all very well, but what if you want to use an array which takes values requiring more than one byte of memory (i.e. integers greater than 255)? The savings in time are no less dramatic using the ! (pronounced 'pling') indirection operator. The Electron stores integers in four consecutive bytes, and !I% gives the integer stored in locations I%, I%+1, I%+2 and I%+3. For an integer array with 1000 members, 4000 (1000*4) memory locations must be reserved, and the step size should be 4. Replace lines 10 and 30 with:

      10 DIM A% 3999
      30 FOR I%=A% TO A%+3999 STEP4:!I%=1:NEXT

This is barely slower, taking 0.94 seconds. In addition, any integer value can be placed in the location I% by using !I%=value.

String arrays can be replaced using the $ (pronounced 'string') indirection operator, and the savings are even greater. Try using:

      10 DIM A$(999)
      30 FOR I%=0 TO 999:A$(I%)="TEST":NEXT

This took 1.48 seconds on my Electron. When using indirection operators the string "TEST" requires five memory locations, one for each letter, and one for a RETURN to indicate the end of the string. To see how the $ indirection operator works, try altering lines 10 and 30 to:

      10 DIM A% 9999
      30 FOR I%=A% TO A%+4999 STEP 5:$I%="TEST":NEXT

This saves over half a second, taking 0.96 seconds. Virtually no time is lost by setting aside more memory, and using a larger step size, for example DIM A% 9999 and STEP 10. The maximum length of a string which can be stored like this is one less than the step size used. Due to the way in which string arrays are allocated memory on the Electron, the savings in memory are quite significant.

Incidentally, when indirection operators are used like this some of the Basic string operators can be simulated very easily. In the above examples, PRINT ?A% gives the ASCII code for T, which PRINT $(A%+1) gives EST, simulating the operation of the RIGHT$ function. The Electron simply reads the string from wherever it is told to start, and stops when it reaches a RETURN (ASCII value 13). LEFT$ can also be simulated by placing a RETURN in a particular memory location. For example $(A%+2)="" which puts a RETURN character at A%+2, followed by PRINT $A% will give TE. Strings can be combined by placing the first letter of one string in the location occupied by the RETURN for another string. For example, type S(A%+2)="STING". PRINT $A% now gives TESTING.

Finally, it is worth examining the savings which can be made on using two (or more) dimensional arrays. These are even slower than one dimensional arrays. For example, type in the lines listed here:

      10 DIM A%(9,99)
      30 FOR K%=0 TO 9:FOR J%=0 TO 99:A%(K%,J%)=1:NEXT

When run, the program now takes 2.27 seconds. Indirection operators do not allow the use of more than one dimension, so the two dimensional array above must be replaced by the one dimensional set of memory locations DIM A% 999. Then K% and J% have to be replaced by I% running from A% to A%+999. This brings the time down to 0.92 seconds, but you do have to be careful with the arithmetic. In this example, the actual location of the element A%(K%,j%) is found as follows:


So you must remember that increasing I% by one corresponds to increasing J% by one, unless the value of J% is 99, when it corresponds to increasing K% by 1 and resetting J% to 0. Increasing I% by 100 corresponds to increasing K% by 1 and leaving J% alone. The situation is essentially similar in the case of the ! and $ indirection operators, but then you also have to be careful about the sizes. By the way, don't succumb to the temptation of letting the micro do the arithmetic for you by using an equation such as the one above inside the FOR-NEXT loop - you will very likely lose all the time saved!

C. Francis, EUG #53
'Stolen' from ELBUG Vol 1 No 10