Caratteristiche del linguaggio mql5, sottigliezze e tecniche - pagina 117

Nuovo commento
 

Questa è la variante che mi è venuta in mente:

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

Si suppone che sia il più veloce di tutti i possibili. Tutti i calcoli sono eseguiti con costanti, quindi sono calcolati durante la compilazione. Quindi, tutto è ridotto a soli 6 confronti consecutivi e niente di più. Tuttavia, questa variante funziona più lentamente della precedente. Non riesco a capirne la ragione.

 
Alexey Navoykov:

Questa è la variante che mi è venuta in mente:

In idea, questo è il più veloce di tutti i possibili. Tutti i calcoli sono fatti con costanti, quindi sono calcolati durante la compilazione. Quindi, tutto è ridotto a soli 6 confronti consecutivi, e niente di più. Tuttavia, questa variante funziona più lentamente della precedente. Non riesco a capire quale sia la ragione.

Dividere per due lo rallenta? Ho il sospetto che le costanti calcolate - devono essere calcolate immediatamente (in questo caso - e lo spostamento nella definizione - deve anche essere sostituito da una costante).

Inoltre, "question" è un operatore piuttosto controverso, come so. Venti anni fa è stato controllato in C++ e a volte "question" genera un codice molto più lungo del solito operatore if. Forse è lo stesso qui?

E renderei il codice di ritorno uint - e se ci fossero dei controlli durante la conversione di valori firmati e non firmati?

Non ho ancora avuto l'opportunità di sperimentare manualmente - la CPU è molto sovraccarica... Anche il testo è scritto "con lentezza"...

 
Georgiy Merts:

Dividere per due lo rallenta? Sospetto che le costanti calcolate - devono essere calcolate immediatamente (in questo caso - e lo spostamento nella definizione - deve anche essere sostituito da una costante).

Inoltre - "domanda" - come so, è un operatore abbastanza controverso ...

Sostituire la divisione con lo spostamento non ha alcun effetto. Ho il sospetto che l'espressione risultante sia troppo lunga, quindi il compilatore non l'ha ottimizzata fino alla fine.

Ma ho eseguito i test con Optimize=0, mentre quando l'ottimizzazione era abilitata, tutto è andato bene - la seconda variante era una volta e mezza più veloce. Bingo!

Se l'ottimizzazione è disabilitata, allora la seconda opzione è leggermente più lenta a valori piccoli, ma leggermente più veloce a valori più grandi. In breve, la seconda opzione è decisamente migliore.

 
Alexey Navoykov:

Questa è la variante che mi è venuta in mente:

Questa è presumibilmente la più veloce di tutte le varianti possibili. Tutti i calcoli sono eseguiti con costanti, quindi sono calcolati durante la compilazione. Quindi, tutto è ridotto a soli 6 confronti consecutivi e niente di più. Tuttavia, questa variante funziona più lentamente della precedente. Non riesco a capirne la ragione.

Proprio così: la tua variante è la più veloce.

È solo che il test è inattivo. I programmatori molto spesso dimenticano una cosa importante quando testano le prestazioni: se un valore calcolato non è usato da nessuna parte, il compilatore semplicemente non eseguirà il calcolo.

Ha senso, che senso ha? È come nella sovrapposizione quantistica. Perché la luna dovrebbe esistere se nessuno la guarda? "La luna esiste solo perché un topo la sta guardando?" (Albert Einstein). :))

Quindi questa versione del test con il calcolo del checksum e la stampa sarebbe più corretta:

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

Risultato:

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 il secondo posto è ancora _FastLog2, non log2 :))
 
Nikolai Semko:

È solo un test a vuoto. Un punto importante è spesso dimenticato nei test di performance: se il valore calcolato non è usato da nessuna parte, il compilatore semplicemente non esegue il calcolo.

Ha senso, che senso ha? È come nella sovrapposizione quantistica. Perché la luna dovrebbe esistere se nessuno la guarda? "La luna esiste solo perché un topo la sta guardando?" (Albert Einstein). :))

Quindi questa versione del test con il calcolo del checksum e la stampa sarebbe più corretta:

Il tuo codice è ingarbugliato. Le variabili usate nella definizione si trovano all'altra estremità del codice del programma - non è conveniente ordinare in un tale caos. Ma non è questo il punto. Il punto è che i risultati dei tuoi test non possono essere considerati affidabili perché il compilatore conosce in anticipo l'algoritmo dei valori passati nella funzione. Quindi ottimizza i tuoi test. Dovresti calcolare su numeri casuali .

A proposito, perché hai srand nel tuo codice? Quando l'ho visto, all'inizio ho pensato che stessi usando random, ma in realtà non è così.

Ecco il mio codice:

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:

Il tuo codice è confuso. Le variabili usate nella definizione si trovano all'altra estremità del codice del programma - è scomodo ordinare in un tale caos. Ma questo non è il punto, il punto è che i risultati dei tuoi test non possono essere considerati affidabili, perché il compilatore conosce in anticipo l'algoritmo dei valori passati nella funzione. Pertanto ottimizza i tuoi test. Dovresti calcolare su numeri casuali .

A proposito, perché hai srand nel tuo codice? Quando l'ho visto, all'inizio ho pensato che stessi usando random, ma in realtà non è così.

Ecco il mio codice:

il codice non è mio. L'ho appena modificato e ho rimosso rand per controllare le stesse checksum e rimuovere la funzione rand relativamente costosa dal ciclo, ma ho semplicemente dimenticato di rimuovere srand.

Restituisco rand. Hai ragione - il compilatore ottimizza il ciclo per la somma dei logaritmi da valori consecutivi. Sono sorpreso, però. Non capisco come faccia a farlo. Forse c'è qualcosa che non stiamo prendendo in considerazione.

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

Risultato:

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
  

Il vincitore attuale è _FastLog2

 
Nikolai Semko:

Risultato:

Vincitore attuale _FastLog2

Mi chiedo come hai ottenuto lo stesso checksum ovunque, se i valori sono casuali.

 
Alexey Navoykov:

Mi chiedo come si possa ottenere lo stesso checksum ovunque, se i valori sono casuali.

srand(45) per tutte le funzioni

Ho fatto così all'inizio, ma ho ottenuto checksum diversi, perché non ho tenuto conto che rand()*rand() può essere 0, il che rompe il checksum. Ora ne ho aggiunto uno per allontanarmi dallo zero.

 
Nikolai Semko:

srand(45) per tutte le funzioni

Ho appena fatto lo stesso all'inizio, ma ho ottenuto checksum diversi, perché non ho tenuto conto che rand()*rand() può essere 0, il che rompe il checksum. Ora ne ho aggiunto uno per allontanarmi dallo zero.

E perché avete bisogno dello stesso checksum se stiamo parlando specificamente di misure di velocità? Lo scopo della somma in questo caso è semplicemente quello di evitare che il compilatore tagli il codice, tutto qui. E facendo srand(45), permettete di nuovo di ottimizzare il test.

A proposito, parlando di zero, FastLog2 non controlla lo zero, il che gli dà un vantaggio. Ma è ancora da una volta e mezza a due volte più lento di log2 se testato correttamente).

 
Alexey Navoykov:
E perché avete bisogno dello stesso checksum se stiamo parlando specificamente di misure di velocità? Lo scopo della somma in questo caso è semplicemente quello di evitare che il compilatore tagli il codice, tutto qui. E fare srand(45), di nuovo, vi permette di ottimizzare il test.

Qui stai sopravvalutando le capacità del compilatore. Rimuovi srand(45) - le checksum saranno diverse, ma il risultato della velocità rimane lo stesso.

Inoltre, sono stato guidato dal fatto che i calcoli erano gli stessi per la purezza dell'esperimento, perché non sono entrato nei dettagli di tutte le funzioni. A volte il valore di un parametro di una funzione può influenzare il tempo della sua esecuzione.

Una ragione in più per controllare la correttezza degli algoritmi.

1...110111112113114115116117118119120121122123124...247
Nuovo commento
Motivazione: