Schnelles Vergleichen von BYTE-Variablen



  • Welche Techniken gibt es, große Mengen von Variablen des Typs BYTE effizient zu vergleichen?
    Als erstes fällt mir MMX ein aber ich würde gern wissen ob es noch andere Möglichkeiten gibt.



  • Definiere Byte vergleichen.



  • class CWeekday {  BYTE bVar;  };
    
    // Vectoren mit Weekdays in 7er-Blöcken seit 1980, Daten werden aus Datei gelesen
    vector<CWeekday*> vec1980, vec1981, ...;
    
    vector<CWeekday*>::Iterator iter1980;
    vector<CWeekday*>::Iterator iter1981 = vec1981.begin();
    for(UNIT uiIndex = 0; uiIndex < 7; ++uiIndex)
      for(iter1980 = vec1980.begin(); iter != vec1980.end(); ++iter)
        {
        if(iter1980->bVar == iter1981->bVar) {}
        if(iter1980->bVar == iter1981->bVar) {}
        if(iter1980->bVar == iter1981->bVar) {}
        if(iter1980->bVar == iter1981->bVar) {}
        if(iter1980->bVar == iter1981->bVar) {}
        if(iter1980->bVar == iter1981->bVar) {}
        if(iter1980->bVar == iter1981->bVar) {}
        ++iter1981;
        }
    

    Es liegt ein std::vector vor der sehr viele Zeiger auf CWeekday-Objekte enthält. Die Weekday-Objekte besitzen
    natürlich noch weitere Member. Im Original sind die BYTE-Variablen privat und die Werte sind immer positiv.



  • @WhiteWolf

    Es liegt ein std::vector vor

    Also etwas anderes als du zeigst.



  • Was willst du genau erreichen? Was ist bei dir ein BYTE? Warum eine Intel Befehlserweiterung aus den 90ern?

    Implementier wie es am besten verständlich ist und guck was der Compiler raus macht. Wenn das nicht reicht, guck nach Optimierungen 😉



  • Das Codebeispiel triftt noch nicht ganz das Original, sollte aber reichen. Das Programm läuft einwandfrei nur wird es durch
    die vielen Vergleiche immer langsamer. Jeden Tag wird es ein BYTE mehr. Ich muss alle bVars auswerten und statistisch
    verarbeiten.

    Es muss nicht MMX sein, das ist ja meine Frage. Welche Möglichkeiten gibt es noch?



  • @WhiteWolf

    sollte aber reichen

    Dann noch viel Spaß mit deinem Problem...



  • was willst du denn überhaupt vergleichen bzw. was soll der vergleich bringen? ein minimum oder maximum? wenn ja: speichere das maximum doch und vergleich den neuen wert damit.



  • @Schlangenmensch
    Welche Sorte Optimierungen könnte man da vorschlagen?
    Nebenbei: Ein BYTE ist bei mir ein Speicherbereich der Platz für Werte zwischen entweder -127 bis 128 oder 0 bis 256 bereitstellt.

    @manni66
    Vielen Dank für die Ermutigung!

    @Wade1234
    Nein ist kein minimum/maximum. Eine der Auswertungen listet Objekte mit gleichen bVars auf.

    @Alle

    Mein Problem mit MMX ist folgendes:

    __m64 mMMXArray1 = _mm_set_pi8(Montag, Dienstag, Mittwoch, Donnerstag, Freitag, Samstag, Sonntag, 0);
    __m64 mMMXArray2 = _mm_set_pi8(Montag, Dienstag, Mittwoch, Donnerstag, Freitag, Samstag, Sonntag, 0);
    
    __m64 mResult = _mm_cmpeq_pi8(_mMMXArray1, _mMMXArray2);
    

    Dann hab ich in mResult sowas oder?

    00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111

    Dann brauch ich ja hinterher trotzdem eine if-Abfrage für jedes Element?
    Oder hab ich was übersehen?



  • Was passiert denn bei Gleichheit?

    Manni fragt nach dem richtigen Code, weil du in deinem abgewandelten Beispiel halt in der Schleife einfach immer den gleichen Vergleich machst.

    Edit: ich schlage vor, sauberen Code zu schreiben, den Compiler die Optimierungen machen zu lassen und wenn das nicht reicht über eine Parallelisierung nachzudenken. (evt. mit openMP)



  • Du hast recht, irgendwas übersieht man immer. Das muss natürlich so aussehen:

    for(iter1980 = vec1980.begin(); iter != vec1980.end(); ++iter)
       for(UNIT uiIndex = 0; uiIndex < 7; ++uiIndex)
         {...}
    

    Bei Gleichheit wird es vorerst mit der WinAPI-Funktion TextOut() auf ein Fenster geschrieben. Bei Ungleichheit nicht.

    OpenMP? Eine Threading-Library? Einen zweiten Thread zur Berechnung hat das Programm schon. Aber ich werd da mal weiter drüber nachdenken.



  • @WhiteWolf und was willst du damit insgesamt feststellen? ob der wert schonmal vorhanden war, wann der wert schonmal vorhanden war, wie oft der wert schonmal vorhanden war? in diesem fall hast du - sofern ich mich nicht irre - etwa 256 möglichkeiten durchzuprüfen und das sollte ein 286er locker in hinnehmbarer zeit schaffen.



  • Ausgabe ist halt auch immer teuer.

    Ich glaube nicht, dass du mit manuellem direkten Aufruf von speziellen Chipsatzbefehlen deutlich besser wirst, als das was dir dein Compiler optimiert. Ich denke, dass es vor allem algorithmische Verbesserungen gibt, aber dazu kann niemand was sagen, weil wir nicht wissen, was dein Ziel ist.

    Wenn es nur darum geht zu überprüfen ob ein Wert schon mal vorgekommen ist und dann eine Ausgabe zu machen, kannst du auch einfach den Wert z.B. in eine Map oder einen Vektor schreiben und gucken ob der schon mal vorgekommen ist.
    Wenn du jeden Tag von jedem Jahr miteinander vergleichen willst, hast du halt auch einige Kombinationen.

    Wenn es dir um einen schnellen Vergleich von deinem Typ "BYTE" geht, wäre hilfreich zu wissen, wie du den == operator aktuell implementiert hast? Oder was für ein Typ dahinter steckt. Ist das einfach ein alias auf ein uint8_t?



  • @WhiteWolf sagte in Schnelles Vergleichen von BYTE-Variablen:

    Bei Gleichheit wird es vorerst mit der WinAPI-Funktion TextOut() auf ein Fenster geschrieben. Bei Ungleichheit nicht.

    Moment mal, kann es sein, dass es ein Problem ist, da diese Vergleiche bei jedem Neuzeichnen durchgeführt werden müssen? Evtl. ist dann double buffering schon die Lösung / (edit: bzw. alles zu speichern, was für die Ausgabe benötigt wird).
    Bei weniger als 15.000 Tagen (nehme ich durch 1980 einfach mal an) sollten diese einzelnen Vergleiche, sofern sie einmalig durchgeführt werden, nicht ins Gewicht fallen.
    Und wenn die alten Daten immer gleich bleiben und nur ein paar neue hinzukommen, könnte man diese alten evtl. auch geschickter speichern (neben anderen Werten,).



  • Jetzt muss ich nochmal auf MMX zurückkommen. Ist der Ablauf den ich weiter oben genannt habe richtig? Wenn ich jedes Element im Ergebnis mit einer if-Abfrage testen muß, dann ist die Beschleunigung ja wieder dahin.



  • @WhiteWolf sagte in Schnelles Vergleichen von BYTE-Variablen:

    vector<CWeekday*>
    

    Tu als erstes mal die wahrscheinlich sinnlose Indirektion weg.



  • Jetzt muss ich aber nochmal auf MMX zurückkommen. Ist der Ablauf den ich weiter oben gennant habe korrekt? Wenn ich jedes Element in mResult mit einer if-Abfrage testen muss, ist die Beschleunigung ja wieder dahin.



  • @Swordfish
    Also Stack-Objekte in den Vector schieben?



  • @WhiteWolf sagte in Schnelles Vergleichen von BYTE-Variablen:

    Stack-Objekte

    ich weiß nicht was das ist, aber ich meine den * in

    @WhiteWolf sagte in Schnelles Vergleichen von BYTE-Variablen:

    Stack-Objekte

    ich weiß nicht was das ist, aber ich meine den Stern in

    @WhiteWolf sagte in Schnelles Vergleichen von BYTE-Variablen:

    vector<CWeekday*>
    

    wegmachen.

    @WhiteWolf sagte in Schnelles Vergleichen von BYTE-Variablen:

    Weekdays in 7er-Blöcken

    habe ich nicht wirklich kapiert. Vielleicht zeigst du mal den vollständigen (funktionierenden) Code der Dir zu langsam ist.



  • @WhiteWolf: wie schon weiter oben vorgeschlagen wurde, könntest Du entweder das Ergebnis der Auswertung oder besser noch die fertige statistische Auswertung speichern. Dann brauchst Du nur noch den täglichen Schritt zu berechnen. Überlasse ansonsten erst mal dem Compiler die Optimierung auf die Fähigkeiten Deiner CPU. Schau Dir den ASM-Code an, den der Compiler bei verschiedenen Optimierungs-Stufen ausspuckt!


Log in to reply