Mikrooptimierung: String-Suche in großen Texten

[Schrompf]

Ich hab für die Arbeit ein Tool geschrieben, was große XML-Files durcharbeitet, pro relevantem XML-Element das Ende bestimmt und in den Schnipseln dann anhand von Textfragmenten entscheidet, ob die Schnipsel aufbewahrt oder verworfen werden sollen. Die String-Operationen sind dann auch der Flaschenhals, wenn nicht gerade der Festplattendurchsatz den ganzen Vorgang auf Entengewatschel runterbremst. Aber da das Arbeiten direkt aus einem ZIP-Archiv noch buggy ist, muss der zu durchsuchende Datensatz eh vorher ausgepackt werden. Und ab dann ist der im OS-Filecache und die Platte spielt keine Rolle mehr.

Ich habe irgendwann nebenbei festgestellt, dass die String-Operationen ganz schön suboptimal implementiert sind. Das hat meinen Ehrgeiz geweckt und ich bin los, ob ich das nicht besser hinkriege. Im Gegensatz zu den Standardlib-Funktionen habe ich ein paar Garantien, die es mir erleichtern: keine Null-Terminierung, immer volle 4kb-Seiten allokiert dank mmap. Der Test-Datensatz ist 17.145MB groß. Zwei Operationen waren zeitkritisch: "Finde Character in String" (kurz strchr()) und "Finde String in String" (kurz strstr()).

Baseline: string_view::find()
real 0m21,547s --> ~800MB/s

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
    return mem.find(c, startPosition);
}
inline size_t memFindText(std::string_view mem, size_t startPosition, std::string_view txt)
{
    return mem.find(txt, startPosition);
}

*********** string_view::find(char) ******************
--> type_traits::find(char) --> memchr_sse2()

************ string_view::find(str) *******************
template<...> size_type basic_string_view::find(const _CharT* __str, size_type __pos, size_type __n) const noexcept
{
	for (; __pos <= this->_M_len - __n; ++__pos)
		if (traits_type::eq(_M_str_[__pos], __str[0]) && traits_type::compare(_M_str + __pos + 1, __str + 1, __n - 1) == 0)
			return __pos;
}

Den Code hab ich um das ganze Template-Gewitter und diversen Verwaltungsoverhead reduziert. Man sieht, dass string_view::find(string) geradezu lächerlich schlicht implementiert ist. Ist wahrscheinlich noch zu jung. traits_type::eq() und Konsorten verstehe ich, sowas musst Du machen, wenn Du übermäßig generisch programmierst. Aber warum wird nicht traits_type::find() verwendet? Das mappt immerhin für <char> auf memchr() und ist wenigstens ein bisschen optimiert. Tsss. Nuja, dann ist aber der erste Optimierungsschritt sehr naheliegend: Plain C!

strchr() + memcmp()
real 0m11,014s --> ~1560MB/s

Guck an, fast verdoppelt. Warum nicht gleich so? Ich habe strchr() benutzt (memchar() hatte keinen messbaren Vorteil) und strstr() damit implementiert. Code sieht dann so aus:

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
    auto txt = strchr(mem.data() + startPosition, c);
    return txt ? size_t(txt) - size_t(mem.data()) : SIZE_MAX;
}

inline size_t memFindText(std::string_view mem, size_t startPosition, std::string_view txt)
{
    size_t pos = startPosition;
    size_t endPosition = mem.size() - txt.size() + 1;
    while (true) {
        pos = memFindChar(mem, pos, txt[0]);
        if (pos >= endPosition) {
            return SIZE_MAX;
        }
        if (memcmp(mem.data() + pos, txt.data(), txt.size()) == 0) {
            return pos;
        }
        ++pos;
    }
}

Dann wollte ich mal mein Bitgeschubse ausm Voxelprojekt ausprobieren. Und sehr zu meiner Verwunderung:

strchr64() unaligned + memcmp()
real 0m8,751s --> 1960MB/s

...gab das nochmal ein Viertel Performance-Schub. Warum bereits das Ding strchr() outperformed, weiß ich nicht.

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
    const char* readPtr = mem.data() + startPosition;
    const char* endPtr = mem.data() + mem.size();
    uint64_t needleMask = ~(uint64_t(uint8_t(c)) * 0x0101010101010101);
    do {
        uint64_t blob = *((const uint64_t*) readPtr);
        blob = blob ^ needleMask;
        blob = blob & ((blob & 0x7f7f7f7f7f7f7f7f) + 0x0101010101010101);
        blob = blob & 0x8080808080808080;
        if (blob) {
            return size_t(readPtr) - size_t(mem.data()) + _mm_tzcnt_64(blob) / 8;
        }
        readPtr += 8;
    } while (readPtr < endPtr);

    return SIZE_MAX;
}

Der Code liest jeweils 8 Byte unaligned und imitiert mit ein bisschen Bitgeschubse 8x CompareEqual. Aber unaligned ist doch angeblich so schlimm für die Performance? Das Internet (z.B. StackOverflow) ist voll von diesen Weisheiten. Also probieren wir es aus:

strchr64() aligned + memcmp()
real 0m10,536s -> 1630MB/s

Verdammt, ich hatte mehr erhofft. Anscheinend macht Aligned/Unaligned keinen Unterschied, aber die zusätzlichen Rechenschritte machen sich bemerkbar. Zumindest in meinem UseCase, wo der nächste PartialHit bestenfalls zweistellige Bytes entfernt ist.

strchr64() unaligned + std::boyer_moore_searcher{}
real 0m7,461s -> 2300MB/s

Nun war #c++ im IRC der Überzeugung, dass State Of The Art-Algorithmen mehr können. Da gibt's zum Einen den KMP und zum Anderen den Boyer-Moore. BoyerMoore gibt's ab C++17 sogar in der STL.

Das Ergebnis gibt ihnen Recht: für große Suchen lohnt sich das. Ich arbeite ja auf XML - wenn man da den Schnipsel "</SomeTag>" sucht, dann matcht der Erstes-Zeichen-Suchen-Algo quasi aller paar Dutzend Bytes. BoyerMoore prüft das Suchmuster von hinten und matcht damit andere XML-Schnipsel nur aus Versehen, wenn sie die selbe Länge haben. Außerdem berechnet er ne kleine Tabelle (in nem std::vector) vornweg, in der er sich merkt, wieviel weiter er bei nem PartialMatch rücken kann. Beides zusammen kann sich sehen lassen.

Code: Alles auswählen

template<...>
pair boyer_moore_searcher<...>::operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const
{
	auto __patlen = _M_pat_end - _M_pat;
	const auto& __pred = this->_M_pred();
	__diff_type __i = __patlen - 1;
	auto __stringlen = __last - __first;
	while (__i < __stringlen)
	{
		__diff_type __j = __patlen - 1;
		while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
		{
			--__i;
		    --__j;
		}
		if (__j < 0)
		{
			const auto __match = __first + __i + 1;
		    return std::make_pair(__match, __match + __patlen);
		}
		__i += std::max(_M_bad_char_shift(__first[__i]),_M_good_suffix[__j]);
	}
    return std::make_pair(__last, __last);
}

strchr128() intrinsic + memcmp()
real 0m7,859s -> 2180MB/s
Ich habe beim Hin und Her den BoyerMoore wieder rausgeworfen - keine Ahnung, warum. Dafür bin ich in das güldene Gebiet der x86 Intrinsics abgetaucht. Und das Ergebnis ist nicht übel. Es holt quasi im memchr() raus, was der BoyerMoore im strstr() geschafft hatte.

mein erster Code sah so aus: Wieder unaligned. Ich habe später noch ne aligned Version geschrieben, aber die hat auf meinem ThreadRipper keinen Deut besser performt. Soll wohl auf älteren Rechnern einen messbaren Unterschied machen, wenn man dem Internet glauben darf. Aber es kann auch gut sein, dass das Internet hier einfach 20 Jahre alte Geschichten als ewige Weisheit wiederkäut und es einfach niemand mehr nachgeprüft hat.

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
    const char* readPtr = mem.data() + startPosition;
    const char* endPtr = mem.data() + mem.size();
    auto charMask = _mm_set1_epi8(c);

    do {
        auto blob = _mm_lddqu_si128((const __m128i*) readPtr);
        auto byteEqualityMask = _mm_cmpeq_epi8(blob, charMask);
        auto equalityBits = _mm_movemask_epi8(byteEqualityMask);
        if (equalityBits) {
            return size_t(readPtr) - size_t(mem.data()) + __builtin_ctz(equalityBits);
        }
        readPtr += 16;
    } while (readPtr < endPtr);

    return SIZE_MAX;
}

_mm_lddqu_si128() lädt 16Byte unaligned. _mm_cmpeq_epi8() vergleicht diese 16Byte byte-weise mit unserer CharMask und ergibt eine Byte-Maske von Ergebnissen. Also:

Code: Alles auswählen

Gesucht:  'f'
CharMask: "ffffffffffffffff"
Speicher: "fluffquifflboeff"
Ergebnis: "x00xx000xx0000xx"

_mm_movemask_epi8() extrahiert dann jeweils das oberste Bit jedes Bytes in einen uint16_t, gegen den wir bequem vergleichen können.

Was mit 16Byte auf einmal schon fix ist, das ist mit 32Byte auf einmal wohl noch fixer, oder? ODER?

strchr256() intrinsic aligned + memcmp()
real 0m9,937s -> 1720MB/s

Ne, ist sogar langsamer. Was zur Hecke? Ist das das berühmte AVX-Runtertakten? Gab's das nicht nur auf Intel und für AVX512? Ich weiß es nicht. Es war jedenfalls reproduzierbar, ich hab mehrfach hin- und hergecheckt.

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
	const char* readPtr = mem.data() + startPosition;
    auto endPtr = (size_t) mem.data() + mem.size();
    auto alignedReadPtr = (const __m256i*) (((size_t) readPtr) & ~0x1f);
    auto charMask = _mm256_set1_epi8(c);
    uint8_t misbits = ((size_t) readPtr) & 0x1f;
    uint32_t mismask = ~0u << misbits;

    auto firstChunk = _mm256_load_si256(alignedReadPtr);
    auto bytemask = _mm256_cmpeq_epi8(firstChunk, charMask);
    auto bitmask = _mm256_movemask_epi8(bytemask) & mismask;

    while (!bitmask && (size_t) ++alignedReadPtr < endPtr) {
    	auto chunk = _mm256_load_si256(alignedReadPtr);
    	bytemask = _mm256_cmpeq_epi8(chunk, charMask);
    	bitmask = _mm256_movemask_epi8(bytemask);
    }

    auto resultPos = (size_t) alignedReadPtr - (size_t) mem.data() + __builtin_ctz(bitmask);
    return resultPos >= mem.size() ? SIZE_MAX : resultPos;
}

Aber da gibt's mit SSE4.2 doch auch so geile String-Intrinsics? Schauen wir mal an, was die leisten.

strchr128() intrinsic + strstr128() intrinsic
real 0m3,131s -> 5480MB/s

WOOAAAAAH. Jetzt sind wir sprechend! Der Code dazu sieht so aus:

Code: Alles auswählen

size_t memFindText(std::string_view mem, size_t startPosition, std::string_view txt)
{
    const char* readPtr = mem.data() + startPosition;
    const char* endPtr = mem.data() + mem.size() - txt.size() + 1;

    auto needleBytes = _mm_loadu_si128((const __m128i*) txt.data());
    auto needleLength = std::min(size_t{16}, txt.size());

    while (readPtr < endPtr) {
        auto chunk = _mm_loadu_si128((const __m128i*)readPtr);
        auto index = _mm_cmpestri(needleBytes, needleLength, chunk, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);
        if (index < 16) {
            if (memcmp(readPtr + index, txt.data(), txt.size()) == 0) {
                return (size_t)readPtr - (size_t)mem.data() + index;
            }
            readPtr += index + 1;
        } else {
            readPtr += 16;
        }
    }

    return SIZE_MAX;
}

Die Magie daran ist eigentlich, das viele - aber nicht alle - ErstesZeichen-Treffer sofort von den nachfolgenden Zeichen invalidiert werden. Dadurch kann der Algorithmus, wenn er z.B. "</SomeTag>" sucht, über die meisten sonstigen schließenden XMl-Elemente drüberblasen, ohne anzuhalten. Teilweise Treffer am Ende eines 16Byte-Chunks müssen aber weiterhin manuell geprüft werden. Beispiel:

Code: Alles auswählen

Gesucht:   "</SomeTag>"
Heuhaufen: "8237</Foo> </Som"
Ergebnis:  "0000000000010000"

Da sieht man auch schön, dass des immer noch Fehl-Matches gibt, wenn zufällig das erste Zeichen passt und das genau am Ende eines 16Byte-Chunks liegt. Da geht noch was! Aber erstmal habe ich aus Gründen nochmal den AVX256-memchr() ausprobiert:

strchr256() intrinsic + strstr128() intrinsic
real 0m3,096s -> 5530MB/s

Minimal schneller, im Gegensatz zum obigen Ergebnis, das ja deutlich langsamer war. Weiß die Hecke warum.

strchr256() intrinsic + 4x128bit strstr() intrinsic
real 0m2,978s -> 5750MB/s

Nochmal minimal schneller. Durchsucht 3x 16Byte auf einmal. Um die Partial Matches am Ende eines Chunks zu reduzieren, werden die auf 4x 12Byte ausgebreitet, und die obersten 4 Byte überlappen mit dem nächsten Stück. Dadurch können die String-Vergleiche alle Treffer jenseits der 12. Stelle ignorieren und ballern über die meisten Problemstellen ungebremst hinweg.

Diese Version ist aber ganz schön ungemütlich zu lesen und ist nicht soo viel schneller. Außerdem liest sie unaligned bis zu 48 Byte über das Ende des Suchstrings hinaus. Das sind Bereiche, die selbst Linux mmap() nicht mehr immer wegsteckt, weswegen für den Produktiveinsatz noch eine Sonderbehandlung für die letzten Bytes notwendig wäre. Code sieht so aus:

Code: Alles auswählen

inline size_t memFindText(std::string_view mem, size_t startPosition, std::string_view txt)
{
    static constexpr short MaxFoundIndex = 13; // one past highest position at which the needle can be found
    auto MaxFoundIndexVector = _mm_set1_pi16(MaxFoundIndex); // blown up to x4

    const char* readPtr = mem.data() + startPosition;
    const char* endPtr = mem.data() + mem.size() - txt.size() + 1;

    auto needleBytes = _mm_loadu_si128((const __m128i*) txt.data());
    auto needleLength = std::min(size_t{16}, txt.size());
    auto chunk0 = _mm_loadu_si128((const __m128i*)readPtr);

    while (readPtr < endPtr) {
        auto chunk1 = _mm_loadu_si128((const __m128i*)(readPtr + 16));
        auto chunk2 = _mm_loadu_si128((const __m128i*)(readPtr + 32));
        auto chunk3 = _mm_loadu_si128((const __m128i*)(readPtr + 48));

        // spread out 3x16 byte into 4x12 byte with upper 4 bytes overlapping
        auto chunk00 = chunk0;                              // C0³ C0² C0¹ C0⁰
        auto chunk01 = _mm_alignr_epi8(chunk1, chunk0, 12); // C1² C1¹ C1⁰ C0³
        auto chunk12 = _mm_alignr_epi8(chunk2, chunk1, 8);  // C2¹ C2⁰ C1³ C1²
        auto chunk23 = _mm_alignr_epi8(chunk3, chunk2, 4);  // C3⁰ C2³ C2² C2¹

        auto index0 = _mm_cmpestri(needleBytes, needleLength, chunk00, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);
        auto index1 = _mm_cmpestri(needleBytes, needleLength, chunk01, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);
        auto index2 = _mm_cmpestri(needleBytes, needleLength, chunk12, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);
        auto index3 = _mm_cmpestri(needleBytes, needleLength, chunk23, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);

        auto indexVector = _mm_set_pi16(index3, index2, index1, index0);
        auto compareResult = _mm_cmpgt_pi16(MaxFoundIndexVector, indexVector);
        auto compareMask = _mm_movemask_pi8(compareResult); // there's no _pi16 version, so we make do
        if (compareMask) {
            size_t foundChunkIndex = __builtin_ctz(compareMask) / 2;
            size_t foundChunkPos = ((_mm_cvtm64_si64(indexVector) >> (foundChunkIndex * 16)) & 0xffff);
            size_t foundOffset = foundChunkIndex * 12 + foundChunkPos;
            if (memcmp(readPtr + foundOffset, txt.data(), txt.size()) == 0) {
                return (size_t)readPtr - (size_t)mem.data() + foundOffset;
            }

            // we start searching one past the mismatch, so we need to reinit the first chunk
            readPtr += foundOffset + 1;
            chunk0 = _mm_loadu_si128((const __m128i*)readPtr);
        } else {
            readPtr += 48;
            chunk0 = chunk3;
        }
    }

    return SIZE_MAX;
}

strchr256() intrinsic + strstr128() intrinsic, Parallel
real 0m1,095s  → 15660MB/s

Zum Optimieren hatte ich die ganze Zeit die Parallelisierung abgeschaltet. Jetzt habe ich sie mal wieder angeschaltet und bin das erste Mal der theoretischen Hardware-Leistung überhaupt nahe gekommen. Eigentlich traurig, oder? Das Tool schreibt am Ende die extrahierten Schnipsel auf die Platte, was im Profiler immer so mit 300ms Dauer angezeigt wurde. Theoretisch sind wir damit jetzt also im Bereich von 25GB/s, was grob der Speicherbandbreite meines ThreadRippers entspricht.

Und welche Schlüsse ziehe ich daraus?
[*]Nicht immer nur dem Compiler und der Standardlib vertrauen
[*]Wir sind ganz schön weit weg vom Ideal.
[*]Intrinsics machen Spaß.

[scheichs]

Danke. Schöner Beitrag!

[Krishty]

Geil, danke!

Der Code liest jeweils 8 Byte unaligned und imitiert mit ein bisschen Bitgeschubse 8x CompareEqual. Aber unaligned ist doch angeblich so schlimm für die Performance? Das Internet (z.B. StackOverflow) ist voll von diesen Weisheiten.
[…]
Ich habe später noch ne aligned Version geschrieben, aber die hat auf meinem ThreadRipper keinen Deut besser performt. Soll wohl auf älteren Rechnern einen messbaren Unterschied machen, wenn man dem Internet glauben darf. Aber es kann auch gut sein, dass das Internet hier einfach 20 Jahre alte Geschichten als ewige Weisheit wiederkäut und es einfach niemand mehr nachgeprüft hat.

This. Ich glaube, als ich erfahren habe, was SSE ist, waren Loads unaligned schon genau so schnell wie aligned. (Bedenk aber, dass die Befehle üblicherweise minimal mehr Bytes belegen.)

Ne, ist sogar langsamer. Was zur Hecke? Ist das das berühmte AVX-Runtertakten? Gab's das nicht nur auf Intel und für AVX512? Ich weiß es nicht. Es war jedenfalls reproduzierbar, ich hab mehrfach hin- und hergecheckt.

Doch, nur auf Intel mit AVX512. Zwei naheliegende Vermutungen:

1. AMD-CPUs haben gar keine 256-Bit-Register, sondern führen diese Befehle auf zwei 128-Bit-Registern durch. Das Scheduling könnte davon beeinträchtigt werden. Nachtrag: Ich glaube, dass 2019 oder 2020 echte 256-bittige Register eingeführt wurden; das dürfte von der genauen Version deiner AMD-CPU abhängen …

2. Aufgrund von 1. emittiert jetzt jeder Schleifendurchlauf doppelt so viele µOps wie vorher. Vielleicht passte die Schleife nun nicht mehr in den Cache und die Befehle mussten bei jedem Durchlauf neu dekodiert werden. Agner Fog sagt das Gegenteil:

256-bit vector instructions (AVX instructions) are split into two micro-ops handling 128 bits each. Such instructions take only one entry in the micro-operation cache.

[Schrompf]

Tatsache. Ein bisschen Googeln ergab keine konkreten Aussagen, aber Wikipedia und diverse Reddit-Bewohner sind sich einig, dass AVX256 mit Ryzen3 gekommen wäre, davor war es mit 2x128bit emuliert worden. Und AVX512 wird von quasi niemandem unterstützt. Was sehr schade ist, weil AVX512 ne Menge "Lücken" in den früheren Generationen gefüllt hat. Die Anzahl unterstützter Permutationen ist aber absurd riesig gewesen.

Danke für die Infos! Der ThreadRipper, auf dem ich die Messungen gemacht habe, war von Ende 2019 - ich *dachte*, der wäre aktuell genug. Ich habe sonst nur noch einen Intel im Haus, den Core i7 Mobile in meinem Laptop. Und ich habe ehrlich keinen Bock, den Code auf Windows zu portieren, nur um auf ner Mobile-CPU mit unbekannten Throttling-Mechanismen nochmal alles durchzurechnen.