Efficient BASIC coding for the ZX Spectrum

[Click here to continue 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, 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.

Por tanto, aquí va la primera regla de eficiencia para mejorar el tiempo de cómputo, quizás una de las más efectivas:

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.

Un caso particular de este problema son las funciones de usuario (DEF FN): dado que están pensadas para ser llamadas en 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 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 (en GO TO, GO SUB, etc.), sino solamente literales numéricos. Además de enlentecer el código, el uso de expresiones en esos lugares 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, 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 apropiadamente. 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.

.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 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.

Notice that user functions (DEF FN) 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; do not use expressions (“parameterical jumps”), 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