[Cursoc] Un articulo sobre porque estudiar C\C++

[Magnanego, Nestor]

Hola lista, encontre este articulo y quiero compartirlo con Uds. Saludos.
Nestor.

De Vuelta a las bases 	

Por Joel Spolsky
Traducido por José Manuel Navarro 
Editado por Jerry Elizondo 
14/04/2003

En esta web dedicamos mucho tiempo a hablar 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, son 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. Finge que eres un
programador principiante. Olvídate de 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:
	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.

	Tus cadenas no pueden contener ceros. Así que no podrás almacenar
cualquier valor binario, como una imagen 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 Cero 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 "Shlemiel el Pintor". ¿Quién es
Shlemiel? Pues el chaval de este chiste:
	Shlemiel 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 moneda.
	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 da una pequeña moneda.
	Al día siguiente, Shlemiel 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 Shlemiel, "cada día estoy más y más
lejos del bote de pintura."


(para más información, ¿qué son los números reales?)
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 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
"Shlemiel 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 Shlemiels 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 llaman 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 aludido a 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 aguántame un poco 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 otra 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 impredecible 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 automáticamente. ¿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 complicada 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 lo resuelven, 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 entender todo sobre lo que estamos
intentando conseguir, y nos intenta ayudar a que no escribamos algoritmos de
Shlemiel inadvertidos.


La semana pasada escribí 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 principio 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>
<libros>
<libro>
<titulo>UI Design for Programmers</titulo>
<autor>Joel Spolsky</autor>
</libro>
<libro>
<titulo>The Chop Suey Club</titulo>
<autor>Bruce Weber</autor>
</libro>
</libros>
Pregunta rápida: ¿Cual es el código para moverse al siguiente registro?
Estoooo....
Llegados a este punto, un buen programador diría: bien, leámos a memoria el
árbol XML para que podamos operar en é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 de cadenas, que hemos descubierto que es lenta, y montones de
operaciones de reserva de memoria, que hemos descubierto que son lentas,
para analizar sintácticamente, leer 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 pre-análisis, el rendimiento de
desplazarse de registro en registro es fijo, pero es un tiempo de inicio
enorme, y si no haces ese pre-aná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é, desde mi punto de vista, la enseñanza en las
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 inicial, 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 programas 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
Shlemiel, 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.