Efficient BASIC coding for the ZX Spectrum (III)

[Click here to read this in English ]

Éste es el tercero 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

Empezaremos esta entrada señalando un hecho bien conocido en la ciencia de la computación:

Las expresiones forman todo un sub-lenguaje dentro de cualquier lenguaje imperativo

Esto significa que evaluar una expresión, por ejemplo 2*cos(x) - 23 o "hola, " + "mundos"(1 TO 5), necesita un trabajo importante de análisis sintáctico además de la propia evaluación, trabajo que, en el caso del ZX Spectrum, realiza el intérprete de la ROM con ayuda del calculador. Por tanto, en máquinas con escasa capacidad de cómputo es necesario tener una especial atención con las expresiones.

Intuitivamente, esto implica que:

Deberíamos utilizar expresiones cortas (en el sentido de pocas operaciones), y simples (en el sentido de operaciones no demasiado complejas ni que involucren demasiados pasos de interpretación / cálculo).

La utilidad de análisis de ZX-Basicus (-a) puede ayudar en este aspecto, pues produce una lista ordenada por complejidad decreciente de todas las expresiones del programa: número de elementos involucrados en la expresión, tanto operaciones como datos, sin considerar sus longitudes textuales ni en memoria. Esto sirve para identificar rápidamente las expresiones más complejas (que deberían ser pocas). Asimismo, el intérprete incluido en ZX-Basicus (-r) puede generar información del perfil de frecuencias de ejecución (--profile) de las expresiones del programa, ordenadas de más frecuentes a menos, lo que completa la información necesaria para saber si hay expresiones complicadas que son evaluadas frecuentemente y que, por tanto, deberían tener formas más simples.

Al hilo de las expresiones merece la pena mencionar un truco muy utilizado para reducir el tamaño en memoria de algunas de ellas: consiste en utilizar la función VAL y una cadena de texto para reemplazar un literal numérico. Por ejemplo, escribir VAL "32768" en lugar del literal 32768. El literal ocupa en memoria tantos bytes como dígitos tiene el número más 6 por culpa de un valor oculto que crea el intérprete cuando hace el análisis léxico; mientras que si usamos VAL ocupamos los mismos bytes debidos a los dígitos y sólo 3 más (1 byte de VAL más las dos comillas).

La herramienta de optimización de ZX-Basicus (-t) incluye una opción para hacer automáticamente este truco en un programa fuente (--valtrick). Sin embargo, hay que tener tres cosas en cuenta a la hora de usarlo, y nunca hacerlo sin reflexionar sobre cada caso:

  • Esta técnica ahorra memoria siempre… que no haya otra forma de obtener el número sin usar su literal. Por ejemplo, PI es mucho más eficiente en memoria que 3.1416 o que VAL "3.1416", ya que ocupa 1 byte (PI se tokeniza), por lo que no sólo es lo más corto sino lo más preciso; es más, se puede usar NOT PI en cualquier expresión como equivalente a cero, o SGN PI como equivalente a 1, y sólo ocuparán 2 bytes (los dos tokens) en lugar de los 7 que ocuparía el literal. También podemos ahorrar memoria usando notación científica: se puede escribir 4E3 en vez de 4000, ahorrando 1 byte (VAL "4E3" en lugar de VAL "4000" ahorra también 1 byte, por lo que no merece la pena por su tiempo extra de cómputo).
  • Hay que considerar que esta técnica incrementa el tiempo de ejecución. No es lo mismo tener que evaluar una expresión, y mucho menos un VAL o un VAL$, para los que el intérprete debe crear un contexto nuevo de evaluación de expresión dentro del original, que leer el valor literal y usarlo directamente. Éste es el principal inconveniente.
  • Muchos programas en BASIC puro del ZX suelen tener memoria suficiente para almacenarse, debido a su relativamente escasa complejidad (otra cosa son los programas en ensamblador, que necesitan cantidades grandes de datos para gráficos y demás), por lo que hay que pensar si realmente es necesario ahorrar tan poco espacio. Por ejemplo, si no se modifican los canales del sistema y si no se ha hecho CLEAR y se ha dejado el tope usable de RAM en 65367 para almacenar tras él los 21 UDGs, la memoria para el BASIC estará como sigue: el programa comenzará en la dirección 23755 y el último byte de las zonas más altas de trabajo estará en 41926 al comenzar a ejecutarlo. Esto nos da 41926 – 23755 = 18171 bytes, que, si sólo ocupáramos con el programa (no es cierto), nos permitiría almacenar del orden de 2019 líneas vacías, sólo con el número de línea y la información de su tamaño y marca de fin: esto ocupa 9 bytes por línea si los números de línea tienen cuatro dígitos. Normalmente, los programas BASIC que se escriben tienen mucho menos de 2000 líneas, y habitualmente no son muy largas (aunque hay que tener en cuenta lo que decíamos en la primera entrega de esta serie sobre eso).

Para tener una idea más precisa de cuánto supone usar el truco del VAL en un programa, se puede ejecutar el siguiente, que mide el tiempo de uso repetido del mismo:

10  POKE 23672 , 0 : POKE 23673 , 0 : POKE 23674 , 0 : FOR f = 1 TO 10000 : LET c = VAL “65535” : NEXT f : LET T = PEEK 23672 + 256 * PEEK 23673 + 65536 * PEEK 23674 : PRINT “VAL: “ ; T ; ” “ ; T * 0.02 ; ” “ ; ( T * 0.02 / 10000 )

Si se ejecuta este programa (unos 2 minutos), se vuelve luego a ejecutar tras cambiarle solamente el VAL "65535" por 65535, y se hace la diferencia entre los tiempos medios por iteración del bucle en ambos casos, se puede ver que el uso de VAL es 15 milisegundos más lento, de media, que el literal numérico simple, lo cual es muchísimo tiempo cuando se ejecuta con frecuencia la expresión (la precisión de este cálculo de tiempos es de +/-115.5 microsegundos con el 95% de probabilidad).

En fin, volviendo a la eficiencia de las expresiones, como señalaba antes deberían usarse lo más cortas y simples posibles (y probablemente sin atajos como el VAL), especialmente dentro de los bucles que más frecuentemente se repitan y que tengan necesidades de rapidez. Esto excluye casi del todo las llamadas a funciones de usuario: FN no es conveniente, ya que no sólo implica el análisis sintáctico de la expresión y su evaluación, sino la búsqueda previa de la línea que contiene al correspondiente DEF FN y la copia de los argumentos en ese sitio, algo que ya señalábamos como fuente de ineficiencia en la primera entrega.

Asimismo, si una expresión se repite en varios lugares cercanos, es conveniente usar una variable para almacenar su valor y así calcularla sólo una vez: siempre es más rápido evaluar una sola variable que la expresión completa. No hay que olvidar inicializar la variable al principio de la ejecución del programa para acelerar aún más sus accesos, como explicábamos en la segunda entrega.

En lo que respecta a expresiones numéricas, el calculador de la ROM es capaz de distinguir dos tipos de datos: enteros y reales (representados en memoria en coma flotante). Los primeros los manipula mucho más rápidamente que los segundos, por lo que, por ejemplo, no es conveniente usar bucles FOR con pasos (STEP) reales en lugares que necesiten rapidez (por cierto, las expresiones para el paso y el límite de un bucle FOR son evaluadas sólo una vez, y guardadas junto a la variable del bucle para no tener que repetir ese cálculo). Tampoco deben usarse funciones reales (trigonometría, por ejemplo) en zonas críticas. Una alternativa, si no tenemos más remedio que usar números reales, sería representar con números enteros esos valores usando coma fija, es decir, suponer que una serie de dígitos del número son la parte decimal, aunque no lo sean, y trabajar siempre con él como entero. Por ejemplo: 255 puede significar para nosotros 2.55, aunque lo usemos como 255 en el programa. Las sumas y restas no cambian el valor final por el hecho de usar coma fija; la coma puede cambiar de sitio sólo en la multiplicación y división. Otra alternativa es precalcular los valores de las expresiones reales al principio del programa (o cargarlos en una tabla desde cinta) y sólo consultarlos luego; por ejemplo, preparar una tabla de senos o cosenos.

Un caso particular de expresiones con números enteros que se puede acelerar en BASIC es la descomposición de valores de 16 bits en sus dos bytes (alto y bajo). Esto es necesario en diversas ocasiones, pero el BASIC del ZX Spectrum no tiene ninguna función que lo realice, por lo que habría que escribir un código bastante ineficiente en tiempo de cómputo: LET h = int(v/256) : LET l = v - h * 256. Hay una forma de hacer esta descomposición más rápidamente aprovechándose de rutinas de la ROM ideadas para otros asuntos: RANDOMIZE v : LET l = PEEK 23670 : LET h = PEEK 23671 , que da el mismo resultado puesto que RANDOMIZE se encarga de la descomposición por nosotros, dejándola en la variable del sistema SEED, localizada en las direcciones de memoria 23670 y 23671. Eso sí, estamos cambiando la semilla de los números aleatorios que generemos para el programa a partir de ese momento.

Otro caso especial de aceleración de expresiones numéricas es cuando queremos incrementar una variable de manera cíclica, es decir, que vaya de 1 hasta cierto valor n-1 y luego vuelva a 1. Esto se puede hacer sin IF así: LET v = v + 1 OR v = n , donde además hemos aprovechado las precedencias en la evaluación de operadores para evitarnos tener que escribir los paréntesis. Este truco se basa en el comportamiento del operador OR en Sinclair BASIC, que no es un OR lógico ni de bits exactamente. Existe la correspondiente variante con AND, que permite ir cíclicamente entre 0 y n-1: LET v = v + 1 AND v < n, quizás más natural para los programadores de lenguajes donde los índices de arrays empiezan en 0.

Por su parte, las expresiones de manipulación de valores de texto también pueden ser optimizadas. Es poco eficiente sumarlas (concatenarlas), pues implica cambiar su tamaño en memoria y, por tanto, desplazar una cantidad potencialmente grande de datos en el proceso, como ya se explicó en la creación de variables en la segunda entrega. Asimismo, compararlas es un proceso costoso, del orden de O(n), siendo n la menor longitud de los dos textos. Si nos aseguramos de que uno de los dos términos de la comparación es muy corto (1 ó 0 caracteres), incrementamos la eficiencia.

A veces es más conveniente para ahorrar memoria almacenar los datos numéricos como textos (en lugar de los 5 bytes que necesita un valor numérico). Por ejemplo, si los números que almacena son enteros menores de 10000, una tabla con los mismos resulta más corta en memoria si se introducen como cadenas de caracteres, a costa de un mayor coste de ejecución al recuperarlos más tarde como números por medio de la función VAL.

Un tercer tipo de expresiones en cualquier lenguaje son las lógicas: aquéllas que se espera que sólo den dos valores, equivalentes de alguna manera a “verdadero” y “falso”. En Sinclair BASIC dichas expresiones se forman con los operadores lógicos NOT, AND y OR, aunque los dos últimos son algo más potentes que los habituales, como se ha explicado más arriba. El punto importante para la eficiencia en este tipo de expresiones es que el intérprete no hace evaluación perezosa o, más concretamente, de “cortocircuito”: los dos operandos son evaluados antes de evaluar los operadores AND y OR, cuando, en realidad, podría ahorrarse la evaluación del segundo si el primero es 0 ó 1, respectivamente. Por tanto, para ahorrar tiempo de ejecución deberíamos usar sólo expresiones muy simples como segundo operando de estos operadores.

Finalmente, toda expresión que contenga partes que no varían debería ser re-escrita con esas partes ya evaluadas, un trabajo que el intérprete de la ROM, al contrario que los compiladores modernos, no hará por nosotros. Esto gana tanto en tiempo como en espacio. Por ejemplo, no escribas A * PI / 180 para pasar el valor de A de grados a radianes; es más conveniente escribir A * 0.017453293, aunque quede más feo y no deba hacerse en plataformas y lenguajes actuales.

.oOo.


[Click here to read this in Spanish ]

This is the third 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

We begin this post by recalling a well-known fact in computer science:

Expressions are an entire sub-set of any imperative programming language

That means that evaluating an expression, let say 2*cos(x) - 23 or "hello, " + "worlds"(1 TO 5) involve an important work of syntactical analysis in addition to the very evaluation, a work that, in the case of the ZX Spectrum, must be done by the interpreter coded in the ROM at execution time. In machines like that, with scarce computational resources, it is therefore necessary to pay special attention to expressions.

Intuitively, for improving efficiency,

We should use expressions that are short (few operations in them) and simple (not too complex operations or involving too many steps of interpretation / calculation).

The ZX-Basicus utility can help with that through its analysis tool (-a): it produces a list of all the expressions of a program ordered by decreasing complexity (number of elements involved in them, both operations and data, without considering their textual lengths). This serves to identify the most complex ones, that should be few. Also, the ZX-Basicus interpreter (-r) can generate a profile (--profile) with the frequency of use of each expression, which completes the information needed to decide whether there are too complex expressions that are evaluated frequently and, therefore, need to be shortened and simplified.

In this context, it is worth to mention a very popular trick to reduce the size in memory of some expressions. It consists in using the VAL function and a string instead of a numeric literal. For example, VAL "32768" would replace literal 32768. The numeric literal is stored in memory with as many bytes as digits has the number plus other 6 for a hidden value that the interpreter stores there when it does its lexical analysis; on the other hand, the VAL version stores the same bytes for the digits plus only 3 more (1 byte for VAL, 2 bytes for the quotes).

The optimization tool of ZX-Basicus (-t) includes an option to perform automatically this trick in a source program (--valtrick). However, there are three important points that should be considered carefully before using the trick:

  • This technique saves memory… as long as there is no way of writing the numeric value without using its digits. For instance, VAL "3.1415" is not convenient since we can write PI, which is much more efficient in memory savings since it only occupies 1 byte (once PI is tokenized); furthermore, you can use NOT PI in any expression as equivalent to 0 and SGN PI as equivalent to 1: they only occupy 2 bytes (2 tokens) instead of the 7 bytes of a literal. This can be pushed even farther if we use scientific notation: you can write 4E3 instead of 4000, saving 1 byte (writing VAL "4E3" instead of VAL "4000" also saves 1 byte, but it is not worthy since it takes longer to run).
  • The technique increases execution time, possibly in an appreciable manner. Evaluating the VAL expression requires to create a new expression environment inside the original expression, which makes things worse than in an expression not using VAL. Reading directly the numeric value is much faster.
  • Most programs written purely in BASIC in the ZX, that, unlike assembly programs, do not need large amounts of data for graphics and stuff, usually have enough memory in RAM for working. Therefore, you have to think carefully if the space saved by the VAL trick is really worthy. For example, if the program does not modify the channels of the system and if CLEAR has not been executed to modify the top limit of usable memory and therefore that limit is still 65367 (default one, for storing 21 UDGs after that), the BASIC memory layout will be as follows: the program will begin at the address 23755 and the last byte of the top working areas will be at 41926 at the start of the execution. That gives us 41926 – 23755 = 18171 bytes that, if filled only with the BASIC program (which is not true), leads to a capacity for 2019 empty program lines, only with their line numbers and their information of size and ending markers (this amounts to 9 bytes if the line numbers have 4 digits). Often, BASIC programs have much less than 2000 lines and they are not too long (although there are some considerations on this commented in the first post of this series).

To get a more precise idea of how longer takes an expression that uses VAL instead of numeric literals, you can test the following program:

10  POKE 23672 , 0 : POKE 23673 , 0 : POKE 23674 , 0 : FOR f = 1 TO 10000 : LET c = VAL “65535” : NEXT f : LET T = PEEK 23672 + 256 * PEEK 23673 + 65536 * PEEK 23674 : PRINT “VAL: “ ; T ; ” “ ; T * 0.02 ; ” “ ; ( T * 0.02 / 10000 )

If the program is run (around 2 minutes), then run again after changing VAL "65535" by the numeric literal 65535 only, and then you calculate the difference between both average times per loop iteration, you will see that using VAL is 15 milliseconds slower than the numeric literal, which is very slow, particularly when the expression is repeatedly evaluated (the precision in the time estimation of the program above is around +/-115.5 microseconds with 95% of probability).

Going back to the efficiency of expressions, as I said before, they should be as short and simple as possible (and likely without VAL shortcuts!), specially those inside loops that are frequently executed and that need to be fast. This excludes almost completely to use user function calls: FN involves not only the syntactical analysis of the expression and its evaluation, but a search of the line that contains the corresponding DEF FN and the copy of the arguments into the placeholders of that function, as it was also explained in the first post.

If the same expression is repeated in nearby places, it is convenient to store its result once and reuse it the rest of times: it is always faster to evaluate a single variable than a whole expression. Do not forget to initialize the variable once at the beginning of the execution (along the rest of variables that the program uses) in order to make this even more efficient, as it was explained in the second post of this series.

Regarding numerical expressions, the ROM interpreter uses a sophisticated software also included in ROM called “the calculator”. That calculator distinguish two kinds of numeric values: integers and reals (represented as floating point reals). The former are much more efficient to work with than the latter; therefore, it is not convenient to use real numbers in FOR loops (for instance, as STEP arguments) if those loops need to be fast (by the way, the step and limit of a FOR loop are evaluated just once and stored along with the loop variable, thus the cost of repeatedly evaluating them is saved). You should not call trigonometric functions within critical code either. An alternative to the latter would be to represent the real numbers with fixed point, i.e., to assume that a number of digits of the integer actually represent the digits after the decimal point in the real. In that manner, the program always work with integers, and only convert them into reals when they need to be shown in the screen or the like. For example, 255 can have the meaning of 2.55 in the program. Additions and substractions do not change the place of the decimal point when using fixed point arithmetics; only multiplications and divisions do. A different alternative is to pre-calculate the values of real expressions needed in the program and store those values in an array; that array can be loaded from tape at the beginning. This is often done for cosine and sine tables.

A particular case of integer number expression that can be accelerated in BASIC is the decomposition of 16 bits integers into their high and low 8-bits parts. This comes handy in a number of situations, but since the ZX Spectrum BASIC has no function that does that, a quite inefficient code should be written: LET h = int(v/256) : LET l = v - h * 256. Luckily, there is a way of doing this decomposition faster by taking advantage of ROM routines devised for other purposes: RANDOMIZE v : LET l = PEEK 23670 : LET h = PEEK 23671. This produces the same result because RANDOMIZE does exactly the desired decomposition and stores it in the system variable SEED, located at memory addresses 23670 y 23671. Take care, though, that we are changing the seed for the random numbers that will be generated for the program from now on.

Another special case of expression with numeric values occurs when we wish to increment a variable cyclically, that is, to assign increasing values from 1 to n-1 and then to 1 again. This can be done without IF in this way: LET v = v + 1 OR v = n , where, in addition, we have used the operator evaluation precedences to avoid the writing of parentheses. This trick is based on the behaviour of the OR operator in Sinclair BASIC, that is not a logical OR or a bitwise OR. There exists a variant with AND that allows us to scan cyclically from 0 to n-1: LET v = v + 1 AND v < n, maybe more natural for programmers of languages where array indexes begin at 0.

String (text) expressions can also be optimized. It is little efficient to add them (concatenation), since that involves to change their size in memory (therefore displacing potentially significant amounts of memory, as it was discussed in the second post), and intermediate strings that are only used for that operation must be created / deleted dynamically. Also, comparing strings is O(n), being n the length of the shortest string to compare. We should be sure to do that only when one of the two compared terms is really short, ideally one character or none.

On the other hand, sometimes it is convenient to store numerical values as text, since that can save memory as explained in the VAL trick. An array of numbers will be shorter in memory if stored as an array of characters as long as the numbers are integers less than 10000. Notice, nevertheless, that this involves to use VAL to recover the numerical values, which increases execution time, as explained before.

A third kind of expression in any language is the “logical” one, that produces only two values, expected to be semantically equivalent to “true” and “false”. In Sinclair BASIC these expressions are formed with the NOT, AND and OR operators, and the last two are slightly more powerful than the common ones, as explained above. The important point for efficiency is that the interpreter does not do lazy evaluation in logical expressions, or, more concretely, short-circuit evaluation: both operand are evaluated before evaluating the operators AND and OR, when, actually, the evaluation of the second could be saved if the first is evaluated to 0 or 1, respectively. That increases innecessarily the execution time, thus we should be careful to use just very simple expressions in the second terms of those operands.

Finally, every expression containing some part that do not vary should be re-written with that part already evaluated, saving in this way effort that the interpreter should do otherwise at running time (unlike modern compilers, the interpreter of the ZX does not do such pre-optimization automatically). This also saves space in RAM. For instance, do not write A * PI / 180 to convert the degrees in A to radians; it is much more efficient to write A * 0.017453293, even when it is uglier and not suitable for modern programming.

Facebooktwitterredditlinkedintumblrmail