una tipos sirve secuencial que para memoria estatica encuentra donde computadora bancos aleatorio acceso arrays assembly hardware ram random-access

arrays - tipos - para que sirve la memoria ram de una computadora



¿Cómo funciona la memoria de acceso aleatorio? ¿Por qué es el acceso aleatorio de tiempo constante? (4)

O en otras palabras, ¿por qué el acceso a un elemento arbitrario en una matriz toma tiempo constante (en lugar de O(n) o en algún otro momento)?

Busqué en Google mi corazón buscando una respuesta a esto y no encontré una muy buena, así que espero que alguno de ustedes pueda compartir su conocimiento de bajo nivel conmigo.

Solo para darte una idea de qué tan baja es la respuesta que espero, te diré por qué PIENSO que toma tiempo constante.

Cuando digo array[4] = 12 en un programa, realmente estoy almacenando la representación de bits de la dirección de memoria en un registro. Este registro físico en el hardware activará las señales eléctricas correspondientes de acuerdo con la representación de bits que lo alimenté. Esas señales eléctricas entonces de alguna manera mágicamente (esperemos que alguien pueda explicar la magia) accedan a la dirección de memoria correcta en la memoria física / principal.

Sé que fue difícil, pero fue solo para darte una idea de qué tipo de respuesta estoy buscando.

(Nota del editor: De los comentarios posteriores del OP, él entiende que los cálculos de direcciones toman tiempo constante, y solo se pregunta qué sucederá después de eso).

Cuando digo array [4] = 12 en un programa, realmente estoy almacenando la representación de bits de la dirección de memoria en un registro. Este registro físico en el hardware activará las señales eléctricas correspondientes de acuerdo con la representación de bits que lo alimenté. Esas señales eléctricas entonces de alguna manera mágicamente (esperemos que alguien pueda explicar la magia) accedan a la dirección de memoria correcta en la memoria física / principal.

No estoy muy seguro de lo que está preguntando, pero no veo ninguna respuesta relacionada con lo que realmente está sucediendo en la magia del hardware. Con suerte, entendí lo suficiente como para pasar por esta explicación tan larga (que todavía es de muy alto nivel).

array[4] = 12;

Por lo tanto, a partir de los comentarios, parece que se entiende que debe obtener la dirección base de la matriz y luego multiplicar por el tamaño de un elemento de la matriz (o cambiar si esa optimización es posible) para obtener la dirección (desde la perspectiva de sus programas) de la ubicación de la memoria. A la derecha del bate tenemos un problema. ¿Estos artículos ya están en los registros o tenemos que ir a buscarlos? La dirección base para la matriz puede o no estar en un registro, dependiendo del código que rodea esta línea de código, en particular el código que la precede. Esa dirección puede estar en la pila o en alguna otra ubicación, dependiendo de dónde la haya declarado y cómo. Y eso puede o no puede importar en cuanto a cuánto tiempo toma. Un compilador optimizador puede (a menudo) ir tan lejos como para calcular previamente la dirección de la matriz [4] y colocarla en algún lugar para que pueda ingresar a un registro y la multiplicación nunca ocurra en tiempo de ejecución, por lo que no es del todo cierto que el cálculo La matriz [4] para un acceso aleatorio es una cantidad de tiempo fija en comparación con otros accesos aleatorios. Dependiendo del procesador, algunos patrones inmediatos son una instrucción que otros toman y también tiene un factor sobre si esta dirección se lee desde .text o stack o etc, etc ... Para no resolver el problema hasta el final, suponga que tenemos la dirección de la matriz [4] calculada.

Esta es una operación de escritura, desde la perspectiva de los programadores. Comenzando con un procesador simple, sin caché, sin búfer de escritura, sin mmu, etc. Finalmente, el procesador simple pondrá la dirección en el borde del núcleo del procesador, con un estroboscopio de escritura y datos, cada bus de procesadores es diferente de otras familias de procesadores , pero es aproximadamente lo mismo que la dirección y los datos pueden aparecer en el mismo ciclo o en ciclos separados. El tipo de comando (lectura, escritura) puede ocurrir al mismo tiempo o diferente. Pero el comando sale. El borde del núcleo del procesador está conectado a un controlador de memoria que decodifica esa dirección. El resultado es un destino, es este periférico si es así cuál y en qué bus está esta memoria, si es así en qué bus de memoria y así sucesivamente. Supongamos que ram, supongamos que este procesador simple no tiene dram sram. Sram es más caro y más rápido en una comparación de manzanas con manzanas. El sram tiene una dirección y flashes de escritura / lectura y otros controles. Eventualmente tendrá el tipo de transacción, lectura / escritura, la dirección y los datos. Sin embargo, el sram, sin embargo, su geometría enrutará y almacenará los bits individuales en sus pares / grupos de transistores individuales.

Un ciclo de escritura puede ser fuego y olvido. Toda la información que se necesita para completar la transacción, esto es una escritura, esta es la dirección, esta es la información, se conoce en ese momento. El controlador de memoria puede, si lo desea, indicar al procesador que la transacción de escritura está completa, incluso si los datos no están cerca de la memoria. Ese par de direcciones / datos tomará su tiempo para llegar a la memoria y el procesador puede seguir funcionando. Aunque algunos de los sistemas de diseño son tales, los procesadores escriben las transacciones en espera hasta que una señal regresa para indicar que la escritura ha llegado hasta el ram. En una configuración de tipo fuego y olvido, esa dirección / datos se colocarán en cola en alguna parte y se abrirán camino hacia el ram. La cola no puede ser infinitamente profunda, de lo contrario sería la propia RAM, por lo que es finita, y es posible que muchas escrituras en una fila puedan completar esa cola más rápido de lo que el otro extremo puede escribir en la RAM. En ese punto, la escritura actual o la siguiente debe esperar a que la cola indique que hay espacio para uno más. Por lo tanto, en situaciones como esta, la rapidez con la que ocurre su escritura, ya sea que su procesador simple esté o no vinculado a I / O, tiene que ver con transacciones anteriores que pueden o no ser instrucciones de escritura que precedieron a esta instrucción en cuestión.

Ahora agregue un poco de complejidad. ECC o el nombre que quieras llamar (EDAC, es otro). La forma en que funciona una memoria ECC es que las escrituras son todas de tamaño fijo, incluso si su implementación es de cuatro partes de memoria de 8 bits de ancho que le proporcionan 32 bits de datos por escritura, debe tener una solución que cubra la ECC y debe escriba los bits de datos más los bits de ecc al mismo tiempo (debe calcular el ecc en todo el ancho). Entonces, si esto fue una escritura de 8 bits, por ejemplo, en una memoria protegida con ECC de 32 bits, entonces ese ciclo de escritura requiere un ciclo de lectura. Lea los 32 bits (verifique el ecc en esa lectura) modifique los nuevos 8 bits en ese patrón de 32 bits, calcule el nuevo patrón de ecc, escriba los 32 bits más los bits de ecc. Naturalmente, esa parte leída del ciclo de escritura puede terminar con un error de ecc, lo que hace que la vida sea aún más divertida. Los errores de un solo bit se pueden corregir por lo general (¿de qué sirve un ECC / EDAC si no se puede)? Los errores de múltiples bits no. La forma en que el hardware está diseñado para manejar estas fallas afecta lo que sucede a continuación, la falla de lectura puede simplemente regresar al procesador que falla la transacción de escritura, o puede regresar como una interrupción, etc. Pero aquí hay otro lugar donde hay un acceso aleatorio. no es lo mismo que otro, dependiendo de la memoria a la que se accede, y el tamaño del acceso que una lectura-modificación-escritura definitivamente toma más tiempo que una simple escritura.

Dram también puede caer en esta categoría de ancho fijo, incluso sin ECC. En realidad, toda la memoria cae en esta categoría en algún momento. La matriz de memoria está optimizada en el silicio para una cierta altura y anchura en unidades de bits. No puedes violar esa memoria, solo se puede leer y escribir en unidades de ese ancho en ese nivel. Las bibliotecas de silicio incluirán muchas geometrías de ram, y los diseñadores elegirán esas geometrías para sus partes, y las partes tendrán límites fijos y, a menudo, puede usar varias partes para obtener un ancho múltiple entero de ese tamaño, y algunas veces el diseño le permite escribir solo en una de esas partes si solo algunos de los bits están cambiando, o algunos diseños forzarán el encendido de todas las partes. Observe cómo la próxima familia de módulos ddr que conecta a la computadora de su casa o computadora portátil, la primera ola está formada por dos partes en ambos lados del tablero. Luego, a medida que la tecnología envejece y se vuelve más aburrida, puede cambiar a menos partes en ambos lados del tablero, lo que eventualmente se vuelve menos en un lado del tablero antes de que esa tecnología sea obsoleta y ya estemos en el siguiente.

Esta categoría de ancho fijo también conlleva penalizaciones de alineación. Desafortunadamente, la mayoría de las personas aprenden en máquinas x86, que no lo restringen a accesos alineados como muchas otras plataformas. Existe una penalización de rendimiento definida en x86 u otros para accesos no alineados, si se permite. Por lo general, cuando las personas acuden a un mips o, por lo general, un brazo en algún dispositivo con batería es cuando aprenden por primera vez como programadores sobre los accesos alineados. Y lamentablemente encuentre que son dolorosas en lugar de una bendición (debido a la simplicidad tanto en la programación como en los beneficios de hardware que se derivan de ella). En pocas palabras, si su memoria tiene 32 bits de ancho y solo se puede acceder, leer o escribir, 32 bits a la vez, lo que significa que está limitado a accesos alineados solamente. Un bus de memoria en una memoria de 32 bits de ancho por lo general no tiene los bits de dirección más bajos a [1: 0] porque no hay uso para ellos. Los bits más bajos desde la perspectiva de los programadores son ceros. Si bien nuestra escritura era de 32 bits contra una de estas memorias de 32 bits y la dirección era 0x1002. Luego, alguien a lo largo de la línea tiene que leer la memoria en la dirección 0x1000 y tomar dos de nuestros bytes y modificar ese valor de 32 bits, luego escribirlo de nuevo. Luego tome los 32 bits en la dirección 0x1004 y modifique dos bytes y vuelva a escribirlos. Cuatro ciclos de bus para una sola escritura. Si estuviéramos escribiendo 32 bits para abordar 0x1008 aunque sería una simple escritura de 32 bits, no habrá lecturas.

sram vs dram. dram es dolorosamente lento, pero super barato. la mitad a un cuarto el número de transistores por bit. (4 para sram por ejemplo 1 para dram). Sram recuerda el bit siempre que la alimentación esté encendida. Dram tiene que actualizarse como una batería recargable. Incluso si la potencia permanece en un solo bit, solo se recordará por un período de tiempo muy corto. Por lo tanto, algún hardware en el camino (controlador ddr, etc.) tiene que realizar ciclos de bus con regularidad para que el ram se acuerde de cierta parte de la memoria. Esos ciclos le roban tiempo a su procesador para acceder a esa memoria. dram es muy lento, puede decir 2133Mhz (2.133ghz) en la caja. Pero en realidad es más como 133Mhz ram, justo 0.133Ghz. El primer truco es ddr. Normalmente, las cosas en el mundo digital suceden una vez por ciclo de reloj. El reloj pasa a un estado afirmado, luego pasa a un estado desactivado (unos y ceros) un ciclo es un reloj. DDR significa que puede hacer algo tanto en el semiciclo alto como en el semiciclo bajo. de modo que la memoria de 2133 GHz realmente usa un reloj de 1066 mhz. Entonces suceden conductos como paralelismos, puede empujar comandos, en ráfagas, a esa alta velocidad, pero finalmente ese ram debe ser accedido. El dram global es no determinístico y muy lento. Sram, por otro lado, no necesita actualizaciones, se recuerda siempre que la alimentación esté encendida. Puede ser varias veces más rápido (133 mhz * N), y así sucesivamente. Puede ser determinista.

El siguiente obstáculo, caché. El caché es bueno y malo. El caché se hace generalmente de sram. Esperemos que tenga una comprensión de un caché. Si el procesador o alguien anterior ha marcado la transacción como no almacenable en la memoria caché, entonces se transfiere al servidor de memoria del otro lado. Si se puede almacenar en caché, la parte de la dirección se busca en una tabla y se traducirá en un error o falla. esto es una escritura, dependiendo de la configuración de la memoria caché y / o de la transacción, si es una falla, puede pasar al otro lado. Si hay un acierto, los datos se escribirán en la memoria caché, dependiendo del tipo de caché, también puede pasar al otro lado o los datos pueden quedar en el caché a la espera de algún otro fragmento de datos para desalojarlos y luego se escribe al otro lado. los cachés definitivamente hacen lecturas y, a veces, hacen escrituras no deterministas. Los accesos secuenciales tienen el mayor beneficio ya que su tasa de desalojo es más baja, el primer acceso en una línea de caché es lento en relación con los demás, luego el resto es rápido. que es donde obtenemos este término de acceso aleatorio de todos modos. Los accesos aleatorios van en contra de los esquemas que están diseñados para hacer que los accesos secuenciales sean más rápidos.

A veces, el lado opuesto de su caché tiene un búfer de escritura. Una cola / pipe / buffer / fifo relativamente pequeña que contiene un cierto número de transacciones de escritura. Otro fuego y trato de olvidar, con esos beneficios.

Múltiples capas de cachés. l1, l2, l3 ... L1 suele ser el más rápido, ya sea por su tecnología o proximidad, y generalmente el más pequeño, y aumenta la velocidad y el tamaño, y parte de eso tiene que ver con el costo de la memoria. Estamos haciendo una escritura, pero cuando usted hace una lectura de caché habilitada, entienda que si l1 tiene una falla, pasa a l2, que si tiene una falla va a l3, que si falla tiene que ir a la memoria principal, entonces l3, l2 y l1 todos almacenarán una copia. Por lo tanto, una falla en los 3 es, por supuesto, la más dolorosa y más lenta que si no tuviera caché, pero las lecturas secuenciales le darán los elementos almacenados en caché que ahora están en l1 y súper rápido, para que la caché sea lecturas secuenciales útiles. sobre la línea de caché debería tomar menos tiempo en general que leer tanta memoria directamente desde el disco lento. Un sistema no tiene que tener 3 capas de cachés, puede variar. Del mismo modo, algunos sistemas pueden separar las recopilaciones de instrucciones de las lecturas de datos y pueden tener cachés separadas que no se desalojan entre sí, y otras no están separadas y las captaciones de instrucciones pueden expulsar datos de las lecturas de datos.

cachés ayuda con problemas de alineación. Pero, por supuesto, hay una penalización aún más severa para un acceso no alineado a través de líneas de caché. Los cachés tienden a operar usando trozos de memoria llamados líneas de caché. Estos son a menudo algunos enteros múltiples en el tamaño de la memoria en el otro lado. una memoria de 32 bits, por ejemplo, la línea de caché puede ser de 128 bits o 256 bits, por ejemplo. Entonces, si y cuando la línea de caché está en el caché, entonces una lectura-modificación-escritura debida a una escritura no alineada es contra una memoria más rápida, aún más dolorosa que alineada pero no tan dolorosa. Si fuera una lectura no alineada y la dirección fuera tal que parte de esos datos se encuentra en un lado de un límite de línea de caché y el otro en el otro, entonces se deben leer dos líneas de caché. Una lectura de 16 bits, por ejemplo, puede costarle muchos bytes en la memoria más lenta, obviamente varias veces más lenta que si no tuviera cachés. Dependiendo de cómo se diseñen los cachés y el sistema de memoria en general, si realiza una escritura a través de un límite de línea de caché, puede ser igualmente doloroso, o quizás no tanto como podría tener la fracción de escritura en el caché, y la otra fracción desaparecer. en el lado opuesto como una escritura de menor tamaño.

La siguiente capa de complejidad es el mmu. Permitir al procesador y al programador la ilusión de espacios de memoria planos y / o el control de lo que se almacena en caché o no, y / o la protección de la memoria, y / o la ilusión de que todos los programas se ejecutan en el mismo espacio de direcciones (para que su cadena de herramientas siempre pueda compilar / enlace para la dirección 0x8000 por ejemplo). El mmu toma una parte de la dirección virtual en el lado central del procesador. parece que en una tabla, o en una serie de tablas, esas búsquedas a menudo se encuentran en el espacio de direcciones del sistema, por lo que cada una de esas búsquedas puede ser una o más de todas las mencionadas anteriormente, ya que cada una es un ciclo de memoria en la memoria del sistema. Esas búsquedas pueden dar como resultado fallas de ecc, incluso si está intentando escribir. Eventualmente, después de una o dos o tres o más lecturas, el mmu ha determinado cuál es la dirección en el otro lado del mmu, y las propiedades (cacheables o no, etc.) y eso se pasa a la siguiente cosa (l1, etc) y todo lo anterior se aplica. Algunos mmus tienen un poco de caché en ellos de un número de transacciones anteriores, recuerde que debido a que los programas son secuenciales, los trucos utilizados para aumentar la ilusión del rendimiento de la memoria se basan en accesos secuenciales, no en accesos aleatorios. Por lo tanto, es posible que se almacene un número de búsquedas en el mmu para que no tenga que ir a la memoria principal de inmediato ...

Así que en una computadora moderna con mmus, caches, dram, lecturas secuenciales en particular, pero también las escrituras son más rápidas que el acceso aleatorio. La diferencia puede ser dramática. La primera transacción en una lectura o escritura secuencial es en ese momento un acceso aleatorio, como no se ha visto nunca ni por un tiempo. Una vez que la secuencia continúa, las optimizaciones caen en orden y las siguientes / algunas son notablemente más rápidas. El tamaño y la alineación de su transacción también juegan un papel importante en el rendimiento. Si bien hay muchas cosas no deterministas en marcha, como programador, con este conocimiento, modificas tus programas para que se ejecuten mucho más rápido, o si el desafortunado o a propósito puede modificar tus programas para que se ejecuten mucho más lentamente. Secuencial será, en general, más rápido en uno de estos sistemas. El acceso aleatorio va a ser muy no determinista. array [4] = 12; seguido de una matriz [37] = 12; Esas dos operaciones de alto nivel podrían tomar dramáticamente diferentes cantidades de tiempo, tanto en el cómputo de la dirección de escritura como en las escrituras reales en sí mismas. Pero, por ejemplo, discarded_variable = array [3]; array [3] = 11; array [4] = 12; Con bastante frecuencia puede ejecutarse significativamente más rápido que la matriz [3] = 11; array [4] = 12;

Porque al software le gusta O (1) la memoria "de trabajo" y, por lo tanto, el hardware está diseñado para comportarse de esa manera

El punto básico es que se piensa que el espacio de direcciones de un programa tiene un rendimiento de acceso O (1) abstracto, es decir, cualquier ubicación de memoria que desee leer, debería tomar un tiempo constante (que de todos modos no está relacionado con la distancia entre ellos). y el último acceso a la memoria). Por lo tanto, como las matrices no son más que trozos contiguos de espacio de direcciones, deben heredar esta propiedad (el acceso a un elemento de una matriz es solo una cuestión de agregar el índice a la dirección de inicio de la matriz y luego eliminar la referencia al puntero obtenido).

Esta propiedad proviene del hecho de que, en general, el espacio de direcciones de un programa tiene cierta correspondencia con la RAM física de la PC, que, como el nombre ( memoria de acceso aleatorio ) implica parcialmente, debe tener por sí misma la propiedad que, cualquiera que sea La ubicación en la memoria RAM a la que desea acceder, la obtiene en un tiempo constante (como opuesto, por ejemplo, a una unidad de cinta, donde el tiempo de búsqueda depende de la longitud real de la cinta que tiene que mover para llegar allí).

Ahora, para la RAM "normal" esta propiedad es (al menos AFAIK) verdadera: cuando el controlador / placa base / controlador de memoria solicita a un chip de RAM que obtenga algunos datos, lo hace en un tiempo constante; los detalles no son realmente relevantes para el desarrollo de software, y las partes internas de los chips de memoria han cambiado muchas veces en el pasado y volverán a cambiar en el futuro. Si está interesado en una descripción general de los detalles de las RAM actuales, puede consultar here acerca de las DRAM.

El concepto general es que los chips de RAM no contienen una cinta que debe moverse, o un brazo de disco que debe colocarse; cuando se les pregunta un byte en algún lugar, el trabajo (que cambia principalmente la configuración de algunos muxes de hardware, que conecta la salida a las celdas donde se almacena el estado del byte) es el mismo para cualquier ubicación que pueda estar solicitando; así, obtienes O (1) rendimiento

Hay algo de sobrecarga detrás de esto (la dirección lógica tiene que ser asignada a la dirección física por la MMU, las diferentes piezas de la placa tienen que hablar entre sí para indicar a la RAM que recoja los datos y los devuelva al procesador, ... ), pero el hardware está diseñado para hacerlo en un tiempo más o menos constante.

Asi que:

los arreglos se asignan sobre el espacio de direcciones, que se asigna a través de RAM, que tiene O (1) acceso aleatorio; Al ser todos los mapas (más o menos) O (1), los arreglos mantienen el rendimiento de acceso aleatorio O (1) de la RAM.

El punto que sí importa a los desarrolladores de software, en cambio, es que, aunque vemos un espacio de direcciones planas y normalmente se asigna a través de RAM, en las máquinas modernas es falso que acceder a cualquier elemento tenga el mismo costo. En realidad, el acceso a los elementos que se encuentran en la misma zona puede ser mucho más barato que saltar alrededor del espacio de direcciones, debido al hecho de que el procesador tiene varias memorias caché integradas (= memorias en chip más pequeñas pero más rápidas) que mantienen los datos y la memoria utilizados recientemente. que está en el mismo barrio; por lo tanto, si tiene una buena ubicación de datos, las operaciones continuas en la memoria no continuarán golpeando el ariete (que tiene una latencia mucho más prolongada que las cachés) y, al final, su código se ejecutará mucho más rápido.

Además, bajo la presión de la memoria, los sistemas operativos que proporcionan memoria virtual pueden decidir mover las páginas que rara vez se utilizan de su espacio de direcciones al disco, y obtenerlas si se accede a ellas (en respuesta a un error de página ); tal operación es muy costosa y, nuevamente, se desvía fuertemente de la idea de que acceder a cualquier dirección de memoria virtual es lo mismo.

El cálculo para obtener desde el inicio de la matriz a cualquier elemento dado toma solo dos operaciones, una multiplicación (times sizeof (elemento)) y suma. Ambas operaciones son de tiempo constante. A menudo, con los procesadores de hoy en día se puede hacer prácticamente en un instante, ya que el procesador está optimizado para este tipo de acceso.

Las matrices en C y C ++ tienen acceso aleatorio porque se almacenan en la RAM - Memoria de acceso aleatorio en un orden finito y predecible. Como resultado, se requiere una operación lineal simple para determinar la ubicación de un registro dado (a [i] = a + sizeof (a [0]) * i). Este cálculo tiene tiempo constante. Desde la perspectiva de la CPU, no se requiere ninguna operación de "búsqueda" o "rebobinado", simplemente le dice a la memoria "cargar el valor en la dirección X".

Sin embargo: en una CPU moderna, la idea de que lleva tiempo constante recuperar datos ya no es cierta. Lleva un tiempo amortizado constante , dependiendo de si un dato determinado está en caché o no.

Aún así, el principio general es que el tiempo para recuperar un conjunto dado de 4 u 8 bytes de la RAM es el mismo, independientemente de la dirección. Por ejemplo, si, desde una pizarra limpia, accede a RAM [0] y RAM [4294967292], la CPU obtendrá la respuesta dentro del mismo número de ciclos.

#include <iostream> #include <cstring> #include <chrono> // 8Kb of space. char smallSpace[8 * 1024]; // 64Mb of space (larger than cache) char bigSpace[64 * 1024 * 1024]; void populateSpaces() { memset(smallSpace, 0, sizeof(smallSpace)); memset(bigSpace, 0, sizeof(bigSpace)); std::cout << "Populated spaces" << std::endl; } unsigned int doWork(char* ptr, size_t size) { unsigned int total = 0; const char* end = ptr + size; while (ptr < end) { total += *(ptr++); } return total; } using namespace std; using namespace chrono; void doTiming(const char* label, char* ptr, size_t size) { cout << label << ": "; const high_resolution_clock::time_point start = high_resolution_clock::now(); auto result = doWork(ptr, size); const high_resolution_clock::time_point stop = high_resolution_clock::now(); auto delta = duration_cast<nanoseconds>(stop - start).count(); cout << "took " << delta << "ns (result is " << result << ")" << endl; } int main() { cout << "Timer resultion is " << duration_cast<nanoseconds>(high_resolution_clock::duration(1)).count() << "ns" << endl; populateSpaces(); doTiming("first small", smallSpace, sizeof(smallSpace)); doTiming("second small", smallSpace, sizeof(smallSpace)); doTiming("third small", smallSpace, sizeof(smallSpace)); doTiming("bigSpace", bigSpace, sizeof(bigSpace)); doTiming("bigSpace redo", bigSpace, sizeof(bigSpace)); doTiming("smallSpace again", smallSpace, sizeof(smallSpace)); doTiming("smallSpace once more", smallSpace, sizeof(smallSpace)); doTiming("smallSpace last", smallSpace, sizeof(smallSpace)); }

Demostración en vivo: http://ideone.com/9zOW5q

Salida (de ideone, que puede no ser ideal)

Success time: 0.33 memory: 68864 signal:0 Timer resultion is 1ns Populated spaces doWork/small: took 8384ns (result is 8192) doWork/small: took 7702ns (result is 8192) doWork/small: took 7686ns (result is 8192) doWork/big: took 64921206ns (result is 67108864) doWork/big: took 65120677ns (result is 67108864) doWork/small: took 8237ns (result is 8192) doWork/small: took 7678ns (result is 8192) doWork/small: took 7677ns (result is 8192) Populated spaces strideWork/small: took 10112ns (result is 16384) strideWork/small: took 9570ns (result is 16384) strideWork/small: took 9559ns (result is 16384) strideWork/big: took 65512138ns (result is 134217728) strideWork/big: took 65005505ns (result is 134217728)

Lo que estamos viendo aquí son los efectos de la memoria caché en el rendimiento de acceso a la memoria. La primera vez que llegamos a smallSpace, se necesitan ~ 8100ns para acceder a todos los 8kb de espacio pequeño. Pero cuando lo volvemos a llamar inmediatamente después, dos veces, toma ~ 600ns menos en ~ 7400ns.

Ahora nos vamos y hacemos bigspace, que es más grande que la memoria caché de la CPU actual, por lo que sabemos que hemos eliminado las cachés L1 y L2.

Volviendo a lo pequeño, lo cual estamos seguros de que no está guardado en caché ahora, nuevamente vemos ~ 8100ns por primera vez y ~ 7400 por los dos segundos.

Expulsamos el caché y ahora introducimos un comportamiento diferente. Usamos una versión de bucle de zancada. Esto amplifica el efecto de "falta de memoria caché" y aumenta considerablemente el tiempo, aunque "espacio pequeño" se ajusta a la memoria caché L2, por lo que todavía vemos una reducción entre la pasada 1 y las siguientes 2 pasadas.