Optimalen dynamischen Schleifencode erstellen



  • Der Titel ist nicht gut, mir ist nur grad keine bessere Beschreibung eingefallen...

    Sagen wir, ich habe eine Schleife, die sehr oft ausgeführt wird und in etwa so ausschaut:

    while (iter.valid())
    {
      if (!checkAllFilters(iter))
        continue;
    
      for (const auto& processor: processors)
        processor.process(iter);
    
      executeAllPostProcessors(iter);
    }
    

    Weiß jetzt nicht mehr, wie das genau ausschaut und was da genau passiert. Jedenfalls hat die Schleife eine Kernfunktionalität, das ist meist ein "Processor", also da wird irgendwas ausgeführt. Davor wird aber ständig geprüft, ob das aktuelle Element irgendwelchen Filterkriterien entspricht. Und danach kann es noch irgendwelche zusätzlichen Filter geben, die die Daten anreichern oder so.

    Die eigentliche Verarbeitung kostet die meiste Zeit. Kann aber sein, dass die dann auch sehr schnell läuft, wenn sie genug Daten gecached hat usw., und die ganzen Prüfungen davor und danach dann stärker ins Gewicht fallen. Ob es irgendwelche Filter steht erst zur Laufzeit fest, kann aber vor der Schleife bestimmt werden. D.h., ich würde die Schleife gern vor der Ausführung optimieren.

    Das ganze ist nicht weiter wichtig. Finds nur grad eben interessant und würd gern Ideen sammeln.
    Man könnte einfach mehrere ähnliche Schleifen schreiben und dann die beste ausführen. Ist aber ziemlich plum. Interessanter wärs vielleicht, eine Mini VM zu schreiben und den Bytecode vor der Schleife in Abhängigkeit der Konfiguration zu generieren. Das wäre aber wahrscheinlich teurere, als paar zusätzliche ifs in die Schleife einzubauen und in jedem Durchlauf die Bedingungen zu prüfen. Man könnte auch mit JIT dynamischen Code generieren, aber das ist für den Anwendungsfall viel zu viel des guten. Hat sonst jemand irgendwelche Vorschläge?



  • Mechanics schrieb:

    Man könnte einfach mehrere ähnliche Schleifen schreiben und dann die beste ausführen.

    Mehrere? Halt eine mit und eine ohne Filter, oder? Das fände ich vertretbar. Oder gibts da mehrere orthogonale Filterkategorien?

    Mechanics schrieb:

    Ist aber ziemlich plum. Interessanter wärs vielleicht, eine Mini VM [...] Bytecode [...] JIT [...]

    Wie du schon sagst, ziemlicher Overkill, zumindest ohne Zahlen gesehen zu haben.



  • Nach deiner Beschreibung kann ich mir zwar grad nicht vorstellen dass die "Prozessoren" und die "Filter" ausreichend schnell sind dass sich überhaupt auszahlt da irgendwas zu machen...

    Aber wenn ich davon ausgehe dass schon...

    FilterPtr filters[8] = {}; // Bzw. halt eine passend gewählte Grösse -- eben so dass genügend Aufrufe mit nur den Filtern im Array auskommen
    std::vector<FilterPtr> moreFilters;
    size_t filterCount = ...;
    
    // filters mit den ersten 8 Filtern und moreFilters mit den restlichen Filtern anfüllen
    
    while (iter.valid())
    {
        if (filterCount > 0 && filters[0](iter))
            continue;
        if (filterCount > 1 && filters[1](iter))
            continue;
        ...
        if (filterCount > 7 && filters[7](iter))
            continue;
    
        if (filterCount > 8)
            for (auto filter : moreFilters)
                if (filter(iter))
                    goto outer_continue;
    
        // Das selbe nochmal für die Prozessoren
    
        // Das selbe nochmal für die Post-Prozessoren
    
    outer_continue:
        ;
    }
    

    Bzw. wenn man dem Optimizer so gar nicht vertraut, kann man die if (filterCount > N && filters[N](iter)) natürlich noch in zwei if s aufspalten. Wobei der else Zweig vom if (filterCount > N) dann die ganzen weiteren Filter für N+1 , N+2 etc. überspringt.

    Grund warum das 'was bringen könnte: es ist Branch-Prediction-freundlich.

    ps: Was Bytecode angeht: Bytecode interpretieren ist AFAIK sehr Branch-Prediction-unfreundlich. Ich kenne zumindest keinen Trick es irgendwie so zu implementieren dass die Branch-Prediction nicht dauernd danebenhaut.
    Um Branch-Prediction-freundlichen Code zu bekommen müsste man also wirklich JITen.
    Daher 2. Vorschlag: schreib das in Java, dann JITet die Java-Runtime für dich 🤡
    (Bzw. C# ginge natürlich auch, da kannst du ja auch jederzeit einfach Code generieren, übersetzen lassen und dann als Assembly laden. Dummerweise wird man solche Assemblies in .NET bloss nie mehr los -- zumindest nicht wenn man sie nicht in eine eigene AppDomain einsperrt. Was dann aber auch wieder gröbere Kosten hat, weil man die ganzen Daten rüberserialisieren muss.)



  • Bzw. das selbe nochmal mit switch:

    FilterPtr filters[6] = {};
    std::vector<FilterPtr> moreFilters;
    size_t filterCount = ...;
    
    // filters und moreFilters passend befüllen.
    // Also wenn > 6 Filter, dann kommen die ersten paar nach moreFilters, und die letzten 6 nach filters, und filterCount wird auf 7 gesetzt.
    // Wenn <= 6 alle nach filters.
    // Und filters wird so befüllt dass immer die letzten Einträge belegt sind.
    
    filters = filters & 7; // Damit der Compiler sich das & 7 im switch sparen kann
    while (iter.valid())
    {
        switch (filters & 7)
        {
        case 7:
            for (auto filter : moreFilters)
                if (filter(iter))
                    goto outer_continue;
        case 6:
            if (filters[0](iter))
                continue;
        case 5:
            if (filters[1](iter))
                continue;
        ...
        case 1:
            if (filters[5](iter))
                continue;
        case 0:
        }
    
        ...
    

    Das sind aber echt alles ziemliche Mikrooptimierungen. Und es würde mich nicht wundern wenn sie quasi gar nichts bringen -- oder auf der einen oder anderen Plattform vielleicht sogar schaden.

    Was dagegen wirklich was bringen könnte wäre Inlining. Aber dazu müsstest du dann schon fast dynamisch C++ Code generieren, kompilieren, als DLL/SO laden und dann ausführen. Und vor allem müsstest du damit der Compiler maximal optimieren kann den Source der ganzen Filter/Prozessoren/... vorliegen haben.
    Bzw. es würde statt des Source natürlich auch eine Intermediate-Form reichen. Müsste halt irgendwas sein was der verwendete Compiler fressen kann, und womit er noch Inlining etc. machen kann.



  • Mal daran gedacht, ob man die Filter als template formulieren kann, so dass die verschiedenen Codepfade erzeugt werden?



  • Mechanics schrieb:

    Ob es irgendwelche Filter steht erst zur Laufzeit fest, kann aber vor der Schleife bestimmt werden.

    da sowohl die filter als auch die processors und auch post filter dieselbe signatur zu haben scheinen, koenntest du ein interface definieren, alle filter, processor und post process davon ableiten und dann baust du vor der schleife ein array mit allen verarbeitenden elementen.

    damit reduziert sich deine schlefie auf:

    while (iter.valid())
    {
      for (const auto& processor: processors)
        processor.process(iter);
    }
    

    die virtual calls sind vorhersehbar und daher werden sie vermutlich von der CPU die normale function calls ausgefuehrt.



  • @audacia und rapso: ich weiß grad echt nicht genau, wie der Code ausschaut. Das ist etwas, was ich vor drei Jahren geschrieben habe und demnächst wieder angehen werde. Deswegen habe ich mich gestern abend schon mal ein bisschen darauf eingestimmt, den Code habe ich mir aber nicht mehr angeschaut.
    So wirklich gleiche Signaturen haben die Funktionen sicher nicht, es gibt eben mindestens drei Aufgaben in der Schleife, Filtern, Verarbeiten und Nachbearbeiten. Aber wie das genau ausgeschaut hat, weiß ich jetzt nicht.
    Der Hintergrund von dem ganzen ist mehr oder weniger, dass ziemlich viel Code vereinheitlicht wurde. Gab viele ähnliche Klassen mit vielen Sonderfällen. Jetzt gibts nur noch eine Klasse und keine Sonderfälle mehr, wird alles durch eine der drei Komponenten erschlagen. Das ganze ist aber etwas langsamer, als die alte Variante, weil die Sonderfälle selten sind und "nur Verarbeiten" der Standardfall ist. Jetzt wollen wir das ganze wieder etwas optimieren. Ist nicht nur die Stelle und nicht nur die Schleife, man kann da schon einiges optimieren. Mir ist nur eingefallen, dass diese Schleife sich ständig um seltene Sonderfälle kümmert und ich hab mich gefragt, was es da für elegante Lösungen geben könnte.
    Mir ist schon klar, dass es an der Stelle nur Mikrooptimierungen sind, hab ja gleich geschrieben, dass das nicht wichtig ist. Mir gehts hier wirklich nur um technische Ideen.

    @TGGC: klar, kanns mir aber noch nicht so wirklich vorstellen.

    @hustbaer: Ok, das sind wahrscheinlich wirklich Mikrooptimierungen 😉 Das wird sich hier nicht lohnen. Ich bin eigentlich hauptsächlich auf das ganze gekommen, weil ich spontan die Idee hatte, dass es sich lohnen könnte, eine kleine VM zu schreiben, in die man nur die Befehle reinschmeißt, die man wirklich braucht, und die dann mit wenig Overhead perfekt konfiguriert durchläuft. Aber die Idee habe ich eigentlich gleich wieder verworfen, weil der Overhead eigentlich gar nicht so klein sein kann, dass sich das tatsächlich lohnen würde. Aber vielleicht hat mal schon mal jemand was ähnliches gemacht, würde mich interessieren.

    nochmal @rapso: und im Endeffekt ist es im Moment auch das, was ich dann wahrscheinlich versuchen werde. Ich werd mal schauen, dass ich alle Eingabedaten und das Ergebnis in ein Objekt verpacke und das durch die Filterkette durchreiche. Also sowas wie Pipes & Filters. Wobei mir irgendwie eher der Begriff "function chain" vorschwebt.


Log in to reply