[C++ Intrinsics] Was zur Hecker macht hier Clang? Und wie halte ich ihn davon ab?
Verfasst: 10.05.2020, 22:59
Hallo Leute,
Linux/Clang. Ich habe ein kleines Tool für Arbeit geschrieben, dass gigantische XML-Files als Text parsed und Abschnitte daraus erkennt und ausschneidet. Das jeweilige File lade ich mit mmap() und mache einen bequemen string_view darauf auf, mit dem ich alle anderen Arbeitsschritte abbilden kann.
Die Löwenarbeit macht dabei std::string_view::find(), die entweder einen Char oder einen 10 bis 15 Zeichen langen Textschnipsel sucht. Nun habe ich mal profiled und dann mal reindebugged und festgestellt, dass die typische übermäßige Generische Programmierung da halt schlichten, aber ganz schön lahmen Code erzwingt. Der StringView ist halt allgemein für Char-Typen aller Art implementiert, der nimmt dann intern type_traits<char_type>::equal() und Konsorten. Klar, dass das lahm ist.
Das muss besser gehen. Geht es auch, wie sich herausstellt. Schon ein schlichter Umbau auf die alten C-Funktionen strchr() und strstr() ergibt ~30% Zeitgewinn. std::search() mit std::boyes_moore_searcher{} ist bei fast 100%. Noch schneller ist mein eigener Versuch, der "Suche char in Speicherblock" mittels SSE2-Intrinsics abbildet, und "Suche Textschnipsel in Speicherblock" als "Suche erstes Zeichen und memcmp()" implementiert. Mit AVX256 kann man da sicher noch was rausholen, aber das ist ein Ding für später. Ich habe jetzt bereits viel gelernt und werde langsam warm mit Intrinsics.
Womit ich nicht warm werde, ist der katastrophale Asm-Code, den CLang aus meinen Intrinsics generiert:
So sah die Funktion aus, bevor ich _mm_movemask_epi8() kennenlernte. Die Version mit movemask ist zwar kürzer und schöner anzusehen, aber reproduzierbar 10% langsamer. Warum auch immer. Aber schaut euch den Asm-Output an. https://godbolt.org/z/tkVSV8 Schaut ihn euch an! Was soll das? Warum resultiert ein einziger _mm_set1_epi8() in dieser Kakaphonie aus 50 Zeilen Bullshit? Warum kopiert der fröhlich die einzigen beiden beteiligten XMM-Register einmal dahin, einmal dorthin, nur um dazwischen genau die eine ASM-Instruction zu generieren, die ich tatsächlich verlangt habe? WAS SOLL DER SCHEIß?
Und wie halte ich den Compilertrottel davon ab?
Linux/Clang. Ich habe ein kleines Tool für Arbeit geschrieben, dass gigantische XML-Files als Text parsed und Abschnitte daraus erkennt und ausschneidet. Das jeweilige File lade ich mit mmap() und mache einen bequemen string_view darauf auf, mit dem ich alle anderen Arbeitsschritte abbilden kann.
Die Löwenarbeit macht dabei std::string_view::find(), die entweder einen Char oder einen 10 bis 15 Zeichen langen Textschnipsel sucht. Nun habe ich mal profiled und dann mal reindebugged und festgestellt, dass die typische übermäßige Generische Programmierung da halt schlichten, aber ganz schön lahmen Code erzwingt. Der StringView ist halt allgemein für Char-Typen aller Art implementiert, der nimmt dann intern type_traits<char_type>::equal() und Konsorten. Klar, dass das lahm ist.
Das muss besser gehen. Geht es auch, wie sich herausstellt. Schon ein schlichter Umbau auf die alten C-Funktionen strchr() und strstr() ergibt ~30% Zeitgewinn. std::search() mit std::boyes_moore_searcher{} ist bei fast 100%. Noch schneller ist mein eigener Versuch, der "Suche char in Speicherblock" mittels SSE2-Intrinsics abbildet, und "Suche Textschnipsel in Speicherblock" als "Suche erstes Zeichen und memcmp()" implementiert. Mit AVX256 kann man da sicher noch was rausholen, aber das ist ein Ding für später. Ich habe jetzt bereits viel gelernt und werde langsam warm mit Intrinsics.
Womit ich nicht warm werde, ist der katastrophale Asm-Code, den CLang aus meinen Intrinsics generiert:
Code: Alles auswählen
#include <cstdint>
#include <string_view>
#include <x86intrin.h>
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();
__m128i charMask = _mm_set1_epi8(c);
do {
auto blob = _mm_lddqu_si128((const __m128i*) readPtr);
auto byteEqualityMask = _mm_cmpeq_epi8(blob, charMask);
if (!_mm_test_all_zeros(byteEqualityMask, ~__m128i{0})) {
auto low64bits = _mm_extract_epi64(byteEqualityMask, 0);
auto high64bits = _mm_extract_epi64(byteEqualityMask, 1);
size_t offset = high64bits ? _mm_tzcnt_64(high64bits) + 64 : _mm_tzcnt_64(low64bits);
return size_t(readPtr) - size_t(mem.data()) + offset / 8;
}
readPtr += 16;
} while (readPtr < endPtr);
return SIZE_MAX;
}
Und wie halte ich den Compilertrottel davon ab?