Hay muchos detalles aquí abajo, así que quien quiera puede ir directamente al resumen final.

1. Créditos

Desde que se aprobara el Real Decreto 1125/2003 (que también implantó las calificaciones oficiales cuantitativas -de 0 a 10- y su correspondencia con las cualitativas -suspenso, aprobado, etc.- que usamos hoy), se emplea en España el sistema ECTS (European Credit Transfer System) para establecer la cantidad de trabajo que suponen para el alumno los planes de estudio universitarios. Estos planes comenzaron a aprobarse y a sustituir a los antiguos a partir de la modificación en forma de Ley Orgánica 4/2007 que se hizo a la anterior Ley de Ordenación Universitaria (LOU) de 2001, donde se extinguían los títulos universitarios anteriores en favor del actual sistema de grados, másteres y doctorado.

En España se decidió que una titulación oficial de grado universitario tuviera un plan de estudios de 4 años de duración en el que hubiera un total de 240 créditos ECTS (Real Decreto 1393/2007). Aunque es el actualmente activo, este formato no coincide con el de la mayoría de países importantes del entorno europeo, que siguieron el esquema 3+2 (180 y 120 créditos ECTS para grado y máster, respectivamente), y, realmente, no resultaba ni necesario ni demasiado lógico implantarlo, dado que las titulaciones existentes anteriormente en España encajaban en el formato 3+2 desde la Ley de Reforma Universitaria de 1983: diplomaturas (3 años) y licenciaturas (5, divisibles en dos ciclos de 3 más 2 cursos). A principios de 2015, justo cuando estaban egresando las primeras promociones de grado y máster del esquema de 4 años, el Gobierno aprobó el Real Decreto 43/2015, que permitía a las universidades elegir entre cualquiera de los dos formatos, pero en un estado tan avanzado de la cosa, aquello no terminó de cuajar. Actualmente parece que están barajando el reincorporar de nuevo el modelo 3+2.

En cualquier caso, los 240 créditos totales repartidos entre los 4 años nos dan 60 créditos ECTS por año, como obliga el R.D. 1125/2003.

2. Tiempo

En España, los estudios universitarios dividen oficialmente el año académico en 2 cuatrimestres desde que, tras la guerra civil española, el régimen dictatorial estableciera las bases de su nuevo sistema docente (en agosto de 1943, para más señas: Ley sobre la ordenación de la Universidad española, art. 18-d). Esta estructura temporal quedó en suspenso en junio de 1968 mientras se tramitaba la siguiente ley universitaria, aunque, sorprendentemente (para el que esto escribe, que no es ningún experto en estos temas), no hay legislación posterior en BOE (ni la L.R.U. ni la L.O.U.) que levante tal suspenso ni derogue el artículo original. En otros países existen estructuras anuales en algún caso similares, pero también variadas.

Como aquí hay 2 cuatrimestres lectivos al año, ya sea por tradición o por falta de derogación de una norma carpetovetónica, tenemos 30 créditos por cuatrimestre. Esos 30 créditos se pueden repartir a su vez de forma exacta en 5 asignaturas de 6 créditos cada una, que es lo que hacen todos los planes de estudio de grado que conozco. El curso completo, por tanto, consta de 10 asignaturas cuatrimestrales.

Podemos considerar asimismo que un cuatrimestre universitario dura 20 semanas naturales si incluimos los períodos de exámenes finales del mismo, que suelen ocupar alrededor de un mes de trabajo para los estudiantes. Un curso, por tanto, durará 40 semanas en nuestros cálculos, lo que entra dentro del rango de entre 36 y 40 semanas establecido por el R.D. 1125/2003.

3. Horas de trabajo

Según la Guía de uso de ECTS de la UE, “la equivalencia de la carga de trabajo [de un alumno] de un curso académico a tiempo completo con 60 créditos ECTS se formaliza a menudo a través de las disposiciones legales nacionales. En la mayoría de los casos, la carga de trabajo oscila entre 1500 y 1800 horas por curso académico, es decir, un crédito equivale a entre 25 y 30 horas de trabajo“. Esto lo ratificó en España, en iguales términos, el anteriormente mencionado Real Decreto 1125/2003, por lo que quedó fijado el rango de 25 a 30 horas de trabajo del alumno por cada crédito ECTS (artículo 4-5).

Además, desde ese R.D. debe entenderse que las horas de trabajo reconocidas oficialmente al alumno incluyen todas las posibles (menos los desplazamientos y el vivir -comer, dormir,…-, como en el caso de la inmensa mayoría de trabajadores), es decir:

• Clases lectivas, teóricas o prácticas.
• Horas de estudio.
• Horas dedicadas a la realización de seminarios, trabajos, prácticas o proyectos.
• Horas exigidas para la preparación y realización de los exámenes y pruebas de evaluación.

No he encontrado normativa alguna que obligue a o recomiende un número concreto de horas por crédito dentro del margen establecido de entre 25 y 30, pero por lo que yo conozco, lo habitual en España en estudios universitarios de grado es que 1 crédito ECTS equivalga a 25 horas totales de trabajo del alumno. Con esta equivalencia básica, una asignatura de 6 créditos supone 6 x 25 = 150 horas de trabajo total del alumno, las cuales, multiplicadas por las 10 asignaturas de un curso, nos da 1500, justo en la cota inferior de lo establecido por la UE.

Las 150 horas de una asignatura cuatrimestral, divididas entre las 20 semanas del cuatrimestre, dan 7.5 horas por semana de trabajo del alumno en dicha asignatura. De esas 7.5 horas por asignatura y semana, las asignaturas de 6 créditos suelen dedicar 4 horas a clases presenciales (bueno, ahora con la COVID, semi-presenciales, pero siguen contando como 4 horas), normalmente divididas en 2 sesiones de 2 horas.

En fin, el caso es que las 7.5 horas por semana multiplicadas por 5 asignaturas son 37.5 horas semanales para todas las asignaturas de un cuatrimestre para un alumno matriculado en uno y sólo en un curso. Esto coincide bastante aproximadamente con lo que supone la jornada laboral actual de un adulto en edad de trabajar en nuestro país (la legal, quiero decir).

Así que, en resumen, una asignatura de 6 créditos de grado se corresponde oficialmente para el alumno con 4 horas de clase más 3.5 horas de trabajo propio (estudio, tutorías, escritura de memorias de prácticas, etc.) a la semana. Las 5 asignaturas de un cuatrimestre, por tanto, son 37.5 horas semanales de trabajo, bastante similares a las horas de trabajo semanales -legales- de cualquier trabajador (si eres estudiante, no te conviene matricularte de más de 5 asignaturas por cuatrimestre, por tanto).

4. Calculando más allá

Para dar una visión más general, podemos comenzar por la siguiente tabla, que muestra las horas de trabajo del alumno dependiendo del número de horas por crédito que se establezcan en su plan de estudios y del número de semanas que tenga el curso, ambos dentro de lo que permite la ley:

A partir de aquí podríamos cambiar los dos parámetros variables en la ecuación: el número de asignaturas por curso y cuántos créditos tiene cada una, siempre que mantengamos constantes los 240 créditos por titulación, los 4 años de la titulación y los rangos de horas/crédito, horas/curso y semanas/curso de la tabla anterior, que vienen escritos más en piedra que este mismo blog, puesto que están en BOE.

En tal sistema genérico, se tendrían que cumplir las siguientes (in)ecuaciones:

1500 \leq A C_a H_c \leq 180025 \leq H_c \leq 30240/4 = A C_aA = 2 nA \in \mathbf{N}^{+}, C_a \in \mathbf{R}^{+}, H_c \in \mathbf{R}^{+}, n \in \mathbf{N}^{+}

donde A es el número de asignaturas por curso, C_a el número de créditos por asignatura, H_c el número de horas por crédito y el superíndice ‘+’ indica no considerar el 0 en el caso de los números naturales ni tampoco los negativos en el caso de los reales (la penúltima ecuación asegura que hay 2 cuatrimestres con el mismo número de asignaturas cada uno). Se puede simplificar este sistema usando la tercera ecuación sobre las demás:

25 \leq H_c \leq 3025 \leq H_c \leq 3060 / C_a = 2 nC_a \in \mathbf{R}^{+}, H_c \in \mathbf{R}^{+}, n \in \mathbf{N}^{+}

Con lo que concluimos dos cosas:

• Que el rango establecido por el Gobierno de España para las horas por crédito era el único posible, dadas las indicaciones de la UE, si establecía 240 créditos por año durante 4 años.
• Que las horas por crédito pueden establecerse de cualquier manera que permita la primera ecuación, independientemente del número de créditos por asignatura.

En resumen, nos ha quedado:

25 \leq H_c \leq 30C_a = 30/n

La segunda ecuación sólo tiene un pequeño subconjunto de soluciones que sean exactas hasta con 2 decimales. La siguiente tabla indica, para cada uno de los correspondientes valores de C_a de dichas soluciones, el número de asignaturas por curso que habría. En todos los casos, el número de horas de trabajo semanales estaría de acuerdo con la tabla azul de arriba: 41.666… (con H_c = 25 y 36 semanas por curso), 37.5 (con H_c = 25 y 40 semanas por curso), 50 (con H_c = 30 y 36 semanas por curso), 45 (con H_c = 30 y 40 semanas por curso), y todos los posibles valores intermedios.

Obviamente, más de 12 asignaturas por curso parece un pelín exagerado, y menos de 4 bastante ridículo, por lo que con las obligaciones normativas actuales, los cursos de grado podrían tener entre 4 y 12 asignaturas por curso de entre 15 y 5 créditos cada una y suponer una carga de trabajo semanal para el alumno de entre 37.5 y 50 horas.

[Click here to read this in English ]

Éste es el quinto y último 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. Funcionalidades diversas y medida del tiempo

V. Operaciones en la pantalla basadas en caracteres

En esta última entrega hablaremos sobre la pantalla del ZX Spectrum y de cómo acelerar operaciones de caracteres en ella cuando se programa en Sinclair BASIC. No hablaremos aquí de cómo dibujar píxeles (PLOT, DRAW, …); para ello, se puede consultar la entrada anterior. Asimismo, el truco del DEFADD para mover bloques de memoria (útil también para trabajar en la pantalla) se describió en aquella entrada.

Para navegar más fácilmente por la presente entrada, éstos son los apartados que contiene:

1. La pantalla y la escritura de caracteres. Sobre la memoria de la pantalla y por qué la eficiencia de la escritura de caracteres fue tan importante para diseñar su estructura.
2. Escribir caracteres. Sprites en BASIC, caracteres de control, compresión de pantallas (con la participación de @igNaCoBo).
3. Leer caracteres. Tiempos de ejecución de SCREEN$ y ATTR.
4. Escribir texto ampliado. Cómo escribir texto a gran tamaño con el truco de LPRINT (en colaboración con @IvanBASIC).
5. Escribir atributos de color. Cómo manipular los atributos de color independientemente de sus caracteres con el truco de LPRINT (en colaboración con @IvanBASIC).

La pantalla y la escritura de caracteres

Aunque en BASIC del Spectrum no es habitual escribir / leer directamente de la memoria de pantalla, es importante conocer cómo se organiza dicha memoria para entender algunas técnicas que pueden acelerar los programas (como el truco de LPRINT que explicamos más adelante, o los límites que tiene el truco del DEFADD que explicamos en la entrada anterior al usarlo en la pantalla). En entradas más antiguas de este mismo blog (como ésta y ésta) ya explicamos algunas de las características de los gráficos en el ZX; aquí nos centramos en por qué tienen la organización en memoria que tienen y qué operaciones son más eficientes con ella.

La primera decisión importante que se tomó durante el diseño de los gráficos del ZX fue asumir que era imprescindible escribir texto en la pantalla, y que, para simplificar el software que se encargara de ello (puesto que no hay hardware dedicado en el ZX a esas funciones y por tanto las tiene que hacer la CPU), los caracteres de texto serían de tamaño fijo: 8 x 8 píxeles, concretamente.

La segunda decisión fue que, dado que el ZX Spectrum, al contrario que su predecesor, el ZX 81, debía desplegar un gran colorido para hacer honor a su nombre, había que asignar más de 2 tonos (blanco y negro) a los píxeles. Lamentablemente, hacer eso para cada píxel por separado disparaba el coste de fabricación prohibitivamente debido a la cantidad de memoria necesaria. Lo más sensato era ajustarse a lo que mínimamente necesitara cada carácter de texto dibujado en pantalla, es decir, tomar bloques de 8 x 8 píxeles como granularidad espacial para el color, y dedicar a cada uno de esos bloques la mínima cantidad de memoria necesaria para almacenar los colores de dichos píxeles asumiendo que en muchísimas ocasiones corresponderían a los de un carácter de texto.

Eso llevó a que, por cada bloque de 8 x 8 píxeles de pantalla, se almacenara sólo 1 byte como “atributo” de color de esa “celda”, tal y como se explica aquí y se ilustra en la figura de abajo. El carácter visible en la televisión se obtiene usando dicho atributo sobre un “mapa de bits” compuesto por 8 bytes (a la izquierda en la figura) cuyos bits indican, a 0, que se use para ellos el color de papel, y a 1 que se use el de tinta.

Por tanto, la memoria de pantalla del ZX Spectrum acabó separada en dos partes almacenadas en zonas de la RAM distintas pero relacionadas entre sí, que eran leídas periódicamente por el hardware (concretamente, por la ULA) para refrescar la imagen mostrada en la televisión:

• El mapa de bits, donde están las “formas” o, si se prefiere ver así, los dibujos en “blanco y negro” de todos los caracteres que caben en pantalla (24 líneas por 32 columnas de caracteres). Empieza en la dirección 16384 (justo tras finalizar la ROM). Ocupa 6144 bytes (24 líneas de caracteres x 8 píxeles de alto por carácter = 192 filas de píxeles, con 32 columnas de caracteres de 1 byte cada una).
• El mapa de atributos, donde están los atributos de color de dichos caracteres. Empieza justo tras el mapa de bits, en la dirección 22528. Ocupa 768 bytes en memoria (24 líneas por 32 columnas de atributos de color, a 1 byte por atributo).

La tercera decisión es la que más nos importa en esta serie de artículos, porque es la que lleva a la (in)eficiencia de acceder a la memoria de pantalla para trabajar con cosas más grandes o más pequeñas que un carácter. Como la CPU, o sea, el software, tenía que ocuparse de todas las labores de escritura en la misma, especialmente de la escritura de caracteres, había que encontrar la forma de hacer eso lo más eficientemente posible. ¿Qué es lo más costoso? Escribir los 8 bytes del mapa de bits de un carácter (¡su atributo de color es sólo 1 byte!). ¿Y qué cálculos son los más frecuentes cuando se tienen que escribir en memoria los 8 bytes del mapa de bits de cada carácter? Básicamente dos, que etiquetamos (Y) y (X) por motivos que quedarán claros más adelante:

• (Y) calcular la dirección de memoria donde hay que almacenar el siguiente byte del mapa de bits en la celda de un carácter (o sea, moverse 1 fila de píxeles hacia abajo en el mapa de bits).
• (X) calcular la dirección de memoria donde hay que almacenar el mapa de bits del siguiente carácter (o sea, moverse a la derecha 1 columna en el mapa de bits).

Lo primero hace falta para almacenar los 8 bytes del mapa de bits de un carácter concreto en la memoria de pantalla de forma que lo pueda mostrar la ULA en la televisión, y lo segundo para pasar a almacenar el siguiente.

Ambas operaciones suponen incrementar direcciones de memoria, que son números enteros positivos. Las instrucciones máquina más rápidas de la CPU Z80 para incrementar números son las INC, que aumentan un número entero en una unidad; son especialmente rápidas cuando lo que tienen que incrementar es un número que quepa en 8 bits. O sea, que si se consiguiera la acción (Y) incrementando en 1 un número de 8 bits y la acción (X) incrementando en 1 otro, la impresión de texto en pantalla sería lo más rápida posible.

Pues bien, una dirección de memoria en el Z80 es un número entero positivo de 16 bits, y para el Z80 acceder independientemente a los dos bytes que componen tales números es prácticamente trivial; de hecho, se pueden considerar a casi todos los efectos que estos números están divididos en el byte más significativo o “alto” y el menos significativo o “bajo”. Así que nos encontramos con dos operaciones independientes de incremento de 8 bits que el Z80 puede hacer rápidamente con direcciones de memoria: incrementar el byte alto e incrementar el byte bajo. Si la primera operación consiguiera bajar a la fila de píxeles siguiente dentro del mapa de bits de un carácter y la segunda a la columna de la derecha, donde debe ir el siguiente carácter, estaría todo solucionado.

Eso es exactamente lo que hicieron en la memoria de mapa de bits del ZX.

Con este diseño, tenemos dos cursores que podemos mover independientemente para situarnos dentro del mapa de bits de la pantalla: uno en horizontal (columnas de caracteres; se mueve incrementando en 1 el byte bajo de la dirección de memoria; podemos movernos en 32 valores diferentes, que necesitan 5 bits para representarse) y uno en vertical (filas de píxeles; se mueve incrementando en 1 el byte alto de la dirección de memoria; podemos movernos en 192 valores diferentes, que necesitan 8 bits para representarse). Algo así:

Ahora bien, con este diseño estamos usando sólo 5 bits del byte más bajo de la dirección de memoria de pantalla para movernos según la acción (X), por lo que hay 3 bits en ese byte bajo sin utilizar, lo que provocará “huecos” en memoria de pantalla (direcciones que nunca usaremos), lo cual, obviamente, hay que evitar. Además, si usáramos este diseño el primer byte del mapa de bits de la pantalla estaría en la dirección 0 de memoria, que ni siquiera es RAM…

La solución a este problema fue trasladar parte de los bits del cursor vertical, alojado inicialmente en el byte alto de la dirección de memoria, hasta el byte bajo (tenemos sitio para alojar 3 bits). No se pueden trasladar los bits menos significativos del byte alto, porque son los que permiten hacer la acción (Y) (¡no los vamos a quitar de ahí!), así que había que trasladar los más significativos. Eso tiene como efecto lateral liberar de todo uso los bits 15, 14 y 13 del byte alto de la dirección de memoria; si se fijan al valor 010 (binario), la primera dirección de memoria del mapa de bits de pantalla, donde los dos cursores son 0, será 16384 exactamente (todas las direcciones del mapa de bits de memoria tienen los 3 bits más significativos con ese mismo valor). Este diseño quedaría así:

Al mover los 3 bits más significativos del cursor vertical (es decir, sus bits 5, 6 y 7) al byte más bajo de la dirección de memoria, nos quedaríamos en el byte alto de la dirección de memoria con 5 bits útiles (además de los constantes 010). Podríamos incrementar 32 veces el número alojado en esos 5 bits antes de saturar su valor, lo que significaría que, haciendo la acción (Y), podemos cubrir 4 filas de caracteres de texto antes de saturar y por tanto tener que tocar el byte bajo de la dirección de memoria (los 3 bits que nos llevamos allí) para seguir.

El problema es que, una vez saturados los 32 posibles valores que tiene el cursor horizontal (X), pasaríamos a cambiar los bits más altos del vertical (Y7, Y6, Y5), lo que haría que, tras incrementar en uno la última columna horizontal (la 31), saltáramos 4 líneas de caracteres más abajo en vertical, lo que es bastante poco útil y extraño.

Lo suyo sería que, al incrementar la última columna horizontal de la pantalla, el cursor vertical pasara a la siguiente línea de texto. Para lograr esto, los diseñadores del sistema decidieron mover los bits 3, 4 y 5 del cursor vertical hasta el byte bajo de la dirección de memoria, en lugar de los 5, 6 y 7. De esa manera, se satura el cursor vertical tras hacer la acción (Y) sólo 8 veces (que es suficiente para acceder a todos los bytes del mapa de bits de 1 carácter), pero conseguimos el paso más natural a la siguiente línea de caracteres cuando lleguemos a la última columna:

Este diseño tiene un efecto algo inesperado: si consideramos qué partes de la pantalla corresponden a bloques de caracteres contiguos en memoria, estamos dividiendo el mapa de bits en 3 secciones contiguas de 8 filas de caracteres cada una, correspondientes a los 3 valores que pueden albergar los bits 6 y 7 del cursor vertical (no pueden llegar a valer 11 en binario pues sólo hay 192 filas de píxeles en pantalla, no 255). Esto es lo que produce que, cuando se cargue una pantalla desde cinta, vaya apareciendo ésta con las filas de píxeles distribuidas de forma tan extraña.

También tiene algunos inconvenientes importantes. Para empezar, requiere cómputos complicados para operaciones que no sean (X) ni (Y), como explican por ejemplo aquí. Asimismo, limita el poner bloques de caracteres de dimensiones medianas en pantallas y el hacer scroll con el truco del DEFADD explicado en la entrada anterior. Sin embargo, considerándolo todo en conjunto, se ve que las ventajas (escribir texto en pantalla lo más rápidamente posible) superan razonablemente a estos inconvenientes.

Se puede visualizar todo lo explicado aquí con este programa BASIC tan sencillo, que escribe en el mapa de bits valores uno detrás de otro, con lo que se observa claramente cómo van repartiéndose por la imagen; además, también muestra cómo el mapa de atributos es lineal y mucho más simple de entender:

Escribir caracteres []

El lenguaje BASIC del ZX Spectrum tiene instrucciones de escritura de caracteres en pantalla que están implementadas en ROM y ocultan al programador los detalles explicados en el apartado anterior. Sin embargo, es importante acelerar estas operaciones, porque son esenciales en casi cualquier programa.

Si tenemos que imprimir, por ejemplo, un sprite que tenga varios caracteres de alto y de ancho (típicamente definidos por el usuario, o UDGs), no parece conveniente hacer dos bucles FOR anidados para ello, con todo el cómputo extra, saltos y espacio en memoria de programa que eso supone. Sería mucho mejor usar dentro del sprite caracteres de control que muevan el cursor de impresión automáticamente conforme el sprite se imprime. De hecho, la ROM del ZX imprime este tipo de comandos de control empotrados en una cadena de texto a una velocidad muy superior a la que haría el programa mediante sentencias explícitas equivalentes a los mismos.

Ay, lamentablemente el intérprete del ZX no implementa bien todos los caracteres de control de movimiento direccional (las flechas). Los controles de izquierda y derecha tienen algunos bugs, y los de arriba y abajo no funcionan. Sólo si queremos pintar siempre en el mismo lugar absoluto de pantalla podremos hacerlo rápidamente usando el carácter de control AT (22). Para el resto de casos, solventar el problema de la lentitud de los bucles que dibujan el sprite sólo puede hacerse con técnicas como el desenrollado de bucles, explicada en la primera entrega de esta serie.

Aquí dejo un ejemplo de programa que, al ejecutar, ilustra algunos problemas que tiene el intérprete de la ROM con los caracteres de control direccionales:

Lo que sí resulta práctico incluir en el sprite son códigos de control de color, para que se imprima con los atributos que deseemos sin tener que usar INK, PAPER, etc., dentro de la sentencia PRINT, lo que, además de ocupar bastante espacio, ejecutaría más lentamente. Esto tiene el inconveniente de estropear la legibilidad del código fuente cuando éste se visualiza mediante el editor de código original del ZX, sin embargo.

Para estimar lo que se tardaría en dibujar un sprite de ciertas dimensiones, se puede ejecutar el siguiente programa:

Este programa repite la impresión en pantalla de bloques cuadrados de caracteres de diversas dimensiones, tomando nota del tiempo que lleva para cada tamaño posible. Los tiempos medios resultantes se muestran en la siguiente gráfica:

El comportamiento se puede dividir en tres componentes aditivos: el principal, claramente cuadrático (470 microsegundos por el número total de caracteres a imprimir), viene de la impresión en sí misma; el secundario, lineal (17 milisegundos por la altura en caracteres del sprite) es producido por el bucle de la línea 20, encargado de imprimir cada fila de caracteres; el último, constante (el offset vertical de unos 12 milisegundos), se debe al resto de trabajo en bucle, evaluación de expresiones, etc., que es siempre igual para cualquier tamaño de sprite.

Como vemos en la gráfica, en general sólo se podrá imprimir 1 carácter, si es que queremos hacerlo a una frecuencia esperada de 25 fps o superior (si queremos borrar el sprite, bajará la frecuencia a la mitad); si vamos a sprites de 2×2 (sin códigos de control de color, lo cual aumentaría el tamaño), sólo esperaríamos alcanzar los 20 fps; algo menos de 8 fps con sprites de 6×6 (equivalentes a sprites de 2×2 con colores añadidos de tinta en cada carácter); y así sucesivamente. En la práctica, sprites de más de 2×2 con colores incluidos consumen más tiempo del disponible en la mayoría de las situaciones.

Nótese que los datos de la gráfica no sólo sirven para estimar cuánto tiempo llevará imprimir un sprite cuadrado de media, sino que se pueden usar para cualquier conjunto de caracteres que queramos imprimir, tenga las dimensiones que tenga. Por ejemplo, imprimir una sola línea horizontal de 32 caracteres (sin controles de color) tendría como tiempo principal esperado 470 x 32 = 15.04 milisegundos si no consideramos los tiempos de las operaciones constantes (expresiones y demás), pues equivaldría a no hacer bucles de impresión de varias líneas, ahorrándonos la componente lineal. Otro ejemplo sería imprimir toda la pantalla (digamos, 24 x 32 caracteres, contando un número razonable de códigos de control entre ellos) con una sola orden PRINT, lo que esperaríamos que llevara principalmente 470 x 24 x 32 = 360.96 milisegundos o, si se hace línea a línea con un bucle FOR, 0.470 x 24 x 32 + 17 x 24 = 768.96 milisegundos.

Hay una pequeña mejora en la impresión de caracteres que el programador de juegos BASIC @igNaCoBo ha utilizado en su juego ArkanoidB2B: consiste en terminar la orden PRINT con un punto y coma (;) con el fin de evitar que el intérprete realice un cambio de línea, como hace por defecto a menos que encuentre ese símbolo al final. Hacer el cambio de línea le lleva más tiempo que interpretar el punto y coma en su lugar. Concretamente, se puede modificar la línea 20 del programa BASIC anterior para que la sentencia PRINT termine en punto y coma y medir los tiempos (más cortos) que lleva imprimir caracteres de esa manera. Las diferencias de tiempo con el programa original se observan en las siguientes gráficas:

Vemos que, de media, una sentencia PRINT tarda 364 microsegundos más en hacer el cambio de línea que en procesar el punto y coma (histograma inferior). Esto puede no parecer mucho, pero si se repite la sentecia varias veces (como sucede al imprimir sprites) la ganancia se acumula linealmente, como se ve en la figura superior (la figura de en medio muestra la misma información que el histograma pero para cada tamaño de sprite probado).

Además de esta pequeña mejora en el tiempo de cómputo, se nos ofrece una oportunidad particular de incremento de eficiencia cuando lo que se imprime es una secuencia de espacios contiguos: si éstos son más de 3, y el último se sabe en qué columna debe situarse, es conveniente utilizar el carácter de control TAB, que automáticamente imprime espacios hasta alcanzar la columna indicada. La herramienta de análisis de ZX-Basicus (-a) puede ayudar con esto porque localiza la lista de literales de texto que tienen espacios contiguos.

También puede servir para esto el carácter de control COMMA, que inserta espacios automáticamente hasta alcanzar la siguiente mitad horizontal de la pantalla, respecto a la posición actual del cursor.

Por supuesto, no se debe borrar toda la pantalla si no es con CLS, o rellenarla si no es con un sólo literal de texto de 32*24 caracteres de longitud (es decir, que ocupe todo el área visible, o, al menos, todo lo que se quiera imprimir). Este puede estar optimizado usando TAB o COMMA si contiene espacios contiguos.

Al hilo de lo expuesto en este último párrafo, hay un truco para rellenar toda la pantalla con cualquier carácter de manera rápida: consiste en redefinir de manera temporal el carácter espacio para el sistema; cuando se escriban TABs o COMMAs suficientes, el intérprete imprimirá en pantalla no espacios, sino el carácter que hayamos definido. Por ejemplo, para rellenar toda la pantalla con ladrillos muy rápidamente basta ejecutar este programa (las 44 comas que hay en la línea 30 son las que rellenan las 22 líneas de la pantalla con espacios; los POKE en 23606 y 23607 le dicen al sistema que use un juego de caracteres nuevo cuyo primer carácter, es decir, el de espacio, está en el UDG “A” que definimos en la línea 20):

Finalmente, el sintetizador de código que incluye la herramienta ZX-Basicus es capaz de comprimir pantallas (o partes de ellas) usando los trucos explicados anteriormente (opción --comprscr). Esta utilidad genera automáticamente los datos binarios de las pantallas (definiciones de conjuntos de caracteres necesarios, datos para la definición de variable que contendrá la pantalla por medio del truco del DEFADD descrito en la entrada anterior) y el código BASIC que puede mostrarlas.

Leer caracteres []

En cuanto a examinar el contenido de la pantalla con ATTR (mapa de atributos) y SCREEN$ (mapa de bits), la verdad es que sus implementaciones en la ROM son todo lo eficientes que pueden ser, por lo que, siempre que sus argumentos no sean expresiones de gran complejidad, no son demasiado acelerables.

Sí que se debería usar ATTR preferentemente, que es más rápida porque no tiene que reconocer el carácter que se examina a partir de su bitmap en pantalla. Esto puede comprobarse usando el siguiente programa, que tarda unos 2 minutos en ejecutarse y produce una medida de tiempo:

Si lo ejecutamos una vez con SCREEN$ y otra igual pero con ATTR, las diferencias entre ambos tiempos serán exactamente las que tengan ambas formas de comprobar la pantalla. Los resultados son que, de media, SCREEN$ es unos 2.6 milisegundos más lenta que ATTR (la precisión de las medidas de tiempo del programa es alta: las medias obtenidas pueden variar, con alrededor del 95% de probabilidad, en +/-115.5 microsegundos de lo mostrado).

Escribir texto ampliado []

Este apartado ha sido elaborado en colaboración con @IvanBASIC, experto programador de juegos en BASIC puro para el ZX Spectrum, como Pedro Pómez, Brain 8 o Rompetechos (aquí pueden descargarse), en los que ha exprimido al máximo éstos y otros trucos.

Como se ha explicado en el primer apartado de esta entrada, el ZX está diseñado para escribir caracteres en pantalla cuyos mapas de bits sean de 8 x 8 píxeles. Sin embargo, a veces es interesante poder escribir con caracteres más pequeños o más grandes. En el primer caso se requiere código en ensamblador, pero el segundo se puede resolver hasta cierto punto en BASIC utilizando la sentencia LPRINT, diseñada originalmente para enviar datos en serie a la impresora ZX.

Entre otras muchas cosas admirables, el ZX dispone de un sistema de comunicación serie universal capaz de manejar muy diversos dispositivos, basado en el concepto de “corrientes” (streams) y “canales” (channels). En resumen (aquí se puede estudiar más a fondo), los canales son análogos a puertos de comunicación con dispositivos hardware junto con sus rutinas de entrada/salida asociadas, y las corrientes son conexiones software que se abren y cierran con esos canales. Se dispone de 16 corrientes (de la #0 a la #15) asignables a 4 canales predefinidos (‘S’ -> parte superior de la pantalla, ‘K’ -> parte inferior de la pantalla y teclado, ‘P’ -> impresora ZX, ‘R’ -> uso interno de la ROM); esta lista de canales puede ampliarse conectando dispositivos hardware externos.

Cuando un ZX Spectrum 16K / 48K arranca, las siguientes corrientes están abiertas: #0 y #1 contra el canal ‘K’, #2 contra el ‘S’, y #3 contral el ‘P’ (el ‘R’ no es accesible desde BASIC). Así, PRINT #0 o PRINT #1 enviarán sus argumentos hacia la parte baja de la pantalla; PRINT #2 hacia la alta (un PRINT normal, por defecto, usa la corriente #2); y PRINT #3 hacia la impresora, lo que puede también conseguirse con la sentencia sinónima LPRINT.

Cada vez que LPRINT tiene una línea de texto que enviar a la impresora (32 caracteres como máximo, al igual que la pantalla), la rutina de salida de datos asociada al canal ‘P’ procesa el mapa de bits de dicha línea de texto (la impresora no puede imprimir colores, así que los atributos se ignoran) y deja los datos procesados en un buffer de memoria en la RAM, de donde supuestamente la impresora los cogerá. Como una línea de texto puede tener un mapa de bits de, como máximo, 8 filas de píxeles por 32 columnas de caracteres, el buffer de impresión tiene un tamaño de 8 x 32 = 256 bytes. Si se imprimen menos caracteres, se usa una porción menor del mismo.

La primera cuestión es cómo se guarda en ese buffer el mapa de bits del texto a imprimir. La respuesta es: primero se almacena en el buffer la primera fila de píxeles (la más alta) del mapa de bits del texto; 32 bytes más adelante del comienzo de eso, se almacena la segunda fila de píxeles; y así sucesivamente hasta terminar las 8 filas de píxeles. Si el texto es más corto de 32 caracteres, las columnas no usadas en el buffer no se escriben (se saltan).

La segunda cuestión es cómo se puede redirigir el proceso de esa rutina de la ROM para que guarde los datos en otro lugar (por ejemplo, en la memoria de la pantalla). Esto es muy fácil de hacer en BASIC, ya que hay una variable del sistema, PR-CC, situada en las direcciones de memoria RAM 23680 y 23681, que almacena dónde comienza el buffer de impresión (byte bajo y alto del comienzo del mismo, respectivamente). Inicialmente, esa variable contiene los valores 0 y 91, que forman la dirección de memoria 23296, pues 0 + 91 * 256 = 23296, pero se pueden cambiar con POKE sin problema. CUIDADO: después de cada sentencia LPRINT, el contenido de PR-CC es devuelto por el sistema automáticamente a la dirección original, 23296 (lo que vuelve a situar el buffer de impresión justo después del mapa de atributos de la pantalla y justo antes de la zona de variables del BASIC, como se puede leer en el manual el ZX Spectrum 16K / 48K).

El truco de LPRINT para escribir caracteres ampliados verticalmente se basa en redirigir adecuadamente el buffer de impresión hacia el mapa de bits de pantalla antes de ejecutar la sentencia. Debido a la organización del mapa de bits de pantalla y a cómo se escriben los datos en el buffer de impresión, si se redirige el buffer hacia la primera fila de píxeles de alguna celda de la pantalla, se conseguirá escribir el texto en pantalla dejando espacios de 7 filas de píxeles intercalados, tal y como muestra este programa tan sencillo:

Nótese que en la línea 10 del programa se sitúa el buffer de impresión en la dirección de memoria 0 + 72 * 256 = 18432, que corresponde con el comienzo de la segunda sección de las tres que componen el mapa de bits de la pantalla, como se explicó en el primer apartado de esta entrada.

El programa anterior ilustra el hecho de que LPRINT envía la primera fila de píxeles del mapa de bits del texto a la dirección a la que apunta el buffer, luego suma 32 bytes a la dirección donde comenzó a escribir esa fila y escribe la segunda fila de píxeles del texto, y así sucesivamente; estos saltos en el buffer de impresión suponen saltos de 8 filas de píxeles en vertical en la pantalla, es decir, va saltando cada vez a la siguiente línea de caracteres.

Por tanto, si repetimos LPRINT con el mismo texto pero situando el buffer de impresión en cada una de las 8 direcciones del mapa de bits de la primera celda, o, equivalentemente, sumamos 1 cada vez al byte más alto de la dirección del mapa de bits de pantalla (la acción (Y) que explicamos en el primer apartado de esta entrada), conseguiremos el efecto de “caracteres estirados”.

El siguiente programa hace exactamente eso, cambiando antes de cada repetición de LPRINT la dirección del buffer mediante incrementos de 1 en su byte alto, almacenado en la variable del sistema PR-CC (en 23681). Nótese cómo los caracteres ampliados tienen 8 veces el tamaño vertical original y 1 vez el tamaño horizontal:

Por supuesto, podemos imprimir en otra columna redirigiendo el buffer hacia la primera fila de píxeles de una celda diferente por medio de la acción (X), es decir, incrementando el byte bajo de su dirección (el que almacenamos en el byte bajo de PR-CC, en 23680):

Si durante la impresión cubrimos con el buffer columnas iguales o superiores a la 32, lo que resulta del truco de LPRINT es algo parecido a una rotación dentro del bloque de los caracteres a imprimir, pues aquellos bytes que se salgan “fuera” pasarán a la izquierda de la pantalla y algo más bajos, como se puede observar ejecutando este programa que establece el byte bajo de la dirección del buffer de impresión a algunos valores superiores a 31 (variable b):

Para terminar este apartado, nótese que la velocidad de ejecución de este truco es similar a la de PRINT pero multiplicada por 8. De hecho, si imprimimos 8 veces el mismo texto con cualquiera de las dos sentencias no observamos diferencia, como muestra este programa, que escribe un texto de longitud 9 y mide 0.18 segundos en ambos casos, es decir, tarda unos 20 milisegundos por carácter (incluyendo el tiempo de ejecución del FOR):

Esta velocidad de impresión puede mejorarse ligeramente usando el mismo truco del punto y coma que comentamos en el apartado de impresión de caracteres, lo que me ha señalado también @igNaCoBo. Si ponemos un punto y coma al final de la sentencia LPRINT, ésta no hace el trabajo de cambiar de línea, que en su caso consiste en vaciar el buffer de impresión, por lo que mejora sus tiempos. El buffer será reescrito con el siguiente LPRINT.

Escribir atributos de color []

Este apartado ha sido elaborado en colaboración con @IvanBASIC, experto programador de juegos en BASIC puro para el ZX Spectrum, como Pedro Pómez, Brain 8 o Rompetechos (aquí pueden descargarse), en los que ha exprimido al máximo éstos y otros trucos.

El hecho de que la memoria de pantalla del ZX Spectrum esté dividida en dos partes almacenadas independientemente, el mapa de bits y el mapa de atributos, como se ha explicado en el primer apartado de esta entrada, da la posibilidad de realizar operaciones gráficas sólo con una de las dos. Así, muchos programas manipulan sólo el mapa de bits, ahorrando el valioso tiempo que se iría en mantener también actualizados los atributos (algo muy común en los primeros juegos desarrollados para el Spectrum, pero también en los realizados hoy en día en BASIC puro).

Aunque es más raro, también se puede manipular sólo el mapa de atributos; a cambio de perder una resolución considerable (de 192 x 256 píxeles pasamos a 24 x 32 celdas), se consigue un aumento de velocidad proporcionalmente importante. Con mucha creatividad, el efecto conseguido puede ser interesante. Por poner un ejemplo muy básico: usando el bit de parpadeo de los atributos se pueden animar un par de rótulos en pantalla, como hacía el maravilloso “Manic Miner” de 1983:

Lamentablemente, para manipular conjuntos de atributos en tiempo real no existe ninguna instrucción BASIC (salvo POKE), lo que reduce la eficiencia porque obliga a utilizar bucles FOR, que son muy lentos, o complica bastante el código si se usan técnicas como el desenrollado de bucles, explicadas en otras entradas de esta serie.

A pesar de eso, se puede engañar al sistema utilizando trucos como el del DEFADD descrito en la entrada anterior. En ésta añadiremos a nuestro arsenal un truco basado en LPRINT similar al explicado en el último apartado con el fin de escribir conjuntos de atributos en pantalla de forma muy rápida. A continuación explicamos cómo se hace y qué limitaciones tiene.

Si redirigimos el buffer de impresión hacia una dirección en el mapa de atributos, por ejemplo, a la celda de atributo localizada en 22784 (es decir, si hacemos POKE 23680,0 y POKE 23681,89, ya que 0 + 89 * 256 = 22784), los bytes que LPRINT envíe al buffer se almacenarán como atributos de color:

Sin embargo, se observa que, aunque el relleno de 8 x 18 celdas de atributos se consigue hacer rapidísimamente (una sola orden LPRINT), el resultado no tiene mucho sentido. Esto se debe a que LPRINT escribe en el buffer de impresión los bytes correspondientes al mapa de bits del texto de 18 caracteres "Esto no colorea...". Esos bytes, al interpretarse como atributos de color, no producen nada útil: no eran números pensados para representar atributos de color, sino mapas de bits de caracteres.

En la imagen de arriba, cada tira vertical de 8 atributos de color corresponde al mapa de bits de uno de los caracteres del texto; por ejemplo, la primera tira vertical son los 8 bytes del mapa de bits de la letra "E" visualizados como atributos de color. Si en lugar de "E" hubiéramos hecho LPRINT "A" usando este truco, se escribirían como atributos los correspondientes a los bytes que definen el mapa de bits de la letra "A", que son 0, 60, 66, 66, 126, 66, 66 y 0:

Este programa BASIC escribe previamente algo en el mapa de bits (línea 6 del programa); como se observa, la manipulación de atributos se hace independientemente de dicho mapa de bits, por lo que sólo cambiarán los colores de lo que hay allí, no las formas.

Está claro, por tanto, que para que este truco produzca algo interesante debemos hacer que los bytes del mapa de bits del texto que imprimimos sean los atributos de color que queremos almacenar en pantalla. O sea, que el texto a imprimir debe estar compuesto de caracteres diseñados por nosotros de forma que sus mapas de bits se correspondan con los atributos que queremos. En BASIC, esto puede hacerse mediante gráficos definidos por el usuario (UDGs).

Por ejemplo, si queremos hacer un “arco iris Spectrum” en pantalla manipulando sólo los atributos de color, usando colores de papel que vayan desde el 0 hasta el 7 en vertical y repitiéndolos a lo largo de toda la pantalla en horizontal, los atributos a escribir por cada columna en el mapa de atributos serían 0, 8, 16, 24, 32, 40, 48, 56 y 64. Podemos definir por tanto el UDG “A” con esos números y hacer LPRINT de ese nuevo carácter repetido 32 veces, como se muestra en el siguiente programa (el carácter extraño de la línea 20 es precisamente la forma o mapa de bits del UDG "A" que hemos definido en la línea 6; aparece así por haber capturado la imagen después de haber ejecutado el programa):

Se puede conseguir un scroll horizontal rotando la cadena de texto que se imprime, como hace el siguiente programa, donde hemos insertado algunos atributos diferentes del arco iris para que se note dicho scroll:

Hay que tener en cuenta en este truco que mediante el POKE que cambia el byte alto de la variable del sistema PR-CC (23681) sólo podemos apuntar el buffer de impresión a tres secciones diferentes del mapa de atributos (haciendo POKE 88, 89 y 90, respectivamente). Afortunadamente, y al contrario que en el mapa de bits, podemos poner el byte bajo (23680) a cualquier valor desde 0 hasta 255; el módulo 32 de dicho valor (desde 0 hasta 31) cambiará la posición horizontal de pantalla en que imprimimos el atributo, y el resto, junto con el byte alto, establecerá la fila y por tanto la celda concreta donde se iniciará la tira vertical de 8 atributos (¡hay que tener cuidado de no salirse del mapa de atributos!).

Además, modificando el byte bajo de PR-CC también se puede hacer scroll horizontal de atributos, como se ilustra con este programa:

La principal ventaja del truco del LPRINT para atributos es su velocidad. A partir de los ejemplos que hemos explicado en este apartado se puede experimentar con otras cadenas de texto y distintos valores de la dirección del mapa de atributos a apuntar con el buffer de impresión. En general, requiere mucha práctica encontrar efectos o programar escenarios (mapas) para movernos en ellos, y serán necesarios lápiz y papel para hacer esos diseños, luego transformarlos en valores numéricos de atributo y finalmente crearlos como UDGs.

.oOo.

[Click here to read this in Spanish ]

This is the fifth and last one 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. Some statements and time measurements

V. Screen operations based on characters

In this last post of the series we will talk about the ZX Spectrum screen, and how to speed up some character printing operations on it when programming in Sinclair BASIC. We do not talk here about drawing with pixels (PLOT, DRAW, …); for that, please refer to the last post. Also, the DEFADD trick to move memory blocks (useful for screen operations as well) was described in that post too.

To navigate through this post more easily, these are the sections it contains:

1. The screen and the printing of characters. On the layout of the display memory and why the efficiency in printing characters was so important for its design.
2. Printing characters. Sprites in BASIC, control characters, screen compression (with some suggestion by the BASIC game programmer @igNaCoBo).
3. Reading characters. Execution times of SCREEN$ and ATTR.
4. Printing scaled text. How to print zoomed in characters with the LPRINT trick (in collaboration with the BASIC game programmer @IvanBASIC).
5. Printing colour attributes only. How to manipulate the colour attributes of the screen independently from their characters with the LPRINT trick (in collaboration with the BASIC game programmer @IvanBASIC).

The screen and the printing of characters

Direct writings and readings in the ZX Spectrum screen memory are not very common in BASIC, but it is important to know how that memory is organized in order to understand some techniques that can speed up programs (like the LPRINT trick explained further on, or the limitations of the DEFADD trick, explained in the previous post, when it is used on the screen). In older posts of this blog (such as this and that) I already explained some of the characteristics of ZX graphics; here I focus on why they have that particular memory organization and what operations are more efficient that way.

The first decision made during the design of the original ZX graphic system was related to the importance of writing text on the screen and the lack of dedicated hardware to do so (the burden was on the CPU): to begin with, fixed size text characters should be used for alleviating that burden, in particular of 8 x 8 pixels.

The second decision had to do with the necessity of displaying a bunch of colours to honour the ZX name, unlike its black and white predecessor, the ZX 81. Unfortunately, doing so for every pixel separately would have driven the price up to a completely prohibitive cost. A sensible approach back then was to provide the minimum required for writing text, that is, to take blocks of 8 x 8 pixels as the spatial granularity for colour, using the smallest amount of memory for storing the colours of the pixels in those blocks since most of the time they would be used to display text characters.

Consequently, just 1 byte was stored for each 8 x 8 pixel block, called the “attribute” of that screen “cell”, as I explained here and it is illustrated in the figure below. The visible character was drawn on the TV display by using that “attribute” along with a bitmap consisting of 8 bytes (shown on the left of the figure) with bits set to 0 for indicating “paper color” and to 1 for “ink color”.

Due to this, the ZX Spectrum screen memory was split into two parts, separately stored but related to each other, that were periodically read by the hardware (concretely, by the ULA) in order to refresh the TV display:

• The bitmap, that stores the “shapes” or, if you prefer, the “black and white drawings” of all characters that can be written on the screen (24 lines times 32 columns of characters). It starts at address 16384 (right after the end of the ROM). It occupies 6144 bytes (24 lines of characters times 8 pixels of height per character = 192 pixel rows, with 32 character columns of 1 byte each).
• The attribute map, that stores the colour attributes for those characters. It starts right after the bitmap, at address 22528. It has 768 bytes (24 lines times 32 columns of colour attributes, 1 byte per attribute).

The third decision is the most important one for us in this series of posts, because it is the one responsible for the (in)efficiency of the direct accesses to the screen memory when working with anything either smaller or larger than one text character. Since the CPU, that is, the software, was in charge of all character writing, that work had to be done as fast as possible. And where was the greatest time cost? In writing the 8 bytes of the bitmap of a character in the screen memory (its attribute is just 1 byte!). And what calculations were the most frequent ones when writing those bitmap bytes? Basically two, that we denote as (Y) and (X) for reasons that will be clarified later on:

• (Y) To calculate the memory address to store the next byte of the bitmap of a given character (that is, to go 1 pixel row down on the screen bitmap).
• (X) To calculate the memory address to store the bitmap of the next character of the text (that is, to go 1 column to the right on the screen bitmap).

The former is needed to store the 8 bytes of a character bitmap in the screen memory in order to be displayed by the ULA on the TV, and the latter to start doing the same to the next character of the text.

Both operations involve to increment memory addresses, and memory addresses are positive integer numbers. The Z80 CPU fastest machine instructions to increment such numbers are INC, which add 1 to an integer; they are specially fast when the number fits into 8 bits. Therefore, if it was possible to do action (Y) by adding 1 to an 8 bits number and action (X) by adding 1 to another one, writing text on the screen would be as fast as it could be.

Well, a Z80 memory address is a positive integer number of 16 bits, and the Z80 finds extremely easy to work with most 16 bits numbers as though they are composed of two independent numbers of 8 bits, called the most significant or “higher” byte of the address and the least significant or “lower” one. Consequently, it can do two independent 1-unit increments on a 16 bits memory address very fast. If incrementing the higher byte of the address gets the pixel row of the character bitmap down and incrementing the lower byte of the address gets the column of the character bitmap one column to the right, where the next character in the text must be stored, everything would be sorted out.

That is exactly what the screen memory designers of the ZX did.

With that design, we have 2 cursors that we can move independently on the screen bitmap: one is horizontal (character columns; it moves by incrementing the lower byte of the memory address; it can take 32 different values -columns-, that need 5 bits to be represented) and the other is vertical (pixel rows; it moves by incrementing the higher byte of the memory address; we can move it along 192 different values, that need 8 bits to be represented). Something like this:

However, with this design we are only using 5 bits from the lower byte of the memory address to do action (X), therefore there are unused 3 bits in that byte, which would produce “gaps” in the screen memory (addresses that we would never consider), and that must be avoided. Moreover, if we use this design, the memory address of the first byte of the screen bitmap would be located at 0, which is not RAM…

The solution was to move part of the vertical cursor bits, stored in the higher byte of the memory address, to the lower byte (we can only move 3 bits). We cannot move the least significant bits of the higher byte, because they are the ones involved in action (Y), thus we have to use the most significant bits. That has an added benefit: it will release bits 15, 14 and 13 of the memory address, and they can be set to the binary value 010, which makes the first screen bitmap address, where both cursors are 0, to be 16384 exactly (all the bitmap addresses will have the same value in those bits). The design is now like this:

Moving the 3 most significant bits of the vertical cursor (that is, its bits 5, 6 and 7) to the lower byte of the memory address we would leave 5 bits of the higher byte for that cursor (in addition to the constant bits 010). With those 5 bits you could increment 32 times the vertical cursor value before it overflows, which means that, doing action (Y), you could cover 4 rows of text before having to modify at all the 3 bits that we moved to the lower byte.

The problem is that, once the 32 possible values of the horizontal cursor (X) are spent, we change the higher bits of the vertical cursor (Y7, Y6, Y5), which means that, after incrementing the last horizontal column (31), we jump 4 rows of characters below the current one, which is of little use and weird.

It would be much more natural that, after incrementing the last horizontal column in the screen, the vertical cursor would go to the next character row below. For doing that, they decided to move bits 3, 4 and 5 from the vertical cursor to the lower byte of the memory address, instead of bits 5, 6 and 7. In that way, the vertical cursor in the higher byte of the memory address overflows after doing action (Y) only 8 times (which is enough to access all bytes of the bitmap of one character), but a natural change in the character line is achieved when reaching the last column:

This design has an unexpected effect: when considering which parts of the screen correspond to contiguous characters in memory, we are splitting the bitmap into 3 contiguous sections of 8 character rows each corresponding to the 3 values that the bits 6 and 7 of the vertical cursor may store (they cannot store the binary value 11 because there are only 192 lines of pixels in the screen, not 255). This is the reason why when a screen is loaded from tape, it appears on the TV display in a so weird sequence of pixel lines.

It also has a couple of important drawbacks. To begin with, it requires more complicated calculations for operations different from (X) and (Y), as it is explained, for instance, here. Also, it imposes limitations to the fast memory copies of the DEFADD trick, explained in the previous post of this series, when used to put graphic blocks on the screen or to do scroll. But all in all, the advantages for writing characters in a fast way overweigh these inconvenients.

Everything explained in this section can be shown with this simple BASIC program, that writes on the bitmap sequentially; you can visualize how these values are distributed in memory. The program also illustrates the much simpler linear organization of the attribute map:

Printing characters []

The ZX Spectrum BASIC language has statements to print characters on the screen which hide the details explained in the paragraphs above. Nevertheless, printing characters on screen is essential in any BASIC program for the ZX, and thus understanding their (in)efficiency and providing some useful hints to accelerate them is needed.

In the case of printing sprites, i.e., a contiguous set of characters with certain width and height (usually composed of UDGs), it is not convenient to use FOR to scan and print every character due to the extra computation time and program space in memory; instead, you may think of embedding within the characters of the sprite some that control the printing position. The ZX ROM prints this kind of embedded control commands very fast, much much more than the equivalent explicit statements.

Alas, unfortunately the interpreter does not implement correctly the control characters in charge of directional movements (arrows). The left/right controls have some bugs, and the up/down ones do not work. Only if we print always at the same absolute place on the screen we can do it fast through the control character AT (22). For the rest of cases, coping with the lack of directional control characters requires to rely on loop unrolling techniques, that we explained in previous posts.

This short program illustrates some of the problems of the interpreter to use the directional control characters:

There is however a practical use of control characters when printing sprites: color control (and bright, flash, etc.). With them we can avoid the use of the INK, PAPER, etc. statements, which are much slower to run and require to evaluate additional expressions (their arguments). Also, we save program memory space. The drawback is that the listing of the program code gets messed up when seeing it in the ZX editor, but that has no effect during execution.

To get an estimate of the time spent in printing a sprite of certain size, you can run this program:

The program repeats the printing of square blocks of characters on the screen with diverse sizes, measuring the time taken for each of those sizes. The resulting average times are shown in this graph:

This behaviour can be split into three aditive components: the main one, clearly quadratic (470 microseconds times the total number of characters to print), comes from the very printing; the secondary, linear (17 milliseconds due to the height in characters) is produced by the loop in line 20, in charge of printing each of the rows of characters; the last one, constant (the vertical offset of about 12 milliseconds) is due to the rest of work in the loop (expression evaluations, etc.), that is always the same, unregarding the size of the sprite.

As you can see in the graph, in general, to get 25 fps or more you can only print one character (not considering the time to erase the sprite, which halves that frequency); moving to 2×2 sprites (without colour control, which would increase their size), you can only get 20 fps; below 8 fps with 6×6 sprites (or their equivalent: 2×2 sprites with ink colour controls inserted for each character); and so on. In practice, sprites larger than 2×2 with embedded colour control characters take more time than the one available in most situations.

Notice that the data shown in the graph do not only serve for estimating how long will take to print a square sprite on average, but can be used for any set of characters we need to print, with any dimensions. For instance, printing one horizontal line of 32 characters (no control codes) would take mainly 470 x 32 = 15.04 milliseconds if we do not consider the time taken by constant-time operations (expressions and the like), because it would be similar to not having the printing row loop and therefore discarding the linear component in the formula. Another example would be to print the entire screen (let say 24 x 32 characters, maybe some of them control characters) with one PRINT statement, which we could expect to take mainly 470 x 24 x 32 = 360.96 milliseconds or, if we do one PRINT for each line using a FOR loop, 0.470 x 24 x 32 + 17 x 24 = 768.96 milliseconds.

You can get a little improvement while printing characters, suggested to me by the BASIC games programmer @igNaCoBo (he used it in its game ArkanoidB2B): you can end the PRINT command with a semicolon (;) in order to avoid the change to a new line that the interpreter does automatically if the semicolon is not present. To do a new line takes longer than interpreting the semicolon. The above BASIC program can be modified to measure that difference: just insert the semicolon at the end of the PRINT statement in line 20. The time differences with the original program are shown in these figures:

It is shown that, on average, a PRINT statement takes 364 extra microseconds in doing the new line with respect to interpreting the semicolon (bottom histogram). This may be little, but if the statement repeats (e.g., to draw a sprite), the gain accumulates linearly, as shown in the top figure (the middle figure shows the same info as the bottom one but spread along all the sizes of the sprite that have been tested).

Besides this little improvement, printing can also be made more efficient when we have to print a sequence of spaces. If they are more than 3, and must end at a known column, it is convenient to use the TAB control character instead of the spaces, which automatically prints them until reaching the column (the TAB control char plus the argument are 2 bytes only, and no expression evaluation is involved). The ZX-Basicus analysis tool (-a) can help in this sense since it locates the text literals that contain sequences of contiguous spaces.

Also, sequences of contiguous spaces can be substituted by the COMMA control character, but that is less flexible: it prints spaces until reaching the next half of the screen with respect to the current cursor position.

Of course, you should not print spaces individually to clear the screen, but use CLS, or, alternatively, print a number of COMMA control characters that fill it. You can use this “trick” also to fill parts of the screen with graphics (either built-in graphic blocks or UDGs) faster than printing them one by one.

Regarding what we explain in the last paragraph, there is a trick to fill the entire screen with any character in a very fast way: it consists in redefining the space character temporarily; when TABs or COMMAs are used, the interpreter will not print blanks, but the character defined by us. For instance, to fill the screen with bricks, just run the following program (the 44 commas in line 30 fill the 22 rows of the screen with spaces; the POKE in 23606 and 23607 tell the system that it has to use a new charset whose first character, i.e., space, is at the UDG “A” that we define in line 20):

Finally, the synthesizer tool included in ZX-Basicus can compress screens using the tricks explained before (option --comprscr), generating automatically their binary data (new charset definitions, definition of the fake variable that will contain the screen using the DEFADD trick explained in the previous post) and the BASIC programs that use them.

Reading characters []

In games it is very useful to read some screen position and tell which character is printed there, or which attribute is used there; in that way, the program can decide whether there has been a collision between sprites, for example.

Both ATTR (attribute map) and SCREEN$ (bitmap) functions are aimed to solve that problem, and they are quite efficiently implemented in ROM. They cannot be greatly accelerated beyond using only integer literals as their arguments.

ATTR is faster, though, since it does not interpret the bitmap to deduce the character, thus it should be the preferred collision-detection method. This can be tested with the following program, that takes about 2 minutes in finishing and producing a precise and accurate time measurement:

If we run it first with SCREEN$ and then with ATTR (not changing anything else in the code), the differences between both time measurements will be due to the ones in those functions only. The results show that, on average, SCREEN$ is around 2.6 miliseconds slower than ATTR (the precision in the time measurements of this program is high: the averages may be, with approximately 95% of probability, around +/-115.5 microseconds from the values shown).

Printing scaled text []

This section has been created in collaboration with @IvanBASIC, an expert programmer of pure BASIC games for the ZX Spectrum, such as Pedro Pómez, Brain 8 or Rompetechos (you can download them here), in which he has made the most of these and other tricks.

As we explained in the first section of this post, the ZX Spectrum is designed to write characters of 8 x 8 pixels on the screen as fast as the Z80 CPU can do it. However, sometimes it is interesting to write smaller or larger characters. The former requires assembly programming, but the latter can be addressed, to some extent, by using the LPRINT BASIC statement, originally designed to send data to the ZX printer in a serial fashion.

Among many remarkable things, the ZX has an universal serial communication system able to deal uniformly with very diverse devices. It is based on the concepts of streams and channels. In short (here you can find more details), channels are communication ports corresponding to specific hardware devices, along with their input/ouput data processing routines, while streams are software connections that can be opened and closed to those channels on the fly. There are 16 available streams (from #0 to #15), that can be associated to 4 pre-defined channels (‘S’ -> upper screen, ‘K’ -> lower screen and keyboard, ‘P’ -> printer, ‘R’ -> ROM internal use); the list of channels can be expanded by connecting other external hardware devices.

When a ZX Spectrum 16K / 48K starts up, the following streams are opened: #0 and #1 for channel ‘K’, #2 for channel ‘S’, and #3 for channel ‘P’ (channel ‘R’ is not accessible from BASIC). Thus, PRINT #0 or PRINT #1 will send their arguments to the lower part of the screen; PRINT #2 to the upper part (a conventional PRINT, by default, uses stream #2); and PRINT #3 to the printer, which can also be done using its synonym LPRINT.

Each time LPRINT has a text line to send to the printer (32 characters at most, the same that the screen), the output data routine associated to channel ‘P’ processes the bitmap of that text line (the printer cannot deal with colours, thus attributes are ignored) and leaves the processed data into a memory buffer in RAM, from which the printer takes them. Since a text line may have a bitmap of, at most, 8 pixel lines times 32 character columns, the printer buffer will occupy a maximum of 8 x 32 = 256 bytes. If LPRINT prints shorter lines, it fills a smaller portion of the buffer.

The first interesting point here is how the bitmap of the text line is stored in the printer buffer: the first pixel line of the bitmap of the text (the one at the top) is stored in the buffer, which amounts to, at most, 32 bytes; 32 bytes after the first of those bytes is where the second line of pixels is stored; and so on until storing the 8 lines of pixels of the text bitmap. If the text is shorter than 32 characters, the columns that are not used in the buffer are not filled with anything.

The second interesting point is how can we redirect the process of that output routine in order to store the data in a different place (for instance, in the screen memory). This is really easy in BASIC, since there is a system variable, PR-CC, placed at RAM addresses 23680 and 23681, that stores the start address of the printer buffer (higher and lower bytes, respectively). Initially, that variable contains the bytes 0 and 91, that form the memory address 23296 because 0 + 91 * 256 = 23296, but they can be changed at any time using POKE. Take into account that, after each LPRINT statement, the content of PR-CC will be set automatically to its original value, 23296, which places the printer buffer right after the attribute map of the screen and before the system variables area of BASIC, as you can read in the ZX Spectrum 16K / 48K manual.

The LPRINT trick to write vertically scaled characters is based precisely on redirectly the printer buffer adequately to the screen bitmap memory before executing the statement. In particular, due to the organization of that memory and how the printer buffer is filled with data, if the redirection is done to the first line of pixels of some screen cell the text will be printed on screen, but with 7 pixel lines between each pair of lines of the text bitmap, as shown by this simple program:

Notice that in the line 10 of the program the printer buffer is placed in the memory address 0 + 72 * 256 = 18432, that corresponds to the first cell (and pixel line) of the second section of the screen bitmap, out of the three sections that constitute the screen explained in the first part of this post.

This program illustrates how LPRINT sends the first pixel line of the text bitmap to the start of the printer buffer, then adds 32 bytes to the first address used for that, writes there the second pixel line, and so on; the jumps of 32 bytes in the printer buffer are jumps of 8 pixel lines (vertically) on the screen bitmap; in other words, we are jumping to the next character row of the screen with each one of them.

Consequently, if we repeat LPRINT with the same text but placing the printer buffer in each one of the 8 pixel addresses of the first cell used above, or, equivalently, if we increment the higher byte of the screen bitmap address at each repetition (the (Y) action explained in the first part of this post), we will enlarge vertically the text.

The following program does exactly that: before each repetition of LPRINT, it moves the printer buffer (increments its higher byte, stored in the higher byte of the system variable PR-CC, at 23681). Notice how the enlarged characters have 8 times their original vertical size and 1 time their original horizontal size:

Of course, we can print at other column just by placing the printer buffer in the first pixel line of a different cell, doing action (X), that is, by incrementing the lower byte of the screen bitmap memory address where the printer buffer is placed (the byte stored in the lower byte of PR-CC, at 23680):

Furthermore, if, during the printing, the buffer covers columns beyond 31, LPRINT produces a sort of rotation of the text to print, because those bytes that fall “outside” (on the right) will go back to the left of the screen, and a little bit below, as you can observe by running this program (the lower byte of the printer buffer is established through variable b):

To end this part, notice that the execution speed of this trick is similar to the one of PRINT times 8. Actually, if we print 8 times the same text using any of these two statements, there is no clear difference in their times, as the following program shows: it writes a text of 9 characters, and measures 0.18 seconds in both cases, that is, it takes about 20 milliseconds per character (including the times involved in the FOR loop management):

This speed can be slightly improved using the same trick of the semicolon commented above in the section about printing characters, which has been pointed out to me by @igNaCoBo. If you write a semicolon at the end of LPRINT, the statement does not perform the new line change, which actually consists in clearing the printing buffer, and that saves some time. The buffer will be overwritten in the next LPRINT.

Printing colour attributes only []

This section has been created in collaboration with @IvanBASIC, an expert programmer of pure BASIC games for the ZX Spectrum, such as Pedro Pómez, Brain 8 or Rompetechos (you can download them here), in which he has made the most of these and other tricks.

The fact that the ZX Spectrum screen is split into two parts stored separately, the bitmap and the attribute map, as explained in the first section of this post, give us the opportunity of performing graphical operations only in one of them. Actually, many programs work with the bitmap only, saving valuable time that would otherwise be spent in keeping the attributes updated (this was very common in the first games developed for the Spectrum, but also in pure BASIC programs written today).

Although more unusual, we can also work with the attribute map only; even losing considerable resolution (from 192 x 256 pixels to 24 x 32 cells), the proportional speed up is worth it, and with some creativity we can get very interesting effects. Just as a very basic example: using the flash bit of the attributes we can animate a banner on the entire screen, like the wonderful “Manic Miner” did in 1983:

Regretfully, there is no BASIC statement to manipulate groups of attributes in real time (except POKE), which reduces efficiency since forces us to use FOR loops, that are very slow, or makes the code much complicated by using techniques like loop unrolling, explained in other posts of this series.

In spite of that, we can cheat the system by using tricks like the DEFADD one described in the previous post. Here we add to our toolkit another based on LPRINT, similar to the one of the previous part of this post, to write blocks of attributes on the screen very fast. In the following we explain how it is done and what limitations it has.

The trick consists in redirecting the printer buffer to the screen attribute map. If we do that, for example, pointing to the middle part of the screen, that has its first attribute cell at address 22784 (that is, if we do POKE 23680,0 and POKE 23681,89, since 0 + 89 * 256 = 22784), the bytes sent by LPRINT to the printer buffer will be used as colour attributes as this program shows:

You can observe how, in spite of the speed of filling 8 x 18 attribute cells with just one LPRINT statement, the result has not much sense. This is because LPRINT writes in the printer buffer the bytes corresponding to the bitmap of the 18 characters text "Esto no colorea..." ("This does not colour..." in Spanish). Those bytes, when interpreted as colour attributes, does not produce anything useful: they were not numbers intended to represent colours, but character bitmaps.

In the above picture, each vertical stripe of 8 colour attributes comes from the bitmap of one of the text characters; for instance, the first stripe are the 8 bytes of the bitmap of the character "E" visualized as colour attributes. If we would have done LPRINT "A" using this trick, the attributes would be the ones of the bitmap of the character "A", that is, 0, 60, 66, 66, 126, 66, 66 and 0:

This BASIC program writes to the screen bitmap before doing the attribute trick (see line 6 in the listing); as you can observe, the attribute manipulation is done independently from the screen bitmap: only colours change on that area, not the written characters.

Consequently, for this trick to do something interesting, we must make the bitmap of the written text equal to the colour attributes we wish to store in the screen. In other words, the text to print must consists of characters designed by us in such a way that their bitmaps corresponds to the desired attributes In BASIC, this can be done with user degined graphics (UDGs).

For example, to draw a “Spectrum rainbow” on the screen by only manipulating attributes, using paper colors ranging from 0 to 7 vertically and repeating that pattern along the entire screen horizontally, the attributes to use at each stripe would be 0, 8, 16, 24, 32, 40, 48, 56 and 64. We can thus define the bitmap of the UDG “A” with those numbers and do LPRINT of that character 32 times, as the following program does (the strange character in line 20 is precisely the bitmap of the UDG "A" defined in line 6; it already appears in its user defined shape because we have captured the screen after running the program):

You can also do horizontal scroll by rotating the text string printed by LPRINT, as the next program does (we have inserted in the string some random characters for the animated scroll to be visualized):

When using this trick, notice that the POKE that changes the higher byte of the system variable PR-CC (23681) can only redirect the printer buffer to three different sections of the screen attribute map (POKE 88, 89 or 90, respectively). Fortunately, and unlike in the bitmap, we can set the lower byte (23680) to any value within 0 and 255; that value modulus 32 (which will range from 0 to 31) will change the horizontal position where we print the attribute on screen, and the rest, including the higher byte, will set the row and therefore the particular cell where the vertical stripe of 8 attributes will be printed (take care not to go beyond the screen attribute map!).

Moreover: by changing the lower byte of PR-CC you can do horizontal attribute scroll, as illustrated below:

The main advantage of the attribute LPRINT trick is its speed. Starting with the examples we have included in this part of the post you can experiment with other text strings and different redirections of the printer buffer. In general, it requires practice to find novel effects or program scenarios (game maps) for moving along them, and pen and paper will be necessary for making the designs, transforming them into numerical attribute values, and create the UDGs.

The answer to this all-time question is not actually complicated, but it is rare to find the real reasons for it since they require a lot of experience and insight in programming. Intuitively, the fomer does seem better than the latter, because, after all, visual things are more pleasant to the eye!

In my opinion, the best and more truthful explanation of why visual programming languages are not better than textual ones for practical coding (except in particular scenarios, see below) goes like this:

1. The end goal of visual programming is to make programming simpler, more manageable than textual code writing.
2. The only way of making something simpler is to drop unnecessary details (complexities) in the code.
3. Unfortunately, in any kind of programming, those details are as a necessary part of the code as any other; morevover, usually they are the ones that are more difficult to represent graphically or more likely to not produce any gain by being represented that way (e.g., assigning values to variables or writing expressions).
4. If those details are abstracted away, the program gets incomplete and cannot run; if those details are reintroduced in visual form, the program gets cluttered and difficult to understand, definitely not easier than text programming.

Besides, we cannot ignore the fact that textual programming is visual: a text is arranged on a plane just as visual programs do, and many of its structures have geometrical layouts enforced by indentation, syntax highlighting and segment folding (provided by the code editor), names formatting, visual signs like comment marks, etc. How much more visual can it get without losing completeness —while reducing complexity?

Halt there! I am not saying that visual programming languages are useless! Actually, there exist a lot of them out there for a diversity of purposes… For instance, they are good for designing (abstract) programs, or for specifying some of their underlying or implicit structures, or for coding in very particular dominions.

What I say is that when it comes to write a complete computer program that can be run on its own, they almost always must be complemented with certain textual coding, and, therefore, if a suitable (and delicate) balance is not achieved, the effort of that, plus the effort of maintaining correctly synchronized a software that exists at the same time in two different ontologies (visual / textual), are simply not worthy.

[Click here to read this in English ]

Éste es el cuarto 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. Funcionalidades diversas y medida del tiempo

V. Operaciones en la pantalla basadas en caracteres

En esta entrega hablaremos sobre la eficiencia de algunas funcionalidades importantes que ofrece el ZX Spectrum para los programadores en Sinclair BASIC, así como de la medida del tiempo de ejecución en los programas. Las operaciones de pantalla basadas en caracteres las dejamos para la siguiente entrada.

Para navegar más fácilmente por la entrada, éstos son los apartados que contiene:

1. Dibujar. Tiempos de ejecución de PLOT, DRAW, CIRCLE, POINT.
2. Leer el teclado. Tiempos de ejecución de INKEY$, PEEK (LAST_K) e IN (254).
3. Crear UDGs. Cómo disimular el tiempo de definición de los UDGs.
4. Copiar datos en memoria. El truco del DEFADD para copias rápidas de bloques de memoria.
5. Medir el tiempo de ejecución. De cualquier sentencia o parte de un programa BASIC.
6. La influencia de los conflictos CPU/ULA. Estos conflictos pueden retrasar (ligeramente) la ejecución del BASIC.

Dibujar

Especialmente sensibles en cuanto a velocidad de ejecución son las sentencias gráficas de dibujo (PLOT, DRAW, CIRCLE), como sabe cualquiera que haya programado lo más mínimo en este lenguaje. DRAW cuando dibuja arcos, y CIRCLE siempre, utilizan cálculos en coma flotante repetidamente, lo que las hace muy lentas a pesar de que sus implementaciones en la ROM están optimizadas. PLOT no es ineficiente en sí mismo (si se le pasan expresiones enteras, evitando así el cálculo en coma flotante), aunque para dibujar con PLOT algo decente hay que hacer muchos PLOT, y, por tanto, el coste se multiplica. DRAW utiliza el algoritmo de Bresenham para líneas rectas, el cual es bastante eficiente porque además no llama al calculador, pero, al igual que el resto de rutinas, tiene que establecer también los atributos de pantalla por los que pasa, además del modo (INVERSE, OVER), lo que lo enlentece.

Con el siguiente programa se pueden estimar los tiempos que tardan PLOT, POINT y DRAW cuando se llaman con parámetros numéricos literales enteros (y no usan modos de escritura especiales ni colores):

Los tiempos medios obtenidos por este programa para cada llamada individual a una de estas sentencias son: PLOT, 7.274 milisegundos; POINT, 9.208 milisegundos; DRAW (línea horizontal de 255 píxeles), 55.16 milisegundos; DRAW (línea vertical de 175 píxeles), 26.89 milisegundos. Curiosamente, trazar líneas verticales es mucho más rápido que hacerlas horizontales (el doble de rápido, a pesar de que las verticales que dibuja el programa tienen casi un 70% de la longitud de las horizontales), y PLOT es más rápido que POINT.

En cuanto a CIRCLE, modificando el programa anterior para que repita 100 veces este comando con distintos radios, obtenemos estos tiempos medios:

La figura muestra claramente cómo la rutina CIRCLE de la ROM divide la circunferencia en varios arcos que resuelve con líneas rectas, lo que produce los “escalones” que se observan (usa distinto número de divisiones de la circunferencia para distintos rangos de valores del radio; por ejemplo, usa el mismo número de escalones para radios entre 40 y 50 píxeles aproximadamente).

Despreciando el efecto cuadrático por su poca importancia en la ecuación, hacer círculos con parámetros enteros resulta aproximadamente proporcional al radio (o a la circunferencia), de forma que tarda unos 15 milisegundos más por cada incremento de 1 píxel en el radio. Nótese que los tiempos del eje vertical son muy elevados: incluso con círculos muy pequeños (1 píxel de radio), sólo podrían dibujarse 3 en 1 segundo…

En resumen:

Las rutinas de dibujo —y las de consulta gráfica, como POINT— deberían usarse esporádicamente, con argumentos enteros, y en lugares que no tengan requisitos de velocidad elevados, dando preferencia en todo caso al dibujo rectilíneo.

Leer el teclado []

Hay 3 formas de leer el teclado en BASIC: INKEY$, PEEK 23560 (variable del sistema LAST_K) e IN de cualquier puerto cuyo byte bajo sea 254. Para saber cuál es la más rápida se puede probar el siguiente programa, cambiando la forma en cuestión por la que queramos (su ejecución tarda unos 10 minutos):

El último número mostrado en pantalla al terminar es el tiempo en segundos que tarda una de las 10000 iteraciones del bucle, lo que involucra la lectura de teclado y otras cosas (asignación de variable y salto de bucle), pero, si se compara con los resultados de las otras dos formas, siempre usando el resto del programa sin cambios, las diferencias reflejarán únicamente el modo de lectura. En particular, los resultados indican que, de media, INKEY$ es 367.2 microsegundos más lenta que las otras dos, que básicamente son indistinguibles entre sí con la precisión conseguida por el programa (las medias de tiempo obtenidas están, con alrededor de un 95% de probabilidad, en +/-36.5 microsegundos de la media).

Crear UDGs []

La creación de gráficos definidos por el usuario (UDGs), si se hace mediante lectura de sentencias DATA en lugar de cargarlos de cinta, es bastante lenta (y, si se hace desde cinta, también ;P), debido al propio bucle, a la lectura de los DATA y a que tendremos que actualizar un puntero a memoria donde hacer POKE con cada dato, lo que implica evaluar una expresión.

No es fácil mejorar esto, pero sí se puede hacer que la espera no sea insufrible para el usuario con una pequeña estrategia:

En cada iteración del bucle FOR se puede aprovechar para mostrar en pantalla parte de la ayuda del programa, o cualquier otro elemento que mantenga la atención lejos de la espera. Esta técnica resulta bastante efectiva en la práctica, y sencilla de implementar si la ayuda o el elemento que se ponga en pantalla se lee de los mismos DATA.

Existen otras posibilidades, como incluir los datos de los UDG al final de una línea del programa BASIC, ya sea en un comentario REM o en un exceso oculto de longitud de línea, y posteriormente establecer la variable del sistema UDG para que apunte allí, pero requieren una manipulación del programa BASIC en su forma binaria bastante delicada y tediosa. Además, esto supone un incremento de tiempo de carga equivalente al de tener que cargar los datos desde cinta.

Quizás la forma menos ofuscada de ahorrar memoria en el almacenamiento de los UDGs, si cargarlos directamente de un archivo con LOAD "" CODE es demasiado costoso en tiempo cuando son pocos, sea, en lugar de situarlos en sentencias DATA, ponerlos en una cadena de texto (un carácter por cada byte de los UDGs), que sea rastreada por el programa para pasarlos a la zona de memoria donde deban estar. Esto, de hecho, puede ser útil para almacenar cualquier conjunto de constantes numéricas enteras (que quepan en un byte) ocupando menos espacio que con DATA. La única restricción es que el valor 34 decimal (las comillas dobles) no puede estar en la secuencia a menos que haya otro 34 justo después, pues uno solo indicaría el fin del texto.

De esta manera, en lugar de tener el siguiente programa:

se puede escribir éste:

lo que da el mismo resultado en ambos casos:

Esto sólo se puede hacer si disponemos de un editor de código fuente BASIC que admita escribir cualquier byte dentro de una cadena (cosa que no permite el editor de código del ZX original). El sintetizador de ZX-Basicus sí tiene esa capacidad, usando la sintaxis especial que se ha mostrado en los ejemplos anteriores.

Copiar datos en memoria []

A veces un programa BASIC se ve en la necesidad de copiar cierta cantidad de datos de una dirección de memoria a otra (por ejemplo, a o desde la pantalla). En BASIC esto sólo puede hacerse con un bucle FOR, lo que puede ser desesperadamente lento.

Hay un truco conocido para hacer esto mucho más rápidamente aprovechándose del comportamiento del intérprete de BASIC de la ROM, llamado brevemente truco del DEF FN o de DEFADD. De hecho, el sintetizador incluido en la herramienta ZX-Basicus puede generar código automáticamente para implementar este truco en programas BASIC existentes (opción --defadd). En lo que sigue explicamos con detalle en qué consiste.

Ya vimos en la segunda entrega de esta serie que las funciones definidas por el usuario con DEF FN traen consigo lo único parecido a un ámbito (scope) local de variables en un programa en BASIC para el ZX Spectrum: junto a cada parámetro de entrada a la función, en el mismo lugar del programa donde ésta se define con DEF FN, se reservan huecos para copiar, en tiempo de ejecución, los argumentos (parámetros reales) que se le pasan a la función cada vez que se llama con FN. Ese conjunto de huecos es el ámbito local al que nos referimos, y, en la práctica, es un área de variables separada del área global. Esta última es la que se usa la mayor parte del tiempo y se sitúa tras el programa BASIC.

Puesto que reservar huecos del mismo tamaño que los argumentos que va a recibir una función es totalmente impráctico cuando éstos son de tipo cadena de texto, ya que pueden ser de tamaños muy diferentes cada vez que la misma función se llame y copiarlos a donde está la sentencia DEF FN muy lento, el intérprete de ROM guarda, en los huecos, no la cadena de texto, sino un puntero a la misma, junto con su longitud. El tipo de datos puntero no existe en Sinclair BASIC salvo en este lugar.

El disponer de variables puntero, y el saber que cuando el intérprete copia una cadena sobre otra variable cadena lo hace rapidísimamente por medio de la instrucción ensamblador LDIR, es lo que permite engañar a la ROM para que haga copias de memoria de y a donde queramos.

Para ello, basta con crear, en algún sitio de memoria libre, una supuesta sentencia DEF FN que tenga como parámetros dos variables de tipo cadena de texto y sus correspondientes huecos reservados para los punteros. Luego, se fuerza al intérprete a creer que está evaluando una función de usuario FN aunque eso no sea cierto, indicándole que la DEF FN correspondiente está en ese lugar de memoria. El resultado es que, a partir de ahí, cualquier referencia en nuestro programa a alguna variable de las que aparecen como parámetros en nuestra falsa DEF FN será tomada de los punteros que hemos preparado; en particular, una asignación del valor de una de las dos cadenas a la otra hará una copia de todo el contenido de memoria de la primera en la segunda. ¿Qué sucede si la segunda es un puntero a la pantalla? Pues que podemos mover grandes bloques hacia ella de forma muy rápida (no tanto como LDIR por los procesos adicionales del intérprete, pero cerca). Y viceversa.

Más concretamente, el formato en memoria de la DEF FN falsa debe ser el siguiente (los números están en decimal):

donde cada celda es un byte y el conjunto de 9 celdas debe repetirse por cada una de las falsas variables locales (punteros) que se quiera tener. En particular, “v” debe ser la letra minúscula de la variable (una letra distinta para cada una, claro); aL y aH deben definir, en orden little endian, la dirección de comienzo de los datos de la falsa variable; sL y SH su longitud en bytes de memoria; y m es una marca de fin de variable: el código ASCII de una coma (“,”) si no es la última variable que estamos definiendo y el de un cierre de paréntesis (“)”) en caso contrario.

Una vez definida así, en alguna zona de memoria P, la falsa DEF FN, sus variables quedan a disposición del programa en el momento en que engañemos al intérprete indicándole que estamos dentro de una supuesta función FN, lo que se logra cambiando la variable del sistema DEFADD por la dirección P. Toda referencia a variable que no se encuentre entre las falsas será tomada sin problemas de la zona común de variables del programa, pero ésas no. Se puede desactivar el conjunto de falsas variables volviendo a cambiar el valor de DEFADD por 0. Para más señas, la variable del sistema DEFADD está situada en la dirección de memoria 23563 y tiene 2 bytes, también almacenados en orden little endian.

Para ilustrar la potencia de este truco, hemos preparado un programa en BASIC que mide su tiempo de ejecución a la hora de copiar bloques de memoria de diversa longitud hacia la pantalla (el contenido de los bloques no nos interesa aquí):

Nótese que hemos empleado el truco de RANDOMIZE para descomponer números enteros de 16 bits en sus dos partes de 8 bits, como se explicó en la entrega anterior de esta serie. Este programa ha sido ejecutado para distintos valores de L (el tamaño de los bloques a mover, o sea, los valores sL y sH explicados antes), obteniendo los siguientes resultados:

Como se ve, el comportamiento es prácticamente lineal en el número de bytes a copiar (eje horizontal), tardando, de media, 23 microsegundos por cada byte (la pendiente de la recta; el offset de 0.21 indica que nuestro bucle de medida añade siempre 210 milisegundos extra). Desde el punto de vista del BASIC, esto es rapidísimo, aunque desde el punto de vista de la CPU es casi 4 veces más lento que hacer un LDIR directamente en ensamblador, el cual llevaría 21 ciclos de reloj por byte, que con 3.5MHz de reloj serían 6 microsegundos.

También se puede modificar el programa para que no muestre datos aleatoriamente, sino siempre los mismos, y así hacer medidas más ajustadas del movimiento de memoria en sí. Haciendo eso hemos podido deducir que, de media, el cálculo aleatorio que tenía el programa original se llevaba unos 20 milisegundos.

El programa toma 7200 medidas de tiempo para calcular la media de todas ellas, por lo que el Teorema del Límite Central indica que los resultados expuestos arriba tienen una incertidumbre pequeña, del orden de 136 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.

En cualquier caso, la conclusión es que este truco es muy potente para mover bloques de memoria en general, por ejemplo pantallas completas (6912 bytes; tardarían alrededor de un tercio de segundo en copiarse), aunque, en el caso de la pantalla del ZX Spectrum, no es muy útil ni para poner bloques gráficos en ella (“sprites”) ni para hacer scroll, pues la estructura del bitmap obliga a hacer saltos de dirección durante la copia en esos casos, algo imposible de esta forma (para hacer scroll de una línea de texto hacia arriba, bitmap y atributos, en cualquier momento se puede llamar directamente a la rutina de la ROM encargada de dicho trabajo: RANDOMIZE USR 3582).

Medir el tiempo de ejecución []

Estamos hablando mucho en esta serie de la eficiencia en tiempo, por lo que es conveniente referirnos con más detalle a la medida del mismo. El ZX no dispone de ninguna instrumentación en el intérprete para averiguar cuánto ha tardado una sentencia BASIC en ejecutar, por lo que sólo nos queda leer la cuenta de “frames” que, gracias a la ULA, se mantiene en la variable del sistema FRAMES. Esta cuenta comienza al arrancar el ordenador (al hacer un reset) y aumenta en 1 unidad por cada 20 milisegundos en los ZX europeos.

El problema que tiene acceder a esta cuenta para medir tiempos es que ese acceso no se puede hacer demasiado eficientemente en BASIC. La forma más rápida sería la expresión 65536 * PEEK 23674 + 256 * PEEK 23673 + PEEK 23672, la cual enlentece bastante de por sí al programa debido a las multiplicaciones y PEEKs, es decir, su complejidad es alta. Se puede acelerar algo si sabemos que los tiempos que debemos medir serán siempre menores de 65536 * 20 milisegundos (algo menos de 22 minutos). En este caso podemos hacer POKE con 0 en los tres bytes de la variable antes de comenzar a contar, y luego leer sólo los dos menos significativos. En caso de querer acelerar aún más tendríamos que asegurarnos de que los tiempos van a ser inferiores o iguales a 5 segundos; entonces podemos ignorar los dos bytes más significativos de la variable de igual forma, y quedarnos sólo con PEEK 23672.

A pesar de estas limitaciones, si se dispone de un buen emulador del ZX Spectrum que permita escribir en la ROM (algo imposible en un ZX real), se podría medir el tiempo que tarda una sección del código BASIC instrumentando dicha ROM y escribiendo un programa en ensamblador que extendiera su funcionalidad original.

Más concretamente, la idea básica sería intervenir la rutina de la ROM encargada de ejecutar sentencias individuales, llamada THE STATEMENT LOOP y ubicada en la dirección 0x1b28. Justo 5 bytes después, en la dirección 0x1b32, comienza la interpretación de la sentencia en curso, cuyo número de línea se encontrará en ese momento en la variable del sistema PPC y cuyo número de sentencia estará en SUBPPC. Por tanto, si escribiéramos en la ROM y sustituyéramos 3 bytes de la dirección 0x1b32 por una llamada a una rutina externa, llamada que ocupa exactamente 3 bytes de código máquina (C/M), y si esa rutina externa tomara nota del tiempo actual tras comprobar que el programa entra en o sale de la sección que queremos medir, sería posible almacenar dichas medidas para sacar luego estadísticas de la duración de su ejecución.

Esto precisamente es lo que hace la herramienta que se puede obtener aquí mismo. Su uso es un poco complicado, y no se recomienda para quien no tenga ya cierta experiencia en la programación del ZX Spectrum.

Se trata de un programa en C/M que ha de cargarse, después de cargar el programa BASIC a medir, en la dirección 60000 de memoria (debe haberse hecho un CLEAR previamente a alguna dirección inferior; este C/M respeta los UDGs). También debe habilitarse en el emulador la escritura sobre la ROM, como hemos dicho antes.

Una vez cargado este C/M, hay que: a) inicializar una tabla de datos para el mismo, así como crear algunas variables (todo esto se muestra en el ejemplo a continuación); b) definir el trozo de programa que se quiere medir, desde la primera sentencia a medir hasta la primera a no medir, mediante la creación de más variables y su almacenamiento en la tabla de datos anterior; c) almacenar en dicha tabla el número n de medidas de tiempo a tomar, que debe ser menor o igual a 1000, y activar el proceso de medida mediante RANDOMIZE USR 60000; d) dejar que se ejecute el programa BASIC mientras el medidor C/M almacena medidas de tiempo tomadas cada vez que se ejecuta la sección definida (si ésta se repite, se tomará más de una medida; si no, sólo una); e) cuando se desee dejar de medir, restaurar la ROM original haciendo RANDOMIZE USR 60038; f) interrumpit el programa BASIC y almacenar los datos obtenidos leyéndolos de memoria del emulador.

Un ejemplo de uso es el siguiente, en el que se mide lo que tarda la impresión en pantalla de la zona sombreada (línea 10, sentencia 2; las sentencias se numeran desde 1 en el ZX), que calcula el coseno de una variable entera:

La línea 9999 se encarga de cargar el C/M y crear la tabla de datos necesaria para éste (paso a). Nótese que para que funcione bien, este programa BASIC no debe tener funciones de usuario llamadas FN h o FN l. Los pasos b y c se implementan en la línea 2, el d es la línea 10, y el e la 20.

El ejemplo de arriba produce 1000 medidas de tiempo (las veces que se repite el bucle FOR, y el máximo que el programa en C/M es capaz de tomar), que se almacenan a partir de la dirección 60368 de la RAM, como se muestra en el visor de memoria del emulador fuse después de terminar el experimento:

Cada medida de tiempo son 5 bytes (la primera que se muestra en la figura de arriba es 03 00 00 60 04): los 3 primeros contienen un valor f igual a la diferencia de la variable del sistema FRAMES al principio y al final de la sección de código monitorizado; los 2 siguientes contienen un valor entero c de 16 bits que afina esa medida de tiempo. El tiempo total transcurrido, eliminando el propio tiempo incurrido por la rutina externa de C/M, puede calcularse a partir de f y c con la siguiente fórmula, que está diseñada específicamente para ella:

donde P_ULA es el período de refresco de la ULA (20 milisegundos en Europa) y P_CPU el período de reloj de la CPU (286 nanosegundos si ésta funciona a 3.5MHz). Esta fórmula no es del todo exacta porque el valor 30 de su segundo término puede estar en realidad en el intervalo [0,30] y porque puede ocurrir una interrupción de la ULA dentro de los 192 T-estados que aparecen en su último término, aumentándolos en lo que servir esa interrupción tarde (que dependerá del valor de la variable FRAMES y del estado del teclado, fundamentalmente). Sin embargo, la probabilidad de que ocurra dicha interrupción en ese período es de 192*P_CPU/0.02 = 0.0027, o sea, despreciable.

Los datos obtenidos de este ejemplo se han grabado en cinta desde el propio intérprete de BASIC (SAVE), se han extraído del fichero de cinta con un visor de datos binario para Linux (Bless), y se han interpretado con un script de Matlab (se podría haber hecho igualmente con cualquier otro lenguaje de scripting, como Python) según la fórmula anterior para obtener estadísticas de los mismos. Los resultados se muestran en la siguiente figura:

Como se puede observar, el ZX Spectrum tarda… ¡70 milisegundos en calcular y mostrar en pantalla el coseno de una variable entera! Le daría para imprimir solamente 14 en un segundo…

La influencia de la ULA []

En el ZX Spectrum, parte de la memoria RAM es accesible directamente por dos circuitos integrados distintos: la CPU y la ULA (Uncommited Logic Array). Este último es el análogo a la tarjeta gráfica de un ordenador actual, pero se ocupa de más cosas: sonido, cassette, teclado, etc., incluso de proporcionar la señal de reloj a la CPU.

La función más importante de la ULA es generar la señal de vídeo a partir de la memoria de imagen almacenada en las direcciones 16384 – 23295 de la RAM (los detalles se explican en la siguiente entrada de esta serie). Para ello, tiene que leer datos de esas direcciones; como la CPU también puede leer y escribir en ellas, y ambos pueden querer hacerlo a la vez, a veces se producen conflictos entre ellos que siempre se resuelven deteniendo a la CPU (de hecho, parándole la señal de reloj) durante el tiempo que la ULA espera necesitar para hacer sus cosas. Este retardo es de entre 1 y 6 ciclos de reloj, y se induce a la CPU de forma poco previsible, en general (para muchos más detalles, puede consultarse esto y esto).

Es más, no sólo se detiene la CPU cuando sucede el conflicto en zonas de pantalla: para simplificar la electrónica de la placa base, se hace esto cuando se accede a cualquier dirección dentro de los primeros 16K de RAM, es decir, en el rango 16384 – 32767. Así, sólo los 32K superiores de RAM (desde 32768 hasta 65535) y la ROM (desde 0 hasta 16383) están libres de conflicto.

También se inyectan retardos en la CPU al acceder a puertos de E/S, pero ésos son menos frecuentes e importantes para nosotros.

Si no tenemos conectado ningún dispositivo externo que inserte información extra sobre canales en la memoria RAM, el programa BASIC empezará en la dirección 23755. En caso contrario, la información de estos canales se almacena justo antes del programa, moviendo hacia arriba su comienzo. En cualquier caso, la variable del sistema PROG (en la dirección 23635, 2 bytes) contiene la dirección de comienzo en memoria de la primera línea de nuestro programa BASIC.

Esto significa que el programa BASIC comienza en memoria conflictiva. De hecho, si empieza en 23755, tendrá 9013 bytes en dicha memoria antes de alcanzar los 32K superiores. Es raro que podamos prescindir de esos 9K a la hora de escribir nuestro programa (9K es casi el 20% de la memoria RAM disponible para nosotros!), pero si quisiéramos hacerlo, bastaría con insertar una línea inicial con una sentencia REM que contuviera un comentario de longitud 9008 (caracteres), lo que haría que la siguiente línea ya estuviera en zona no conflictiva (si, además, queremos que la ejecución del resto de líneas no sufra por tener ésa antes, podemos cambiar el contenido de la variable del sistema PROG para que apunte a la dirección de la segunda línea; todo esto se detalla en la primera entrega de esta serie).

¿Cuál es el tiempo esperado de retardo que puede tener un programa BASIC a causa de los conflictos con la ULA? Bueno, aquí podemos tener en cuenta lo siguiente:

• Los retardos fundamentales se producirán por las consultas del intérprete al programa que hay en memoria (leer sentencias para interpretarlas, buscar líneas, buscar variables, etc.), no tanto por los accesos del propio código BASIC a memoria conflictiva: el tiempo de acceso a esa memoria es mínimo comparado con el de interpretación y ejecución del programa.
• Cada programa es diferente de cualquier otro, pero en general el intérprete siempre está haciendo lo mismo sin parar: leer la sentencia a ejecutar, interpretarla, ejecutarla y pasar a la siguiente. Por tanto, las diferencias en accesos a memoria de programa BASIC que haya entre programas distintos, y, en particular, para sentencias BASIC distintas, pueden ser pocas desde el punto de vista de los conflictos que pudieran producir con la ULA.

Asumiendo estas premisas, podemos estimar el tiempo incurrido en los conflictos ejecutando un pequeño programa primero en memoria conflictiva y luego en no conflictiva, y viendo las diferencias de tiempo. En la segunda entrega de la serie ya hicimos eso, pero no proporcionamos el código del programa movido a zonas no conflictivas. Repetimos aquí primero el programa original: es un bucle que sirve para medir el tiempo esperado (líneas 10 y 30) en hacer una operación muy sencilla de decremento de variable entera (línea 20):

La versión que desplaza el bucle principal a una zona no conflictiva es la siguiente:

Nótese que no sólo el bucle principal se pone en zona no conflictiva, sino también se accede desde él a una zona de memoria del mismo área. Asimismo, en lugar de usar un sólo REM para desplazar el bucle, hemos puesto 9 para que sea algo más fácil de visualizar el código.

Tras ejecutar estos programas, el tiempo por iteración del bucle del programa original es de 10.901961 milisegundos, mientras que el del programa modificado es de 10.823529 milisegundos. La diferencia es de 78.432 microsegundos para una iteración, o, lo que es lo mismo, un 0.72% del tiempo de iteración original. Para afinar más se puede considerar que una iteración del bucle principal consiste en: 1) decrementar el valor de un byte en memoria, 2) comprobar que no sea igual a 0 y 3) saltar al principio del bucle para repetir en caso de que no sea igual a 0. Si simplificamos la cuestión suponiendo que esas 3 sentencias van a tomarle el mismo tiempo al intérprete, cada una llevaría 3.633987 milisegundos, por lo que el retardo por iteración supondría un 2.16% del de cada sentencia.

Siendo impreciso, este valor nos puede servir de referencia para estimar cuánto podemos esperar que se enlentezca una sentencia de programa a causa de los conflictos con la ULA. Como se ve, es escaso, debido fundamentalmente a que el tiempo gastado por el intérprete haciendo su trabajo es mucho mayor que el utilizado para leer de memoria el programa BASIC.

Finalmente, nótese que en programas largos es de lo más probable que las variables sí estén en memoria no conflictiva (puesto que se almacenan tras el programa), por lo que no sufrirán de este problema.

.oOo.

[Click here to read this in Spanish ]

This is the fourth 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. Some statements and time measurements

V. Screen operations based on characters

In this post we talk about the efficiency of some important functionality in the ZX Spectrum BASIC and also about time measurements. The screen operations based on characters are dealt with in the next post.

To navigate through this post more easily, these are the sections it contains:

1. Drawing. Execution times of PLOT, DRAW, CIRCLE, POINT.
2. Reading the keyboard. Execution times of INKEY$, PEEK (LAST_K) and IN (254).
3. Creating UDGs. How to hide the execution time of defining UDGs.
4. Copying memory blocks. The DEFADD trick for fast memory copies.
5. Measuring time. Of any statement or part of a BASIC program.
6. Influence of the ULA on a BASIC program. Contended memory produces delays that have a (slight) influence on BASIC.

Drawing

The drawing statements (PLOT, DRAW, CIRCLE) are specially sensitive regarding their execution speed, as anyone that has programmed sometime in the ZX knows well. When DRAW is used to draw arcs, and in all uses of CIRCLE, the interpreter does repeated floating point calculations, which makes them very slow in spite of having optimized ROM implementations. PLOT is not inefficient in principle (particularly if its arguments are integer expressions and do not use real numbers), but to draw something interesting only with PLOT you need a lot of plots!

Drawing straight lines with DRAW uses a version of the Bresenham’s algorithm which is quite efficient (it does not use the ROM calculator), but, like other drawing routines, it must set appropriately the color attributes of the screen cells which the line goes through, besides executing the INVERSE or OVER modes correctly. That reduces its efficiency.

With the next program you can estimate the time taken by PLOT, POINT and DRAW when they are called with integer numeric literals as parameters (and without special modes or colours):

The average times measured by the program for each individual call to one of these statements are: PLOT, 7.274 milliseconds; POINT, 9.208 milliseconds; DRAW (horizontal line with 255 pixels), 55.16 milliseconds; DRAW (vertical line with 175 pixels), 26.89 milliseconds. Maybe surprisingly, drawing vertical lines is much faster as drawing horizontal ones (twice faster, in spite of the former having almost a 70% of the length of the latter), and PLOT is faster than POINT.

As for CIRCLE, we can modify the previous program to repeat that statement a number of times with different radii. If we repeat it 100 times, we get the following average times (per circle):

The figure shows how the ROM CIRCLE routine divides the circumference in several arcs that are drawn with straight lines, which produces the “steps” in the red data points (it uses different number of divisions of the circumference for different ranges of values of the radius; for instance, it uses the same number of steps for radii in the approximate range [40,50]).

You can see that, discarding the small effect of the quadratic term in the equation, drawing circles with integer parameters is approximately proportional to their radii (or circumferences); particularly, it takes around 15 milliseconds more for each increment of the radius of the circle. Notice that all the times in the figure are quite high: even very small circles (radius = 1 pixel) can only be drawn at a pace of about 3 per second…

In summary:

Drawing statements (and bitmap consulting statements, like POINT) should be used sporadically, with integer arguments, in parts of the code that do not have special speed requirements, and preferably for straight drawings.

Reading the keyboard []

We have 3 ways of reading the keyboard in BASIC: INKEY$, PEEK 23560 (system variable LAST_K), and IN from any port which low byte is 254. To decide which one is the fastest, you can use the following program, changing the way of reading the keyboard by the one you wish (its complete execution takes around 10 minutes):

The last number shown on the screen after finishing is the time in seconds taken by each one of the 100000 iterations of the loop (considering an European ZX), which includes the keyboard reading but also the rest of the program statements (assignment, loop). However, you can compare the results of the program with different ways of reading the keybard without changing anything else, and then the differences between those results will be due only to the keyboard reading. In particular, they indicate that, on average, INKEY$ is 367.2 microseconds slower than the other two, which are basically indistinguishable with the precision of this program (the time measurements have around a 95% of probability of be in +/-36.5 microseconds of the average).

Creating UDGs []

Creating UDGs means to fill a certain area of memory with the bitmaps of those UDGs. If this is done by reading DATA values and POKE-ing them, it is quite slow, due to the loop itself (consulting the FOR variable, jumping in NEXT…), reading the DATA (locating the line where the DATA is, recall the first post in this series), and maintaining the pointer to memory that holds the address where to POKE the next byte.

It is not easy to improve this (if you load the UDGs from tape, the loading time is not much better). However, there is a technique that can hide that time for the user, making him/her to be mentally active in the meanwhile instead of doing a simple wait till completion:

In each iteration of the loop that is defining the UDGs, you can show in the screen part of information needed to use your program, or any element that distracts the attention of the user. It is amazing how this simple strategy can make the wait more pleasant and even dissapear in the conscience of the viewer! It is also quite simple to implement; you even can use the same DATA statements that hold the UDG bitmaps to hold the information to display, thus READing it on the fly.

There are other possibilities, such as including the UDG data at the end of a line of the BASIC program, either as a REM comment or in a hidden excess of the line length, and set the system variable UDG to point there. However, they requiere a careful and tedious manipulation of the BASIC program in its binary form, and they involve, at the end, the same loading time as though the data is loaded separately from tape.

Maybe the less obfuscated way of saving space when storing the UDG definition data, without loading them with LOAD "" CODE because that takes too long if there are few UDGs, is, instead of placing their bytes into DATA statements, put them into a text string (one character per UDG byte), that can be scanned by the program in order to pass the bytes to the final UDG memory address. Actually, this can be useful to store any set of integer numeric constants (that fit into a byte) saving a lot of space with respect to DATA. The only restriction is that the decimal value 34 (double quotes) cannot be in the sequence unless another 34 is right after it, since only one value like that would mark the end of the string.

In this way, instead of the next program:

you can write this one:

which produces the same result:

This can only be done (confortably) with a BASIC source code editor that admits escaped characters into strings (the original ROM editor does not). The synthesizer of ZX-Basicus allows for that using the special syntax shown in the previous examples.

Copying memory blocks []

Sometimes, a BASIC program needs to copy certain amount of data from a memory address to another (for example, to or from the screen). In BASIC, that can only be done through a FOR loop, which is usually desperately slow.

There is a trick to do that much faster, by leveraging the way the BASIC interpreter of the ROM deals with user functions, called the DEF FN or DEFADD trick. Actually, the synthesizer tool included in ZX-Basicus can generate code automatically for implementing this trick in existing BASIC programs (option --defadd). In the following we explain the trick in more detail.

We already saw in the second post of this series that user defined functions (DEF FN) produce the only thing close to a local scope of variables in a BASIC program written for the ZX Spectrum. This happens because, in the same place that the DEF FN is in the program memory, and alongside each of its input parameters, the interpreter reserves some space for copying there the actual parameters during each function call (FN). Those placeholders form the local scope, and, in practice, an area of variables different and isolated from the global, common one that exists in memory after the end of the program.

Since reserving space in memory in these placeholders when copying entire string parameters would be impractical (strings may have very diverse lengths and it would be certainly slow to copy them at each FN call), the interpreter stores there just pointers to the strings, and their lengths. The pointer data type does not exists in Sinclair BASIC except here.

It is worth to mention that the interpreter copies strings in a very fast way, using the assembly instruction LDIR. These fast copies plus the existence of pointers is what allows us to cheat the ROM to do fast memory block movements.

In order to do that, we need to store at some memory location a fake DEF FN statement that has as input parameters two string variables. Once that this is done, we will cheat the interpreter by indicating that it is evaluating a user function FN that corresponds to that DEF FN. That is not true, but from that point on, any reference in the program to one of the fake variables will use the pointers instead of consulting the global variable area of the program, and therefore any assignment of one of the variables to the other one will do a fast copy of the former pointed data to the latter in memory. For instance, what happens if the latter points to the screen? Aha! You can now move large blocks of memory to the screen very fast (well, not as fast as LDIR due to the rest of processes involved in the interpreter, but close enough).

The format in memory of the fake DEF FN must be this one (the numbers are in decimal):

Each cell in that figure is a byte, and the set of 9 cells must be repeated for all the fake local variables (pointers) that you need. In particular, “v” must be the lowercase letter of the variable (you must use a different letter for each variable); aL and aH must define, in little endian order, the starting address of the data of that fake variable; sL and SH must be its length in bytes; and m is a marker that must be the ASCII code of comma (“,”) if that is not the last fake variable in the DEF FN or a closing parenthesis (“)”) otherwise.

Once you have filled some memory place with the data defined above, starting at, let say, address P, those variables can be used by the program if we cheat the interpreter by indicating it is evaluating a user function. For doing that, we just have to store in the system variable DEFADD the address P. Any reference to a fake variable name will use the memory block pointed by it from that moment on, while references in the program to variables not defined at P will lead the interpreter to consult the set of global, common variables. For finishing the use of the fake variables, you need to reset the value of DEFADD to 0. By the way, the system variable DEFADD is located at memory address 23563 and it has 2 bytes that store a value in little endian.

To illustrate the power of this trick, we have prepared a BASIC program that measures the execution time of this kind of memory copies. We have used it with diverse memory block lengths to move them to the screen (the content of the blocks is not interesting):

Notice that we use the RANDOMIZE trick described in the previous post in this series to do the decomposition of a 16-bit number into its two 8-bits parts. After executing the program for different values of L (the size of the memory blocks to copy, i.e., the values sL and sH), we got these results:

As shown, the behaviour is very close to linear in the length of the blocks that are moved (horizontal axis), taking 23 microseconds per byte on average (the slope of the line; the intercept of 0.21 indicates that our measuring loop injects around 210 extra milliseconds to that time). From the point of view of the ZX Spectrum BASIC, this is very very fast, although from the perspective of assembly programming it is almost 4 times slower than a direct LDIR, which would take 21 clock cycles per byte, i.e., 6 microseconds with a 3.5MHz CPU.

The program above can be modified to not do the random calculation in the measuring loop in order to get finer measurements. By doing that, we can deduce that on average, the random calculation takes around 20 milliseconds.

Since the program does 7200 measurements to get the final average time, the Central Limit Theorem suggests that the results in the figure above have a small amount of uncertainty, of around 136 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.

Anyway, the conclusion is that this trick is very powerful for moving memory blocks in general (for instance, entire screens), but not so much for putting graphic blocks on the screen or doing scrolls, due to the bitmap layout in the ZX, that requires to make gaps within the copy procedure, something imposible with the trick (to do scroll one line of text upwards, bitmap and attributes, you can use at any time the ROM routine that does precisely that: RANDOMIZE USR 3582).

Measuring time []

Besides making programs time-efficient, often you need to take notice of the time spent in some part of your code. The ROM interpreter is not instrumented to measure the time spent in any BASIC statement, but we have the system variable FRAMES, that, thanks to the ULA, keeps a count of the 20 millisecs ticks (16.7 millisecs in non-european countries) that have passed since the computer was reset the last time.

The problem with reading this variable is that it is a long number formed by 3 bytes. Getting the whole value is slow even using the most direct expression for it: 65536 * PEEK 23674 + 256 * PEEK 23673 + PEEK 23672. There are a bunch of multiplications, sums and memory readings there. Fortunately, it can be simplified if we know that the times to measure are always shorter than 65536 * 20 millisecs (around 22 minutes). In that case, we can POKE a 0 in the three bytes of the variable before starting to count, and then reading only the 2 least significan bytes. Moreover, we can use just the least significant byte if all times to measure will be shorter than 5 seconds: the previous expression becomes then PEEK 23672.

In spite of these limitations, we could think of measuring the time spent in a section of a BASIC program better if we use a good emulator that allows us to do writings at ROM addresses (something imposible with a real ZX Spectrum!). That ROM could be instrumented and extended with some assembly code to gather the measurements.

More concretely, the basic idea would be to change the original ROM routine that is in charge of interpreting and executing individual BASIC statements, called THE STATEMENT LOOP and placed at 0x1b28 within the ROM. Right 5 bytes after that, at 0x1b32, the code that interprets the current statement starts. When that happens, the line number of that statement is in the system variable PPC, and the statement number in SUBPPC. Consequently, if we could write at that ROM address in order to substitute 3 bytes at 0x1b32 by a call to an external machine code (M/C) routine (such a call are exactly 3 bytes) which timestamps the current time when the BASIC program is entering or leaving the section to measure, it would be possible to store those measurements in order to do an offline statistical analysis.

This is precisely what the tool that you can download here does. Notice that this tool is not for beginners; it is only recommended if you have experience in ZX Spectrum programming.

The tool is a M/C program that must be loaded in memory after the BASIC program that we wish to measure is loaded. The M/C must be placed concretely at address 60000 (CLEAR must has been done previously to a smaller address; the M/C program respects the UDGs); in the emulator, you must enable ROM writings, as we have commented.

Once the M/C program is loaded, you have to: a) initialize a data table for it, and create some variables (all of that is shown in the example below); b) define the section of BASIC code you wish to measure, from the first statement to be measured to the first statement NOT to be measured, and store in the data table that information; c) store in the data table the number n of measurements to accumulate on that section, that must be smaller than or equal to 1000, and activate the measurement procedure through RANDOMIZE USR 60000; d) leave the BASIC program to run while the monitoring M/C program gathers one measurement each time the monitored section executes (if the section executes more than once, several measurements are gathered); e) when you wish to stop measuring, restore the original ROM with RANDOMIZE USR 60038; f) stop the BASIC program and gather the measurements for offline analysis, for instance in a tape file.

A case use is the following, where we measure how long takes to calculate and print in the screen the cosine of an integer variable (line 10, statement 2 in the code; statements are numbered from 1 in the ZX Spectrum):

Line 9999 loads the M/C program and fill the data table for it (step a). Notice that in this example, the BASIC program cannot use user functions FN h or FN l. Steps b and c are implemented in line 2, d in line 10, and e in line 20.

The above example produces 1000 measurements (the number of times that the FOR loop iterates, and the maximum to gather by the M/C program), that are stored from address 60368 up, as it is shown in the memory browser of the fuse emulator after finishing the experiment:

Each measurement consists of 5 bytes (the first one shown above is 03 00 00 60 04): the first 3 bytes are an integer value f that equals the increment of the FRAMES system variable since the starting of the monitored section to its end; the next 2 bytes contain an integer value c that refines that measurement. The total time spent in the monitored BASIC section, once the very time of the M/C routine is discarded, can be calculated from both values using the following formula, designed for the particular implementation of the M/C routine:

where P_ULA is the refresh period of the ULA (20 milliseconds in Europe) and P_CPU the clock period of the CPU (286 nanoseconds if it is a 48K@3.5MHz). This formula is not entirely exact since the value 30 in the second term can actually be within the interval [0,30] and because one interruption of the ULA may occur within the 192 T-states that are in the last term, increasing them by what the ULA service routine takes (which depens on the value of the FRAMES system variable and the state of the keyboard, essentially). However, the probability of that interrupt to occur in such a short interval is 192*P_CPU/0.02 = 0.0027, which is negligible.

The data gathered from our example have been saved in a tape file (SAVE), have been extracted from that file with a binary viewer in Linux (Bless), and have been interpreted with a Matlab script (you could use any other scripting language, such as Python) according to the formula above. The statistical results are as follows:

As you can see, the BASIC interpreter of the ROM takes… 70 milliseconds to calculate and print the cosine of an integer variable! It could only print 14 of these variables in one second…

The influence of the ULA []

In the ZX Spectrum, part of the RAM is accessible directly by two circuitries: the CPU and the ULA (Uncommited Logic Array). The latter is like a graphic card of a modern computer, except that it takes care of many more tasks: sound, cassette, keyboard, etc., even of generating the clock signal for the CPU.

The most important function of the ULA is to generate the video signal from the bitmap and attribute map memories stored in addresses 16384 – 23295 of the RAM (the details are explained in the next post of this series). For that, it has to read bytes from these addresses; since the CPU can also read and write on them, and both might wish to do it at the same time, there are occasions when access conflicts appear. All of them are are always solved by halting the CPU (actually, its clock signal is stalled) during the time that the ULA expects to need for doing its job. This delay ranges from 1 to 6 CPU clock cycles, and it is induced on the CPU work in a quite unpredictable fashion in general (for many more details, you can consult this and this).

Furthermore, the CPU is not only stalled when the conflict occurs in screen memory: to simplify the ZX circuitry, this actualy happens when both access any address within the first 16K of RAM, i.e., in the area 16384 – 32767. Thus, only the higher 32K of RAM (32768 to 65535) and the ROM (0 to 16383) are free of conflict.

This kind of delays are also injected in the CPU when accessing I/O ports, but these are less frequent and important for us.

If there is no external device connected to the ZX that inserts information about channels in the RAM, the BASIC program will start at address 23755. Otherwise, the information of those channels is stored right before the program, displacing it to a higher zone. In any case, the system variable PROG (located at 23635, with 2 bytes) contains the start address in memory of the BASIC program, concretely of its first line.

This means that the BASIC program starts at contended memory. Actually, if it is at 23755, it will have 9013 bytes in that memory before it reaches the higher 32K. It is uncommon that we can lose those 9K in our program (9K is almost 20% of the RAM available or it!), but if we wish to, the only thing to do is to insert a first line in the program that contains a REM statement with a comment of length 9008 (characters), which puts the next line in non-contended memory (if, in addition, we wish that the execution of the rest of lines does not suffer from not being at the beginning, we can change the content of the system variable PROG and make it point to the address of the second line; all of this is detailed in the first post of this series).

Now, how long takes the contended delays in a BASIC program? Well, we can consider these:

• The fundamental delays wil be due to the readings of program memory done by the interpreter (get statements to interpret them, searching for lines or variables, etc.), not so much to the accesses of the very program to contended memory: that access time to memory is negligible with respect to the time taken for interpreting and executing the BASIC statements.
• Every program is different from any other, but in general the interpreter is always doing the same thing: reading the statement to be executed, interpreting it, and jumping to the next one. Therefore, differences in accesses to the program memory are expected to be small as well, even among different programs, from the point of view of the contention.

Assuming these premises, we can estimate the time caused by contention by executin first a program in contended memory and then the same one displaced to non-contended one, and examining the time differences in their executions. In the second post of this series we did that already, but did not provide the code of the second program. The original one was a loop whose execution time was measured; the loop was doing a simple task of decreasing a byte value stored in memory. Its code is repeated here for your convenience:

The version with the loop displaced to non-contended memory is this:

Notice that we do not only put the main loop in non-contended memory, but we also do accesses to non-contended RAM in the loop. Also, instead of just one REM to do the displacement, we use 9 for the sake of clarity in the listing.

After running these programs, the time spent, on average, in one iteration of the original loop is 10.901961 milliseconds, while the one of the non-contended version is 10.823529 milliseconds. The difference is 78.432 microseconds per iteration, or, in other terms, 0.72% of the iteration time in the original program. To be more detailed we can consider that one iteration of the loop consists in : 1) decrementing a byte in memory, 2) checking whether that byte is now 0, and 3) jumping to the beginning of the loop for a new iteration if the byte is not 0. We can simplify the issue by assuming the three statements take the same time, which leads to 3.633987 milliseconds per statement; in that case, the delay per iteration is 2.16% of the time taken by interpreting and executing one statement.

As imprecise as this figure may be, the value can serve as a reference to estimate how long we can expect to be delayed any statement in a BASIC program that is at contended memory. As you can see, that time is pretty short, essentially due to the fact that the time taken by the interpreter to do its internal tasks is much longer than the one employed in reading the BASIC program memory.

Finally, notice that in long programs is more than likely that the variables are in non-contended memory (since they are stored after the BASIC code), thus they will not suffer of contention.

[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. Funcionalidades diversas y medida del tiempo

V. Operaciones en la pantalla basadas en caracteres

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.

De forma general, 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.

Se ha de tener especial cuidado de que las expresiones sean cortas y simples 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.

Deteniéndonos en los componentes de cualquier expresión, encontramos que éstas constan de cuatro: literales (números y cadenas de caracteres en el caso del ZX), operadores (+,-,*,OR, AND, indexaciones de tablas o cadenas,…), llamadas a funciones (COS, SIN, INT, FN(),…) y agrupadores (paréntesis). Como ya se ha dicho, algunas llamadas a funciones son bastante ineficientes; los paréntesis pueden eliminarse siempre que se comprendan las precedencias de evaluación de los operadores; los operadores no pueden optimizarse demasiado en sí mismos (véanse los siguientes apartados); pero de los literales podemos decir más cosas:

Los literales numéricos que forman parte de las expresiones pueden ser optimizados, especialmente en su tamaño en memoria, pero eso tiene consecuencias en el tiempo de ejecución.

NOTA: En un programa BASIC ya “tokenizado” en memoria, cada literal numérico está almacenado como el texto que muestra su valor seguido de 6 bytes con el mismo valor codificado en binario; curiosamente, no se almacenan nunca valores negativos en la codificación binaria -aunque el intérprete es capaz de manejarlos sin problemas-: el operador “-” que precede a dichos literales no se considera parte del número, sino una operación previa, distinta del literal.

Existe truco muy utilizado para reducir el tamaño en memoria de los literales numéricos: 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, ya que sustituye un literal por una expresión más compleja. 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. Hay ocasiones en que, sin embargo, no importa esa pérdida de eficiencia: por ejemplo, PAUSE NOT PI está plenamente justificado puesto que ahorra 4 bytes respecto a PAUSE 0 y el retardo adicional de la evaluación de la expresión NOT PI no va a influir en absoluto en el tiempo que tarde el usuario en pulsar una tecla.
• 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:

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

El resto de esta entrada lo dedicaremos a cada uno de los principales tipos de expresiones que existen en Sinclair BASIC (y en cualquier lenguaje de programación imperativo).

Las expresiones de manipulación de textos son particularmente costosas para el intérprete de BASIC.

Aun así, también pueden ser optimizadas. Es poco eficiente sumar (concatenar textos), 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, comparar textos 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.

En cuanto a las expresiones lógicas, hay que tener bien presente que no funcionan exactamente igual que en los lenguajes modernos, y también que existen varias expresiones distintas, con distinta eficiencia, para algunos cálculos comunes.

Las expresiones lógicas son 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 verá en el apartado de expresiones numéricas. 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.

Además, hay varios cálculos lógicos muy comunes que pueden implementarse con varias expresiones distintas, de modo que es conveniente seleccionar la más eficiente. En la siguiente tabla recogemos algunas que el programador @igNaCoBo ha utilizado en su juego ArkanoidB2B:

Los tiempos de la tabla se han obtenido usando el programa patrón que se muestra abajo. La columna “T” de la tabla recoge los tiempos esperados en una iteración del bucle de las líneas 10 a 50; las entradas en cursiva de la última columna son sólo resultados interesantes, quizás no muy útiles para optimizar.

Este programa ha sido diseñado para que se evalúe la expresión para casos en que g < 0, g = 0 y g > 0 (el cálculo de la variable g en la línea 20 produce -1, 0 ó 1 cíclicamente). El programa repite 1000 iteraciones de un bucle en el que se evalúa dicha expresión y se hacen otras cosas; si dividimos por 1000 obtenemos una estimación del tiempo esperado para una sola iteración (columna “T”). Ese tiempo puede entonces compararse con el del mismo programa cuando se cambia la expresión a evaluar por otra, de lo que deducimos los datos de la última columna.

Finalmente, las expresiones numéricas ofrecen posibilidades de optimización importantes si son enteras y trabajan con números que no excedan los 16 bits.

El calculador de la ROM es capaz de distinguir dos tipos de datos: enteros y reales (representados en memoria en coma flotante). Los primeros, en particular aquéllos dentro del rango -65535 hasta +65535, 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.

Cuando nos haga falta un número entero a partir de un valor real siempre podemos usar la función INT, pero hay que tener en cuenta que ésta hace un redondeo hacia abajo, es decir, elimina la parte decimal del número por completo. Si queremos un redondeo hacia arriba (obtener el número entero más pequeño que sea mayor o igual al valor real que estamos redondeando) podemos aprovecharnos de que el intérprete de BASIC hace exactamente esa operación cuando a una sentencia que necesita un número entero se le pasa uno real. Así, si hacemos LET a = INT 10.6 obtendremos el valor 10, pero si hacemos POKE 40000,10.6 el valor que obtendremos con PEEK 40000 será 11. En cualquier caso, ten en cuenta que el tiempo que tarda en ejecutar INT(10.6 + 0.5), que hace el mismo redondeo hacia arriba, puede ser menor: en el caso de usar POKE/PEEK como antes, INT tarda aproximadamente 3 milisegundos menos. También es más eficiente en cuanto al consumo de memoria.

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, y ¡no podemos hacerlo si v es 0, porque entonces el comando RANDOMIZE no guarda el 0 en esa variable del sistema!

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 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 - 1, quizás más natural para los programadores de lenguajes donde los índices de arrays empiezan en 0.

Se puede medir la ganancia en tiempo de estos incrementos cíclicos de variable entera mediante el siguiente programa:

Ejecutándolo primero tal y cual está, y luego cambiando la línea 20 por:

nos da una diferencia de tiempos de 540 microsegundos a favor de la segunda opción. Esta aceleración puede ser importante (¡ejecutar tan sólo dos veces esta nueva línea 20 nos mejora los tiempos en más de 1 milisegundo!). Por otra parte, si hacemos lo análogo con los incrementos cíclicos de 0 a n-1 obtenemos una mejora de 420 microsegundos respecto a usar IF. De este experimento también se puede deducir que contar de 0 a n-1 de manera acelerada es 540 microsegundos más rápido que contar de manera acelerada de 1 a n.

Para terminar esta sección hay que recordar que 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. Some statements and time measurement

V. Screen operations based on characters

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.

In general, 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.

Expressions should be short and simple 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.

Let deep in more detail in the components of any expression. They are four: literals (numbers and strings in the case of the ZX), operators (+,-,*,OR, AND, indexing of tables or strings,…), function calls (COS, SIN, INT, FN(),…) and groupings (parentheses). As I said before, function calls are pretty inefficient; parentheses can be avoided as long as we know well the operator evaluation precedences; operators cannot be optimized much (see the rest of this post); but we can say a little more about literals:

Numeric literals can be optimized, especially in its storage, but that has consequences in the execution time.

NOTE: In a “tokenized” BASIC program, each numeric literal is stored as the text that shows its value followed by 6 bytes containing the same value coded in binary; surprisingly enough, negative values are never stored in that binary coding -though the interpreter is quite capable of dealing with them-: the corresponding positive values are coded in binary because the negation operator is not considered part of the numeric literal.

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, because it turns a literal into a more complex expression. 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. There are situations where, nevertheless, that loss of efficiency is not relevant: for example, PAUSE NOT PI is completely justified since it saves 4 bytes compared to PAUSE 0 and the additional delay produced by the evaluation of the expression NOT PI has no influence in the time the user takes to press a key.
• 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:

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

The rest of this post is devoted to each of the main types of expressions that exist in Sinclair BASIC (and in any imperative programming language).

Firstly, string manipulation expressions are particularly costly for the BASIC interpreter.

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.

Regarding logical expressions, it must be taken into account that they do not work exactly the same as in modern languages, and also that there are different expressions for some common calculations, with different efficiency.

“Logical” expressions produce 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 in the next section. 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.

Besides, there are some common logical calculations that can be implemented with diverse expressions, thus it is convenient to choose the one more efficient for our purposes. In the next table we list some of these expressions, used by the programmer @igNaCoBo in his game ArkanoidB2B:

The times in the table have been obtained using the program below. In the table, the “T” column shows the time per iteration (lines 10 to 50); the italic gains are just interesting results, maybe not very useful for optimization.

This program has been carefully designed for evaluating the expression of interest for cases where g < 0, g = 0 and g > 0. The code does 1000 iterations of a loop where that expression is evaluated (and other things happen too); if we divide the total time by 1000 we get an estimation of the expected time per iteration, that can then be compared with the one of the same program when we change the expression by another one (last column in the table)

Finally, numerical expressions offer relevant possibilities for optimization especially if they are integer ones that fit in 16 bits.

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, particularly those in the range -65535 to +65535; 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.

When we need to get an integer number from a real number we can use the INT function, but you should know that it rounds the number towards 0, that is, we lose all the decimal part of the number. If you need to round towards infinity instead (get the smaller integer that is equal or greater than the real value) you can leverage the behaviour of the interpreter, because it does exactly that kind of rounding every time a statement that needs an integer parameter is provided with a real argument. For instance, if we do LET a = INT 10.6 we will get 10, but if we do POKE 40000,10.6 the value that we get with PEEK 40000 will be 11. Anyway, take into account that the time spent in doing INT(10.6 + 0.5) for obtaining the same rounding toward infinity can be shorter: in the case of using POKE/PEEK as before, INT will spend around 3 milliseconds less. The same occurs with the memory footprint of both alternatives.

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, and also that you cannot use this trick when v is 0, because in that case RANDOMIZE does not store that value into SEED.

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 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 - 1, maybe more natural for programmers of languages where array indexes begin at 0.

We can measure the time gain of these cyclic increments of integer variables with this program:

If we run it as it is and then change line 20 by:

and run it again, we get a difference of 540 microseconds in favor of the second version. This acceleration can be important (running just twice the second version of line 20 saves more than 1 millisecond!). On the other hand, if we do the same with the cyclical increments from 0 to n-1 we save 420 microseconds with respect to using IF. We can also deduce from this experiment that counting (cyclically) from 0 to n-1 in this fast way is 540 microseconds faster than counting (fast, cyclical) from 1 to n.

Finally, do not forget that 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.

[Click here to read this in English ]

Éste es el segundo 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. Funcionalidades diversas y medida del tiempo

V. Operaciones en la pantalla basadas en caracteres

En la entrega anterior de esta serie de artículos explicábamos que el intérprete de BASIC de la ROM del ZX Spectrum no dispone de una tabla de acceso aleatorio para las líneas de programa, lo que incrementa el tiempo de ejecución a la hora de buscar una concreta, pasando de coste computacional constante a lineal.

En esta segunda parte descubriremos un problema análogo con las variables:

El intérprete no dispone de ninguna información que relacione en tiempo constante el nombre de una variable con la dirección de memoria donde se halla

Hay que reconocer que esto hubiera sido complicado de incluir en aquella época, pues hubiera implicado implementar una estructura de datos más compleja que una simple tabla, debido a que la clave de búsqueda es una cadena de texto (el nombre de la variable) y no un número. A no ser que se hubiera usado un hash, no hubiera tenido coste de O(1) en ningún caso, por lo que tampoco habría merecido mucho la pena en una máquina tan limitada como el ZX.

En cualquier caso, la consecuencia de esta carencia es que encontrar una variable en memoria tiene un coste en el peor caso de O(n*m), donde n es el número de variables existentes y m la longitud del nombre más largo de variable (numérica) definida en el programa. Indicamos numérica porque las variables de texto, las tablas y las de bucle FOR no pueden tener más de una letra en su nombre.

Este proceso de búsqueda es igual al de los números de línea: el intérprete empieza con un puntero a la primera variable en memoria, comprueba si es la que busca recorriendo las letras de su nombre, y, en caso contrario, incrementa el puntero en base al espacio ocupado en memoria por la variable para pasar a comprobar la siguiente.

Por tanto, aquí podemos recomendar, para incrementar la velocidad de ejecución del código, lo siguiente:

Aquellas variables que se usen más a menudo o en zonas que requieran un tiempo de ejecución crítico a) deben crearse antes en el programa y b) deben tener nombres más cortos.

En otras palabras: es conveniente que exista una parte del programa que se encargue de dar valor a todas las variables, en orden de uso decreciente, y que se ejecute al comenzar (debería estar situada al final del programa, por lo que explicamos en la primera entrega de esta serie). También, deberíamos usar nombres cortos en el caso de variables numéricas escalares de uso frecuente. De esa manera las más utilizadas ocuparán lugares iniciales en la zona de variables y se encontrarán más rápido.

A este respecto, la utilidad de transformación de código de ZX-Basicus tiene una opción (--shortenv) que acorta automáticamente los nombres de todas las variables numéricas de nombres largos que pueda. Su contrapartida es que los nombres acortados ya no serán tan comprensibles, por lo que es conveniente usarla sobre un código ya terminado para producir el optimizado.

El programador de juegos BASIC @igNaCoBo me ha sugerido hacer una medida de tiempos incurridos por el intérprete al buscar variables, pues había detectado que a partir de un número determinado de ellas es más conveniente utilizar la memoria directamente para, al menos, las variables de tamaño byte (mediante POKE / PEEK) en lugar de crear esas variables. Para hacer estas medidas se puede partir del siguiente programa: