Perché CharInSet è più veloce dell'istruzione Case?

Question

Sono perplesso. Oggi a CodeRage, Marco Cantu ha affermato che CharInSet era lento e che avrei dovuto provare invece un'istruzione Case. L'ho fatto nel mio parser e poi ho verificato con AQTime quale fosse lo speedup. Ho trovato l'istruzione Case molto più lenta.

4.894.539 esecuzioni di:

  

pur non essendo CharInSet (P ^, ['', # 10, # 13, # 0]) do inc (P);

è stato cronometrato a 0,25 secondi.

Ma lo stesso numero di esecuzioni di:

  

mentre True fa
  & nbsp; & nbsp; caso P ^ di
  & Nbsp; & nbsp; & nbsp; & nbsp;' ', # 10, # 13, # 0: pausa;
  & nbsp; & nbsp; & nbsp; & nbsp; else inc (P);
  & Nbsp; & nbsp; fine;

impiega .16 secondi per " mentre True " ;, .80 secondi per il primo caso e .13 secondi per l'altro caso, per un totale di 1,09 secondi o oltre 4 volte di più.

Il codice assembler per l'istruzione CharInSet è:

  

aggiungi edi, $ 02
  mov edx, $ 0064b290
  movzx eax, [edi]
  chiama CharInSet
  test a1, a1
  jz $ 00649f18 (torna all'istruzione add)

considerando che la logica del caso è semplicemente questa:

  

movzx eax, [edi]
  sotto ascia, $ 01
  jb $ 00649ef0
  sotto ascia, $ 09
  jz $ 00649ef0
  sotto ascia, $ 03
  jz $ 00649ef0
  aggiungi edi, $ 02
  jmp $ 00649ed6 (torna all'istruzione movzx)

La logica del case mi sembra che stia usando un assemblatore molto efficiente, mentre l'istruzione CharInSet deve effettivamente effettuare una chiamata alla funzione CharInSet, che è in SysUtils ed è anche semplice, essendo:

  

funzione CharInSet (C: AnsiChar; const CharSet: TSysCharSet): Boolean;
  iniziare
    Risultato: = C in CharSet;
  fine;

Penso che l'unico motivo per cui questo sia fatto sia perché P ^ in ['', # 10, # 13, # 0] non è più consentito in Delphi 2009, quindi la chiamata esegue la conversione dei tipi per consentirlo.

Tuttavia sono molto sorpreso da questo e ancora non mi fido del mio risultato.

AQTime sta misurando qualcosa di sbagliato, mi sto perdendo qualcosa in questo confronto o CharInSet è davvero una funzione efficiente che vale la pena usare?

---

Conclusione:

Penso che tu l'abbia capito, Barry. Grazie per aver dedicato del tempo e fatto l'esempio dettagliato. Ho testato il tuo codice sul mio computer e ho ottenuto .171, .066 e .052 secondi (suppongo che il mio desktop sia un po 'più veloce del tuo laptop).

Test quel codice in AQTime, dà: 0,79, 1,57 e 1,46 secondi per i tre test. Lì puoi vedere il grande overhead dalla strumentazione. Ma ciò che mi sorprende davvero è che questo sovraccarico cambia l'apparente "migliore" risulta essere la funzione CharInSet che in realtà è la peggiore.

Quindi Marcu è corretto e CharInSet è più lento. Ma inavvertitamente (o forse di proposito) mi hai dato un modo migliore tirando fuori cosa sta facendo CharInSet con il metodo AnsiChar (P ^) in Set. Oltre al vantaggio di velocità minore rispetto al metodo case, è anche meno codice e più comprensibile rispetto all'utilizzo dei casi.

Mi hai anche reso conto della possibilità di un'ottimizzazione errata utilizzando AQTime (e altri profilatori di strumenti). Sapere questo mi aiuterà a prendere Strumenti di analisi del profilo e della memoria per Delphi ed è anche un'altra risposta alla mia domanda Come funziona AQTime? . Ovviamente, AQTime non cambia il codice quando lo strumento, quindi deve usare qualche altra magia per farlo.

Quindi la risposta è che AQTime sta mostrando risultati che portano a conclusioni errate.

---

Seguito: ho lasciato questa domanda con l'accusa " accusa " che i risultati di AQTime potrebbero essere fuorvianti. Ma per essere onesti, dovrei indirizzarti a leggere questa domanda:

È stato utile?

Invia

Soluzione

AQTime è un profiler di strumenti. I profiler degli strumenti spesso non sono adatti per misurare il tempo del codice, in particolare nei microbenchmark come i tuoi, perché il costo della strumentazione spesso supera il costo della cosa misurata. I profilatori di strumenti, d'altro canto, eccellono nella memoria di profilazione e nell'uso di altre risorse.

I profili di campionamento, che controllano periodicamente la posizione della CPU, sono in genere migliori per misurare il tempo del codice.

In ogni caso, ecco un altro microbench che dimostra che un'istruzione case è più veloce di CharInSet . Tuttavia, si noti che il controllo impostato può ancora essere utilizzato con un typecast per eliminare l'avviso di troncamento (in realtà questa è l'unica ragione per cui esiste CharInSet):

{$apptype console}

uses Windows, SysUtils;

const
  SampleString = 'foo bar baz blah de;blah de blah.';

procedure P1;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while not CharInSet(cp^, [#0, ';', '.']) do
    Inc(cp);
end;

procedure P2;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    case cp^ of
      '.', #0, ';':
        Break;
    else
      Inc(cp);
    end;
end;

procedure P3;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while not (AnsiChar(cp^) in [#0, ';', '.']) do
    Inc(cp);
end;

procedure Time(const Title: string; Proc: TProc);
var
  i: Integer;
  start, finish, freq: Int64;
begin
  QueryPerformanceCounter(start);
  for i := 1 to 1000000 do
    Proc;
  QueryPerformanceCounter(finish);
  QueryPerformanceFrequency(freq);
  Writeln(Format('%20s: %.3f seconds', [Title, (finish - start) / freq]));
end;

begin
  Time('CharInSet', P1);
  Time('case stmt', P2);
  Time('set test', P3);
end.

L'output sul mio laptop qui è:

CharInSet: 0.261 seconds
case stmt: 0.077 seconds
 set test: 0.060 seconds

Answer 1

AQTime è un profiler di strumenti. I profiler degli strumenti spesso non sono adatti per misurare il tempo del codice, in particolare nei microbenchmark come i tuoi, perché il costo della strumentazione spesso supera il costo della cosa misurata. I profilatori di strumenti, d'altro canto, eccellono nella memoria di profilazione e nell'uso di altre risorse.

I profili di campionamento, che controllano periodicamente la posizione della CPU, sono in genere migliori per misurare il tempo del codice.

In ogni caso, ecco un altro microbench che dimostra che un'istruzione case è più veloce di CharInSet . Tuttavia, si noti che il controllo impostato può ancora essere utilizzato con un typecast per eliminare l'avviso di troncamento (in realtà questa è l'unica ragione per cui esiste CharInSet):

{$apptype console}

uses Windows, SysUtils;

const
  SampleString = 'foo bar baz blah de;blah de blah.';

procedure P1;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while not CharInSet(cp^, [#0, ';', '.']) do
    Inc(cp);
end;

procedure P2;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    case cp^ of
      '.', #0, ';':
        Break;
    else
      Inc(cp);
    end;
end;

procedure P3;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while not (AnsiChar(cp^) in [#0, ';', '.']) do
    Inc(cp);
end;

procedure Time(const Title: string; Proc: TProc);
var
  i: Integer;
  start, finish, freq: Int64;
begin
  QueryPerformanceCounter(start);
  for i := 1 to 1000000 do
    Proc;
  QueryPerformanceCounter(finish);
  QueryPerformanceFrequency(freq);
  Writeln(Format('%20s: %.3f seconds', [Title, (finish - start) / freq]));
end;

begin
  Time('CharInSet', P1);
  Time('case stmt', P2);
  Time('set test', P3);
end.

L'output sul mio laptop qui è:

CharInSet: 0.261 seconds
case stmt: 0.077 seconds
 set test: 0.060 seconds

Answer 2

Barry, vorrei sottolineare che il tuo benchmark non riflette le prestazioni effettive dei vari metodi, perché la struttura delle implementazioni differisce. Invece, tutti i metodi dovrebbero usare un " mentre True do " costruire, per riflettere meglio l'impatto dei diversi modi di effettuare un controllo a caratteri.

Qui un sostituto per i metodi di test (P2 è invariato, P1 e P3 ora usano il costrutto "quot" mentre True fa "):

procedure P1;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    if CharInSet(cp^, [#0, ';', '.']) then
      Break
    else
      Inc(cp);
end;

procedure P2;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    case cp^ of
      '.', #0, ';':
        Break;
    else
      Inc(cp);
    end;
end;

procedure P3;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    if AnsiChar(cp^) in [#0, ';', '.'] then
      Break
    else
      Inc(cp);
end;

La mia workstation fornisce:

CharInSet: 0.099 seconds
case stmt: 0.043 seconds
 set test: 0.043 seconds

Che corrisponde meglio ai risultati previsti. Per me, sembra che usare il costrutto "case in" non sia davvero d'aiuto. Mi dispiace Marco!

Answer 3

Un profiler di campionamento gratuito per Delphi è disponibile qui:

https://forums.codegear.com/thread.jspa?messageID=18506

Oltre alla questione della misurazione errata del tempo dei profilatori di strumentazione, va notato che ciò che è più veloce dipenderà anche dalla prevedibilità del "caso". i rami sono. Se i test nel "caso" hanno tutte una probabilità simile di essere incontrato, prestazioni di "caso" può essere inferiore a quello di CharInSet.

Answer 4

Il codice nella funzione " CharInSet " è più veloce di "case", il tempo è dedicato a "call", uso  mentre no (cp ^ in [..]) quindi

vedrai che questo è il digiuno.

Answer 5

Come so, la chiamata richiede la stessa quantità di operazioni del processore come il salto, se utilizzano entrambi puntatori brevi. Con puntatori lunghi possono essere diversi. La chiamata nell'assemblatore non utilizza lo stack per impostazione predefinita. Se c'è abbastanza registro libero usato registrati. Quindi anche le operazioni dello stack richiedono zero tempo. Sono solo i registri ad essere molto veloci.

Nella variante del caso contrario, come vedo, usa le operazioni add e sub che sono piuttosto lente e probabilmente aggiungono la maggior parte degli extratime.