Desafío que un “programador” respondería en segundos
Como era de esperar, el apunte Diez señales de que no eres tan buen programador como piensas generó mucho debate (también en Java Hispano, como era de esperar por mencionar a Java:-) ), como también respuestas falaces y alguna que otra crítica como “que es muy generalista y/o poco técnico”. Pues vale, empecemos con algo más “técnico” para seguir pasando el agosto.
Supongamos que en C (en Java debería dar resultados comparables [1]) inicializamos una matriz de tamaño considerable:
#define S 10000 int a[S][S];
Al bucle siempre lo haríamos de la siguiente forma:
for (i=0; i<S; i++)
for (j=0; j<S; j++)
a[i][j] = 0;
Preguntas:
Explicar porqué –casi intuitivamente aunque muchas veces sin saberlo– hacemos la asignación así y no
a[j][i].Fundamental aunque derivada de la anterior. ¿Por qué si hacemos la asignación
a[j][i]el código se ejecuta al menos un orden de magnitud más lento? La respuesta es muy concreta y se puede dar en menos de dos tres líneas.¿Por qué pongo a la matriz como global y no local?
¿Por qué a veces las primeras veces que se ejecuta el código toma más tiempo que en las siguientes?
¿Qué relación tienen este problema de eficiencia con la programación estructurada?
[1] Pruebas con Java
Hice las pruebas en un “sencillo” programa en Java.
class j1 {
public static void main(String[] args) {
int[][] a = new int[10000][10000];
int i, j;
for (i=0;i<10000;i++)
for (j=0;j<10000; j++)
a[i][j] = 0;
}
}
Con Java GNU no tuve ningún problema para ejecutarlo, todavía no sé cómo lograr que se ejecute el Java6 de Sun sin que me de problemas de heap y luego que pueda pre-asignar la memoria con el -Xmx y -Xms, me da siempre Could not create the Java virtual machine ¿Alguien sabe cómo resolverlo si liarme con clases especiales? En resumen, el ejecutable “óptimo” tarda unas 6 veces más que C, unos 6.5 segundos. Mientras que en C el bucle erróneo toma 11 segundos, en Java 25 segundos.
Conclusión de Java: la gestión de memoria es bastante más lenta y se nota menos la diferencia entre uno y otro (no llega al orden de magnitud). Pero lo importante: también hay con el mismo cuidado que con C, el compilador no “optimza” estos casos. No vale la excusa, “en Java no te preocupas de estos temas”.
PS: Por favor abstenerse mis alumnos y amigos que me hayan escuchado sobre este ejemplo 
Vale, tengo las cuatro primeras pero no te pillo que quieres decir con la quinta. Por cierto ¿regalas cervezas o algo por acertar?
Comment by PerroVerd — Monday 13/8/2007 @ 16:22
Y yo que sólo se mucho PHP, Java por encima y comprendo Perl… veo que me estoy quedando atrás. ¿Dónde está el hype aquí?
Comment by CSEON — Monday 13/8/2007 @ 16:25
Creo que tengo lAs respuestas a las Cinco preguntas de Hoy, y sin haberte escuchado el Ejemplo.
Lo de usar Programación Estructurada, más que por la eficiencia, lo haría por el resto de motivos
Ahora bien, ¿no haces trampa? Estás tratando una “especialidad” que la mayoría de programadores no va a tocar nunca. La “eficiencia” a bajo nivel no lo es todo.
Comment by DZPM — Monday 13/8/2007 @ 16:26
1.- Por que “ji” es de risa, e internet is serious bussines.
2.- Por que marcha atrás la caja de cambios reduce más que las que son hacia delante.
3.- Por que así flota.
4.- Por que se aprende el camino.
5.- Sí.
Comment by krusher — Monday 13/8/2007 @ 16:26
1 y 2 porque las matrices se almacenan en memoria por filas y por tanto el acceso será más rápido si se hace también en este orden (a memoria principal/caché se llevarán los datos más cercanos a la posición accedida, y los datos más cercanos por tanto son los de la misma fila).
3. Porque las variables locales se almacenan en memoria de pila en tiempo de ejecución; al ser global se almacenará en memoria estática al comenzar la ejecución del programa.
4. Porque se accede a posiciones de memoria que no se habían accedido previamente, por lo que se producen fallos de página y hay que traer los datos a memoria caché, o memoria principal si no caben.
La 5 no la sé o no la entiendo :-S
¿Qué he sacado?
Comment by Pablo — Monday 13/8/2007 @ 16:32
#5, no hagas spoilers ¬¬
Comment by DZPM — Monday 13/8/2007 @ 16:40
#5,
1 y 2: Es una parte de la ecuación, pero falta todavía, de igual o más importancia pero menos obvio que la conocida cache de RAM
3. Lo de la pila es verdad, pero la razón no es esa (que además no es del todo así, ya que todos los SO con gestión de memoria usan la paginación por demanda).
4. Es una parte.
5. Espero a ver si lo saca alguien, pero está íntimamente relacionado con 1 y 2 es uno de los criterios fundamentales de porqué se ha definido la prog. estructurada y porqué hay que usarla. Algunos lo explican de forma pedestre con “no usar el GOTO”
Comment by gallir — Monday 13/8/2007 @ 16:53
1. Yo me imagino como se recorre el bucle y en las matrices, siempre pienso en que lo más exterior es el primer índice.
2. De acuerdo con Pablo.
3. De acuerdo con Pablo.
4. De acuerdo con Pablo.
5. Debido a que no se usan GOTOs sino bucles, ya se saben más condiciones del problema y se podrían aplicar técnicas de optimización como hacer varias asignaciones en paralelo de diferentes iteraciones del bucle. Esto se hace bastante en los procesadores Itanium de Intel.
Comment by David Horat — Monday 13/8/2007 @ 17:00
Sé la respuesta pero no la diré (aunque está mencionado en el artículo anterior). El silencio en las respuestas es estremecedor. Ricardo no deberias hacer pensar tanto que a algunos les explotan las neuronas o todavia están intentando entender las preguntas xD
Comment by a_toni — Monday 13/8/2007 @ 17:02
a #3: no creo que la pregunta sea trampa. Yo, que no soy informática, pero como física tengo que programar en C, ya sabía lo de las filas y las columnas de las matrices. O sea, que si lo sé yo, que di un semestre de C en la uni, me parecería bastante vergonzoso que un informático no lo supiera. Aunque luego no se dedicara en exclusiva a optimización de código.
Comment by luces — Monday 13/8/2007 @ 17:09
Tus alumnos nos abstenemos, pero pon esto en un examen y no te aprueban ni tres personas, ya te lo digo.
Comment by unf — Monday 13/8/2007 @ 17:44
Es fácil.
Cuando a [S] la entiendes como [j] es lógico que acontezca.. “for (i=0; i
Comment by Jan — Monday 13/8/2007 @ 18:01
Propongo para salir del atolladero una lectura rápida de [poesía]. Es que cuando le picas [a] [ricardo] el [te] devuelve nota[S] [S]olidas. Por eso me voy [S]ilbando bajito. Pero como mi área de competencia es el diseño de absurdos dejo esto para los programadores: ¿Cuántos pixeles físicos entran en un pixel virtual?
Comment by Jan — Monday 13/8/2007 @ 18:04
Jejeje, quiero participar con animo de suspender
1,2) La 1 y la 2, en memoria las matrices se guardan de manera líneal por filas [Fila1][Fila2][Fila3]. El escribirlo ji o ij la matriz quedará igual al acabar el algoritmo pero solo diferencia el orden de como se ha realizado. En Java tienes la ventaja de que la primera fila puede tener 2 columnas y la segunda 4 columnas por lo que un recorrido ij es mejor ya que en cada momento puedes evaluar cuantas columnas tiene la fila. Supongo que irá más rápido hacer ij ya que en ASM hacer un INC 1 en más rápido que un ADD AX, Tamañofila
Es decir un recorrido de memoria de uno en uno y no dando saltos.
3) Si la voy a utilizar poco yo la haría local y pasarla por parámetro. De hecho, se recomienda evitar las variables globales ya que se quedan en memoria durante toda la ejecución. Supongo que si la haces global es muy utilizada desde todas las funciones/métodos y así evitas poner ese parámetro en todas las llamadas. Pero yo haría los algoritmos genéricos que traten matrices genéricos. Por ejemplo, un algoritmo que inicialice a 0 la matriz que recibe, etc.
4) Buff, que dificil!. Creo que tiene que ver con la reserva de memoria, que no la primera vez tiene que buscar y le cuesta más. Luego también podría influir la cache del procesador, en procesadores (no me acuerdo ahora a partir de que modelo) los saltos JMP tenian mayor penalización
5) Esta la peor:( Supongo que tiene que ver con el Prefetching (Cache de instrucciones), el procesador cuando realiza una lectura en RAM, aprovecha y se trae varias instrucciones (ya que va, ir pa naa). Las carga como si no hubiese saltos por lo que hace menos lecturas en RAM si se programa sin que haya saltos. El programar en ASM te da la ventaja de recorrer sin dar saltos. Programarlo como está ahora (se utilizan condicionales que a veces darán false por lo que se “penalizará” a la cache y tendrá que volver a recargar.
http://www.dcc.uchile.cl/~rbaeza/cursos/proyarq/randreu/randreu.html
Espero no haber suspendido. Un poco de piedad.
Comment by JRubira — Monday 13/8/2007 @ 18:11
#14, tienes razón en el la forma de almacenamiento (quizás responde a 1), pero respondes erróneamente a la segunda.
En la 3 te equivocas, de hecho este caso no funciona en C, da un segmentation fault. La pregunta es ¿por qué?
4. Hm… va por el teme de memoriua virtual.
5. Si afecta es muy colateralmente, así que no.
Suspendido
Comment by gallir — Monday 13/8/2007 @ 18:16
#10, luces, no te sorprendas, es la intrepidez de la ignorancia
Es el patrón de muchas de las respuestas que recibí del otro apunte, por eso escribí antes, para que podamos evaluar más objetivamente el nivel de “buen programador” que tienen los comentaristas (de otras forma todos son la ostia de expertos)
PS: estos temas se enseñan en las carreras, ya sea explícitamente porque alguien les explicó así, o se puede deducir fácilmente de lo que se enseñan en unas pocas asignaturas claves.
Comment by gallir — Monday 13/8/2007 @ 18:19
Je, je, como se nota que Ricardo es profesor en la Uni. Si es que la cabra tira al monte…
Comment by pitito — Monday 13/8/2007 @ 18:21
Eso lo explicastes en clase, así que lo se (hace aaaaños) xD
Porque se guardan trozos enteros de la matriz en cache, por tanto los accesos a memoria son menores que de la otra forma (ya que por cada acceso a la matriz, habrías de acceder una vez a memoria, mientras que de esta forma no ya que están en la cache del procesador).
Las otras no las contesto que me tengo que ir :p
Comment by a — Monday 13/8/2007 @ 18:28
2.- mover un puntero dos bytes es barato. Avanzar y retroceder 10.000 bastante más costoso
Comment by david — Monday 13/8/2007 @ 18:50
Yo te contesto las 5 pero soy alumno tuyo. mejor dicho era…
Que tengas un buen dia!
Comment by Pedro Sureda — Monday 13/8/2007 @ 19:01
#19, david, no, cambiar el valor de un puntero es siempre O(1), no es eso… aunque derivado del valor de ese puntero. Ya han dicho uno, la cache de RAM.
Comment by gallir — Monday 13/8/2007 @ 19:02
¿los mileuristas-buenos-programadores pueden responder o es solo para los que ganan una pasta sean buenos o malos?
el punto 10 del anterior artículo para no echar gota, como decía el anuncio “hay muchos mundos pero están en este” a lo que añado “los hay que solo viven en su burbuja y se creen que el resto es lo mismo”
Comment by Defunkid — Monday 13/8/2007 @ 19:03
Viendo este ejemplo comprendo mejor lo que quieres decir con el post anterior. Son casos interesantes que te hacen reflexionar sobre la maquinaria que hay debajo. Java va un paso más alla a costa de dejar estas optimizaciones al compilador. Por un lado es un poco triste obviar de un plumazo lo que hay debajo, por otro, podrias dedicar el año entero a teoría de compiladores. Es mi opinión que es apropiado dejar fuera de un curso de introducción a la programación los detalles de implementación realizados por el compilador, y los detalles de hardware. Sobre todo, cuando hay asignaturas dedicadas a ello.
Comment by Anon — Monday 13/8/2007 @ 19:36
El manejo de los arrays y matrices en C siempre ha sido curioso e inusual comparado con otros lenguajes. En el lenguaje B, el predecesor del lenguaje C, cuando se inicializaba un array de la forma:
v[N];
en realidad se creaban N + 1 variables, no N como se podría esperar. La primera de ellas era la que en realidad correspondía a la variable “v”, y contenía la dirección de memoria del primer elemento del N-array propiamente dicho. De esta forma los demás elementos se obtenían sumando índices a esta variable-apuntadora, y de-referenciándolos, y “v” era simplemente un puntero.
Así, v[x] era equivalente a *(v + x). Esta forma era extremadamente flexible, ya que realmente al compilador le daba igual de dónde obtenías la dirección “v”: con tal de que fuese una dirección de memoria, ya se podía usar la notación v[x] para acceder al elemento “x” del bloque de memoria.
El problema de este sistema era que no se podían crear matrices de más dimensiones de forma cómoda. El lenguaje en sí no prohibía usar cosas como v[i][j], pero era simplemente equivalente a *(*(v + i) + j)). Es decir, “v” era un array de direcciones de memoria, cada uno de las cuales era a su vez otra dirección de memoria. Con lo que para obtener una matriz de orden N x M, hacía falta crear N * M + N + 1 variables.
Con la evolución de B a C se modificó un poco este proceso. Ahora, cuando se inicializaba un array de la forma:
int v[N];
simplemente se creaba un bloque de N variables. La dirección de memoria estaba ahora implícita: cuando el compilador encontraba “v”, sabía que correspondía a la dirección del primer elemento, pero no era necesario que éste se crease de forma explícita. v[x] era ahora equivalente a decir *(_base_ + x), donde _base_ es la dirección de memoria implícita.
Con el nuevo sistema de “punteros implícitos” era posible crear matrices de varias dimensiones. Cuando el compilador encontraba:
int v[N][M];
simplemente creaba un espacio contiguo de N * M variables. Los punteros estaban implícitos, de forma que v[x] equivalía a (_base_ + x * N), siendo _base_ la dirección de memoria base del espacio. Así, v[i][j] equivalía a *(_base_ + i * N + j). En realidad era muy parecido al sistema que utilizaba B pero con punteros implícitos en lugar de explícitos.
Volviendo al ejemplo en concreto, podemos ver que equivaldría a lo siguiente:
for (i=0; i<S; i++)for (j=0; j<S; j++)
*(_base_ + i * N + j) = 0;
Lo cual explicaría las ganancias en caché que se mencionaron.
De hecho, teniendo esto en cuenta, podemos ver que incluso podemos inicializar la matriz obviando uno de los bucles “for”:
#include <stdio.h>
#define S 100
int m[S][S];
int main () {
int* base = &m[0][0];
int lim = S * S;
while (lim– > 0) base[lim] = 398;
}
Comment by M2Z — Monday 13/8/2007 @ 19:57
#23,
> Java va un paso más alla a costa de dejar estas optimizaciones al compilador.
Ya agregué las pruebas en Java y las agregué al artículo. No es así, el efecto es similar.
#24,
> De hecho, teniendo esto en cuenta, podemos ver que incluso podemos inicializar la matriz obviando uno de los bucles “for”:
Sipes, pero te queda más ofuscado si quieres hacer los “saltos” de la versión errónea
Por cierto, int* base = &m[0][0] me parece queda más claro como:
int *base = (int *) m;
Comment by gallir — Monday 13/8/2007 @ 20:32
Voy a arriesgarme a contestar la 5ª, Creo que a relación que existe entre la programación estructurada y que el rendimiento sea mayor en las ejecuciones posteriores a la primera viene dado en que la arquitectura de los computadores esta pensada para este tipo de programación ( la estructurada, usando además el concepto de segmentación ) y optimizando la ejecución en base a previsiones sobre el código ya ejecutado. Por ejemplo si se esta accediendo a memoria de manera consecutiva, lo más probable es que el siguiente dato a acceder sea el siguiente de la serie (aquí también entran en juego las caches). Al inicio de la ejecución el procesador no tiene información en que basar las predicciones (Además la cache estará ’supuestamente’ vacía). Por otra parte en programación ‘no’ estructurada las previsiones tienen menos sentido. Y ahí esta mi respuesta , lo mismo me he marcado un triple arriesgandome
Comment by Pac — Monday 13/8/2007 @ 21:04
#26, bingo, es eso, se llama “localidad”. La programación estructurada ayuda mucho a que haya más localidad temporal y espacial.
Comment by gallir — Monday 13/8/2007 @ 21:07
Y otra errata que se me coló: donde dije
“int v[N][M]; […] de forma que v[x] equivalía a (_base_ + x * N),”
debería decir
“int v[N][M]; […] de forma que v[x] equivalía a (_base_ + x * M),”
Oops :S .
Comment by M2Z — Monday 13/8/2007 @ 21:21
Bonito problema, pero para que veas la diferencia de aproximació entre la academia y la empresa, yo llenaría la matriz así:
memset(A, 0, S*sizeof(A[0]));
Y el resto de las preguntas no me interesaría responderlas a menos que me dijeras cual es el premio.
Es más, no se si contrataría a un programador que use un loop para llenar de ceros un arreglo.
/* Tampoco contrataría a ningún programador que sólo aprendió java */
Comment by Eduardo Diaz — Monday 13/8/2007 @ 22:28
#29, eduardo, una de las virtudes de los académicos y científicos es encontrar modelos simples que permitan la comprensión y discusión. En este caso además que sirva para distintos lenguajes. Eso no tiene nada que ver con “empresa” vs “academia”.
Es muy fácil darse cuenta que el a[i][j] = 0 puede ser algo como (lo más probable es que en algo similar lo sea) a[i][j] = sin(i) * cos(j) (por dar un ejemplo, no tiene porqué ser cero, para eso se usan técnicas de matrices ralas (sparse).
> Es más, no se si contrataría a un programador que use un loop para llenar de ceros un arreglo.
No lo creas: http://www.google.com/codesearch?hl=en&lr=&q=%22%5Bi%5D%5Bj%5D%22&btnG=Search
Comment by gallir — Monday 13/8/2007 @ 22:41
Si nos ponemos así, ¿por qué no simplemente memset(A, 0, S*sizeof(A));
?
Además, en vez de 0 puede ser -1 por ejemplo (y un memset con 0xff es como poco, poco portable :D)
Comment by M2Z — Monday 13/8/2007 @ 22:44
argh, quise decir por qué no simplemente memset(a, 0, sizeof(a)); :S
Comment by M2Z — Monday 13/8/2007 @ 22:44
Ricardo, solo trataba de hacer una broma.
En todo caso, si ante una pregunta de este estilo un programador me muestra que conoce la RTL de C eso es interesante, significa que tiene práctica, y lo voy a considerar mejor.
Los ejemplos que mencionas en google no son exactamente iguales, tu estas proponiendo llenar un arreglo solo con 0s, eso puede ser mas eficiente hacerlo con una rutina estandar (con todas las consideraciones adecuadas).
Recuerdo un problema en la universidad en que se solicitaba portar un codigo que funcionaba muy bien en ciertas maquinas, pero fallaba al compilarlo en arquitectura SPARC/RISC.
La solucion optima era usar memmove, dado el problema de alineamiento y traslape de las estructuras de datos en memoria (ese es otro ejercicio interesante, ¿por que es mejor usar memmove en vez de un for, y que tiene que ver con el alineamiento de los datos ?).
Claro que nuestro profesor venia de trabajar en los Bell Labs, asi que aprendimos a manejar la RTL, pues eso nos daba más puntos en los exámenes….
Esas cosas ya no las enseñan…
Espero que tú sí lo hagas.
Saludos
Comment by Eduardo Diaz — Monday 13/8/2007 @ 23:45
#33, Perdón, quizás sea demasiado sensible al tema “academia” vs. “empresa” y me trago como ciertas todas las ironías sobre el tema
Comment by gallir — Tuesday 14/8/2007 @ 0:08
A todos nos visita la Tia Irma
(es broma nuevamente)
Comment by Eduardo Díaz — Tuesday 14/8/2007 @ 3:06
QUE SILENCIO!!!! Con tantos expertos programadores nadie dio la solución. Ricardo lo siento pero la dire.
Es el TLB, fallos del TLB!!!!!!!!!!!!!!
Al recorrer el array a saltos hace que se generen muchos fallos en el TLB. Además del acceso adicional a la RAM obliga a actualizar el TLB consumiendo varios ciclos de reloj cada vez.
Bah, es básico. Tanto experto y tan poca chicha.
Aprobé? Me subirás la nota en las actas? xD
Comment by a_toni — Tuesday 14/8/2007 @ 3:34
> PS: Por favor abstenerse mis alumnos y amigos que me hayan escuchado sobre este ejemplo
Cachis! Para una que me sabía!
Comment by Paco Ros — Tuesday 14/8/2007 @ 8:38
FYI:
public class Test{
private static int SIZE = 10000;
public static void main(String args[]){
long l = System.currentTimeMillis();
int arr[][] = new int[SIZE][SIZE];
for (int i=0; i
public class Test{
private static int SIZE = 10000;
public static void main(String args[]){
long l = System.currentTimeMillis();
int arr[][] = new int[SIZE][SIZE];
for (int i=0; i
Ahora no tengo un compilador de C a mano. En cuanto lo tenga repito el test.
Comment by Paco Ros — Tuesday 14/8/2007 @ 8:52
La 1 es muy sospechosa. Una persona que no sabe como funciona internamente un computador, no sabe que en memoria una matriz esta guardada por filas… pero =mente ponen [i][j]… La razón… orden alfabético…
Como entre comillas, pones “muy intuitivamente”… quizá la respuesta que quieras es esta XDDDD
Comment by brent — Saturday 18/8/2007 @ 20:20
Ui… se me ha colado un =mente, y mira que soy de los que no le gustan escribir SMS, pero cuando se pasa el día enviando SMS’s, no se puede evitar, es la costumbre.
Quise decir “igualmente”
Comment by brent — Saturday 18/8/2007 @ 20:22
Se me han ido las ganas de estudiar esto xD
Comment by Adrián — Wednesday 22/8/2007 @ 10:23
1.Explicar porqué –casi intuitivamente aunque muchas veces sin saberlo– hacemos la asignación así y no a[j][i].
Yo siempre lo hago por el tema de almacenamiento de filas/columnas.
2.Fundamental aunque derivada de la anterior. ¿Por qué si hacemos la asignación a[j][i] el código se ejecuta al menos un orden de magnitud más lento? La respuesta es muy concreta y se puede dar en menos de dos tres líneas.
Con semejante matriz, te falla todo, cache, prefetching(aunque si tu compilador es listo igual te detecta el stride), probablemente tengas fallos de página, etc…
3.¿Por qué pongo a la matriz como global y no local?
Porque no la tienes lo bastante grande(la pila digo).
4.¿Por qué a veces las primeras veces que se ejecuta el código toma más tiempo que en las siguientes?
Te refieres a la ejecución del programa o del bucle? Si es del bucle, supongo que será porque al inicio te fallan todas las páginas, y luego con suerte se salvarán algunas. Si te refieres al programa, sospecho que puede influir que el sistema tiene que liberar mucha ram para ejecutar(quitando buffers o paginando), y a la segunda o tercera ejecución tienes ese trabajo ya hecho.
5.¿Qué relación tienen este problema de eficiencia con la programación estructurada?
Esta ya la tienes.
Un saludo
Iván
Comment by elbarney — Wednesday 22/8/2007 @ 10:41
Para los que no somos tan pros, aunq nos gusten todos estos temas… ¿Podrías dar la solución “didáctica”?
Porq más o menos, en mi caso, algunas de las respuestas sería las q yo daría, temas de fallos de página, lo q has llamado “localidad”, la forma de almacenar en memoria las filas y columnas, la pila, etc… todos se han aproximado, pero nadie ha dado la respuesta correcta, o mejor dicho, completa, salvo en la 5ª q ya se ha entendido… ¿pero y el resto?
Un saludo a todos
Comment by Pepe — Thursday 23/8/2007 @ 18:13