Newlines zählen

fefe hat am 23. Jänner 2015 ein Experiment gepostet, wie man am schnellsten/besten Newlines im Speicher zählt. Der naive Code ist bezüglich der Laufzeit nicht optimal, da jedes Zeichen einzeln behandelt wird. fefe schlägt div. Tricks ('Bitfrickelei') vor die man dann evt. mit SIMD-Befehlen noch weiter beschleunigen kann.

Bei mir liefert der Code folgende Ergebnisse (64-bit, GCC 4.8, -O2 -march=native, Intel i5-2400) auf 160 000 000 zufällig gleichverteilt generierten Zeichen:

Hier versuche ich den Algorithmus einfach zu halten, aber gleich auf SIMD zu setzen. Mit Intrinsics geht das recht einfach... Randbehandlung spare ich mir, korrektes Alignment ist Voraussetzung.

SSE4.1

Verwende einen SSE2-Befehl um immer 16-Bytes auf einmal zu vergleichen (_mm_cmpeq_epi8() bzw. pcmpeqb), das Ergebnis wird maskiert (je Element aus 0xff / 0x00 -> 0x01 / 0x00) und dann mit dem SAD-Befehl (Sum-of-Absolute-Difference, _mm_sad_epu8() bzw. psadbw) aufsummieren. Das Ergebnis sind zwei Summen (jeweils 16 Bit) in einem 128 Bit Register).

size_t byfoot3(const char *s, size_t l) {
  size_t i, r = 0;
  __m128i pattern = _mm_set1_epi8('\n');
  __m128i zero = _mm_setzero_si128();
  __m128i mask = _mm_set1_epi8(1);

  for (i = 0; i < l; i += 16) {
    __m128i res = _mm_cmpeq_epi8(*(__m128i *)&s[i], pattern);
    res = _mm_and_si128(res, mask);
    res = _mm_sad_epu8(res, zero);
    r += _mm_extract_epi64(res, 1); // SSE4.1, could just use a shift
    r += _mm_cvtsi128_si64(res);
  }

  return r;
}

SSE2/POPCNT

Noch einfacher und schneller geht's mit _mm_movemask_epi8() bzw. pmovmskb, gefolgt vom speziellen Befehl popcnt (Population Count, zählt die gesetzten Bits in).

 size_t byfoot4(const char *s, size_t l) {
  size_t i, r = 0;
  __m128i pattern = _mm_set1_epi8('\n');

  for (i = 0; i < l; i += 16) {
    __m128i res = _mm_cmpeq_epi8(*(__m128i *)&s[i], pattern);
    r += __builtin_popcount(_mm_movemask_epi8(res));
  }

  return r;
}

Das Ergebnis auf meinem System; mit AVX könnten prinzipiell 256 Bits statt 128 Bits auf einmal bearbeitet werden... Die verwendeten SIMD-Befehle passen recht gut auf den Anwendungsfall, der Overhead ist gering; vielleicht geht noch etwas mit loop unrolling, etc.

Peter Meerwald, pmeerw@pmeerw.net