Por qué no sumar FPS y la ley de Amdahl

Hace poco leí de un desarrollador de videojuegos algo así como "cuando uso el nuevo método, pierdo 30 FPS". Los FPS son los fotogramas por segundo. Es decir, son una frecuencia. Generalmente la suma y las frecuencias se llevan mal y este es un buen ejemplo de por qué no es válido sumar.

Pantalla del Crysis con grandes cantidades de vegetación que ralentizan el renderizado bajando los FPS a lo mínimo imprescindible para que la vista sea suave: 26, la cifra en la esquina superior derecha. El estándar de cine es de 24 FPS, pero las imágenes suelen contener movimiento. Generalmente esto es muy costoso de conseguir en tiempo real por lo que en los videojuegos el resultado es más brusco a esa misma tasa de fotogramas.

Al trabajar con frecuencias contamos cuántas veces podemos realizar una operación que dura [$ t $] segundos. La frecuencia será precisamente
[$$ f=\frac{1}{t} $$]
Si añado algo a esa operación, me durará lo que duraba antes más el añadido [$ t+a $]. La nueva frecuencia será
[$$ f_a=\frac{1}{t+a} $$]

Generalmente no añadimos o quitamos nada. Simplemente, al cambiar una parte de nuestra operación, ésta se hace más larga o más corta. Es lo que pasaba con el desarrollador de videojuegos que cambiaba la manera de hacer algo y cambiaba su frecuencia de desempeño.

Supongamos que de todo ese tiempo [$ t $] solamente la fracción [$ p $] es la parte que tocamos. Esto quiere decir que la parte tarda en ejecutarse [$ tp $] y todo lo que no es la parte cambiada es [$ t(1-p) $].

El cambio que hago será probablemente una mejora. Si antes de la mejora tardaba [$ tp $] en realizar la operación de la parte a cambiar, después de una mejora de [$s$] veces tardará [$s$] veces menos. Es decir,

[$$ \frac{tp}{s} $$]

Como bien se sabe, en computación mejorar es ir más rápido haciendo algo. Tardamos menos tiempo así que dividimos. Ir el doble de rápido significa tardar la mitad.

Ahora voy a sumar los tiempos que tardo en la parte no mejorada y la parte mejorada. Es esta expresión:

[$$ \frac{tp}{s}+t(1-p) = t\left( \frac{p}{s} + (1-p) \right)$$]

Finalmente voy a obtener en vez del tiempo que tardo en hacer la operación completa, cuántas veces voy a poder realizarla. Esto es la frecuencia con mejora [$ f_s $].

[$$ f_s = \frac{1}{ t\left( \frac{p}{s} + (1-p) \right) } $$]

Afortunadamente podemos expresar esta frecuencia con mejora en función de la frecuencia sin mejora.

[$$ f_s = f \frac{1}{ \frac{p}{s} + (1-p) } $$]

El factor de mejora no es una suma como decía el desarrollador de videojuegos al hablar de FPS. El factor de mejora es una constante multiplicativa. Precisamente es

[$$ A =  \frac{1}{ \frac{p}{s} + (1-p) } $$]

Esta expresión es la conocida Ley de Amdahl y el factor que calcula puede escribirse como un tanto por ciento. Habría sido más correcto entonces que el desarrollador de videojuegos hubiese dicho que perdía el 30% de rendimiento con el nuevo método.

miniSL parte 6 - Campos de celda

En las entradas anteriores hemos decidido los tipos de celdas que tenemos. Falta por saber qué información guarda cada uno de estos tipos. Está claro que, por lo menos, toda celda ha de guardar el tipo de celda que es. De esta manera lo que tendremos es una unión etiquetada.

Además, necesitaremos según el tipo:

• UNUSED: Un puntero a la siguiente celda sin usar. De esta manera mantenemos una lista simplemente enlazada de las celdas sin usar.
• EMPTY_LIT: La lista vacía no requiere ningún valor adicional.
• INT_LIT: Un literal entero requiere el valor entero que almacena.
• STRING_LIT: Un literal de cadena requiere la cadena que almacena.
• LAMBDA_VAL: Un valor de función definida por el usuario requiere tres cosas: el código a ejecutar, los parámetros que tiene la función y la clausura léxica del código. Usaremos una lista para agrupar el código con los parámetros por lo que sólo requeriremos dos valores.
• NATIVE_VAL: Un puntero a la función nativa.
• ENVIR_VAL: Un puntero a la tabla hash o árbol de búsqueda que relaciona los nombres de las variables con sus valores. Además, otro puntero a el entorno padre (si existe) donde se buscarán los nombres que no se encuentren en la tabla de éste.
• BOOL_VAL: El valor verdadero o falso del booleano.
• NAME_CODE: Un puntero a la cadena con el nombre de la variable.
• COMBINE_CODE: El operador y sus operandos en una lista.
• CONS_CTOR: La cabeza y el resto de la lista.

Adicionalmente, vamos a guardar en cada celda un bit con la marca del recolector de basura. Esta marca significa que la celda está en uso y no se puede borrar.

Con todas estos campos en la cabeza, la estructura de una celda queda así:

struct CELL
{
 CELL_TYPE type;
 bool mark;    //Garbage collection mark
 union
 {
  CELL* next_unused;   //UNUSED
  int int_val;    //INT_LIT
  bool bool_val;    //BOOL_VAL
  STRING const* string_val; //STRING_LIT
  CELL* head;     //CONS.
  CELL* code;     //LAMBDA_VAL. The cell must be a CONS_CTOR with parameters and body
  NATIVE native;    //NATIVE_VAL
  ENVIR_TABLE* envir_table; //ENVIR_VAL
  CELL* op;     //COMBINE_CODE. The cell must be code (Any *_CODE type or CONS or EMPTY)
 };

 union
 {
  CELL* tail;   //CONS. Must be CONS or EMPTY.
  CELL* closure;  //LAMBDA_VAL. The cell must be an environment (ENVIR_VAL)
  CELL* parent_envir; //ENVIR_VAL. The pointer may be NULL or an environment cell (ENVIR_VAL)
  CELL* operands;  //COMBINE_CODE. The cell must be a list of code.
 };
};

La mayoría de los tipos de C++ que hemos usado han quedado por definir. En principio dependerán de la plataforma.

typedef std::wstring STRING;
typedef std::wistream ISTREAM;
typedef std::wostream OSTREAM;
typedef std::map<STRING, CELL*> STRING_MAP;
typedef std::map<CELL*, CELL*> ENVIR_TABLE;
typedef std::deque<CELL> CELL_STORAGE;
typedef CELL& (*NATIVE) (Script& script, CELL& args, CELL& envir);

En la siguiente entrada hablaremos con más tranquilidad de STRING_MAP y ENVIR_TABLE; en otra posterior hablaremos de CELL_STORAGE y, mucho después, de NATIVE, ISTREAM y OSTREAM.

Asincronía en C# 5.0

En octubre Eric Lippert empezó una serie en su blog dedicada a la nueva característica de C#: la posibilidad de escribir programas asíncronos. Es un paso lógico tras los cambios producidos en las versiones anteriores de C#.

¿Qué tienen en común las siguientes características de C#? (Todas convenientemente explicadas por Eric)

1. Los iteradores
2. Métodos anónimos
3. LINQ
4. Asincronía

Muy sencillo. Todas estas características se obtienen mediante una transformación sintáctica del código. Es decir. No hay una nueva semántica, sólo transformaciones sintácticas. ¿Y por qué es esto relevante? Porque se habrían evitado todo el follón si hubieran introducido un mecanismo de macros en el lenguaje. No algo tan crudo como el preprocesador de C. Quizás algo como los patrones de C++. O, mucho mejor, algo como las macros del LISP o Scheme.

Si es que al final volvemos al principio.

miniSL parte 5 - Tipos de celda

Como se comentó anteriormente, nuestra implementación de lenguaje script no sólo requiere almacenar valores, también requiere almacenar código o el estado de la ejecución. Esto se consigue mediante el uso de celdas (CELL).

Ahora que conocemos la sintaxis, sabemos qué tipos de celdas necesitamos para almacenar el código. De hecho, cada tipo de nodo del AST tendrá que ser una celda así que tenemos los siguientes tipos de celdas por ahora:

enum CELL_TYPE
{
UNUSED, 

//Literals
EMPTY_LIT, INT_LIT, STRING_LIT,

//Value constructors

//Code constructors
NAME_CODE, COMBINE_CODE,

//Value and code constructors
CONS_CTOR
};

Finalmente debemos saber cuáles van a ser los resultados de nuestras evaluaciones. Aparte de los literales, usaremos tres valores.

1. Los booleanos. 
2. Las funciones definidas por el usuario (lambda).
3. Las funciones predefinidas (nativas).

Para las evaluaciones, además, necesitamos un contexto que guarde la relación entre los nombres de las variables y el valor vinculado a ellas. Son los entornos de ejecución. En definitiva, los tipos de celdas que tenemos son:

enum CELL_TYPE
{
UNUSED, 

//Literals
EMPTY_LIT, INT_LIT, STRING_LIT,

//Value constructors
LAMBDA_VAL, NATIVE_VAL, ENVIR_VAL, BOOL_VAL, 

//Code constructors
NAME_CODE, COMBINE_CODE,

//Value and code constructors
CONS_CTOR
};

Ahora nos queda por saber qué información requiere cada tipo de celda y cómo vamos a almacenarla.