[Click here to read this in English 
]
Éste es el primero de una serie de artículos que explican los fundamentos de la (in)eficiencia de los programas en BASIC puro para el ZX Spectrum:
I. Sobre los números de línea
El intérprete de lenguaje Sinclair BASIC incluido en la ROM del ZX Spectrum es, en muchos aspectos, una maravilla del software, concretamente de la programación en ensamblador, y daría para hablar durante mucho tiempo. En esta serie queremos destacar los puntos más importantes a tener en cuenta para que los programas escritos en ese lenguaje sean lo más eficientes posibles, en primer lugar en tiempo de ejecución, pero también en espacio ocupado en memoria.
En esta primera entrega de la serie trataremos de las líneas de dichos programas; más allá de la necesidad de numerarlas, algo que no se hace desde hace décadas en ningún lenguaje de programación, está el propio hecho de la eficiencia del intérprete a la hora de manejarlas.
Antes de meternos en el meollo, conviene resumir los límites que existen en esta máquina relativos a las líneas de programa:
- Las líneas de programa, una vez éste queda almacenado en la memoria listo para su ejecución, ocupan 2 bytes (por cierto, almacenados en formato big-endian, el único caso de este formato en el ZX). Esto podría llevar a pensar que tenemos disponibles desde la línea 0 a la 65535 (el máximo número que puede almacenarse en 2 bytes), pero no es exactamente así. A la hora de editar manualmente un programa sólo se nos permite numerar las líneas desde 1 a 9999. Si el programa es manipulado fuera del editor (se puede hacer con
POKE), es posible tener la línea 0, y ésta aparecer al listarlo, pero no será editable. De la misma manera (manipulando el programa conPOKE) se pueden numerar líneas por encima de la 9999; sin embargo, esto causará problemas en ejecución: muchas sentencias del lenguaje que admiten un número de línea como parámetro, comoGO TOoRESTORE, dan error si la línea es mayor de 32767; la pila de llamadas dejará de funcionar correctamente si se hace unGO SUBa una línea mayor de 15871 (3DFF en hexadecimal); el intérprete reserva el número de línea 65534 para indicar que está ejecutando código escrito en el buffer de edición (y no en el listado del programa); por último, listar programas por pantalla tampoco funciona bien con líneas mayores de 9999, y en cuanto las editemos manualmente volverán a quedar con sólo 4 dígitos decimales. - La longitud en bytes de cada línea de programa se almacena justo después del número de línea, ocupando 2 bytes (esta vez en little-endian). Esta longitud no incluye ni el número de línea ni la longitud en sí misma. Por tanto, podríamos esperar poder tener líneas de un máximo de 65535 bytes en su contenido principal (menos 1, porque siempre tiene que haber un 0x0D al final para indicar el fin de línea); asimismo, las líneas más cortas ocuparán en memoria 2+2+1+1 = 6 bytes: serían aquéllas que contienen una sola sentencia que no tiene parámetros, p.ej.,
10 CLEAR. Una rutina muy importante en la ROM del Spectrum, la encargada de buscar la siguiente línea o la siguiente variable saltándose la actual (llamadaNEXT-ONEy situada en la dirección 0x19B8) funciona perfectamente con rangos de tamaño de línea entre 0 y 65535, pero en ejecución el intérprete dejará de interpretar una línea en cuanto se encuentre un 0x0D al comienzo de una sentencia (si la línea es más larga, por ejemplo porque se haya extendido mediante manipulaciones externas, ignorará el resto, por lo que puede ser usado ese espacio para almacenar datos dentro del programa). Más importante aún: dará error al tratar de ejecutar más de 127 sentencias en una misma línea, es decir, una línea en ejecución sólo puede tener, en la práctica, desde 1 hasta 127 sentencias.
Una vez resumidos los datos básicos sobre las líneas y los números de línea, nos centraremos en una característica muy concreta del intérprete de BASIC que resulta fundamental para conseguir incrementar su eficiencia en la ejecución de programas:
El intérprete no usa una tabla indexada de líneas de programa 
Los programas BASIC del ZX se pre-procesan nada más teclearlos (tras teclear líneas completas en el caso del ZX Spectrum +2 y superiores), lo que ahorra espacio en ROM al evitar el analizador léxico que haría falta posteriormente. En ese pre-proceso no sólo se resumen palabras clave de varias letras en un sólo byte, es decir, se tokeniza (qué palabro más feo), sino que se aprovecha para insertar en los lugares más convenientes para la ejecución algunos elementos pre-calculados: un ejemplo es el propio tamaño en memoria de cada línea, como se ha explicado antes, pero también se almacenan silenciosamente los valores numéricos de los literales escritos en el texto (justo tras dichos literales), y se reservan huecos para recoger los argumentos de las funciones de usuario (justo tras los nombres de los correspondientes parámetros en la sentencia DEF FN), por ejemplo.
Lo que nunca, nunca se hace es reservar memoria para almacenar una tabla con las direcciones en memoria de cada línea de programa. Es decir, una tabla que permita saber, a partir de un número de línea y con complejidad computacional constante (tardando siempre lo mismo independientemente del número de línea, lo que formalmente se escribe O(1)), el lugar de memoria donde comienza el contenido tokenizado de dicha línea, para poder acceder rápidamente a las sentencias correspondientes y ejecutarlas.
Esto tiene una consecuencia importante para el intérprete: cualquier sentencia del lenguaje que admita como parámetro una línea (GO TO, GO SUB, etc.) implica, durante su ejecución, buscar activamente el comienzo de dicha línea a lo largo de toda la memoria donde reside el programa. Desde el punto de vista de la complejidad computacional, esto no es constante, sino lineal (o sea, peor): O(n), siendo n el número de líneas de programa; en otras palabras: tarda más cuanto más lejos esté la línea que se busca del comienzo del programa. El intérprete implementa esa búsqueda con un puntero (o sea, una dirección de memoria) que empieza apuntando a donde reside la primera línea en memoria; mientras no sea ésta la línea que se busca, o la inmediatamente posterior a la que se busca si se busca una que no existe, suma al puntero el tamaño que ocupa el contenido de la línea en memoria, obteniendo un nuevo puntero que apunta al lugar de memoria donde reside la siguiente línea, y repite el proceso.
Un importante resultado de esta implementación del intérprete es que toda sentencia que implique un salto a una línea de programa (GO TO, GO SUB, NEXT, FN) incrementará su tiempo de cómputo linealmente con el número de líneas que haya antes de la de destino. Esto se puede comprobar con un programa que mide el tiempo para distintas líneas de destino, como el que puede descargarse aquí. Tras ejecutarlo (¡cuidado!: tarda más de 17 horas en terminar debido al nivel de precisión con el que queremos estimar los tiempos) obtenemos los siguientes resultados:
Como se observa, los saltos incrementan su tiempo en 71 microsegundos por cada línea más que haya antes de la de destino; eso supone unos 7 milisegundos cuando hay 100 líneas antes, lo que puede ser mucho si el salto se repite a menudo (por ejemplo, si lo hace un bucle FOR–NEXT). El programa anterior toma 10000 medidas de tiempo para calcular la media mostrada finalmente en la gráfica, por lo que el Teorema del Límite Central indica que los resultados expuestos arriba tienen una incertidumbre pequeña, del orden de 115.5 microsegundos si consideramos como fuente de incertidumbre original más importante los 20 milisegundos producidos como máximo por la discretización del tiempo de la variable del sistema FRAMES (el hecho de tomar tantos datos hace, por el mismo teorema, que la distribución de la estimación sea simétrica y no tenga bias, por lo que la media mostrada en la figura será prácticamente la verdadera, a pesar de dicha incertidumbre). También se observan en la gráfica los 5.6 milisegundos de media que se tarda en ejecutar todo lo que no es el salto en el programa de prueba.
Por tanto, aquí va la primera regla de eficiencia para mejorar el tiempo de cómputo:
Si quieres que cierta parte de tu programa BASIC se ejecute más rápido, y esa parte contiene el destino de bucles (
GO TO,NEXT) o es llamada muy frecuentemente por otras (GO SUBoDEF FN), deberías moverla al principio del programa, o lo más cerca del principio que puedas; de esa manera, el intérprete tardará sensiblemente menos en encontrar las líneas a las que hay que saltar.
Para ayudar en la tarea de identificar estos problemas, el intérprete de BASIC incluido en la herramienta ZX-Basicus puede producir un perfil de la frecuencia de ejecución de cada sentencia de un programa (opción --profile); si la lista ordenada de frecuencias que recopila no va en orden creciente de número de línea, significa que algunas líneas de las más frecuentemente llamadas podrían estar mal situadas.
Existe un truco en BASIC para hacer que el intérprete no tenga que buscar desde el principio del programa para encontrar una línea, sino que empiece la búsqueda en otro lugar (más cercano a lo que busque). Consiste en cambiar el contenido de la variable del sistema PROG, que está en la dirección 23635 y ocupa 2 bytes, por la dirección de memoria donde resida la primera línea que queramos que el intérprete use para sus búsquedas (eso hará que el intérprete ignore la existencia de todas las anteriores, así que ¡éstas dejarán de ser accesibles!). En general no hay modo fácil de saber en qué dirección de memoria reside una línea, pero la variable del sistema NXTLIN (dirección 23637, 2 bytes) guarda en todo momento la dirección de la línea siguiente a la que estamos (la herramienta de análisis de ZX-Basicus también puede ser útil, pues produce un listado con la localización de cada elemento del programa BASIC en memoria si éste se ha guardado en un fichero .tap). Por tanto, para, por ejemplo, hacer que un bucle vaya más rápido, se puede hacer POKE a los dos bytes de PROG con el valor que tengan los de NXTLIN cuando estemos en la línea anterior a la del bucle; desde ese momento, la primera línea del bucle irá tan rápida como si fuera la primera de todo el programa. Eso sí, ¡es importante recuperar el valor original de PROG si queremos volver a ejecutar alguna vez el resto!
El problema de la búsqueda secuencial de líneas que hace la ROM del ZX tiene un efecto particular en el caso de las funciones de usuario (DEF FN): dado que están pensadas para ser llamadas desde diversos puntos del programa, deberían ir al principio del mismo si esas llamadas van a ser frecuentes, pues cada vez que sean llamadas el intérprete tiene que buscarlas. (Una alternativa, preferida por muchos programadores, es no utilizar DEF FN, dado el mayor coste de su ejecución respecto a insertar la expresión directamente donde se necesite.) El perfil de frecuencias de uso producido por el intérprete de ZX-Basicus también informa sobre el número de veces que se ha llamado a cada función de usuario con FN, y la utilidad de transformación tiene una opción (--delunusedfn) que borra automáticamente todas las sentencias DEF FN no utilizadas en el código.
Es importante hacer notar aquí que el intérprete de BASIC no sólo tiene un comportamiento lineal (O(n)) a la hora de buscar líneas de programa, sino también al buscar sentencias. Es decir: si el programa pretende saltar a una sentencia distinta de la primera de una línea, el intérprete tendrá que buscar dicha sentencia recorriendo todas las anteriores. En Sinclair BASIC existen instrucciones de salto a sentencias distintas de la primera de una línea: NEXT y RETURN, que por tanto sufren del problema de las búsquedas lineales. Es conveniente situar el retorno de la llamada o el principio del bucle al principio de la línea, para que el intérprete no tenga que buscar la sentencia concreta dentro de la misma, yendo sentencia a sentencia hasta encontrarla.
No existen instrucciones para saltar a sentencias (distintas de la primera) explícitamente dadas por el usuario, pero esto se puede lograr engañando al intérprete con un truco, que podríamos llamar el “GOTO con POKE”, cuya existencia me ha señalado Rafael Velasco al verlo usado en algún programa escrito en una sola línea de BASIC. Este truco se basa en dos variables del sistema: NEWPPC (dirección 23618 de memoria, 2 bytes) y NSPPC (dirección 23620, 1 byte). En caso de que una sentencia del programa haga un salto (GO TO, GO SUB, RETURN, NEXT …), se rellenan con la línea (en NEWPPC) y la sentencia (en NSPPC) a donde hay que saltar, mientras que si no hace un salto, sólo se rellena NSPPC con 255. Antes de ejecutar la siguiente sentencia, el intérprete consulta NSPPC, y, si su bit nº 7 no es 1, salta a donde indiquen estas dos variables, mientras que si es 1, sigue ejecutando la siguiente sentencia del programa. El truco del “GOTO con POKE” consiste en manipular estas variables con POKE, primero en NEWPPC y luego en NSPPC, de forma que, justo tras ejecutar el POKE de NSPPC, el intérprete se cree que tiene que hacer un salto a donde indican. De esta manera podemos ir a cualquier punto del programa, línea y sentencia incluidas.
Recuperando el hilo principal de esta entrada, las sentencias del lenguaje Sinclair BASIC afectadas por el problema de los números de línea / número de sentencia son:
GO TOGO SUBFN(requiere buscar la línea del correspondienteDEF FN)RETURN(debe retornar a un número de línea almacenado en la pila de direcciones de retorno)NEXT(debe ir a la línea correspondiente alFORde su variable)RESTORERUNLISTLLIST
Como las cuatro últimas no suelen usarse más que esporádicamente (las tres últimas prácticamente nunca dentro de un programa), la identificación de las zonas de código que deben moverse al principio debería enfocarse en bucles, rutinas y funciones de usuario (FN).
Así, los RETURN deberían hacerse hacia lugares próximos al comienzo del programa, es decir, los GO SUB correspondientes deberían estar allí (al principio del programa), y, si puede ser, en la primera sentencia de sus respectivas líneas para que no haya que buscar dentro de la línea la sentencia en cuestión, búsqueda que también se hace linealmente.
Los bucles FOR pueden sustituirse por réplicas consecutivas del cuerpo en caso de que éstas no sean muy numerosas (esto se llama “desenrrollado de bucles”), lo cual queda muy feo y ocupa más memoria de programa pero evita el coste adicional de ejecución del salto NEXT (y el de creación de variable en el FOR).
En pocas palabras: el código que llama mucho a otro código, es llamado mucho por otro código, o tiene muchos bucles internos debería ir al principio de un programa BASIC y en las primeras sentencias de dichas líneas.
Quiero aprovechar para mencionar en este punto que, aunque es de lo más común, en muchos casos sería recomendable no usar expresiones para las referencias a líneas, al menos en las primeras etapas de la escritura de un programa (es decir, no escribir “saltos paramétricos” como GO TO 2*n+100, GO SUB x*1000, etc., sino solamente con literales numéricos, como GOTO 100, GO SUB 2000). El uso de los saltos paramétricos hace el mantenimiento del programa un verdadero infierno, e impide su análisis automático. De todas formas, hay que admitir que usar expresiones como argumento de GO TO / GO SUB puede ser más rápido que escribir sentencias IF para lograr el mismo objetivo.
Todo el asunto de los números de línea tiene una segunda consecuencia:
Para acelerar lo más posible todo el programa deberías escribir líneas lo más largas posible. Así, la búsqueda de una línea particular será más rápida, ya que habrá que recorrer menos líneas hasta llegar a ella (ir de una línea a la siguiente durante la búsqueda que hace el intérprete de la ROM cuesta el mismo tiempo independientemente de su longitud).
ZX-Basicus tiene una transformación disponible con la opción --mergelines que hace esto automáticamente: aumenta el tamaño de las líneas siempre que esto respete el flujo del programa original.
Nótese que el usar menos líneas pero más largas ahorra también espacio en memoria, ya que no hay que almacenar números, longitudes ni marcas de fin de esas líneas. Por contra, con líneas largas es más costoso encontrar una sentencia a la que haya que retornar con un RETURN o volver con un NEXT, así como buscar una función de usuario (DEF FN) que no esté al principio de su línea, por lo que hay que tener también eso en cuenta y llegar a una solución de compromiso.
Aún hay una tercera consecuencia de esta limitación del intérprete de BASIC de la ROM:
Las sentencias no ejecutables (
REMy sentencias vacías) que ocupan una sola línea deberían eliminarse siempre que se pueda, pues incrementan el tiempo de búsqueda, o bien ponerlas al final del todo. Asimismo, las sentenciasDATA, que normalmente no se usan más de una vez durante la ejecución del programa, deberían estar al final del programa.
ZX-Basicus también ayuda en esto: permite eliminar automáticamente comentarios REM (opción --delrem) y sentencias vacías (opción --delempty). La primera opción permite preservar algunos comentarios sin ser eliminados: los que comiencen por algún carácter que nosotros decidamos, pues siempre es interesante no dejar el código totalmente indocumentado.
En cualquier caso, quizás la opción más importante del optimizador de código de que dispone ZX-Basicus es --move, que da la posibilidad de mover trozos de código de un lugar a otro con menos esfuerzo que a mano. Con ella se puede cambiar de sitio una sección completa del programa; la utilidad se encarga de renumerar el resultado automáticamente. Hay que tener en cuenta, sin embargo, que esta utilidad (como cualquier otra existente) no puede renumerar ni trabajar con números de línea calculados mediante expresiones, por lo que todas las referencias a líneas de programa deberían estar escritas como literales, tal y como se ha recomendado antes.
.oOo.
[Click here to read this in Spanish 
]
This is the first in a series of posts that explain the foundations of the (in)efficiency of pure BASIC programs written for the ZX Spectrum:
I. On line numbers
II. On variables
III. On expressions
The Sinclair BASIC interpreter that the ZX Spectrum included in ROM was, in so many aspects, a wonder of software, particularly in assembly programming.
In this series of posts we will visit the main issues that allow our BASIC programs to execute efficiently, mainly considering time, but also memory consumption.
In this first post we are concerned in particular with the lines in a program; beyond the need for numbering them explicitly, something that does not exist in any programming language since decades, we are interested in the efficciency of the BASIC interpreter when managing lines and their numbers.
Before going to the point, we summarize here some limits that the ZX Spectrum has related to program lines:
- Program line numbers, once the program is stored in memory and ready to be executed, take 2 bytes (by the way, they are stored in big-endian format, the only case of that in the ZX). This could lead to line numbers in the range 0 to 65535 (maximum value that can be stored into 2 bytes), but unfortunately that cannot be done easily. When editing a program manually, only lines from 1 to 9999 are allowed. If the program is manipulated outside the editor (which can be done with
POKE), it is possible to have a line numbered as 0, and that line will appear in the listing of the program, but it will no longer be editable. In the same way (usingPOKE) you can have lines above 9999, but this causes trouble: many statements that admit a line number as a parameter, such asGOTOorRESTORE, produce an error if that line is greater than 32767; the call stack stop working correctly if we do aGO SUBto a line greater than 15871 (3DFF in hexadecimal); the interpreter reserves the line number 65534 to indicate that it is executing code from the edition buffer (and not from the program listing); also, listing the program on the screen does not work well with lines greater than 9999, and right at the moment we edit these lines manually, they will be set to line numbers with just 4 digits. - The length of each program line (in bytes) is stored after the line number, and occupies 2 bytes (this time in little-endian). This length does not take into account the 2 bytes of the line number or the 2 bytes of itself. We could think that each line can have up to 65535 bytes (a 0x0D byte has to always be at the end to mark the end of the line), and that the shortest line takes 2+2+1+1 = 6 bytes of memory if it contains just one statement without parameters, e.g.,
10 CLEAR. A very important ROM routine, the one in charge of finding the line or variable that is after the current one, skipping the latter (calledNEXT-ONEand located at 0x19B8) works perfectly well with line lengths in the range 0 to 65535. However, during execution, the interpreter stops its work on a line as soon as it finds 0x0D in the beginning of a statement (if the line is longer because it has been externally manipulated, it will ignore the rest, thus the remaining space can be used for storing -hidden- data within the program), and more importantly: the interpreter yields an error if trying to execute more than 127 statements in a given line. Consequently, a line in execution can only have from 1 to 127 statements.
Once we have summarized these data, we will focus on a very specific feature of the BASIC interpreter of the ZX Spectrum, one that is crucial for the efficiency of running BASIC programs:
There is no table of program addresses indexed with line numbers
BASIC programs were pre-processed right after typing them (after typing whole lines in the case of ZX Spectrum +2 and up), which saved space in ROM by not implementing a lexical analyzer. In that pre-processing, multi-character keywords were summarized into one-byte tokens, but many other things happened too: number literals were coded in binary form and hidden near the source numbers, line lengths were stored at the beginning of each line, placeholders were prepared for the parameters of user functions (DEF FN) in order to store arguments when they are called, etc.
Unfortunately, there is one thing that was not done before executing the program: to build a table that, for each line number, provides in constant time (computational complexity O(1)) the memory address where that line is stored.
This has an important effect in the interpreter execution: every time it finds a statement in the program that has a line number as a parameter, (e.g., GOTO, GOSUB, etc.), the interpreter must search the entire program memory, line by line, until finding the place in memory where the referred line resides. This has a computational complexity of O(n), being n the number of lines in the program, i.e., it is linearly more costly to find the last lines in the program than the earlier ones. The interpreter works like this: it starts with a memory address that points to the beginning of the program, reads the line number that is there, if it is the one searched for, or the one immediatly after it, ends, otherwise reads the line length, add that length to the pointer, and repeats the process.
The result of this interpreter inner workings is that any statement that involves a jump to a line in the program (GOTO, GOSUB, NEXT, FN) will increase its execution time linearly with the number of lines that exist before the one of destination. That can be checked out with a BASIC program that measures that time for different destinations, such as the one you can download here. After executing it (care!: it takes more than 17 hours to achieve the precision we require in the estimations) we got this:
As you can see, the execution time in a jump increases in 71 microseconds per line of the program that we add before the destination line; that amounts to about 7 milliseconds if you have 100 lines before the destination, which can be a lot if the jump is part of a loop that repeats a lot of times. Our testing program takes 10000 measurements to get the final average time, thus the Central Limit Theorem suggests that the results in the figure above have a small amount of uncertainty, of around 115.5 microseconds if we consider as the main source of original uncertainty the [0,20] milliseconds produced by the time discretization of the FRAMES system variable (this uncertainty does not affect the fact that, due to the same theorem and the large number of measurements, the average estimates will be distributed symmetrically and unbiasedly, i.e., they are practically equal to the real ones). You can also observe in the graph above that the parts of the loops in the testing program that are not the jump itself consume 5.6 milliseconds on average.
The first consequence of this is the first rule for writing efficient programs in pure Sinclair BASIC for the ZX Spectrum:
ZX-Basicus has an optimizing tool that can help in this aspect. For instance, it can execute a BASIC program in the PC and collect a profile with the frequency of execution of each statement (using the --profile option). In this way, you can identify those parts of the code that would require to be re-located earlier in the listing.
There is a BASIC trick to cheat the interpreter and make it to search for a line starting in a place different from the start of the program. It consists in changing the value of the system variable PROG, which is located at the memory address 23635 and occupies 2 bytes, to the memory address of the first line we wish the interpreter to use for its line search (therefore ignoring all the previous ones). In general, it is not easy to get the memory address of a line, but you can consult the system variable NXTLIN (at 23637, 2 bytes), which stores the address of the next line to be executed (the analysis tool of ZX-Basicus also provides this kind of information with the location in memory of every element in the BASIC program if it is stored in a .tap file). You can make, for example, a loop faster: do POKE in the two bytes of PROG with the value stored in NXTLIN, and do that right at the line previous to the one of the loop; the result is that the loop will be as fast as though it was in first line of the program. However, do not forget to restore the original value of PROG in order to access previous parts of that program!
User functions definitions (DEF FN) are specially sensitive to the problem of searching line numbers. They are devised for being called repeteadly, therefore, they should also be at the beginning of the program. However, many programmers choose not to use them because of their high execution cost (which includes finding the line where they are defined, evaluating arguments, placing their values in the placeholders, and evaluating the expression of their bodies). The profile produced by ZX-Basicus also reports the number of calls to user functions (FN), and it provides an option (--delunusedfn) that automatically delete all DEF FN that are not called in the program.
It is important to note that the BASIC interpreter has a linear (O(n)) behaviour not only when searching for lines, but also when searching for statements within a line. If the program tries to jump to a statement different from the first one in a line, the interpreter will search for that statement by skipping all the previous ones. In Sinclair BASIC we have instructions that may jump to statements different from the first ones in their lines: NEXT and RETURN, that, consequently, suffer from the problem of the linear searches. It is better to place the return of the call or the start of the loop at the beginning of a line to prevent the interpreter to conduct a linear search (statement by statement) to find them.
There are no instructions in the language to jump to statements that are explicitly given by the user, but that can be achieved by cheating the interpreter with a trick, that we could call “GOTO-with-POKE”, whose has been brought to my attention by Rafael Velasco, that saw it in a BASIC program entirely written in a single line. It is based on two system variables: NEWPPC (address 23618, 2 bytes) and NSPPC (address 23620, 1 byte). When a program statement makes a jump (GO TO, GO SUB, RETURN, NEXT …), the target line is stored into NEWPPC and the target statement into NSPPC; if the statement does not make a jump, NSPPC is filled with 255; before executing the next statement, the interpret reads NSPPC and, if the bit 7 of this variables is not 1, jumps to the place defined by NEWPPC:NSPPC, but if that bit is 1 it just goes on with the next statement. The “GOTO-with-POKE” trick consists in POKEing those variables, firstly NEWPPC, then NSPPC; right after the last POKE, the interpreter believes there is a jump to do. In this way, we can go to any line and statement in our program.
Recovering the main thread of this post, the statements of the Sinclair BASIC language that involve to search lines in the program are:
GO TOGO SUBFN(sinceDEF FNmust be searched for)RETURN(it returns to a certain number of line and statement)NEXT(it jumps to the correspondingFOR)RESTORERUNLISTLLIST
Since the last four are used sporadically (the last three are very rare inside a program), the identification of parts of the program to be placed at the beginning for gaining in efficiency should focus on loops, routines and user functions. RETURN statements should be used to return to places close to the beginning too, if they are frequently used, i.e., the corresponding GO SUB should be placed at the beginning, and, if possible, at the beginning of their lines in order to reduce the cost of searching them within those lines. Also, in cases where they can not be re-placed, FOR loops can be unrolled (repeating their bodies as many times as iterations they have) to avoid the jumps and the maintainance of the iteration variable. In summary: the code that calls a lot of routines, or is called frequently, or has many internal loops, should be placed at the beginning of the program.
I also recommend to only use literal numbers in the parameters of the statements that need a line (e.g., GOTO 100, GO SUB 2000), at least in the first stages of the writing of a program; do not use expressions at that time (“parametrical jumps”, e.g., GO TO 2*n+100, GO SUB x*1000, etc.), since that makes the maintainance and analysis of the program really difficult. I have to admit, though, that using expressions as arguments in GO TO / GO SUB usually runs faster than writing IF statements to achieve the same functionality.
The second consequence of the interpreter lacking an efficient line number table is:
In this aspect, ZX-Basicus has an option (--mergelines) that automatically merges contiguous lines, as long as that does not changes the program execution flow, in order to obtain the least number of lines.
Notice that having less but longer lines also saves memory space, since there are less line numbers and lengths (and end-line markers) to store. However, having longer lines makes less efficient the search for some statement within them (as in the case of FOR…NEXT, or GO SUB, or DEF FN). A suitable trade-off must be reached.
Finally, the third consequence of not having a line number table is:
REMand empty statements) that fill entire lines should be eliminated or placed at the end, since they increase the search time for no reason. Also,DATAstatements, that are commonly used only once during the program execution, are excellent candidates to be placed at the end of the program.
In this, ZX-Basicus has also some help for the programmer: it can delete automatically empty statements (--delempty) and REM (--delrem); it can preserve some of the latter for keeping minimum documentation, though.
All in all, there is a fundamental tool in ZX-Basicus that is related to this post: option --move re-locates portions of code, renumbering automatically all the line references (it can also serve to renumber the whole program, but that has no relation to speed-ups). Only take into account that it cannot work with line references that are not literal numbers (expressions, variables, etc.).
Pingback: Efficient BASIC coding for the ZX Spectrum (II) – Lithographica
Pingback: Efficient BASIC coding for the ZX Spectrum (III) – Lithographica
Pingback: Efficient BASIC coding for the ZX Spectrum (IV) – Lithographica
Pingback: Efficient BASIC coding for the ZX Spectrum (V) – Lithographica