Características da linguagem mql5, subtilezas e técnicas - página 117

 

Esta é a variante que eu inventei:

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); 
}

É suposto ser o mais rápido de todos os possíveis. Todos os cálculos são efectuados com constantes, por isso são calculados durante a compilação. Assim, tudo é reduzido a apenas 6 comparações consecutivas e nada mais. Contudo, esta variante funciona mais lentamente do que a anterior. Não consigo compreender a razão para isso.

 
Alexey Navoykov:

Esta é a variante que eu inventei:

Na ideia, este é o mais rápido de todos os possíveis. Todos os cálculos são feitos com constantes, pelo que são calculados durante a compilação. Assim, tudo é reduzido a apenas 6 comparações consecutivas, e nada mais. Contudo, esta variante funciona mais lentamente do que a anterior. Não consigo compreender qual é a razão.

Dividir por dois desacelera o processo ? Tentar substituir por um turno? suspeito que as constantes calculadas - devem ser calculadas imediatamente (neste caso - e o turno na definição - também deve ser substituído por uma constante).

Além disso, "pergunta" é um operador bastante controverso, como eu sei. Há vinte anos foi verificado em C++ e por vezes "pergunta" gera um código muito mais longo do que o habitual se operador. Talvez seja o mesmo aqui?

E, eu faria com que o código de retorno não fosse utilizado - e se houver algumas verificações na conversão de valores assinados e não assinados?

Ainda não tenho oportunidade de experimentar manualmente - a CPU está muito sobrecarregada... Até o texto é dactilografado "com lentidão"...

 
Georgiy Merts:

Dividir por dois desacelera o processo ? Tentar substituí-lo por um turno ? suspeito que as constantes calculadas - devem ser calculadas imediatamente (neste caso - e o turno na definição - também deve ser substituído por uma constante).

Também - "pergunta" - como sei, é um operador bastante controverso ...

A substituição da divisão por turno não tem qualquer efeito. Suspeito que a expressão resultante seja demasiado longa, pelo que o compilador não a optimizou até ao fim.

Mas fiz os testes quando Optimize=0, enquanto que quando a optimização foi activada, tudo correu bem - a segunda variante foi uma vez e meia mais rápida. Bingo!

Se a optimização for desactivada, então a segunda opção é ligeiramente mais lenta a valores pequenos, mas ligeiramente mais rápida a valores maiores. Em suma, a segunda opção é definitivamente melhor.

 
Alexey Navoykov:

Esta é a variante que eu inventei:

Esta é supostamente a mais rápida de todas as variantes possíveis. Todos os cálculos são efectuados com constantes, pelo que são calculados durante a compilação. Assim, tudo é reduzido a apenas 6 comparações consecutivas e nada mais. No entanto, esta variante funciona mais lentamente do que a anterior. Não consigo compreender a razão para isso.

É isso mesmo - a sua variante é a mais rápida.

É que o teste é ocioso. Os programadores esquecem-se muitas vezes de uma coisa importante quando testam o desempenho: se um valor calculado não for utilizado em qualquer lugar, o compilador simplesmente não efectua o cálculo.

Faz sentido, qual é o objectivo? É como em sobreposição quântica. Porque deveria a lua existir se ninguém está a olhar para ela. "A lua existe só porque um rato está a olhar para ela?" (Albert Einstein). :))

Assim, esta versão do teste com o cálculo da soma de controlo e a sua impressão seria mais 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
E o segundo lugar continua a ser _FastLog2, não log2 :))
 
Nikolai Semko:

É apenas um teste ocioso. Um ponto importante é muitas vezes esquecido nos testes de desempenho: se o valor calculado não for utilizado em qualquer lugar, o compilador simplesmente não efectua o cálculo.

Faz sentido, qual é o objectivo? É como em sobreposição quântica. Porque deveria a lua existir se ninguém está a olhar para ela. "A lua existe só porque um rato está a olhar para ela?" (Albert Einstein). :))

Assim, esta versão do teste com o cálculo da soma de controlo e a impressão será mais correcta:

O seu código está emaranhado. As variáveis utilizadas na definição estão localizadas no outro extremo do código do programa - não é conveniente ordenar através de tal caos. Mas não é essa a questão. A questão é que os resultados dos seus testes não podem ser considerados fiáveis porque o compilador conhece antecipadamente o algoritmo de valores passados para a função. Por isso, optimiza os seus testes. Deve calcular em números aleatórios .

A propósito, porque é que tem uma ordem no seu código? Quando o vi, no início pensei que estava a usar aleatoriamente, mas na verdade não está.

Aqui está o meu 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:

O seu código é confuso. As variáveis utilizadas na definição estão localizadas no outro extremo do código do programa - é inconveniente ordenar através de tal caos. Mas não é esta a questão, a questão é que os resultados dos seus testes não podem ser considerados fiáveis, porque o compilador conhece antecipadamente o algoritmo de valores passados para a função. Por isso, deve optimizar os seus testes. Deve calcular sobre números aleatórios .

A propósito, porque é que tem uma ordem no seu código? Quando o vi, no início pensei que estava a usar aleatoriamente, mas na verdade não está.

Aqui está o meu código:

o código não é meu. Apenas o afinei e removi o rand para verificar os mesmos checksums e remover a função rand relativamente cara do laço, mas esqueci-me simplesmente de remover o srand.

Eu devolvo rand. Tem razão - o compilador optimiza o laço para a soma dos logaritmos a partir de valores consecutivos. Estou surpreendido, no entanto. Não compreendo como é que isso acontece. Talvez haja algo que não estamos a ter em conta.

#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
   

O vencedor actual é _FastLog2

 
Nikolai Semko:

Resultado:

Vencedor actual _FastLog2

Pergunto-me como terá obtido o mesmo checksum em todo o lado, se os valores são aleatórios.

 
Alexey Navoykov:

Pergunto-me como se obtém o mesmo checksum em todo o lado, se os valores são aleatórios.

srand(45) para todas as funções

No início também o fiz dessa forma, mas consegui diferentes checksums, porque não tive em conta que rand()*rand() pode ser 0, o que quebra o checksum. Agora acrescentei um para me afastar do zero.

 
Nikolai Semko:

srand(45) para todas as funções

Fiz o mesmo no início, mas consegui diferentes checksums, porque não tive em conta que rand()*rand() pode ser 0, o que quebra o checksum. Agora acrescentei um para me afastar do zero.

E porque é que precisa do mesmo checksum se estamos a falar especificamente de medições de velocidade? O objectivo da soma neste caso é simplesmente evitar que o compilador corte o código, só isso. E ao fazer srand(45), permite novamente optimizar o teste.

A propósito, falando de zero, FastLog2 não verifica o zero, o que lhe dá um avanço. Mas ainda é uma vez e meia a duas vezes mais lento do que o log2 se testado correctamente).

 
Alexey Navoykov:
E porque precisa do mesmo checksum se estamos a falar especificamente de medições de velocidade? O objectivo da soma neste caso é simplesmente evitar que o compilador corte o código, só isso. E fazer srand(45), mais uma vez, permite-lhe optimizar o teste.

Está aqui a sobrestimar as capacidades do compilador. Remover srand(45) - os checksums serão diferentes, mas o resultado da velocidade permanece o mesmo.

Além disso, fui guiado pelo facto de os cálculos serem os mesmos por causa da pureza da experiência, porque não entrei em detalhes de todas as funções. Por vezes, o valor de um parâmetro de função pode afectar o tempo da sua execução.

Mais uma razão para verificar a correcção dos algoritmos.