Efficient BASIC coding for the ZX Spectrum (III)

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

Hay que tener tres cosas en cuenta a la hora de usar este truco, y nunca hacerlo sin reflexionar sobre cada caso:

  • Esta técnica ahorra memoria sólo si la parte de la expresión consistente en el VAL y la cadena ocupa menos bytes en memoria que el lireral numérico (el cual incluye la representación textual del número más 1 byte marcador, oculto, más 5 bytes con el valor numérico, también ocultos). Por ejemplo, VAL "3.1415" es ideal para ahorrar espacio frente al literal 3.1415, ya que lo primero ocupa en memoria 9 bytes (VAL se tokeniza), mientras que lo segundo ocupa 6 + 1 + 5 = 12 bytes (sería ventajoso hasta VAL "3.141563"). Sin embargo, PI es mucho más eficiente en memoria que cualquiera de los dos, ya que sólo ocupa 1 byte (PI se tokeniza). Por supuesto, VAL "3.14156295" es definitivamente desaconsejable. Aplicar esta técnica con literales numéricos enteros, que en principio desperdician más memoria en el BASIC del ZX (2 bytes de los 5 de su representación binaria oculta no se usan), parece más ventajoso, pues el literal tendrá que estar en cualquier caso, y el VAL es 1 byte (las comillas dobles son 2 bytes). Así, VAL "65535" ocupa en total 8 bytes, mientras que 65535, su versión como número literal, ocupa 11.
  • Hay que considerar que esta técnica incrementa el tiempo de ejecución, posiblemente de manera apreciable. 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).

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, ni tampoco usar 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; sólo la coma puede cambiar de sitio 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.

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.

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.

There are three important points regarding this, and the use of the trick should be carefully considered based on them:

  • This technique only saves memory if the VAL expression has less bytes than the numeric value (the latter also includes a hidden binary representation of the number with 5 bytes plus a literal number marker of 1 byte). For instance, VAL "3.1415" is ideal to save space against the literal 3.1415, since the former occupies 9 bytes (once the VAL keyword is tokenized) while the latter is 6 + 1 + 5 = 12 bytes long (we could benefit up to VAL "3.141563"). However, PI is much more efficient in memory savings than any of these, since it only occupies 1 byte (once PI is tokenized). Of course, VAL "3.14159265" is definitely not an option. Using the technique with integers, which in principle waste more memory than reals (they store 2 bytes out of the 5 in their hidden binary representation that are never used), seems better, because the integer will be written in the program anyway, and VAL is 1 byte (double quotes are 2 bytes); thus, VAL "65535" is 8 bytes long, while 65535 is 11.
  • 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).

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, or calling trigonometric functions within critical code. 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.

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.

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

2 thoughts on “Efficient BASIC coding for the ZX Spectrum (III)

  1. Pingback: Efficient BASIC coding for the ZX Spectrum (II) – Lithographica

  2. Pingback: Efficient BASIC coding for the ZX Spectrum – Lithographica

Comments are closed.