schneller Weg, um zu überprüfen, ob ein Array von Zeichen Null ist

Question

Ich habe ein Array von Bytes, im Speicher. Was ist der schnellste Weg, um zu sehen, ob alle Bytes im Array Null sind?

Answer 1

Heute kurze SIMD Erweiterungen der Verwendung (wie SSE auf x86-Prozessoren), könnte man genauso gut Iterierte über das Array und vergleichen Sie jeden Wert auf 0

In der fernen Vergangenheit, einen Vergleich durchführen und bedingte Verzweigung für jedes Element im Array (in Zusätzlich zum Schleifenzweig selbst) wäre es teuer gewesen, und je nachdem, wie oft (oder früher) Sie erwarten könnten, dass ein Nicht-Null-Element im Array erscheint, haben Sie möglicherweise ohne Bedingungen in der Schleife gewählt , unter Verwendung von nur bitweise oder keine gesetzten Bits und Aufschieben der tatsächliche Kontrolle bis zu detektieren, nachdem die Schleife vervollständigt:

int sum = 0; 
for (i = 0; i < ARRAY_SIZE; ++i) { 
    sum |= array[i]; 
} 
if (sum != 0) { 
    printf("At least one array element is non-zero\n"); 
} 

jedoch mit dem heutigen Pipeline- superskalare Prozessor-Design komplett mit branch prediction, alle nicht-SSE Ansätze sind virtualy innerhalb einer Schleife nicht unterscheidbar. Wenn es überhaupt möglich ist, jedes Element mit Null zu vergleichen und früh aus der Schleife auszubrechen (sobald das erste Nicht-Null-Element gefunden wird), könnte es langfristig effizienter sein als der sum |= array[i] Ansatz (der immer das gesamte Array durchläuft) Es sei denn, Sie erwarten, dass Ihr Array fast immer ausschließlich aus Nullen besteht (in diesem Fall könnte der sum |= array[i] Ansatz mit GCCs -funroll-loops Ihnen wirklich die besten Werte geben - siehe die unten stehenden Zahlen für einen Athlon Prozessor, Ergebnisse mit Prozessor Modell und Hersteller variieren.)

#include <stdio.h> 

int a[1024*1024]; 

/* Methods 1 & 2 are equivalent on x86 */ 

int main() { 
    int i, j, n; 

# if defined METHOD3 
    int x; 
# endif 

    for (i = 0; i < 100; ++i) { 
# if defined METHOD3 
    x = 0; 
# endif 
    for (j = 0, n = 0; j < sizeof(a)/sizeof(a[0]); ++j) { 
#  if defined METHOD1 
     if (a[j] != 0) { n = 1; } 
#  elif defined METHOD2 
     n |= (a[j] != 0); 
#  elif defined METHOD3 
     x |= a[j]; 
#  endif 
    } 
# if defined METHOD3 
    n = (x != 0); 
# endif 

    printf("%d\n", n); 
    } 
} 

$ uname -mp 
i686 athlon 
$ gcc -g -O3 -DMETHOD1 test.c 
$ time ./a.out 
real 0m0.376s 
user 0m0.373s 
sys  0m0.003s 
$ gcc -g -O3 -DMETHOD2 test.c 
$ time ./a.out 
real 0m0.377s 
user 0m0.372s 
sys  0m0.003s 
$ gcc -g -O3 -DMETHOD3 test.c 
$ time ./a.out 
real 0m0.376s 
user 0m0.373s 
sys  0m0.003s 

$ gcc -g -O3 -DMETHOD1 -funroll-loops test.c 
$ time ./a.out 
real 0m0.351s 
user 0m0.348s 
sys  0m0.003s 
$ gcc -g -O3 -DMETHOD2 -funroll-loops test.c 
$ time ./a.out 
real 0m0.343s 
user 0m0.340s 
sys  0m0.003s 
$ gcc -g -O3 -DMETHOD3 -funroll-loops test.c 
$ time ./a.out 
real 0m0.209s 
user 0m0.206s 
sys  0m0.003s 

Answer 2

Wenn Sie das C in 32-Bit tun wollen, wahrscheinlich nur eine Schleife über das Array als 32-Bit-Integer-Array und vergleichen Sie es mit 0, dann das Zeug am Ende stellen Sie sicher, auch 0.

Answer 3

Wenn das Array von jeder anständige Größe ist, ist Ihr limitierender Faktor auf einer modernen CPU, Zugriff auf das sein Erinnerung.

Stellen Sie sicher, Cache-Prefetching für eine angemessene Entfernung voraus zu verwenden (d. H. 1-2K) mit etwas wie __dcbt oder prefetchnta (oder prefetch0, wenn Sie den Puffer bald wieder verwenden).

Sie möchten auch etwas wie SIMD oder SWAR zu oder mehrere Bytes gleichzeitig tun. Selbst bei 32-Bit-Wörtern sind es viermal weniger Operationen als bei einer Version mit einem Zeichen. Ich würde empfehlen, das oder die zu entrollen und sie in einen "Baum" von oder zu füttern. Sie können sehen, was ich in meinem Codebeispiel meine - dies nutzt die Superskalar-Fähigkeit, um zwei Integer-Ops (die Oder) parallel zu machen, indem Sie Ops verwenden, die nicht so viele Zwischendatenabhängigkeiten haben. Ich benutze eine Baumgröße von 8 (4x4, dann 2x2, dann 1x1), aber Sie können diese auf eine größere Anzahl erweitern, abhängig davon, wie viele freie Register Sie in Ihrer CPU-Architektur haben.

Das folgende Pseudocode-Beispiel für die innere Schleife (kein Prolog/Epilog) verwendet 32-Bit-Ints, aber Sie könnten 64/128-Bit mit MMX/SSE oder was auch immer Ihnen zur Verfügung steht. Dies wird ziemlich schnell sein, wenn Sie den Block vorab in den Cache geladen haben. Möglicherweise müssen Sie auch vorher eine unausgeglichene Überprüfung durchführen, wenn Ihr Puffer nicht 4-Byte-ausgerichtet ist, und danach, wenn Ihr Puffer (nach der Ausrichtung) kein Vielfaches von 32 Byte ist.

const UINT32 *pmem = ***aligned-buffer-pointer***; 

UINT32 a0,a1,a2,a3; 
while(bytesremain >= 32) 
{ 
    // Compare an aligned "line" of 32-bytes 
    a0 = pmem[0] | pmem[1]; 
    a1 = pmem[2] | pmem[3]; 
    a2 = pmem[4] | pmem[5]; 
    a3 = pmem[6] | pmem[7]; 
    a0 |= a1; a2 |= a3; 
    pmem += 8; 
    a0 |= a2; 
    bytesremain -= 32; 
    if(a0 != 0) break; 
} 

if(a0!=0) then ***buffer-is-not-all-zeros*** 

Ich würde eigentlich den Vergleich einer „Linie“ des Wertes in eine einzige Funktion und dann entrollt, dass ein paar Mal mit dem Cache-Prefetching vorschlagen kapseln.

Answer 4

Hier ist eine kurze, schnelle Lösung, wenn Sie Inline-Montage in Ordnung sind.

#include <stdio.h> 

int main(void) { 
    int checkzero(char *string, int length); 
    char str1[] = "wow this is not zero!"; 
    char str2[] = {0, 0, 0, 0, 0, 0, 0, 0}; 
    printf("%d\n", checkzero(str1, sizeof(str1))); 
    printf("%d\n", checkzero(str2, sizeof(str2))); 
} 

int checkzero(char *string, int length) { 
    int is_zero; 
    __asm__ (
     "cld\n" 
     "xorb %%al, %%al\n" 
     "repz scasb\n" 
     : "=c" (is_zero) 
     : "c" (length), "D" (string) 
     : "eax", "cc" 
    ); 
    return !is_zero; 
} 

Falls Sie mit Montage nicht vertraut sind, werde ich erklären, was wir hier tun: Wir speichern die Länge der Zeichenfolge in einem Register, und fragen Sie den Prozessor die Zeichenfolge für eine Null zu scannen (wir angeben dies wird durch Setzen der unteren 8 Bits des Akkumulators, nämlich %%al, auf Null gesetzt, wobei der Wert des Registers bei jeder Iteration reduziert wird, bis ein Nicht-Null-Byte angetroffen wird. Wenn nun die Zeichenkette nur aus Nullen bestand, ist das Register ebenfalls Null, da es Male dekrementiert wurde. Wenn jedoch ein Wert ungleich Null aufgetreten ist, wird die "Schleife", die auf Nullen überprüft hat, vorzeitig beendet, und daher wird das Register nicht Null sein. Wir erhalten dann den Wert dieses Registers und geben seine boolesche Negation zurück.

Profiling dies ergab die folgenden Ergebnisse:

$ time or.exe 

real 0m37.274s 
user 0m0.015s 
sys  0m0.000s 


$ time scasb.exe 

real 0m15.951s 
user 0m0.000s 
sys  0m0.046s 

(Beiden Testfälle liefen 100000 mal auf Arrays der Größe 100000. Der or.exe Code stammt aus Vlads Antwort Funktionsaufrufe in beiden Fällen wurden eliminiert..)

Answer 5

Teilen Sie die überprüfte Speicherhälfte und vergleichen Sie den ersten Teil mit dem zweiten.
a. Wenn irgendein Unterschied, kann es nicht alle gleich sein.
b. Wenn kein Unterschied für die erste Hälfte wiederholen.

Worst Case 2 * N. Memory-effizient und Memcmp basiert.
Nicht sicher, ob es im wirklichen Leben verwendet werden sollte, aber ich mochte die Selbstvergleichsidee.
Es funktioniert für ungerade Länge. Siehst du warum?

:-)

bool memcheck(char* p, char chr, size_t size) { 
    // Check if first char differs from expected. 
    if (*p != chr) 
     return false; 
    int near_half, far_half; 
    while (size > 1) { 
     near_half = size/2; 
     far_half = size-near_half; 
     if (memcmp(p, p+far_half, near_half)) 
      return false; 
     size = far_half; 
    } 
    return true; 
} 

Answer 6

Gemessene zwei Implementierungen auf ARM64, einen eine Schleife mit früher Rückkehr auf falsche Verwendung, eine, die RUP alle Bytes:

int is_empty1(unsigned char * buf, int size) 
{ 
    int i; 
    for(i = 0; i < size; i++) { 
     if(buf[i] != 0) return 0; 
    } 
    return 1; 
} 

int is_empty2(unsigned char * buf, int size) 
{ 
    int sum = 0; 
    for(int i = 0; i < size; i++) { 
     sum |= buf[i]; 
    } 
    return sum == 0; 
} 

Ergebnisse:

Alle Ergebnisse, in Mikrosekunden:

 is_empty1 is_empty2 
MEDIAN 0.350  3.554 
AVG  1.636  3.768 

nur falsche ergebnisse:

 is_empty1 is_empty2 
MEDIAN 0.003  3.560 
AVG  0.382  3.777 

einzig wahre Ergebnisse:

 is_empty1 is_empty2 
MEDIAN 3.649  3,528 
AVG  3.857  3.751 

Zusammenfassung: nur für Datensätze, wo die Wahrscheinlichkeit von falschen Ergebnissen sehr klein ist, der zweite Algorithmus ORing mit besseren Ergebnissen führt, aufgrund des weggelassen Zweig. Ansonsten ist die frühzeitige Rückkehr eindeutig die Outperforming-Strategie.

Answer 7

Rusty Russels memeqzero ist sehr schnell.Es verwendet memcmp, um das schwere Anheben durchzuführen: https://github.com/rustyrussell/ccan/blob/master/ccan/mem/mem.c#L92.