Características del lenguaje mql5, sutilezas y técnicas - página 117

 

Esta es la variante que se me ha ocurrido:

int log2_(ulong n)
{
  if (n==0) return -1;

  #define  M(n, i, base, S) ( n >= (ulong(1)<<(i)) ? S(n, i+base/2) : S(n, i-(base+1)/2) )

  #define  S_0(n, i)  i
  #define  S_1(n, i)  M(n, i, 1, S_0)
  #define  S_2(n, i)  M(n, i, 2, S_1)
  #define  S_4(n, i)  M(n, i, 4, S_2)
  #define  S_8(n, i)  M(n, i, 8, S_4)
  #define  S_16(n, i) M(n, i, 16, S_8)
  #define  S(n)       M(n, 32, 32, S_16)

  return S(n); 
}

Se supone que es la más rápida de todas las posibles. Todos los cálculos se realizan con constantes, por lo que se calculan durante la compilación. Así, todo se reduce a sólo 6 comparaciones consecutivas y nada más. Sin embargo, esta variante funciona más lentamente que la anterior. No puedo entender la razón de ello.

 
Alexey Navoykov:

Esta es la variante que se me ha ocurrido:

En idea, esta es la más rápida de todas las posibles. Todos los cálculos se hacen con constantes, por lo que se calculan durante la compilación. Así, todo se reduce a sólo 6 comparaciones consecutivas, y nada más. Sin embargo, esta variante funciona más lentamente que la anterior. No puedo entender cuál es la razón.

Dividir por dos lo hace más lento? ¿Tratar de reemplazar con un desplazamiento? Sospecho que las constantes calculadas - deben ser calculadas inmediatamente (en este caso - y el desplazamiento en la definición - también debe ser reemplazado por una constante).

Además, "question" es un operador bastante controvertido, como sé. Hace veinte años se comprobó en C++ y a veces "question" genera un código mucho más largo que el operador if habitual. ¿Tal vez sea lo mismo aquí?

Y, yo haría el código de retorno uint - ¿y si hay algunas comprobaciones al convertir valores con y sin signo?

Todavía no he tenido la oportunidad de experimentar manualmente - la CPU está muy sobrecargada... Incluso el texto se escribe "con lentitud"...

 
Georgiy Merts:

Dividir por dos lo hace más lento? Sospecho que las constantes calculadas - deben ser calculadas inmediatamente (en este caso - y el desplazamiento en la definición - también debe ser reemplazado por una constante).

También - "pregunta" - como sé, es un operador bastante controvertido ...

La sustitución de la división por el desplazamiento no tiene ningún efecto. Sospecho que la expresión resultante es demasiado larga, por lo que el compilador no la optimizó hasta el final.

Sin embargo, realicé las pruebas con Optimize=0, mientras que cuando la optimización estaba activada, todo iba bien: la segunda variante era una vez y media más rápida. ¡Bingo!

Si se desactiva la optimización, la segunda opción es ligeramente más lenta con valores pequeños, pero ligeramente más rápida con valores mayores. En resumen, la segunda opción es definitivamente mejor.

 
Alexey Navoykov:

Esta es la variante que se me ha ocurrido:

Esta es supuestamente la más rápida de todas las variantes posibles. Todos los cálculos se realizan con constantes, por lo que se calculan en la compilación, por lo que todo se reduce a sólo 6 comparaciones consecutivas y nada más. Sin embargo, esta variante funciona más lentamente que la anterior. No puedo entender la razón de ello.

Así es, su variante es la más rápida.

Es que la prueba está inactiva. Los programadores olvidan muy a menudo una cosa importante cuando prueban el rendimiento: si un valor calculado no se utiliza en ningún sitio, el compilador simplemente no realizará el cálculo.

Es lógico, ¿qué sentido tiene? Es como en la superposición cuántica. Por qué debería existir la luna si nadie la mira. "¿Existe la luna sólo porque la mira un ratón?" (Albert Einstein). :))

Así que esta versión de la prueba con el cálculo de la suma de comprobación y su impresión sería más correcta:

#property strict
#define    test(M,S,EX)        {long sum=0; uint nn=(uint)pow(10,M); ulong mss=GetMicrosecondCount(); for(uint t12=1;t12<=nn;t12++){EX;sum+=(long)n1;} \
                                Print(S+": loops="+(string)nn+" μs="+string(GetMicrosecondCount()-mss)+" Контрольная сумма="+string(sum));}

int log2(ulong n){
  if (n==0) return -1;
  #define  S(k) if (n >= (ulong(1)<<k)) { i += k;  n >>= k; }
  int i=0;  S(32);  S(16);  S(8);  S(4);  S(2);  S(1);  return i;
  #undef  S}


static const uint ulLogTable[64] = {
0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };

uint _FastLog2(ulong ulInput){
   ulInput |= ulInput >> 1;
   ulInput |= ulInput >> 2;
   ulInput |= ulInput >> 4;
   ulInput |= ulInput >> 8;
   ulInput |= ulInput >> 16;
   ulInput |= ulInput >> 32;  
   return(ulLogTable[(uint)((ulInput * 0x03f6eaf2cd271461) >> 58)]);};
   
int log2_(ulong n)
{
  if (n==0) return -1;

  #define  M(n, i, base, S) ( n >= (ulong(1)<<(i)) ? S(n, i+base/2) : S(n, i-(base+1)/2) )

  #define  S_0(n, i)  i
  #define  S_1(n, i)  M(n, i, 1, S_0)
  #define  S_2(n, i)  M(n, i, 2, S_1)
  #define  S_4(n, i)  M(n, i, 4, S_2)
  #define  S_8(n, i)  M(n, i, 8, S_4)
  #define  S_16(n, i) M(n, i, 16, S_8)
  #define  S(n)       M(n, 32, 32, S_16)

  return S(n); 
}

void OnStart(){
  srand(GetTickCount());
  ulong n1;
  test(8,"MathLog",n1=ulong(MathLog((double)t12)/MathLog(2.0)))
  test(8,"log2",n1=log2(t12))
  test(8,"log2_",n1=log2_(t12))
  test(8,"_FastLog2",n1=_FastLog2(t12))}

Resultado:

2019.01.05 02:30:03.681 TestLog (.BrentCrud,H4) MathLog:   loops=100000000 μs=805196 Контрольная сумма=2465782300
2019.01.05 02:30:04.092 TestLog (.BrentCrud,H4) log2:      loops=100000000 μs=410657 Контрольная сумма=2465782300
2019.01.05 02:30:04.234 TestLog (.BrentCrud,H4) log2_:     loops=100000000 μs=141975 Контрольная сумма=2465782300
2019.01.05 02:30:04.432 TestLog (.BrentCrud,H4) _FastLog2: loops=100000000 μs=198015 Контрольная сумма=2465782300
Y el segundo lugar sigue siendo _FastLog2, no log2 :))
 
Nikolai Semko:

Es sólo una prueba en vacío. A menudo se olvida un punto importante en las pruebas de rendimiento: si el valor calculado no se utiliza en ninguna parte, el compilador simplemente no realiza el cálculo.

Tiene sentido, ¿qué sentido tiene? Es como en la superposición cuántica. Por qué debería existir la luna si nadie la mira. "¿Existe la luna sólo porque la mira un ratón?" (Albert Einstein). :))

Así que esta versión de la prueba con el cálculo de la suma de comprobación y su impresión será más correcta:

Tu código está enmarañado. Las variables utilizadas en la definición están situadas en el otro extremo del código del programa - no es conveniente ordenar ese caos. Pero esa no es la cuestión. La cuestión es que los resultados de tus pruebas no pueden considerarse fiables porque el compilador conoce de antemano el algoritmo de los valores pasados a la función. Así que optimiza tus pruebas. Deberías calcular sobre números aleatorios .

Por cierto, ¿por qué tienes srand en tu código? Cuando lo vi, al principio pensé que estabas usando random, pero en realidad no es así.

Aquí está mi código:

void OnStart()
{
  Print("OnStart");
  srand(GetTickCount());
  int count= 50000000;
   
  #define  TEST(func) { \ 
    ulong sum=0; \
    ulong mcscount= GetMicrosecondCount(); \
    for (int i=0; i<count; i++) \
      sum += func(rand() | rand()<<15); \
    Print("Result "+#func+":  sum=",sum,"  time=",(GetMicrosecondCount()-mcscount)/1000," ms"); \    
  }
  
   TEST(log2);
  TEST(log2_);
}
 
Alexey Navoykov:

Tu código es confuso. Las variables usadas en la definición están situadas en el otro extremo del código del programa - es inconveniente ordenar tal caos. Pero este no es el punto, el punto es que los resultados de tus pruebas no pueden ser considerados fiables, porque el compilador conoce de antemano el algoritmo de los valores pasados a la función. Por lo tanto, optimiza tus pruebas. Deberías calcular sobre números aleatorios .

Por cierto, ¿por qué tienes srand en tu código? Cuando lo vi, al principio pensé que estabas usando random, pero en realidad no es así.

Aquí está mi código:

el código no es mío. Acabo de retocarlo y he eliminado rand para comprobar las mismas sumas de comprobación y eliminar la función rand, relativamente cara, del bucle, pero simplemente me olvidé de eliminar srand.

Devuelvo el rand. Tienes razón: el compilador optimiza el bucle para la suma de logaritmos de valores consecutivos. Sin embargo, me sorprende. No entiendo cómo lo hace. Quizás hay algo que no estamos teniendo en cuenta.

#property strict
#define    test(M,S,EX)        {srand(45); long sum=0; uint nn=(uint)pow(10,M); ulong mss=GetMicrosecondCount(); for(uint t12=1;t12<=nn;t12++){EX;sum+=(long)n1;} \
                                Print(S+": loops="+(string)nn+" μs="+string(GetMicrosecondCount()-mss)+" Контрольная сумма="+string(sum));}

int log2(ulong n){
  if (n==0) return -1;
  #define  S(k) if (n >= (ulong(1)<<k)) { i += k;  n >>= k; }
  int i=0;  S(32);  S(16);  S(8);  S(4);  S(2);  S(1);  return i;
  #undef  S}


static const uint ulLogTable[64] = {
0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };

uint _FastLog2(ulong ulInput){
   ulInput |= ulInput >> 1;
   ulInput |= ulInput >> 2;
   ulInput |= ulInput >> 4;
   ulInput |= ulInput >> 8;
   ulInput |= ulInput >> 16;
   ulInput |= ulInput >> 32;  
   return(ulLogTable[(uint)((ulInput * 0x03f6eaf2cd271461) >> 58)]);};
   
int log2_(ulong n)
{
  if (n==0) return -1;

  #define  M(n, i, base, S) ( n >= (ulong(1)<<(i)) ? S(n, i+base/2) : S(n, i-(base+1)/2) )

  #define  S_0(n, i)  i
  #define  S_1(n, i)  M(n, i, 1, S_0)
  #define  S_2(n, i)  M(n, i, 2, S_1)
  #define  S_4(n, i)  M(n, i, 4, S_2)
  #define  S_8(n, i)  M(n, i, 8, S_4)
  #define  S_16(n, i) M(n, i, 16, S_8)
  #define  S(n)       M(n, 32, 32, S_16)

  return S(n); 
}

void OnStart(){
  ulong n1,n;
  test(8,"MathLog",n=(rand()+1)*(rand()+1);n1=ulong(MathLog((double)n)/MathLog(2.0)))
  test(8,"log2",n=(rand()+1)*(rand()+1);n1=log2(n))
  test(8,"log2_",n=(rand()+1)*(rand()+1);n1=log2_(n))
  test(8,"_FastLog2",n=(rand()+1)*(rand()+1);n1=_FastLog2(n))}

Resultado:

2019.01.05 04:10:25.808 TestLog (EURUSD,H1)     MathLog:   loops=100000000 μs=1168737 Контрольная сумма=2661391201
2019.01.05 04:10:26.474 TestLog (EURUSD,H1)     log2:      loops=100000000 μs=665631  Контрольная сумма=2661391201
2019.01.05 04:10:27.315 TestLog (EURUSD,H1)     log2_:     loops=100000000 μs=841299  Контрольная сумма=2661391201
2019.01.05 04:10:27.694 TestLog (EURUSD,H1)    _FastLog2:  loops=100000000 μs=378627   Контрольная сумма=2661391201
   

El ganador actual es _FastLog2

 
Nikolai Semko:

Resultado:

Ganador actual _FastLog2

Me pregunto cómo has conseguido la misma suma de comprobación en todas partes, si los valores son aleatorios.

 
Alexey Navoykov:

Me pregunto cómo se obtiene la misma suma de comprobación en todas partes, si los valores son aleatorios.

srand(45) para todas las funciones

Yo también lo hice así al principio, pero obtuve sumas de comprobación diferentes, porque no tuve en cuenta que rand()*rand() puede ser 0, lo que rompe la suma de comprobación. Ahora he añadido uno para alejarme del cero.

 
Nikolai Semko:

srand(45) para todas las funciones

Yo hice lo mismo al principio, pero obtuve sumas de comprobación diferentes, porque no tuve en cuenta que rand()*rand() puede ser 0, lo que rompe la suma de comprobación. Ahora he añadido uno para alejarme del cero.

¿Y por qué necesitas la misma suma de comprobación si estamos hablando específicamente de medidas de velocidad? El punto de la suma en este caso es simplemente para evitar que el compilador corte el código, eso es todo. Y al hacer srand(45), de nuevo permites optimizar la prueba.

Por cierto, hablando de cero, FastLog2 no comprueba el cero, lo que le da una ventaja. Pero sigue siendo de una vez y media a dos veces más lento que log2 si se prueba correctamente).

 
Alexey Navoykov:
¿Y por qué necesitas la misma suma de comprobación si estamos hablando específicamente de medidas de velocidad? El punto de la suma en este caso es simplemente para evitar que el compilador corte el código, eso es todo. Y hacer srand(45), de nuevo, te permite optimizar la prueba.

Estás sobreestimando las capacidades del compilador. Eliminar srand(45) - las sumas de comprobación serán diferentes, pero el resultado de la velocidad sigue siendo el mismo.

Además, me guié por el hecho de que los cálculos fueran los mismos en aras de la pureza del experimento, porque no entré en detalles de todas las funciones. A veces, el valor de un parámetro de la función puede afectar al tiempo de su ejecución.

Razón de más para comprobar la corrección de los algoritmos.