c++ - ¿Por qué las adiciones elementwise son mucho más rápidas en bucles separados que en un bucle combinado?

performance compiler-optimization

Question

Supongamos que a1 , b1 , c1 y d1 apuntan a la memoria del montón y mi código numérico tiene el siguiente bucle central.

const int n = 100000;
for (int j = 0; j < n; j++) {
a1[j] += b1[j];
c1[j] += d1[j];
}

Este bucle se ejecuta 10.000 veces a través de otro bucle externo. Para acelerarlo, cambié el código a:

for (int j = 0; j < n; j++) {
a1[j] += b1[j];
}
for (int j = 0; j < n; j++) {
c1[j] += d1[j];
}

Compilado en MS Visual C ++ 10.0 con optimización completa y SSE2 habilitado para 32 bits en un Intel Core 2 Duo (x64), el primer ejemplo toma 5.5 segundos y el ejemplo de doble bucle toma solo 1.9 segundos. Mi pregunta es: (Por favor refiérase a mi pregunta reformulada en la parte inferior)

PD: No estoy seguro, si esto ayuda:

El desmontaje para el primer bucle básicamente tiene este aspecto (este bloque se repite unas cinco veces en el programa completo):

movsd xmm0,mmword ptr [edx+18h]
addsd xmm0,mmword ptr [ecx+20h]
movsd mmword ptr [ecx+20h],xmm0
movsd xmm0,mmword ptr [esi+10h]
addsd xmm0,mmword ptr [eax+30h]
movsd mmword ptr [eax+30h],xmm0
movsd xmm0,mmword ptr [edx+20h]
addsd xmm0,mmword ptr [ecx+28h]
movsd mmword ptr [ecx+28h],xmm0
movsd xmm0,mmword ptr [esi+18h]
addsd xmm0,mmword ptr [eax+38h]

Cada bucle del ejemplo de doble bucle produce este código (el siguiente bloque se repite aproximadamente tres veces):

addsd xmm0,mmword ptr [eax+28h]
movsd mmword ptr [eax+28h],xmm0
movsd xmm0,mmword ptr [ecx+20h]
addsd xmm0,mmword ptr [eax+30h]
movsd mmword ptr [eax+30h],xmm0
movsd xmm0,mmword ptr [ecx+28h]
addsd xmm0,mmword ptr [eax+38h]
movsd mmword ptr [eax+38h],xmm0
movsd xmm0,mmword ptr [ecx+30h]
addsd xmm0,mmword ptr [eax+40h]
movsd mmword ptr [eax+40h],xmm0

La pregunta resultó no tener relevancia, ya que el comportamiento depende en gran medida de los tamaños de los arreglos (n) y la memoria caché de la CPU. Entonces si hay más interés, reformulo la pregunta:

¿Podría proporcionar alguna información sólida sobre los detalles que conducen a los diferentes comportamientos de la memoria caché, como lo ilustran las cinco regiones en el siguiente gráfico?

También podría ser interesante señalar las diferencias entre las arquitecturas de CPU / caché, al proporcionar un gráfico similar para estas CPU.

PPS: Aquí está el código completo. Utiliza TBB Tick_Count para una sincronización de mayor resolución, que se puede desactivar al no definir la macro TBB_TIMING :

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
//#define TBB_TIMING
#ifdef TBB_TIMING
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif
using namespace std;
//#define preallocate_memory new_cont
enum { new_cont, new_sep };
double *a1, *b1, *c1, *d1;
void allo(int cont, int n)
{
switch(cont) {
case new_cont:
a1 = new double[n*4];
b1 = a1 + n;
c1 = b1 + n;
d1 = c1 + n;
break;
case new_sep:
a1 = new double[n];
b1 = new double[n];
c1 = new double[n];
d1 = new double[n];
break;
}
for (int i = 0; i < n; i++) {
a1[i] = 1.0;
d1[i] = 1.0;
c1[i] = 1.0;
b1[i] = 1.0;
}
}
void ff(int cont)
{
switch(cont){
case new_sep:
delete[] b1;
delete[] c1;
delete[] d1;
case new_cont:
delete[] a1;
}
}
double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
allo(cont,n);
#endif
#ifdef TBB_TIMING
tick_count t0 = tick_count::now();
#else
clock_t start = clock();
#endif
if (loops == 1) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++){
a1[j] += b1[j];
c1[j] += d1[j];
}
}
} else {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a1[j] += b1[j];
}
for (int j = 0; j < n; j++) {
c1[j] += d1[j];
}
}
}
double ret;
#ifdef TBB_TIMING
tick_count t1 = tick_count::now();
ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
clock_t end = clock();
ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif
#ifndef preallocate_memory
ff(cont);
#endif
return ret;
}
void main()
{
freopen("C://test.csv", "w", stdout);
char *s = " ";
string na[2] ={"new_cont", "new_sep"};
cout << "n";
for (int j = 0; j < 2; j++)
for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
cout << s << i << "_loops_" << na[preallocate_memory];
#else
cout << s << i << "_loops_" << na[j];
#endif
cout << endl;
long long nmax = 1000000;
#ifdef preallocate_memory
allo(preallocate_memory, nmax);
#endif
for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
{
const long long m = 10000000/n;
cout << n;
for (int j = 0; j < 2; j++)
for (int i = 1; i <= 2; i++)
cout << s << plain(n, m, j, i);
cout << endl;
}
}

(Muestra FLOP / s para diferentes valores de n .)

Answer 1

Bien, la respuesta correcta definitivamente tiene que hacer algo con el caché de la CPU. Pero usar el argumento del caché puede ser bastante difícil, especialmente sin datos.

Hay muchas respuestas que llevaron a mucha discusión, pero seamos realistas: los problemas de caché pueden ser muy complejos y no son unidimensionales. Dependen en gran medida del tamaño de los datos, por lo que mi pregunta fue injusta: resultó ser un punto muy interesante en el gráfico de caché.

La respuesta de @Mysticial convenció a mucha gente (incluyéndome a mí), probablemente porque era la única que parecía confiar en los hechos, pero era solo un "punto de datos" de la verdad.

Es por eso que combiné su prueba (utilizando una asignación continua frente a una separada) y el consejo de @James en Respuestas.

Los gráficos a continuación muestran que la mayoría de las respuestas y especialmente la mayoría de los comentarios a la pregunta y las respuestas pueden considerarse completamente incorrectas o verdaderas, según el escenario exacto y los parámetros utilizados.

Tenga en cuenta que mi pregunta inicial fue en n = 100.000 . Este punto (por accidente) exhibe un comportamiento especial:

1. Posee la mayor discrepancia entre la versión de uno y dos bucles (casi un factor de tres)

2. Es el único punto en el que un bucle (es decir, con asignación continua) supera la versión de dos bucles. (Esto hizo posible la respuesta de Mysticial, en absoluto).

El resultado utilizando datos inicializados:

El resultado utilizando datos sin inicializar (esto es lo que Mysticial probó):

Y es difícil de explicar: los datos inicializados se asignan una vez y se reutilizan para cada siguiente caso de prueba de diferentes tamaños de vectores:

Propuesta

¡Todas las preguntas relacionadas con el rendimiento de bajo nivel en deben ser proporcionadas para proporcionar información de MFLOPS para toda la gama de tamaños de datos relevantes de caché! Es una pérdida de tiempo para todos pensar en las respuestas y, sobre todo, discutirlas con otros sin esta información.

Answer 2

El primer bucle alterna la escritura en cada variable. El segundo y el tercero solo hacen pequeños saltos de tamaño de elemento.

Intenta escribir dos líneas paralelas de 20 cruces con un bolígrafo y papel separados por 20 cm. Intente una vez terminando una y luego la otra línea e intente otra vez escribiendo una cruz en cada línea alternativamente.

Answer 3

El segundo bucle implica mucha menos actividad de caché, por lo que es más fácil para el procesador mantenerse al día con las demandas de memoria.

Answer 4

Es porque la CPU no tiene tantos fallos de caché (donde tiene que esperar a que los datos de la matriz provengan de los chips de RAM). Sería interesante para usted ajustar el tamaño de las matrices continuamente para que exceda los tamaños de la caché de nivel 1 (L1), y luego la caché de nivel 2 (L2) de su CPU y trace el tiempo necesario para su código para ejecutar contra los tamaños de las matrices. La gráfica no debería ser una línea recta como cabría esperar.

Answer 5

Imagine que está trabajando en una máquina en la que n era el valor correcto, ya que solo es posible mantener dos de sus arreglos en la memoria al mismo tiempo, pero la memoria total disponible, a través del almacenamiento en caché del disco, aún era suficiente para mantener los cuatro.

Suponiendo una política de almacenamiento en caché LIFO simple, este código:

for(int j=0;j<n;j++){
a[j] += b[j];
}
for(int j=0;j<n;j++){
c[j] += d[j];
}

primero causaría que a y b se carguen en la RAM y luego se trabajen completamente en la RAM. Cuando comience el segundo bucle, d se cargarán desde el disco a la RAM y se ejecutarán.

el otro bucle

for(int j=0;j<n;j++){
a[j] += b[j];
c[j] += d[j];
}

Repartirá dos matrices y una página en las otras dos cada vez que esté alrededor del bucle . Esto obviamente sería mucho más lento.

Probablemente no esté viendo el almacenamiento en caché de disco en sus pruebas, pero probablemente esté viendo los efectos secundarios de alguna otra forma de almacenamiento en caché.

Parece que hay un poco de confusión / malentendido aquí, así que trataré de elaborar un poco usando un ejemplo.

Diga n = 2 y estamos trabajando con bytes. Por lo tanto, en mi escenario solo tenemos 4 bytes de RAM y el resto de nuestra memoria es significativamente más lento (por ejemplo, acceso 100 veces mayor).

Asumiendo una política de almacenamiento en caché bastante tonta de si el byte no está en el caché, colóquelo allí y obtenga el siguiente byte también mientras estamos en ello obtendrá un escenario como este:

• Con

  for(int j=0;j<n;j++){
  a[j] += b[j];
  }
  for(int j=0;j<n;j++){
  c[j] += d[j];
  }

• caché a[0] y a[1] luego b[0] y b[1] y establezca a[0] = a[0] + b[0] en caché - ahora hay cuatro bytes en caché, a[0], a[1] b[0], b[1] . Costo = 100 + 100.

• establece a[1] = a[1] + b[1] en caché. Costo = 1 + 1.
• Repita para c y d .

• Costo total = (100 + 100 + 1 + 1) * 2 = 404

• Con

  for(int j=0;j<n;j++){
  a[j] += b[j];
  c[j] += d[j];
  }

• caché a[0] y a[1] luego b[0] y b[1] y establezca a[0] = a[0] + b[0] en caché - ahora hay cuatro bytes en caché, a[0], a[1] b[0], b[1] . Costo = 100 + 100.

• Expulse a[0], a[1], b[0], b[1] de la caché y la caché c[0] c[1] luego d[0] d[1] y establezca c[0] = c[0] + d[0] en caché. Costo = 100 + 100.
• Sospecho que estás empezando a ver a dónde voy.
• Costo total = (100 + 100 + 100 + 100) * 2 = 800

Este es un clásico caso de thrash caché.

Answer 6

No es por un código diferente, sino por el almacenamiento en caché: la memoria RAM es más lenta que los registros de la CPU y la memoria caché está dentro de la CPU para evitar escribir la RAM cada vez que cambia una variable. Pero el caché no es grande como lo es la memoria RAM, por lo tanto, asigna solo una fracción de él.

El primer código modifica las direcciones de memoria distantes alternándolas en cada bucle, lo que requiere que se invalide continuamente la memoria caché.

El segundo código no se alterna: simplemente fluye en direcciones adyacentes dos veces. Esto hace que todo el trabajo se complete en el caché, invalidándolo solo después de que comience el segundo bucle.

Answer 7

Tras un mayor análisis de esto, creo que esto es (al menos parcialmente) causado por la alineación de los datos de los cuatro punteros. Esto causará algún nivel de conflicto de banco / forma de caché.

Si he adivinado correctamente cómo está asignando sus arreglos, es probable que estén alineados con la línea de la página .

Esto significa que todos sus accesos en cada bucle caerán en la misma forma de caché. Sin embargo, los procesadores Intel han tenido asociatividad de caché L1 de 8 vías por un tiempo. Pero en realidad, el rendimiento no es completamente uniforme. Acceder a 4 vías es aún más lento que decir 2 vías.

EDIT: De hecho, parece que está asignando todas las matrices por separado. Por lo general, cuando se solicitan asignaciones tan grandes, el asignador solicitará páginas nuevas del sistema operativo. Por lo tanto, existe una alta probabilidad de que las grandes asignaciones aparezcan en el mismo desplazamiento desde un límite de página.

Aquí está el código de prueba:

int main(){
const int n = 100000;
#ifdef ALLOCATE_SEPERATE
double *a1 = (double*)malloc(n * sizeof(double));
double *b1 = (double*)malloc(n * sizeof(double));
double *c1 = (double*)malloc(n * sizeof(double));
double *d1 = (double*)malloc(n * sizeof(double));
#else
double *a1 = (double*)malloc(n * sizeof(double) * 4);
double *b1 = a1 + n;
double *c1 = b1 + n;
double *d1 = c1 + n;
#endif
// Zero the data to prevent any chance of denormals.
memset(a1,0,n * sizeof(double));
memset(b1,0,n * sizeof(double));
memset(c1,0,n * sizeof(double));
memset(d1,0,n * sizeof(double));
// Print the addresses
cout << a1 << endl;
cout << b1 << endl;
cout << c1 << endl;
cout << d1 << endl;
clock_t start = clock();
int c = 0;
while (c++ < 10000){
#if ONE_LOOP
for(int j=0;j<n;j++){
a1[j] += b1[j];
c1[j] += d1[j];
}
#else
for(int j=0;j<n;j++){
a1[j] += b1[j];
}
for(int j=0;j<n;j++){
c1[j] += d1[j];
}
#endif
}
clock_t end = clock();
cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;
system("pause");
return 0;
}

Resultados de referencia:

EDIT: Resultados en una máquina de arquitectura Core 2 real :

2 x Intel Xeon X5482 Harpertown a 3,2 GHz:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206
#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116
//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894
//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

Observaciones:

• 6.206 segundos con un bucle y 2.116 segundos con dos bucles. Esto reproduce exactamente los resultados del OP.

• En las dos primeras pruebas, las matrices se asignan por separado. Notarás que todos tienen la misma alineación con respecto a la página.

• En las segundas dos pruebas, las matrices se empaquetan juntas para romper esa alineación. Aquí notarás que ambos bucles son más rápidos. Además, el segundo bucle (doble) es ahora el más lento, como es de esperar.

Como @Stephen Cannon señala en los comentarios, es muy probable que esta alineación provoque falsos alias en las unidades de carga / almacenamiento o en la caché. Busqué en Google para encontrar esto y descubrí que Intel en realidad tiene un contador de hardware para las paradas parciales de aliasing de direcciones :

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html

5 Regiones - Explicaciones

Región 1:

Este es fácil. El conjunto de datos es tan pequeño que el rendimiento está dominado por la sobrecarga como el bucle y la bifurcación.

Región 2:

Aquí, a medida que aumenta el tamaño de los datos, la cantidad de sobrecarga relativa disminuye y el rendimiento "se satura". Aquí, dos bucles son más lentos porque tienen el doble de bucles y la sobrecarga de ramificación.

No estoy seguro de lo que está sucediendo aquí ... La alineación podría tener un efecto, ya que Agner Fog menciona los conflictos del banco de caché . (Ese enlace es sobre Sandy Bridge, pero la idea aún debería ser aplicable a Core 2.)

Región 3:

En este punto, los datos ya no caben en el caché L1. Por lo tanto, el rendimiento está limitado por el ancho de banda de caché L1 <-> L2.

Región 4:

Lo que estamos observando es la caída del rendimiento en el bucle único. Y como se mencionó, esto se debe a la alineación que (lo más probable) causa fallas de alias falsas en las unidades de carga / almacenamiento del procesador.

Sin embargo, para que se produzcan falsos alias, debe haber un paso suficientemente grande entre los conjuntos de datos. Es por esto que no ves esto en la región 3.

Región 5:

En este punto, nada cabe en el caché. Así que estás limitado por el ancho de banda de la memoria.

Answer 8

La pregunta original

¿Por qué un bucle es mucho más lento que dos bucles?

Evaluando el problema

El código del OP:

const int n=100000;
for(int j=0;j<n;j++){
a1[j] += b1[j];
c1[j] += d1[j];
}

Y

for(int j=0;j<n;j++){
a1[j] += b1[j];
}
for(int j=0;j<n;j++){
c1[j] += d1[j];
}

La consideración

Teniendo en cuenta la pregunta original del OP sobre las 2 variantes de los bucles for y su pregunta modificada respecto al comportamiento de los cachés junto con muchas de las otras excelentes respuestas y comentarios útiles; Me gustaría intentar y hacer algo diferente aquí tomando un enfoque diferente sobre esta situación y este problema.

El enfoque

Teniendo en cuenta los dos bucles y toda la discusión sobre el almacenamiento en memoria caché y la página, me gustaría adoptar otro enfoque para ver esto desde una perspectiva diferente. Uno que no involucra el caché y los archivos de página ni las ejecuciones para asignar memoria, de hecho, este enfoque ni siquiera concierne al hardware real o al software en absoluto.

La perspectiva

Después de mirar el código por un tiempo, se hizo bastante evidente cuál es el problema y qué lo genera. Vamos a dividir esto en un problema algorítmico y analizarlo desde la perspectiva del uso de notaciones matemáticas, luego aplicar una analogía a los problemas matemáticos, así como a los algoritmos.

Lo que sabemos

Lo que sabemos es que su bucle se ejecutará 100.000 veces. También sabemos que a1 , b1 , c1 y d1 son punteros en una arquitectura de 64 bits. Dentro de C ++ en una máquina de 32 bits, todos los punteros son de 4 bytes y en una máquina de 64 bits tienen un tamaño de 8 bytes, ya que los punteros tienen una longitud fija. Sabemos que tenemos 32 bytes para asignar en ambos casos. La única diferencia es que estamos asignando 32 bytes o 2 conjuntos de 2-8 bytes en cada iteración, mientras que en el segundo caso estamos asignando 16 bytes para cada iteración para ambos bucles independientes. Por lo tanto, ambos bucles siguen siendo igual a 32 bytes en el total de asignaciones. Con esta información, avancemos y mostremos las matemáticas generales, el algoritmo y la analogía. Sabemos la cantidad de veces que el mismo conjunto o grupo de operaciones tendrá que realizarse en ambos casos. Sabemos la cantidad de memoria que debe asignarse en ambos casos. Podemos evaluar que la carga de trabajo global de las asignaciones entre ambos casos será aproximadamente la misma.

Lo que no sabemos

No sabemos cuánto tiempo tomará para cada caso a menos que establezcamos un contador y ejecutemos una prueba de evaluación comparativa. Sin embargo, los puntos de referencia ya se incluyeron en la pregunta original y también en algunas de las respuestas y comentarios, y podemos ver una diferencia significativa entre los dos, y este es el razonamiento completo de esta pregunta para este problema y para su respuesta a empezar con.

Vamos a investigar

Ya es evidente que muchos ya lo han hecho al observar las asignaciones de almacenamiento dinámico, las pruebas comparativas, la memoria RAM, la caché y los archivos de página. También se incluyeron los puntos de datos específicos y los índices de iteración específicos y las diversas conversaciones sobre este problema específico hacen que muchas personas empiecen a cuestionar otras cosas relacionadas al respecto. Entonces, ¿cómo comenzamos a ver este problema utilizando algoritmos matemáticos y aplicando una analogía a este? ¡Comenzamos haciendo un par de aserciones! Luego construimos nuestro algoritmo desde allí.

Nuestras afirmaciones:

• Dejaremos que nuestro bucle y sus iteraciones sean una suma que comience en 1 y finalice en 100000 en lugar de comenzar con 0 como en los bucles, ya que no tenemos que preocuparnos por el esquema de indexación 0 de direccionamiento de memoria, ya que solo estamos interesados ​​en el algoritmo mismo.
• En ambos casos tenemos 4 funciones para trabajar y 2 llamadas de función con 2 operaciones que se realizan en cada llamada de función. Así que vamos a establecer estas arriba como funciones y llamadas de funciones a ser F1(), F2(), f(a), f(b), f(c)y f(d).

Los algoritmos:

1er caso: - Sólo una suma, pero dos llamadas a funciones independientes.

Sum n=1 : [1,100000] = F1(), F2();
F1() = { f(a) = f(a) + f(b); }
F2() = { f(c) = f(c) + f(d); }

Segundo caso: - Dos sumas pero cada una tiene su propia función de llamada.

Sum1 n=1 : [1,100000] = F1();
F1() = { f(a) = f(a) + f(b); }
Sum2 n=1 : [1,100000] = F1();
F1() = { f(c) = f(c) + f(d); }

Si te has dado cuenta F2()solo existe en Sumdonde ambos Sum1y Sum2solo contiene F1(). Esto también será evidente más adelante cuando empecemos a concluir que hay una especie de optimización que está sucediendo desde el segundo algoritmo.

Las iteraciones a través del primer caso de Sumllamadas f(a)que se agregarán a sí mismas y f(b)luego llamadas f(c)que harán lo mismo pero se agregarán f(d)a sí mismas para cada una 100000 iterations. En el segundo caso, tenemos Sum1y Sum2Y ambos actúan de la misma manera como si fueran la misma función que se llama dos veces seguidas. En este caso, podemos tratar Sum1y Sum2simplemente como antiguo Sumdonde Sumen este caso se ve así: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }y ahora esto parece una optimización donde solo podemos considerar que es la misma función.

Resumen con analogía

Con lo que vimos en el segundo caso, casi parece que hay optimización, ya que ambos bucles tienen la misma firma exacta, pero este no es el problema real. El problema no es el trabajo que se está realizando f(a), f(b), f(c)y f(d)en ambos casos, y la comparación entre los dos es la diferencia en la distancia que la suma tiene que viajar en ambos casos que le da la diferencia en tiempo de ejecución.

Piense en el For Loopscomo el Summationsque hace las iteraciones como ser una Bossque está dando órdenes a dos personas Ay By que sus puestos de trabajo son a la carne Cy D, respectivamente, y para recoger algún paquete de ellos y lo devuelve. En la analogía aquí, las iteraciones de bucle for o sumación y las comprobaciones de condición en sí mismas no representan el Boss. Lo que en realidad representa el Bossaquí no es directamente de los algoritmos matemáticos reales, sino del concepto real de Scopey Code Blockdentro de una rutina o subrutina, método, función, unidad de traducción, etc. El primer algoritmo tiene 1 alcance donde el 2do algoritmo tiene 2 alcances consecutivos.

En el primer caso, en cada recibo de llamada, Bossva Ay da el pedido y Asale para buscar el B''spaquete, luego Bossva Cy da las órdenes para hacer lo mismo y recibir el paquete Den cada iteración.

En el segundo caso, Bossfunciona directamente con Air y buscar el B''spaquete hasta que se reciben todos los paquetes. Luego Bossfunciona con Chacer lo mismo para obtener todos los D''spaquetes.

Como estamos trabajando con un puntero de 8 bytes y tratando con la asignación de Heap, consideremos este problema aquí. Digamos que Bossestá a 100 pies de distancia Ay que Aestá a 500 pies de C. No debemos preocuparnos por la distancia Bossinicial del Corden debido al orden de las ejecuciones. En ambos casos, la Bossprimera se desplaza desde el Aprimero hasta el siguiente B. Esta analogía no quiere decir que esta distancia es exacta; es solo un caso de prueba de uso para mostrar el funcionamiento de los algoritmos. En muchos casos, al realizar asignaciones de almacenamiento dinámico y trabajar con el caché y los archivos de página, estas distancias entre las ubicaciones de las direcciones pueden no variar mucho en las diferencias o pueden ser muy importantes, dependiendo de la naturaleza de los tipos de datos y los tamaños de matriz.

Los casos de prueba:

Primer caso: en la primera iteración,Bossinicialmente tiene que recorrer 100 pies para que la orden se resbaleAyAse apague y haga lo suyo, pero luegoBosstiene que viajar 500 piesCpara darle la hoja de la orden. Luego, en la siguiente iteración y en cada otra iteración después de laBosstiene que ir y venir 500 pies entre los dos.

Segundo caso: The Boss tiene que viajar 100 pies en la primera iteraciónA, pero después de eso ya está allí y solo esperaAregresar hasta que se llenen todos los resbalones. Luego,Bosstiene que viajar 500 pies en la primera iteraciónCporqueCestá a 500 piesAdesde queBoss( Summation, For Loop )se está llamando justo después de trabajar conAy luego solo espera como lo hizoAhasta que seC''scompletentodos losformulariosdepedido.

La diferencia en distancias recorridas

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500);
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst = 10000500;
// Distance Traveled On First Algorithm = 10,000,500ft
distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;

La comparación de valores arbitrarios

Podemos ver fácilmente que 600 es mucho menos que 10 millones. Ahora bien, esto no es exacto, ya que no sabemos la diferencia real en la distancia entre la dirección de la RAM o desde la cual el caché o el archivo de la página en cada iteración se debe a muchas otras variables invisibles, pero esto es simplemente una evaluación de la situación para conocer y tratar de verla desde el peor de los casos.

Entonces, por estos números, casi parecería que Algorithm One debería ser 99% más lento que el Algorithm Two; sin embargo, esto es solo la The Boss''sparte o responsabilidad de los algoritmos y no tiene en cuenta los trabajadores reales A, By C, Dy lo que tienen que hacer en cada iteración del bucle. Así que el trabajo de los jefes solo representa alrededor del 15 - 40% del trabajo total que se está realizando. Por lo tanto, la mayor parte del trabajo que se realiza a través de los trabajadores tiene un impacto ligeramente mayor hacia el mantenimiento de la proporción de las diferencias de velocidad entre aproximadamente el 50 y el 70%

La observación: - Las diferencias entre los dos algoritmos.

En esta situación, es la estructura del proceso del trabajo que se está realizando y muestra que el Caso 2 es más eficiente tanto por la optimización parcial de tener una declaración de función similar como por definición donde solo las variables difieren por nombre . Y también vemos que la distancia total recorrida en el Caso 1 es mucho mayor que en el Caso 2 y podemos considerar que la distancia recorrida es nuestro Factor de tiempo entre los dos algoritmos. El caso 1 tiene mucho más trabajo que hacer que el caso 2 . Esto también fue visto en la evidencia de laASMEso se demostró entre ambos casos. Incluso con lo que se dijo ya sobre estos casos, también no tener en cuenta el hecho de que en el caso 1 el jefe tendrá que esperar por tanto Ay Cpara volver antes de que pueda volver a Aotra vez en la siguiente iteración y también doesn No tenga en cuenta el hecho de que si Ao Bestá tomando un tiempo extremadamente largo, tanto el Bosstrabajador como los otros trabajadores también están esperando en inactividad. En el caso 2, el único que está inactivo es el Bosshasta que el trabajador regrese. Así que incluso esto tiene un impacto en el algoritmo.

Conclusión:

El caso 1 es un problema clásico de interpolación que resulta ser ineficiente. También creo que esta fue una de las razones principales por las que muchas arquitecturas de máquinas y desarrolladores terminaron construyendo y diseñando sistemas de múltiples núcleos con la capacidad de realizar aplicaciones de subprocesos múltiples, así como programación paralela.

Así que incluso mirándolo desde este enfoque sin siquiera involucrar cómo el hardware, el sistema operativo y el compilador trabajan juntos para realizar asignaciones de almacenamiento dinámico que impliquen trabajar con RAM, caché, archivos de página, etc .; La matemática subyacente ya nos muestra cuál de estos dos es la mejor solución al usar la analogía anterior donde el Bosso Summationslos For Loopsque tenían que viajar entre los trabajadores Ay B. Podemos ver fácilmente que el Caso 2 es al menos tan rápido como 1/2, si no un poco más que el Caso 1, debido a la diferencia en la distancia recorrida y el tiempo empleado. Y esta matemática se alinea de manera casi virtual y perfecta tanto con el Bench Mark Times como con la Cantidad de diferencia en la cantidad de Instrucciones de montaje.

Las preguntas modificadas de los OP

EDITAR: La pregunta resultó no tener relevancia, ya que el comportamiento depende en gran medida de los tamaños de los arreglos (n) y la memoria caché de la CPU. Entonces si hay más interés, reformulo la pregunta:

¿Podría proporcionar alguna información sólida sobre los detalles que conducen a los diferentes comportamientos de la memoria caché, como lo ilustran las cinco regiones en el siguiente gráfico?

También podría ser interesante señalar las diferencias entre las arquitecturas de CPU / caché, al proporcionar un gráfico similar para estas CPU.

Con respecto a estas preguntas

Como lo he demostrado sin lugar a dudas, existe un problema subyacente incluso antes de que el Hardware y el Software se involucren. Ahora en lo que respecta a la administración de la memoria y el almacenamiento en caché junto con los archivos de páginas, etc., todo funciona en conjunto en un conjunto integrado de sistemas entre: The Architecture{Hardware, Firmware, algunos Controladores integrados, Kernels y Conjuntos de instrucciones ASM}, The OS{Sistemas de gestión de archivos y memorias , Controladores y registro}, The Compiler{Unidades de traducción y optimizaciones del código fuente}, e incluso el Source Codemismo con sus conjuntos de algoritmos distintivos; ya podemos ver que hay un cuello de botella que está sucediendo dentro del primer algoritmo antes de que incluso lo aplicamos a cualquier máquina con cualquier arbitraria Architecture, OSyProgrammable LanguageEn comparación con el segundo algoritmo. Así que ya existía un problema antes de involucrar los intrínsecos de una computadora moderna.

Los resultados finales

Sin embargo; no quiere decir que estas nuevas preguntas no tengan importancia porque ellas mismas sí lo son y desempeñan un papel después de todo. Impactan los procedimientos y el rendimiento general, y eso es evidente con los diversos gráficos y evaluaciones de muchos que han dado sus respuestas y / o comentarios. Si presta atención a la analogía de los Bossy los dos trabajadores Ay Bquién tuvo que ir y recuperar paquetes de Cy Drespectivamente y considerando las notaciones matemáticas de los dos algoritmos en cuestión, puede ver que sin la participación de la computadora Case 2es aproximadamente del 60% más rápido queCase 1 y cuando observa los gráficos y cuadros después de que estos algoritmos se hayan aplicado al código fuente, se hayan compilado y optimizado y ejecutado a través del sistema operativo para realizar operaciones en el hardware dado, incluso verá un poco más de degradación entre las diferencias en estos algoritmos.

Ahora bien, si el conjunto de "Datos" es bastante pequeño, puede que no parezca tan malo de una diferencia al principio, pero ya que Case 1es 60 - 70%más lento de Case 2lo que podemos considerar el crecimiento de esta función en términos de las diferencias en las ejecuciones de tiempo:

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

Y esta aproximación es la diferencia promedio entre estos dos bucles, tanto algorítmicamente como las operaciones de la máquina que involucran optimizaciones de software e instrucciones de la máquina. Entonces, cuando el conjunto de datos crece linealmente, también lo hace la diferencia de tiempo entre los dos. El algoritmo 1 tiene más captaciones que el algoritmo 2, lo cual es evidente cuando Bosstuvo que viajar de ida y vuelta a la distancia máxima entre Ay Cpara cada iteración después de la primera iteración, mientras que el algoritmo 2 Bosstuvo que viajar Auna vez y luego, después de haber terminado A, tuvo que viajar una distancia máxima solo una vez cuando se va de Aa C.

Entonces, tratar de Bossconcentrarse en hacer dos cosas similares a la vez y hacer malabares con ellas en lugar de enfocarse en tareas consecutivas similares, lo pondrá muy enojado al final del día porque tuvo que viajar y trabajar el doble. Por lo tanto, no pierda el alcance de la situación al permitir que su jefe se meta en un cuello de botella interpolado porque el cónyuge y los hijos del jefe no lo apreciarían.

Answer 9

No puedo replicar los resultados discutidos aquí.

No sé si el culpable es un código de referencia pobre, o qué, pero los dos métodos están dentro del 10% uno del otro en mi máquina usando el siguiente código, y un bucle suele ser un poco más rápido que dos, como usted esperar.

Los tamaños de los arreglos variaron de 2 ^ 16 a 2 ^ 24, usando ocho bucles. Tuve la precaución de inicializar las matrices de origen, por lo que la asignación += no pedía a la FPU que agregue basura de memoria interpretada como un doble.

InitToZero[j] con varios esquemas, como poner la asignación de b[j] , d[j] a InitToZero[j] dentro de los bucles, y también usando += b[j] = 1 y += d[j] = 1 , y obtuve resultados bastante consistentes.

Como es de esperar, la inicialización de b y d dentro del bucle utilizando InitToZero[j] le dio una ventaja al enfoque combinado, ya que se realizaron en forma consecutiva antes de las asignaciones a y c , pero aún dentro del 10%. Imagínate.

El hardware es Dell XPS 8500 con generación 3 Core i7 a 3,4 GHz y 8 GB de memoria. Para 2 ^ 16 a 2 ^ 24, usando ocho bucles, el tiempo acumulado fue 44.987 y 40.965 respectivamente. Visual C ++ 2010, totalmente optimizado.

PD: cambié los bucles para contar a cero, y el método combinado fue ligeramente más rápido. Rascarme la cabeza Tenga en cuenta el nuevo tamaño de matriz y recuentos de bucle

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>
#define dbl double
#define MAX_ARRAY_SZ 262145 //16777216 // AKA (2^24)
#define STEP_SZ 1024 // 65536 // AKA (2^16)
int _tmain(int argc, _TCHAR* argv[]) {
long i, j, ArraySz = 0, LoopKnt = 1024;
time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;
a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
// Initialize array to 1.0 second.
for(j = 0; j< MAX_ARRAY_SZ; j++) {
InitToOnes[j] = 1.0;
}
// Increase size of arrays and time
for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
// Outside the timing loop, initialize
// b and d arrays to 1.0 sec for consistent += performance.
memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));
start = clock();
for(i = LoopKnt; i; i--) {
for(j = ArraySz; j; j--) {
a[j] += b[j];
c[j] += d[j];
}
}
Cumulative_Combined += (clock()-start);
printf("/n %6i miliseconds for combined array sizes %i and %i loops",
(int)(clock()-start), ArraySz, LoopKnt);
start = clock();
for(i = LoopKnt; i; i--) {
for(j = ArraySz; j; j--) {
a[j] += b[j];
}
for(j = ArraySz; j; j--) {
c[j] += d[j];
}
}
Cumulative_Separate += (clock()-start);
printf("/n %6i miliseconds for separate array sizes %i and %i loops /n",
(int)(clock()-start), ArraySz, LoopKnt);
}
printf("/n Cumulative combined array processing took %10.3f seconds",
(dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
printf("/n Cumulative seperate array processing took %10.3f seconds",
(dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
getchar();
free(a); free(b); free(c); free(d); free(InitToOnes);
return 0;
}

No estoy seguro de por qué se decidió que MFLOPS era una métrica relevante. Pensé que la idea era centrarme en los accesos a la memoria, así que intenté minimizar la cantidad de tiempo de cálculo de punto flotante. Me fui en el += , pero no estoy seguro de por qué.

Una asignación directa sin cálculo sería una prueba más limpia del tiempo de acceso a la memoria y crearía una prueba que sea uniforme independientemente del conteo de bucles. Tal vez me perdí algo en la conversación, pero vale la pena pensarlo dos veces. Si se deja fuera de la asignación, el tiempo acumulado es casi idéntico a 31 segundos cada uno.

Answer 10

Puede ser viejo C ++ y optimizaciones. En mi computadora obtuve casi la misma velocidad:

un bucle: 1.577 ms dos bucles: 1.507 ms

Ejecuto VS2015 en el procesador E5-1620 3.5Ghz con un ram de 16Gb