[C++ Intrinsics] Was zur Hecker macht hier Clang? Und wie halte ich ihn davon ab?

Programmiersprachen, APIs, Bibliotheken, Open Source Engines, Debugging, Quellcode Fehler und alles was mit praktischer Programmierung zu tun hat.
Antworten
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

[C++ Intrinsics] Was zur Hecker macht hier Clang? Und wie halte ich ihn davon ab?

Beitrag von Schrompf »

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:

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;
}
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?
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++ Intrinsics] Was zur Hecker macht hier Clang? Und wie halte ich ihn davon ab?

Beitrag von Krishty »

Öh lese ich falsch oder fehlt in dem Godbolt-Link die Optimierung (-O2)?

Denn wenn ich die hinzufügte, kollabiert das alles zu einem Dutzend Befehle.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++ Intrinsics] Was zur Hecker macht hier Clang? Und wie halte ich ihn davon ab?

Beitrag von Krishty »

P.S.: Bereits SSE 4.2 brachte eigene Substring-Search-Funktionen. Die dürften mit mmap() einfach und schnell nutzbar sein. Bin leider nie dazu gekommen, sie auszuprobieren, aber falls du neugierig bist: https://www.strchr.com/strcmp_and_strlen_using_sse_4.2

Ich schätze ja, dass limitierend eh die Speicherbandbreite ist, und wenn’s schon nicht schneller ist bekommst du so vielleicht zumindest kompakteren Code.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: [C++ Intrinsics] Was zur Hecker macht hier Clang? Und wie halte ich ihn davon ab?

Beitrag von xq »

Krishty hat geschrieben: 10.05.2020, 23:30 Öh lese ich falsch oder fehlt in dem Godbolt-Link die Optimierung (-O2)?
Dem stimme ich zu. Mit O3, O2, Os wird der Code schön klein
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++ Intrinsics] Was zur Hecker macht hier Clang? Und wie halte ich ihn davon ab?

Beitrag von Schrompf »

Oh haua, das ist ausnehmend doof. Sorry. Ich finde mich erst langsam rein in die Hunderte an Instructions. Ich habe schon Intrinsics für String Processing gesehen, die byteweise irgendwas vergleichen und auch beim Nullbyte passend terminieren. Die Nullbyte-Terminierung kann ich aber ignorieren, weil mmap() ja eh min. 4kb-Pages liefert.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++ Intrinsics] Was zur Hecker macht hier Clang? Und wie halte ich ihn davon ab?

Beitrag von Schrompf »

Der Code mit _mm_movemask_epi8() ist übrigens nochmal deutlich kürzer und hübscher: https://godbolt.org/z/ss-yiK

Auf meinem Arbeitsrechner (AMD Epyc) ist der Code allerdings reproduzierbar 10% langsamer. Wenn ich euch gerade mal an der Leitung habe, kann ich ja gleich mal fragen, ob ihr eine Idee habt, warum das so ist?
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Antworten