Schnellste Möglichkeit, Massendaten zu überprüfen, wenn sie in C null sind? [duplicate]

Ich habe eine Menge Daten, vielleicht 4 MB. Jetzt wollen wir prüfen, ob alle Bits darin 0 sind.

Beispiel: Hier sind die Daten:

void* data = malloc(4*1024*1024);
memset(data, 0, 4*1024*1024);

Überprüfen Sie, ob alle Bits darin 0 sind. Hier ist meine Lösung, die nicht schnell genug ist:

int dataisnull(char* data, int length)
{
    int i = 0;
    while(i<length){
        if (data[i]) return 0;
        i++;
    }
    return 1;
}

Dieser Code könnte einige Dinge haben, um die Leistung zu verbessern. Beispielsweise kann es bei einem 32/64-Bit-Computer schneller sein, 4/8 Bytes gleichzeitig zu prüfen.

Da frage ich mich, wie geht das am schnellsten?

Sie können mehrere Bytes gleichzeitig verarbeiten und die Schleife entrollen:

int dataisnull(const void *data, size_t length) {
    /* assuming data was returned by malloc, thus is properly aligned */
    size_t i = 0, n = length / sizeof(size_t);
    const size_t *pw = data;
    const unsigned char *pb = data;
    size_t val;
#define UNROLL_FACTOR  8
#if UNROLL_FACTOR == 8
    size_t n1 = n - n % UNROLL_FACTOR;
    for (; i < n1; i += UNROLL_FACTOR) {
        val = pw[i + 0] | pw[i + 1] | pw[i + 2] | pw[i + 3] |
              pw[i + 4] | pw[i + 5] | pw[i + 6] | pw[i + 7];
        if (val)
            return 0;
    }
#endif
    val = 0;
    for (; i < n; i++) {
        val |= pw[i];
    }
    for (i = n * sizeof(size_t); i < length; i++) {
        val |= pb[i];
    }
    return val == 0;
}

Abhängig von Ihrem spezifischen Problem kann es effizienter sein, Werte ungleich Null früh oder spät zu erkennen:

• Wenn der Nullfall am häufigsten vorkommt, sollten Sie alle Bits in berechnen val Akku und erst am Ende testen.
• Wenn der Nullfall selten vorkommt, sollten Sie häufiger nach Nicht-Null-Werten suchen.

Die entrollte Version oben ist ein Kompromiss, der je nach Größe alle 64 oder 128 Bytes auf Nicht-Null-Werte testet size_t.

Abhängig von Ihrem Compiler und Prozessor erzielen Sie möglicherweise eine bessere Leistung, indem Sie weniger oder mehr entrollen. Sie könnten auch intrinsische Funktionen verwenden, die für Ihre spezielle Architektur verfügbar sind, um Vektortypen zu nutzen, aber dies wäre weniger portabel.

Beachten Sie, dass der Code die korrekte Ausrichtung für die nicht überprüft data Zeiger:

• es kann nicht portabel gemacht werden.
• Es wird davon ausgegangen, dass die Daten über zugewiesen wurden malloc oder ähnliches, daher für jeden Typ richtig ausgerichtet.

Vergleichen Sie wie immer verschiedene Lösungen, um zu sehen, ob es einen wirklichen Unterschied macht. Diese Funktion ist möglicherweise überhaupt kein Engpass, das Schreiben einer komplexen Funktion zur Optimierung eines seltenen Falls ist kontraproduktiv, sie macht den Code weniger lesbar, enthält mit größerer Wahrscheinlichkeit Fehler und ist viel weniger wartbar. Beispielsweise kann die Annahme zur Datenausrichtung möglicherweise nicht gelten, wenn Sie das Speicherzuweisungsschema ändern oder wenn Sie statische Arrays verwenden, die Funktion kann dann ein undefiniertes Verhalten hervorrufen.

Im Folgenden wird überprüft, ob das erste Byte Ihren Wünschen entspricht und alle nachfolgenden Bytepaare gleich sind.

int check_bytes(const char * const data, size_t length, const char val)
{
    if(length == 0) return 1;
    if(*data != val) return 0;
    return memcmp(data, data+1, length-1) ? 0 : 1;
}

int check_bytes64(const char * const data, size_t length, const char val)
{
    const char * const aligned64_start = (char *)((((uintptr_t)data) + 63) / 64 * 64);
    const char * const aligned64_end = (char *)((((uintptr_t)data) + length) / 64 * 64);
    const size_t start_length = aligned64_start - data;
    const size_t aligned64_length = aligned64_end - aligned64_start;
    const size_t end_length = length - start_length - aligned64_length;

    if (!check_bytes(data, start_length, val)) return 0;
    if (!check_bytes(aligned64_end, end_length, val)) return 0;

    return memcmp(aligned64_start, aligned64_start + 64, aligned64_length-64) ? 0 : 1;
}

Eine ausgefeiltere Version dieser Funktion sollte wahrscheinlich an Cache-Zeilen ausgerichtete Zeiger übergeben memcmpund überprüfen Sie die verbleibenden Blöcke manuell, anstatt nur das erste Byte.

Natürlich müssen Sie ein Profil auf Ihrer spezifischen Hardware erstellen, um festzustellen, ob diese Methode einen Geschwindigkeitsvorteil gegenüber anderen bietet.

Falls jemand zweifelt, ob das funktioniert, Idee.

Ich habe einmal die folgende Funktion für meinen eigenen Gebrauch geschrieben. Es wird davon ausgegangen, dass die zu prüfenden Daten ein Vielfaches einer konstanten Blockgröße sind und für einen Puffer von Maschinenwörtern richtig ausgerichtet sind. Wenn dies in Ihrem Fall nicht gegeben ist, ist es nicht schwierig, die ersten und letzten paar Bytes einzeln zu loopen und nur die Masse mit der optimierten Funktion zu überprüfen. (Genau genommen ist es ein undefiniertes Verhalten, selbst wenn das Array richtig ausgerichtet ist, die Daten jedoch von einem Typ geschrieben wurden, der nicht kompatibel ist unsigned long. Ich glaube jedoch, dass Sie mit diesem vorsichtigen Regelbruch hier ziemlich weit kommen können.)

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool
is_all_zero_bulk(const void *const p, const size_t n)
{
  typedef unsigned long word_type;
  const size_t word_size = sizeof(word_type);
  const size_t chunksize = 8;
  assert(n % (chunksize * word_size) == 0);
  assert((((uintptr_t) p) & 0x0f) == 0);
  const word_type *const frst = (word_type *) p;
  const word_type *const last = frst + n / word_size;
  for (const word_type * iter = frst; iter != last; iter += chunksize)
    {
      word_type acc = 0;
      // Trust the compiler to unroll this loop at its own discretion.
      for (size_t j = 0; j < chunksize; ++j)
        acc |= iter[j];
      if (acc != 0)
        return false;
    }
  return true;
}

Die Funktion selbst ist nicht sehr schlau. Die wichtigsten Ideen sind:

• Verwenden Sie große vorzeichenlose Maschinenwörter für den Datenvergleich.
• Aktivieren Sie das Abrollen von Schleifen, indem Sie eine innere Schleife mit einer konstanten Iterationsanzahl ausklammern.
• Reduzieren Sie die Anzahl der Verzweigungen, indem Sie die Wörter in einen Akkumulator ODER-verknüpfen und ihn nur alle paar Iterationen mit Null vergleichen.
• Dies sollte es dem Compiler auch leicht machen, vektorisierten Code mit zu generieren SIMD Anweisungen, die Sie wirklich für Code wie diesen wollen.

Zusätzliche nicht standardmäßige Optimierungen wären, die Funktion mit zu kommentieren __attribute__ ((hot)) und verwenden __builtin_expect(acc != 0, false). Das Wichtigste ist natürlich, die Optimierungen Ihres Compilers einzuschalten.