De vuelta a las bases
Hoy no voy a hablar de montilla, ni de las Kelly Finder, ni nada por el estilo, hoy toca demostrar que somos informáticos, cojones, asik, hoy toca aprender algo. Es largo, pero merece la pena, fusilado con cariño de aquí con licencia Creative Commons. Empecemos… (Si no eres informático, huye, estas a tiempo…)
Acabo de leer este articulo en LaWebDeJM y me ha parecido curioso. Absteneros de leerlo los que no seais programadores o frikis de la informatica porque os va a parecer un coñazo que te cagas. Quedais avisados.
En esta web dedicamos mucho tiempo hablando sobre temas grandiosos como “.NET vs. Java”, la estrategia del XML, bloqueos, estrategia competitiva, diseño de software, arquitectura, y así sucesivamente.
Todos estos temas son, de alguna manera, como un pastel hecho de capas. En la capa superior, tenemos la estrategia del software. Por debajo de esto, reflexionamos sobre arquitecturas como .NET, y por debajo están los productos individuales: productos de desarrollo de software como Java o plataformas como Windows.
Vayamos más abajo en el pastel, por favor. ¿DLLs? ¿Objetos? ¿Funciones? ¡No! ¡Más abajo! En algún momento estarás pensando en líneas de código escritas en lenguajes de programación.
Aún no bajaste lo suficiente. Hoy quiero reflexionar sobre las CPUs: un pequeño pedazo de silicio moviendo bytes a su alrededor. Finje que eres un programador principiante. Deja caer todo el conocimiento que has adquirido sobre programación, software, gestión, y regresa al nivel más bajo de los temas fundamentales de Von Neumann. Saca al J2EE de tu cabeza por un momento. Piensa en los bytes.
¿Por qué estamos haciendo esto? Creo que muchos de los mayores errores que la gente comete incluso en los niveles más altos de la arquitectura, vienen de tener un conocimiento muy débil o nulo de unas pocas cosas sencillas, en los niveles más bajos. Hemos construido un maravilloso palacio, pero los cimientos son un desastre. En vez de una buena base de cemento, tienes escombros ahí abajo. Así que el palacio parece bueno, pero a veces la bañera se desliza por el suelo del cuarto de baño y no tienes ni idea de lo que está pasando.
Así que hoy, tómate un buen respiro. Camina conmigo, por favor, a través de un pequeño ejercicio, que guiaré usando el lenguaje de programación C.
Recuerda el modo en que trabajan las cadenas en C: consisten en un manojo de bytes seguidos por un carácter nulo, que tiene el valor 0. Esto tiene dos implicaciones obvias:
1. No hay ningún modo de saber dónde termina la cadena (es decir, su longitud) sin moverse a través de ella, buscando el carácter nulo del final.
2. Tus cadenas no pueden contener ceros. Así que no podrás almacenar cualquier valor binario, como una imágen JPEG, en una cadena de C.
¿Por qué las cadenas de C trabajan de este modo? Esto es debido a que el microprocesador PDP-7, en el que se inventaron el sistema operativo UNIX y el lenguaje de programación C, tiene un tipo de dato llamado ASICZ. ASICZ significa ASCII con un Zero al final.
¿Es este el único modo de almacenar cadenas? No, de hecho, es uno de los peores métodos de almacenar cadenas. Para programas no-triviales, APIs, sistemas operativos, librerías de clases, etc., debes evitar el uso de cadenas ASICZ como una plaga. ¿Por qué?
Comencemos escribiendo una versión del código de strcat, la función que añade una cadena a otra.
void strcat( char* dest, char* src )
{
while (*dest) dest++;
while (*dest++ = *src++);
}
Estudia el código un poco y observa qué es lo que estamos haciendo. Para empezar, recorremos la primera cadena buscando su carácter terminador nulo. Cuando lo encontramos, recorremos la segunda cadena copiando un carácter a la segunda cadena cada vez.
Este tipo de manipulación y concatenación de cadenas fue suficientemente bueno para Kernighan y Ritchie, pero esto tiene sus problemas. Aquí está el problema. Supón que tienes un manojo de nombres que quieres concatenar juntos en una gran cadena.
char bigString[1000]; /* Nunca sé cuanto tengo que reservar… */
bigString[0] = ‘\0′;
strcat(bigString,”John, “);
strcat(bigString,”Paul, “);
strcat(bigString,”George, “);
strcat(bigString,”Joel “);
Esto funciona ¿verdad? Sí. Y parece correcto y elegante.
¿Y cómo va de rendimiento? ¿Es tan rápido como podría llegar a ser? ¿Se puede ampliar bien? Si tenemos un millón de cadenas que concatenar, ¿sería un buen modo de hacerlo?
No. Este código usa el algoritmo de “Juanito el Pintor”. ¿Quién es Juanito? Pues el chaval de este chiste:
Juanito consiguió un trabajo como pintor de calles, pintando la línea discontinua de las carreteras. El primer día cogió su cubo de pintura y acabó 300 yardas de carretera. “¡Eso está realmente bien!” le dijo su jefe. “Eres un trabajador muy rápido” y le dio una propina.
El día siguiente, sólo consiguió hacer 150 yardas. “Bueno, no ha estado tan bien como ayer pero todavía eres un trabajador rápido. 150 yardas es una cantidad muy respetable”. Y le pagó una pequeña propina.
Al día siguiente, Juanito completó 30 yardas de carretera. “¡Sólo 30 yardas!” le gritó su jefe. “¡Esto es inaceptable!. El primer día hiciste 10 veces más distancia ¿Qué está pasando aquí?”
“No puedo hacerlo mejor”, dijo Juanito, “cada día estoy más y más lejos del bote de pintura.”
Este chiste malo ilustra exactamente lo que ocurre cuando usas la función strcat tal y como yo lo hice. Mientras que la primera parte del strcat tiene que escanear por la cadena destino cada vez, buscando el maldito carácter nulo una y otra vez, esta función es más y más lenta de lo que necesita ser, y no se amplía del todo bien. Montones de código que usas cada día tienen este problema. Muchos sistemas de archivos están implementados de un modo en el que no es buena idea poner muchos archivos en el mismo directorio. Para ver este efecto, intenta abrir la Papelera de Reciclaje de Windows cuando está a rebosar — te llevará horas que se abra, lo que tiene claramente un rendimiento no lineal al número de archivos que contiene. Ahí seguro que está el algoritmo de “Juanito el Pintor” por algún lado. Cada vez que algo parezca que debe tener un rendimiento lineal, pero parezca que tiene un rendimiento exponencial, busca a los Juanitos ocultos. A menudo están por tus librerías. Mirando en un grupo de “strcats” o en un strcat dentro de un bucle, puede que no parezca tener un rendimiento exponencial, pero eso es lo que está pasando.
¿Cómo puedo corregir esto? Algunos programadores espabilados de C, implementaron su propia función mistrcat del siguiente modo:
char* mistrcat( char* dest, char* src )
{
while (*dest) dest++;
while (*dest++ = *src++);
return –dest;
}
¿Qué hemos hecho ahí? Con un pequeño coste extra, retornamos un puntero al final de la nueva cadena, que es más larga. De ese modo, el código que llama a esta función puede decidir añadir al final sin tener que volver a recorrer la cadena:
char bigString[1000]; /* Nunca sé cuanto tengo que reservar… */
char *p = bigString;
bigString[0] = ‘\0′;
p = mistrcat(p,”John, “);
p = mistrcat(p,”Paul, “);
p = mistrcat(p,”George, “);
p = mistrcat(p,”Joel “);
Esto tiene, por supuesto, un rendimiento lineal, no exponencial., así que no sufre ninguna degradación cuando tengas un montón de cadenas para concatenar.
Los diseñadores de Pascal se dieron cuenta de este problema y lo solucionaron almacenando el número de bytes en el primer byte de la cadena. Estas se llamas Cadenas Pascal. Pueden contener ceros, y no están terminadas por nulo. Debido a que un byte sólo puede almacenar números entre 0 y 255, las cadenas Pascal están limitadas a 255 bytes de longitud, pero debido a que no están terminadas por el carácter nulo, ocupan la misma cantidad de memoria que las cadenas ASCIZ. Lo mejor de las cadenas Pascal es que nunca tienes que hacer un bucle para averiguar la longitud de la cadena. Buscar la longitud de la cadena es una instrucción en ensamblador, en vez de un bucle. Es monumentalmente más rápido.
El viejo sistema operativo de Macintosh usaba cadenas Pascal por todos los lados. Muchos programadores de C en otras plataformas usaban cadenas Pascal para acelerar los programas. Excel usa cadenas Pascal internamente, lo que es la razón por la que las cadenas, en muchos lugares en Excel, estén limitadas a 255 bytes, y es también una de las razones por las que Excel es brillantemente rápido.
Durante mucho tiempo, si querías poner un literal como cadena Pascal es tu código C, tenías que escribir:
char* str = “\006Hello!”;
Pues si, tienes que contar el número de bytes a mano, tú mismo, y codificarlo en el primer byte de tu cadena. Los programadores perezosos solían hacer esto, para sus programas lentos:
char* str = “*Hello!”;
str[0] = strlen(str) - 1;
Fíjate que en este caso, tienes una cadena que está terminada en nulo (esto lo hace el compilador) así como una cadena Pascal. Yo solía llamarlas jodidas cadenas, porque es más fácil que llamarlas cadenas Pascal terminadas en nulo, pero este es un canal para niños, así que tú tendrás que llamarlas por su nombre largo.
Antes, he eludido una cuestión importante. Recuerdas esta línea de código?
char bigString[1000]; /* Nunca sé cuanto tengo que reservar… */
Como hoy estamos dedicando atención a los bytes, no debería ignorar esto. Tendría que haber hecho esto correctamente: averiguar cuantos bytes necesito y reservar la cantidad necesaria de memoria.
¿Debería?
Porque de otro modo, como ves, un hacker avispado leerá mi código y se dará cuenta que estoy reservando sólo 1000 bytes y esperando que sean suficientes, así encontrará algún modo fácil de burlarme y hacerme concatenar una cadena de 1100 bytes en mi memoria de 1000 bytes, así que sobrescribiendo el marco de pila y cambiando la dirección de retorno, se ejecutará algún código que el hacker haya escrito. De esto es de lo que hablan cuando dicen que un programa en particular es susceptible al desbordamiento de buffer. Esta fue la causa número uno de intrusiones y gusanos en los viejos días, antes de que el Microsoft Outlook hiciera el pirateo lo suficientemente fácil para que los adolescentes lo practicaran.
De acuerdo, así que todos esos programadores son un poco torpes. Deberían averiguar cuanta memoria reservar.
Pero en realidad, el C no nos lo pone fácil. Volvamos a mi ejemplo de los Beatles:
char bigString[1000]; /* Nunca sé cuanto tengo que reservar… */
char *p = bigString;
bigString[0] = ‘\0′;
p = mistrcat(p,”John, “);
p = mistrcat(p,”Paul, “);
p = mistrcat(p,”George, “);
p = mistrcat(p,”Joel “);
¿Cuanto debo reservar? Intentemos hacerlo por el método correcto:
char* bigString;
int i = 0;
i = strlen(”John, “)
+ strlen(”Paul, “)
+ strlen(”George, “)
+ strlen(”Joel “);
bigString = (char*) malloc (i + 1);
/* recuerda reservar espacio para el terminador nulo */
…
No puedo creerlo. Probablemente ya estás a preparado para cambiar de canal. No te voy a echar las culpas, pero enfádate conmigo porque esto se pone realmente interesante.
Tenemos que escanear a través de todas las cadenas una vez sólo para averiguar lo largas que son, y después, escanearlas otras vez para concatenarlas. Al menos si usas cadenas Pascal, la operación strlen es rápida. Quizá podemos escribir una versión de strcat que redireccione la memoria por nosotros.
Eso nos abre un nuevo agujero para los gusanos: las reservas de memoria. ¿Sabes cómo funciona malloc? Por la naturaleza de la función malloc, tiene una lista enlazada muy larga de bloques de memoria disponible, llamada “cadena de libres” (free chain). Cuando llamas a malloc, se recorre la lista enlazada buscando un bloque de memoria que sea lo suficientemente grande para tu petición. Entonces, corta ese bloque de memoria en dos trozos: uno del tamaño que has pedido y el otro con los bytes que sobran, te da el bloque que pediste y pone el bloque sobrante (si hay) de nuevo en la lista enlazada. Cuando llamas a la función free, añade el bloque que estás liberando en la cadena libre. Eventualmente, la cadena libre cambia continuamente hasta sólo contener pequeñas piezas, y si pides una pieza grande, no hay ninguna disponible del tamaño que querías. Así que malloc hace una espera, y comienza a rumiar alrededor de la cadena de libres, ordenando cosas y juntando pequeños bloques adyacentes en bloques más grandes. Esto tarda 3 días y medio. El resultado final de todo este lío es que el rendimiento de malloc nunca es muy bueno (siempre debe recorrer la cadena de libres) y, a veces, es impredeciblemente y espantosamente lento mientras hace esta limpieza. Esto es, dicho sea de paso, el mismo rendimiento que los sistemas de recolección de basura, así que todas las aclamaciones de la gente, acerca de cómo los recolectores de basura imponen una penalización en el rendimiento, no son del todo ciertas, mientras que las implementaciones típicas del malloc tienen el mismo tipo de inconvenientes). De todas formas, hay una menor pérdida de rendimiento en el caso del malloc que en caso de los recolectores de basura.
Los programadores espabilados minimizan los inconvenientes potenciales de malloc, reservando siempre bloques de memoria que son potencias de 2. Ya sabes, 4 bytes, 8 byes, 16 bytes, 18446744073709551616 bytes, etc. Por razones que deberían ser intuitivas para todo el mundo que juegue con Lego, esto minimiza la cantidad de la fragmentación que ocurre en la cadena de libres.
Aunque pueda parecer que esto desperdicia espacio, es también fácil de ver cómo nunca se desperdicia más del 50% del espacio. Así que tu programa usa, no más de dos veces la cantidad de memoria que necesita, lo que no es nada del otro mundo. Supongamos que escribes una función strcat, que redirecciona el buffer de destino automaticamente. ¿debería redireccionar exactamente a la nueva cantidad necesitada? Mi profesor y mentor Stan Eisenstat sugiere que cuando llames a realloc, deberías duplicar el tamaño de la memoria que previamente ha sido reservada. Esto significa que nunca tienes que llamar a realloc más de log n veces, lo cual tiene un rendimiento aceptable incluso para cadenas gigantescas, y nunca desperdiciarás más del 50% de tu memoria.
De cualquier modo, la vida se vuelve más y más liada aquí abajo en bytelandia. ¿No estás contento de no tener que escribir en C nunca más? Tenemos todos esos magníficos lenguajes como Perl, Java y VB, y XSLT que nunca te hizo pensar de un modo como este, sólo tratan con él, de algún modo. Pero en ocasiones, la infraestructura de cañerías sobresale en el medio de la sala de estar, y tenemos que pensar si debemos o no utilizar la clase String o StringBuilder, o alguna otra distinción, debido a que el compilador no es lo suficientemente inteligente para entenderlo todo sobre lo que estamos intentando conseguir, y nos intenta ayudar a que no escribamos algoritmos de Juanito inadvertidos.
La semana pasada escribía que no puedes implementar la instrucción SQL SELECT autor FROM libros de un modo rápido cuando tus datos están almacenados en XML. Sólo en el caso en que nadie entienda de qué estuve hablando, y ahora, que ya hemos estado rondando alrededor de la CPU durante todo el día, tiene más sentido.
¿Cómo implementa una base de datos relacional la instrucción SELECT autor FROM libros? En una base de datos relacional, cada fila de la tabla (p.e. la tabla libros) tiene exactamente la misma longitud en bytes, y cada campo está siempre situado a la misma distancia del principio de la fila. Así, por ejemplo, si cada fila de la tabla libros tiene 100 bytes de longitud, y el campo autor está a una distancia de 23 desde el principios de la fila, entonces habrá autores almacenados en los bytes 23, 123, 223, 323, etc. ¿Cuál es el código para moverse al siguiente registro en el resultado de una consulta? Básicamente, este:
puntero += 100;
Una instrucción del procesador. Ráaaaaaaapido.
Ahora, echemos in vistazo a la tabla de libros en XML
< ?xml bla bla>
Pregunta rápida: ¿Cual es el código para moverse al siguiente registro?
Estoooo….
Llegados a este punto, un buen programador diría: bien, hagamos un parse en memoria del XML para que podamos operar con él razonablemente rápido. La cantidad de trabajo que tiene que hacer la CPU en este caso, para hacer el SELECT autor FROM libros te aburriría hasta que se te salten las lágrimas. Como todo programador de compiladores sabe, el análisis léxico y sintáctico son las operaciones más lentas de la compilación. Basta decir que esto conlleva manipulación con cadenas, que hemos descubierto que es lenta, y montones de operaciones de reserva de memoria, que hemos descubierto que es lenta, para analizar sintácticamente, hacer el parse, y construir el árbol en memoria. Todo esto suponiendo que tendrás suficiente memoria para cargar todo a la vez. Con las bases de datos relacionales, el rendimiento de desplazarse de registro en registro es constante, y es, de hecho, una instrucción del procesador. Esto es así por su diseño. Y gracias a los archivos proyectados en memoria, sólo tienes que cargar las páginas de disco que realmente vayas a utilizar. Con el XML, si haces un preanálisis, el rendimiento de desplazarse de registro en registro es fijo, pero es un tiempo de inicio enorme, y si no haces ese preanálisis, el rendimiento de moverte entre registros varía dependiendo de la longitud del registro y es todavía cientos de instrucciones del procesador.
Lo que esto significa para mi es que no puedes usar XML si necesitas un buen rendimiento y tienes montones de datos. Si tienes muy pocos datos, o si lo que estás haciendo no tiene por qué ser rápido, el XML es un buen formato. Y si realmente quieres lo mejor de ambos mundos, tienes que idear un modo de almacenar metadatos junto con tu XML, algo parecido a la cuenta de bytes de las cadenas Pascal, que te proporciona consejos acerca de donde están las cosas en el archivo, de modo que no tengas que analizarlo y escanearlo para ello. Pero, por supuesto, en ese caso no puedes usar un editor de textos para modificar el archivo, porque eso echaría a perder los metadatos, así que no es realmente XML.
Llegados a este punto, para aquellos tres simpáticos miembros de mi audiencia que están aún conmigo, espero que hayáis aprendido o reflexionado algo. Espero que haber pensado en los temas aburridos de primero de carrera, como el modo de funcionar de strcat y malloc, te haya dado una nueva herramienta para pensar sobre los últimos y más altos de los niveles, estrategias y decisiones que tomas sobre la arquitectura, tratando con tecnologías como XML. Como trabajo para casa, puedes pensar sobre cómo los chips Transmeta siempre parecerán lentos, o porqué las especificaciones originales para las tablas de HTML fueron tan mal diseñadas, que tablas grandes en páginas web no se podían ver rápidamente por las personas que usaban módem. O piensa acerca de por qué la arquitectura COM es tan rápida, aunque deja de serlo cuando atraviesas las fronteras de tu proceso. O sobre porqué la gente del NT puso el controlador de vídeo en el espacio del kernel en vez del espacio de usuario.
Todas estas cosas requieren que pienses en los bytes, y afectan a las capas más altas de decisión que hacemos en todos los tipos de arquitectura y estrategia. Este es el por qué de que mi punto de vista sobre la enseñanza en la carreras informáticas debe comenzar desde las bases, usando C y construyendo desde el procesador. En estos momentos estoy muy disgustado porque muchos programas de enseñanza creen que Java es un buen lenguaje introductorio, porque es “fácil” y no te confunde con todos los temas aburridos sobre cadenas y malloc, pero puedes aprender una buena POO que hará tus programa incluso más modulares. Esto es un desastre pedagógico que acabará por ocurrir. Generaciones de graduados están llegando a nosotros y creando algoritmos de Juanito, y ellos ni siquiera se dan cuenta, porque no tienen ni idea de lo qué son las cadenas en un nivel profundo, difícil, incluso si no puedes ver eso dentro de tu script en Perl. Si quieres enseñar a alguien alguna cosa bien, debes empezar en los niveles más bajos. Como en “Karate Kid”. Limpiar, Encerar. Limpiar, Encerar. Haz esto durante tres semanas. Después, tumbar a otros karatekas es fácil.
Artículo publicado originalmente en originalmente en Joel On Software (inglés o castellano), y reproducido en esta página con el permiso del autor.
Y yo me digo, los chistes de algunos de windows estan de pm, pero porqué no nos comentan de paso estas cosas … Manda carallo…
)
