Efficient BASIC coding for the ZX Spectrum

[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

II. Sobre las variables

III. Sobre las expresiones

IV. Funcionalidad y medida del tiempo

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. Aquí nos centraremos en una característica muy concreta que resulta fundamental para conseguir incrementar su eficiencia en la ejecución de programas BASIC:

No tiene 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, como el tamaño en memoria de cada línea (en bytes, al principio de la misma), los valores numéricos de literales escritos en el texto (justo tras dichos literales), o espacio para recoger los argumentos de las funciones de usuario (justo tras los nombres de los correspondientes parámetros en la sentencia DEF FN).

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, lo que formalmente se escribe O(1)), el lugar de memoria donde comienza dicha línea, para 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 implica, durante su ejecución, buscar a lo largo de todo el programa dicha línea. Desde el punto de vista de la complejidad computacional, esto no es constante, sino lineal (peor): O(n), siendo n el número de líneas de programa efectivas que hay antes de la línea que se busca, o sea, que se tarda más cuanto más lejos esté la línea del comienzo del programa. Para más detalles, el intérprete implementa esa búsqueda con un puntero que empieza apuntando a la primera línea; mientras no sea la 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 de la línea, obteniendo un nuevo puntero que apunta a la siguiente línea, y repite el proceso.

El 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 BASIC que mida 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 se va acumulando porque el salto se repita a menudo (por ejemplo, en un FOR). El programa anterior toma 10000 medidas de tiempo para calcular la media, que es lo que se ve 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 [0,20] milisegundos producidos por la discretización del tiempo en 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 SUB o DEF 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 referenciadas.

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. 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 de la primera línea que queramos que el intérprete use dentro del programa (eso hará que el intérprete ignore la existencia de todas las anteriores). En general no hay modo fácil de saber en qué dirección de memoria está 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). 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 en la línea anterior a la del bucle; desde ese momento, ésta irá tan rápida como si fuera la primera. Eso sí, ¡es importante recuperar el valor original de PROG si queremos volver a ejecutar alguna vez el resto del programa!

El problema de la búsqueda secuencial de líneas 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. (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 que definen funciones no utilizadas en el código.

Las sentencias del lenguaje Sinclair BASIC afectadas por el problema de los números de línea son:

  • GO TO
  • GO SUB
  • FN (requiere buscar la línea del correspondiente DEF 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 al FOR de su variable)
  • RESTORE
  • RUN
  • LIST
  • LLIST

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.

Así, los RETURN deberían hacerse a lugares próximos al comienzo del programa, es decir, los GO SUB correspondientes deberían estar al principio del programa, y, si puede ser, en la primera sentencia de sus respectivas líneas para que no haya que buscarlos.

Los bucles FOR pueden sustituirse por repeticiones consecutivas del cuerpo en caso de que éstas no sean muy numerosas (esto se llama “desenrrollado de bucles”), que 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.

Quiero aprovechar para mencionar en este punto que es recomendable no usar expresiones para las referencias a líneas (es decir, no es bueno escribir “saltos paramétricos” como GO TO 2*n+100, GO SUB x*1000, etc.), sino solamente literales numéricos (GOTO 100, GO SUB 2000). Además de enlentecer el código, el uso de lo primero hace su mantenimiento un verdadero infierno, e impide su análisis automático.

Este 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 (el máximo que el intérprete de la ROM puede ejecutar sin error son 127 sentencias). 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 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 (REM y 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 sentencias DATA, 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

IV. Functionality and time measurement

The Sinclair BASIC interpreter that the ZX Spectrum included in ROM was, in so many aspects, a wonder of software, particularly in assembly programming. A lot of things can be analysed and studied about it; here we focus on a particular feature that is crucial for the efficiency in the execution of 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, the interpreter must search the entire program, line by line, until finding the place in memory where the referred line is. 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. More concretely, 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:

Those parts of the program that require a faster execution should be placed at the beginning (smaller line numbers). The same should be done for parts that contain loops or routines that are frequently called.

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 prevent it to search for a line by scanning all previous lines. 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 in the program (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 in a listing file with the location in memory of every element in the BASIC program). 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 latter will be as fast as though it was the first line in the program. However, do not forget to restore the original value of PROG in order to access previous parts of the 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.

The statements of the Sinclair BASIC language that involve to search lines in the program are:

  • GO TO
  • GO SUB
  • FN (since DEF FN must be searched for)
  • RETURN (it returns to a certain number of line and statement)
  • NEXT (it jumps to the corresponding FOR)
  • RESTORE
  • RUN
  • LIST
  • LLIST

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); do not use expressions (“parametrical jumps”, e.g., GO TO 2*n+100, GO SUB x*1000, etc.), since that involves additional cost of execution, besides making the maintainance and analysis of a program really difficult.

The second consequence of the interpreter lacking an efficient line number table is:

Lines should be long (the maximum length is 127 statements in a line for the ROM interpreter not to issue an error). In that way, the search for a particular one will be more efficient, since traversing the lines has the same cost independently on their lengths (it only depends on the number of lines).

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 FORNEXT, 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:

Non-executable statements (REM and empty statements) that fill entire lines should be eliminated or placed at the end, since they increase the search time for no reason. Also, DATA statements, 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.).

Facebooktwitterredditlinkedintumblrmail