3. Brauche Optimierungshilfe :)

Brauche Optimierungshilfe :)

  • M

    @hustbaer: könntest du wenn du zeit hast ein wenig erklären was da passiert bei dir?
    würde mir sehr helfen - ein blosses vertauschen von rows und columns passt - es funktioniert auch so...aber ne erklärung brauch ich noch 🙂

    EDIT: MarkColumns habe ich jetzt kapiert....was heißt denn das andOne? Ist doch überflüssig oder nicht?

    EDIT2:

    diesen teil bräuchte ich noch etwas erklärt:

    // make column advances 
    size_t c = 0; 
    size_t keep = 0; // nr. of columns to keep 
    while(c < columns) 
    { 
        advance[keep]++; 

        if(!flags[c]) 
        { 
             // keep 
            ++keep; 
        } 
        ++c; 
    } 

    if(keep && (keep != columns)) 
    { 
         // make start ptr and fix advance 
        double const* src = matrix + advance[0] - 1; 
        advance[keep] += advance[0]; 
        ++advance; 

         // process all rows 
        double* dest = matrix; 
        size_t n = rows * keep; 
        c = 0; 
        while(n--) 
        { 
            *dest = *src; 
            ++dest; 
            src += advance[c]; 
            ++c; 
            if(c == keep) 
                c = 0; 
        } 
    }
    0

  • Könnte daran liegen dass die linux clib (gcc?) beleidigt ist wenn man mit alloca zuviel Speicher anfordert. Änder das von 1000 mal auf 10 oder so, und guck obs dann immer noch crasht bei grossen Matritzen. Ich werd das heute später noch überprüfen und den ganzen Code nochmal durchgehen. Genaue Erklärung folgt dann auch.

    Schonmal soviel: die letzte Schleife kopiert so dass die doubles für die neue Matrix quasi "der Reihe nach" geschrieben werden, also geschrieben wird matrix[0], dann matrix[1], matrix[2], matrix[3] etc. - ganz egal welche columns gelöscht werden. Das ist gut weil cache misses beim schreiben viel teurer sind als beim lesen (die cache-row muss ja wieder zurückgeschrieben werden). Und dazu muss die Schleife wissen wie weit sie der "source" Zeiger nach jedem kopierten Wert weiterrücken muss, und natürlich muss man den "source" Zeiger zu Beginn auch auf den ersten nicht-zu-löschenden Wert setzen. Diese "Weiterspring-Weiten" sind im "advance" Array gespeichert. Natürlich könnte man die Schleife auch über die gesamte Matrix laufen lassen, und dann quasi jedesmal mit "if" checken ob die Column gelöscht wird oder nicht, aber ifs sind teuer und langsam und böse (*g*), und es macht ja auch wenig Sinn über die ganze Matritze drüberzupfeiffen wenn man doch bloss die Werte die man wirklich kopieren will einsammeln muss. Und da der Schreibe-Zeiger immer gleich auf mit oder vor dem Lese-Zeiger ist geht das auch ohne dass man sich seine Source-Werte überschreibt bevor man sie kopiert hat.

    Ahja, wenn der Fehler nicht am alloca liegt würde es helfen wenn du den gesamten Callstack hier reinklatscht. Kenn mich bei Linux nich so aus, hab auch keins laufen, und auch die Sourcecodes nicht zur Hand.

    Und das "NukeZeroColumnsAndOne" heisst lösche alle "alles null" Zeilen, und eine die per Index spezifiziert wird ("und eine": "and one"). Deine Funktion macht das ja auch so, dachte mir du wirst das wohl auch brauchen, sonst wäre das Parameter ja ziemlich Sinn-frei.

    0
  • M

    passt passt...es war ein fehler meinerseits...es funktioniert für beliebig große matrizen!!!

    Vielen dank hustbaer....ich schaffe es nicht mehr zu profilen heute aber morgen sag ich auf alle fälle bescheid wie groß der speed up ist 🙂

    jetzt verstehe ich nur noch nicht wie du dir die spungweiten merkst:

    Sehr eleganz übrigens diese methodik....da muss ich noch um einiges fitter werden 🙂
    großes dankeschön schon mal an dieser stelle....mein pointer-wissen steigt 😉

    // make column advances 
     size_t c = 0; 
     size_t keep = 0; // nr. of columns to keep 
     while(c < columns) 
     { 
         advance[keep]++; 

         if(!flags[c]) 
         { 
              // keep 
             ++keep; 
         } 
         ++c; 
     }
    0

  • Mati schrieb:

    ...aber morgen sag ich auf alle fälle bescheid wie groß der speed up ist 🙂

    (...)

    jetzt verstehe ich nur noch nicht wie du dir die spungweiten merkst:

    (...)

    Naja, hoffentlich isses überhaupt schneller als deine Version (denke aber schon) 🙂

    Also erstmal die Schleife läuft über alle Spalten der ausgangs Matrix drüber.
    Anfangen in "advance" zu zählen tun wir mit "advance[0]" ("keep" ist der Index - ist an der Stelle kein guter Name, aber ich bin faul *pfeiff*). Nun wird "advance[keep]" in jedem Durchlauf um eins inkrementiert, und danach wird "keep" inkrementiert (also zum nächsten Element in advance umgeschaltet) wenn die aktuelle Spalte eine ist die übernommen werden soll. Das führt dazu dass nachdem die Schleife durchgelaufen ist in "advance" bestimmte "Distanzen" gesammelt sind, und "keep" die Anzahl der zu kopierenden Spalten enthält. Sagen wir mal "keep" ist 5. Advance sieht dann so aus:

    advance[0] = ???
    advance[1] = Distanz von der ersten zu kopierenden Spalte zur zweiten zu kopierenden Spalte
    advance[2] = Distanz von der zweiten zu kopierenden Spalte zur dritten zu kopierenden Spalte
    advance[3] = ... von der dritten zur vierten ...
    advance[4] = ... von der vierten zur fünften ...
    advance[5] = ???

    Eine Distanz von 1 heisst dabei es ist die nächste Spalte, es wird also nix übersprungen (keine Spalte dazwischen ausgelassen). 1 ist also das Minimum. Soweit sollte es denke ich klar sein.

    Was steht nun in "advance[0]" und "advance[5]". Hm. Also es gibt keine "nullte zu kopierende Spalte" - von daher muss da was anderes drinstehen. Gucken wir uns an was in "advance[0]" drin steht wenn wir gleich die erste Spalte der original Matrix kopieren wollen, bzw. was wenn wir erst die zweite kopieren wollen. Im ersten Fall (gleich die erste Spalte soll kopiert werden) steht in "advance[0]" eben 1 drin (zuerst wird "advance[0]" von 0 auf 1 inkrementiert, dann wird "keep" inkrementiert, womit der Wert von "advance[0]" sich nimmer ändern kann). Im zweiten Fall steht in "advance[0]" eben 2 drin, sollte auch klar sein.

    -> In "advance[0]" steht die Spaltennummer der ersten zu kopierenden Spalte, bzw. anders ausgedrückt: die Distanz von der imaginären nullten Spalte der original Matrix zur ersten Spalte die kopiert werden soll. Oder noch anders gesagt: die Distanz von der letzten Spalte in der vorhergehenden Zeile zur ersten Spalte die kopiert werden soll in der neuen Zeile.

    Und in "advance[5]"? Was relativ leicht ersichtlich ist: wenn die 5. zu kopierende Spalte auch die letzte in der original Matrix war, steht in "advance[5]" 0. Ich kürze hier etwas ab, und behaupte einfach: in "advance[5]" steht die Distanz von der letzten zu kopierenden Spalte zur letzten Spalte der original Matrix 🙂
    (Wenn die letzte zu kopierende Spalte zugleich die überhaupt letzte Spalte ist dann ist diese Distanz eben 0)

    So, was haben/können wir bis jetzt. Wir haben die Distanzen zwischen allen zu kopierenden Spalten 1 bis 5, fehlt nur noch die Distanz von 5 auf 1, also der Sprung zur nächsten Zeile. Und den bekommen wir einfach durch "advance[5] + advance[0]", denn "advance[5]" bringt uns bis zur letzten Spalte der original Matrix, und "advance[0]" bringt uns von dort weiter zur ersten zu kopierenden Spalte.

    Daher die Addition:

    advance[keep] += advance[0];

    In "advance[keep]" steht nun also diese Distanz von der letzten zu kopierenden Spalte zur ersten zu kopierenden in der nächsten Zeile.

    Jetzt steht in jedem "advance[N]" also (mit N von 1 bis "keep") die korrekte Distanz zum nächsten zu kopierenden Element. Da ich aber mit einem 0 basierten Index drauffahre rücke ich den Zeiger "advance" noch um ein Element weiter, so dass ich nun mit 0...(keep-1) drauffahren kann.

    Jetzt fehlt nur noch die korrekte Startposition, und das ist auch einfach. In "advance[0]" (VOR dem weiterrücken des Zeigers!) steht ja die (1-basierte) Nummer der ersten zu kopierenden Spalte, also muss ich bloss vom Anfang der Matrix "advance[0] - 1" Elemente weitergehen um dort zu landen.

    Und dann muss nur noch kopiert werden 🙂

    Ich hoffe das war einigermassen verständlich. Wenn nicht sag einfach bescheid, wenns an einem bestimmten Punkt hakt kann ich dir das nochmal genauer erklären, bzw. es versuchen.

    0

  • So. Hab nu selbst ein wenig Profiling gemacht (MSVC 7.1, single threaded runtime, Release, Full Opt.)...

    Ich denke es wird sich auszahlen 😉
    Bitte schreib was sobald du Resultate hast... würde mich interessieren wie schnell das bei dir wirklich ist (mit "realen" Daten und so).

    0
  • M

    hallo hustbaer...

    ich hätte noch ne frage...warum bentzt du char arrays?

    ich versuche gerade noch eine zeile einzufügen die aber probleme macht:

    const int col = 8; //z.B
flags[col] = 1;

    kann ich so denn nicht ein char array verändern?

    Ich komme einfach nicht zum austesten...aber damit ichs vergleichen kann muss ich eben die obige zeile einsetzen...

    auf diese weise gehts:

    char* unit; 
    char* dynamicBuffer = 0; 

     // alloc temp space 
    if(rows <= 1000) 
        unit = static_cast<char*>(alloca(rows)); 
    else 
    { 
        dynamicBuffer = new char[rows]; 
        unit = dynamicBuffer; 
    }
    unit[unit_col] = true;

    c = 0; 
    n = rows; 
    while(n--) 
    { 
        flags[c] &= unit[c]; 
        ++c; ++src; 
    } 

    delete [] dynamicBuffer;

    aber als abkürzung reicht doch ein einzeiler bei dem ich lediglich eine stelle auf true setze....nur
    läuft das so nicht korrekt...und am ende gibts nen sefault *grmpf

    0

  • Mati, Freund, was glaubst du was folgende Stelle macht?

    size_t NukeZeroColumnsAndOne(double* matrix, size_t rows, size_t columns, long andOne) 
{ 
    // ...
        MarkZeroColumns(matrix, rows, columns, flags); 
        if((andOne >= 0) && (andOne < columns)) 
            flags[andOne] = 1; 
    // ...
}

    Naja, egal. Klar reicht es wenn du einfach eine Stelle in "flags" auf true setzt nachdem MarkZeroColumns gelaufen ist. Du musst natürlich sicher stellen dass der Index >= 0 und < "rows" ist.

    Und ein char array verwende ich weil ein char das kleinste ist was man in C++ direkt addressieren kann (brauch ja bloss 1 bit), und weil bei bool die Chance bestehen würde dass der Compiler sich genötigt fühlt langsameren Code zu erzeugen als mit char möglich wäre.

    Dass du seg-faults bekommst verstehe ich nicht ganz, bei mir läuft das ohne Probleme, auch mit 4000x4000 Matritzen...

    0
  • M

    ach scheiße...jetzt versteh ichs auch ...peinlich sorry -
    ich mach mich endlcih ans profiling....sorry

    0

  • Kein Problem 🙂

    0
  • M

    *lach
    langsam werd ich verrückt...Ich glaube ich hab nen BUG:

    versuch mal als input folgende "matrix"
    0 0 0 0 0 5

    und als andOne = 4 oder andOne = 3

    ich bin dabei schon zu lösen aber habs nocht net ....grrrrrr
    EDIT: ich heinz: sollte auch beschreiben worans liegt:
    also er nimmt in keep hier nicht mehr die eine zeile auf die behalten werden soll durch das andOne...

    0

  • Hihi.
    Ja das liegt daran weil ich das falsch verstanden habe, und die Logik umgedreht *pfeiff*
    Er behält also nicht die Zeile deren Nummer du übergibst sondern er löscht die dann immer 😃

    Ändere einfach das "flags[andOne] = 1" auf "flags[andOne] = 0". Den Funktionsnamen und den Namen "andOne" solltest du dann natürlich entsprechend anpassen.

    0
  • M

    jo jetzt hab ichs 🙂
    geprofiled auch - respekt.

    Die harte pointer-arithmetik und dein algorithmus bringen bei meinen testläufen sehr viel.
    Ich habe natürlich die methode zum nullzeilenlöschen innerhalb eines anderen algorithmus.
    Ursprünglich nach meiner ersten implementierung frass sie 75 % der gesamtlaufzeit. Habe dann eine optimierung (reimplemenierung der methode) gemacht und den anteil auf 55 - 60% gedrückt. Mit deiner variante bekomme ich jetzt 20 - 25 % ! Das ist enorm!

    Vielen dank an dieser stelle! Es funkioniert wunderbar 🙂

    0

  • Jo gerne. 🙂

    0
Anmelden zum Antworten