[C] linked list traversal optimalisatie

[Macros]

Ik ben een programma aan het schrijven dat zo snel mogelijk moet zijn. Daarom dat ik inplaats van eerst wat werkends schrijven alles wat ik doe meteen zo optimaal wil schrijven, want elke miliseconde is er 1. Ergens in de applicatie moet ik regelmatig linked lists doorlopen. De elementen in die list liggen niet achter elkaar, wat wel jammer is, maar daar kan ik niks aan doen.
Ik loop die linked list af en vergelijk elk item met een waarde die ik zoek en ik test natuurlijk of de volgende in de list NULL is, zo ja, dan stop ik en heb ik niks gevonden. Toevallig weet ik ook hoe lang die list is, dus ik zou ipv, op NULL checken, ook dat tellertje af kunnen laten lopen.

Teller:
pro: cpu hoeft niet te wachten op de NULL test om door te lopen naar het volgende item (loop unrolling)
con: extra instructies in de inner loop
Geen teller:
pro: ziet er efficient en schoon uit
con: mogelijk kans dat de cpu stalled bij het evalueren

offtopic:
De list is eigenlijk een double linked list, ook moet ik regelmatig een nieuw item invoegen, dat doe ik altijd aan het begin (4 instructies in C). Soms moet ik er een item uithalen (2 instructies) en ook wel eens 2 items wisselen van 2 verschillende lists (in theorie 8, maar ik kom op 10 instructies).
Vraagje: wat zou de snelste methode zijn van deze 3 operaties?

Als je nog andere optimalisatie tips hebt, help uw medemens en toon je inteligentie

[curry684]

Op welk platform werk je?

Onder Win32 heb je namelijk op het allerallerallerlaagste niveau de Singly Linked Lists, welke onder atomaire operaties vallen. Ergo extreem f*cking snel

edit:
hmm mental note: XP en 2k3 only feature trouwens. Indien geinteresseerd zoek je in ieder geval de InitializeSListHead, InterlockedPushEntrySList, InterlockedPopEntrySList en InterlockedFlushSList functies

[ Voor 38% gewijzigd door curry684 op 02-12-2003 21:45 ]

[curry684]

Ik heb trouwens nog wel een praktijktip: de verleiding is heel groot om functies die door de lijst moeten zoeken recursief te schrijven, maar dat kun je dus beter niet doen en een simpele loop gebruiken. Compilers kunnen namelijk van een loop veel meer performance afsnoepen dan van een recursieve actie die een hoop stack-optuigwerk vereist.

Het is overigens zo dat sommige compilers recursieve lookups herkennen en plat uitschrijven, maar daar kun je beter niet op rekenen.

[MSalters]

Uit eigen ervaring: schrijven, meten, optimaliseren. Je zou niet de eerste zijn die 1000000 milliseconden besteedt om 10000 milliseconden te besparen. Bovendien is het vaak handig om op een hoger nivo te optimaliseren. Als je een container gebruikt, en je zoekt daarin naar waardes, is een linked list dan wel het meest slimme? Kun je uit profilen bepalen of bepaalde elementen vaker gevonden worden dan anderen? Bv. aan het einde vaker dan aan het begin? Of moet je misschien alleen bepalen of die waarde voorkomt?

[Macros]

Ik werk onder Linux in "simple" C, dus geen C++ met al zijn goodies.
Het klopt dat het zoeken in een linked list niet het snelste is wat er bestaat. Maar het is zo dat ik een hele lange lijst met items heb. Deze lijst kan wel meer dan een milioen items bevatten. Sommige van deze items worden in zogenaamde sacks gedaan. Een item bevat een pointer naar die sack.
Vaak zijn er maar een fractie van alle items in een sack, en er zijn meerdere sacks, dus het is niet vreemd dat er 1.000.000 items zijn en maar 10 sacks en er zitten in elke sack ongeveer 1000 items.
Het komt vaak voor dat ik alleen wil zoeken naar de items in een bepaalde sack. Het is dan efficienter om een linked list bij te houden van alle items in elke sack zodat je die dan kan doorzoeken ipv de hele lijst van 1.000.000 items (dit moet soms ook gebeuren, bv. als je naar alle items niet in een sack zoekt, dan zoek ik door een binairy search en check ik voor elk item of het al in een sack zit)
Het elendige is dat ik niet zoek naar een item dat precies 1 waarde moet hebben maar een range van waardes (min en max). Met die binairy search zoek ik dan naar die min en ga dan naar boven lopen totdat ik bij de max bent.

Dit is de code van mijn binairy search:

C:

static Item * getMinProfit(int target, Item *sorted_items)){
    int max = noi-1;
    int min = 0;
    int p;
    while(1){
        p = (max - min)/2;
        if (max - min <= 2){
            if (sorted_items[p]->profit > target)
                return sorted_items[min]; // we konden niks vinden
            else
                return sorted_items[p];
        }
        else if (sorted_items[p]->profit > target)
            max = p;
        else /* if (sorted_items[p]->weight <= target) */
            min = p;
        // cant come here
        return;
    }
    // cant come here
    return;
}

Nog niet echt getest, alleen met de hand, moet eerst nog andere delen van het algoritme afmaken.

[ Voor 6% gewijzigd door Macros op 02-12-2003 22:03 ]

[Macros]

MSalters schreef op 02 december 2003 @ 21:50:
Uit eigen ervaring: schrijven, meten, optimaliseren. Je zou niet de eerste zijn die 1000000 milliseconden besteedt om 10000 milliseconden te besparen. Bovendien is het vaak handig om op een hoger nivo te optimaliseren. Als je een container gebruikt, en je zoekt daarin naar waardes, is een linked list dan wel het meest slimme? Kun je uit profilen bepalen of bepaalde elementen vaker gevonden worden dan anderen? Bv. aan het einde vaker dan aan het begin? Of moet je misschien alleen bepalen of die waarde voorkomt?

Teneerste, al 10 seconden eraf schaven door 3 weken te denken en testen, natuurlijk heb ik dat er voor over!
Ik optimaliseer op alle niveaus. Ik moet vaak zoeken in de array, dus ik heb hem gesorteerd voor binairy search. Als hij erg groot is gebruik ik radix sort, anders gebruik ik quicksort.

Ik hoef niet te bepalen of het voorkomt in dit gedeelte, ik moet een item vinden dat voldoet aan meerdere waarden. Denk aan dit probleem in SQL.
Je hebt een tabel van items.
Elk item heeft een aantal velden:
Item (key, profit, weight, util, sack) // util = profit/weight
En wat ik dan zoek:
SELECT key FROM item WHERE weight <= $max AND weight >= $min AND sack = '$sack' ORDER BY util DESC limit 1;
En variaties daarop, wel intersant probleem

[curry684]

Als je zoveel en zo grote searches moet doen, kun je dan niet beter het hele ding als b-tree opslaan ipv een linked list?

[Macros]

B-tree itereerd slecht over alle items (slechter dan een linked list).
Een b-tree gaat je ook niet helpen als je alleen alle items in een bepaalde sack wilt hebben en je B-tree is gebaseerd op bijvoorbeeld de weight, profit of util. Een extra b-tree bijhouden voor de sack is niet efficient omdat er maar weinig waardes zijn. En een b-tree is opzich even snel als een b-search.

[ Voor 8% gewijzigd door Macros op 02-12-2003 22:41 ]

[curry684]

Macros schreef op 02 december 2003 @ 22:40:
B-tree itereerd slecht over alle items (slechter dan een linked list).

Dat kan kloppen. Maar je moet je gebruiken goed afwegen: als jij 10 keer zo vaak een search doet dan een for-each-item kun je wsch beter een goed geoptimaliseerde b-tree opentrekken. In principe hoeft een b-tree niet inefficienter te zijn dan een linked list.

Een b-tree gaat je ook niet helpen als je alleen alle items in een bepaalde sack wilt hebben en je B-tree is gebaseerd op bijvoorbeeld de weight, profit of util. Een extra b-tree bijhouden voor de sack is niet efficient omdat er maar weinig waardes zijn.

Dan is het juist vaak wel efficient, als je weighted trees met alleen pointers naar de eigenlijke items maakt? Staat je toe diverse verschillende lookups te doen zonder te hoeven switchen van sortering e.d.

En een b-tree is opzich even snel als een b-search.

Indien alles goed gesorteerd is wel.

[Macros]

Alles wordt gesorteerd door radix sort ( O(kN), waarbij k = 5 of 3, wat beter kan zijn dat qsort op grote arrays, welke O(NlogN) is.

[Verwijderd]

een beetje mierenneuken : volgens mij is de derde return in je GetMinProfit functie niet goed, deze zorgt ervoor dat na je if/else if/else blok de functie verlaten wordt. Die kan je dus gewoon weg halen (anders maar 1 iteratie in je while)

en curry : is een b-tree niet erg onhandig als je veel inserts doet (ik bedoel dus, 'kosten' die niet meer dan een insert in een gesorteerde linked list?)

[MSalters]

Een mogelijke optimalisatie is een optimized allocator die probeert opeenvolgende list nodes in het geheugen bij elkaar te houden. Wat je dan doet is tijdens de allocatie een 'hint' parameter meegeven, wat dus het vorige/volgende list item is. Op die manier kun je soms een beter geheugen gebruik bereiken. In elk geval heb je dan alle list nodes uit een klein aantal blocks gealloceerd, en zitten er geen random andere malloc'ed blokken tussen. Dit kan de cache efficiency verbeteren.

[Verwijderd]

Macros schreef op 02 december 2003 @ 22:02:
Dit is de code van mijn binairy search:

C:

static Item * getMinProfit(int target, Item *sorted_items)){
    int max = noi-1;
    int min = 0;
    int p;
    while(1){
        p = (max - min)/2;
        if (max - min <= 2){
            if (sorted_items[p]->profit > target)
                return sorted_items[min]; // we konden niks vinden
            else
                return sorted_items[p];
        }
        else if (sorted_items[p]->profit > target)
            max = p;
        else /* if (sorted_items[p]->weight <= target) */
            min = p;
        // cant come here
        return;
    }
    // cant come here
    return;
}

Nog niet echt getest, alleen met de hand, moet eerst nog andere delen van het algoritme afmaken.

Die deling die je doet is natuurlijk erg duur. Een shift is hier goedkoper..

Verder heeft de AMD Optimization Guide nog wat handige tips:
www.amd.com/products/cpg/athlon/techdocs/pdf/22007.pdf

[madwizard]

Verwijderd schreef op 03 december 2003 @ 17:34:
[...]
Die deling die je doet is natuurlijk erg duur. Een shift is hier goedkoper..

Verder heeft de AMD Optimization Guide nog wat handige tips:
www.amd.com/products/cpg/athlon/techdocs/pdf/22007.pdf

Vrijwel elke compiler zal delingen door machten van 2 omzetten in een shift dus het heeft weinig zin dat zelf te gaan doen.

[Macros]

Verwijderd schreef op 03 december 2003 @ 15:54:
een beetje mierenneuken : volgens mij is de derde return in je GetMinProfit functie niet goed, deze zorgt ervoor dat na je if/else if/else blok de functie verlaten wordt. Die kan je dus gewoon weg halen (anders maar 1 iteratie in je while)

en curry : is een b-tree niet erg onhandig als je veel inserts doet (ik bedoel dus, 'kosten' die niet meer dan een insert in een gesorteerde linked list?)

Je hebt gelijk met die return, in mijn hoofd had ik daar een continue, maar die was er natuurlijk niet.
B-tree is inderdaad best wel zwaar met inserts.
Over die deling door 2, ik kon inderdaad die vervangen door een shift, maar ik ging er vanuit dat de compiler zelf wel zou vervangen, dan blijft het beter leesbaar.

[Verwijderd]

Macros schreef op 03 december 2003 @ 20:13:
[...]

Je hebt gelijk met die return, in mijn hoofd had ik daar een continue, maar die was er natuurlijk niet.
B-tree is inderdaad best wel zwaar met inserts.
Over die deling door 2, ik kon inderdaad die vervangen door een shift, maar ik ging er vanuit dat de compiler zelf wel zou vervangen, dan blijft het beter leesbaar.

Nog even over die deling. Ja de meeste compilers zullen dat wel automatisch converteren naar een shift-right. Trouwens delen door 2 en shiften is niet precies het zelfde:

C:

int testfunction_1(int c){
  c = c / 2;
  }

int testfunction_2(int c){
  c = (c >> 1);
  }

Test 1:

code:

testfunction_1:
        movl    4(%esp), %eax
        movl    %eax, %edx
        shrl    $31, %edx
        addl    %edx, %eax
        sarl    %eax
        ret

Test 2:

code:

testfunction_2:
        movl    4(%esp), %eax
        sarl    %eax
        ret

Sinds je ook negatieve getallen kunt hebben wordt er bij het delen rekening gehouden terwijl bij shiften dat niet gebeurt. Als we die int naar unsigned int veranderen krijgen we dit:


Test 1:

code:

testfunction_1:
        movl    4(%esp), %eax
        shrl    %eax
        ret

Test 2:

code:

testfunction_2:
        movl    4(%esp), %eax
        shrl    %eax
        ret

[Macros]

Dat klopt, dat las ik ook, dus dat heb ik al veranderd.
Als het hele algoritme af is zal ik de code wel posten, dan kan iedereen nog naar optimalisaties zoeken

[demonite]

De post van meneer Salters over memory is een goede.

Linked lists die gevuld worden 'along the way' hebben nogal de neiging om overal wat memory vandaan te plukken.

Lees dit maar eens:
http://msdn.microsoft.com...time.2d.critical_code.asp

Met name het gedeelte over page faults

[Macros]

Mijn linked list wordt gealloceerd als een array. De elementen in de array worden dan gelinked in een linked list. Elk element wordt dus niet opzichzelf gealloceerd, dus alles blijft 1 groot blok.

[MSalters]

Je nodes worden wel gealloceerd, alleen niet door de runtime, maar door je eigen algoritme. Je moet toch ergens beslissen waar die node binnen het blok komt te staan?

Na het opnieuw lezen van je post viel me ook op dat je nodes tussen lists swapt. Is dat handig? Kun je niet beter de contents swappen? Het veschil is dat de content mogelijk groter is, maar dan blijven je nodes tenmniste in hetzelfde blok zitten.

code:

// Methode 1
1 - 2 -3      1   2   3      
          ->    X   X
9 - 8 -7      9   8   7

// Methode 2
1 - 2 -3      1 - 8 - 3      
          ->
9 - 8 -7      9 - 2 - 7

Je eindigt in beide gevallen met 1 8 3 en 9 2 7, maar de tweede is beter voor de cache (en sneller bij content<=2 pointers)

[Macros]

MSalters schreef op 07 december 2003 @ 20:47:
Je nodes worden wel gealloceerd, alleen niet door de runtime, maar door je eigen algoritme. Je moet toch ergens beslissen waar die node binnen het blok komt te staan?

De nodes zijn al van tevoren gealloceerd. En niet 1 voor 1 maar als 1 groot blok. Waar de nodes in het blok staan is niet erg relevant. Er zijn ook nog andere structuren die naar de nodes verwijzen, zoals pointer arrays (2 op dit moment), die op andere manier zijn gesorteerd.

Na het opnieuw lezen van je post viel me ook op dat je nodes tussen lists swapt. Is dat handig? Kun je niet beter de contents swappen? Het veschil is dat de content mogelijk groter is, maar dan blijven je nodes tenmniste in hetzelfde blok zitten.

code:

// Methode 1
1 - 2 -3      1   2   3      
          ->    X   X
9 - 8 -7      9   8   7

// Methode 2
1 - 2 -3      1 - 8 - 3      
          ->
9 - 8 -7      9 - 2 - 7

Je eindigt in beide gevallen met 1 8 3 en 9 2 7, maar de tweede is beter voor de cache (en sneller bij content<=2 pointers)

Als ik de contents swap, dan kloppen die gesorteerde pointer arrays niet meer. Maar wel slim als je die niet hebt, want dan blijft je locality behouden. Jammer genoeg was die er al vanaf het begin aan al niet
Bij een andere routine kopieer ik die lists eerst naar 2 arrays als ik er veel operaties op moet doen zodat ze in de cache terecht komen.

[riezebosch]

MSalters schreef op 03 december 2003 @ 16:12:
Een mogelijke optimalisatie is een optimized allocator die probeert opeenvolgende list nodes in het geheugen bij elkaar te houden. Wat je dan doet is tijdens de allocatie een 'hint' parameter meegeven, wat dus het vorige/volgende list item is. Op die manier kun je soms een beter geheugen gebruik bereiken. In elk geval heb je dan alle list nodes uit een klein aantal blocks gealloceerd, en zitten er geen random andere malloc'ed blokken tussen. Dit kan de cache efficiency verbeteren.

Ehmmm, hoe doe je dat? Aan de allocator een hint meegeven? Is dat dan gewoon de operator new of een variant daarop (dat is toch wat je bedoelt)?

[.oisyn]

Verwijderd schreef op 03 december 2003 @ 20:44:

Nog even over die deling. Ja de meeste compilers zullen dat wel automatisch converteren naar een shift-right. Trouwens delen door 2 en shiften is niet precies het zelfde:

Shiften op negatieve getallen werkt prima met arithmetic shift rights hoor, -8 >> 1 levert gewoon -4 op, zoals je zou verwachten. Het probleem is echter als noemer < 0 en deler > -noemer, zodat het resultaat 0 zou moeten worden. Bij een negatief getal kun je rightshiften wat je wilt, maar 0 wordt het nooit (hij blijft hangen op -1)

(Overigens staat het niet vast in C/C++ dat een >> op signed integrals altijd een logical shift right geeft, en >> op unsigned integrals een arithmetic shift right. Maar meestal is dat wel zo)

[ Voor 15% gewijzigd door .oisyn op 10-12-2003 19:18 ]

[MSalters]

riezebosch schreef op 10 december 2003 @ 18:22:
[...]

Ehmmm, hoe doe je dat? Aan de allocator een hint meegeven? Is dat dan gewoon de operator new of een variant daarop (dat is toch wat je bedoelt)?

Niet de operator new, maar een operator new. Je mag zelf extra versies definieren, mits ze niet conflicteren - een overload dus. Dan krijg je dus iets als

Node* newnode = new( hint(old_node) ) Node;

waarbij hint() dus iets retourneert dat je operator new snapt.

Je kunt niet direct old_node doorgeven, omdat je dan de signaure hebt van placement new.

[Macros]

Ik heb wat testjes gedaan met loop unrolling.
Ik roep een kleine inline functie (die heet dos()) 800.000.000 keer aan en ik wil die loop zo snel mogelijk hebben.
De standaard loop:

C:

    for(i = 0; i < n; i++){
        dos(i);
    }

Doet er 8.65 seconden over.
Terwijl deze loop:

C:

    int v = n/8;
    int r = n - v*8;
    int i, p;
    for(i = 0; i < v; i++){
        p = 8*i;
        dos(p);
        dos(p + 1);
        dos(p + 2);
        dos(p + 3);
        dos(p + 4);
        dos(p + 5);
        dos(p + 6);
        dos(p + 7);
    }
    i = n-r;
    switch (r){
        case 8: dos(i--);
        case 7: dos(i--);
        case 6: dos(i--);
        case 5: dos(i--);
        case 4: dos(i--);
        case 3: dos(i--);
        case 2: dos(i--);
        case 1: dos(i--);
    }

Er maar 6,78 seconden over doet.
Hoe minder je functie doet hoe meer winst. Hoe groter de functie doet, hoe minder je hem moet unrollen voor het meeste snelheid. In dit test geval was er 27.5% snelheids toename. Je code wordt wel wat groter, maar nu kan je loops unrollen als de compiler het niet kan, bijvoorbeeld als je een variabel aantal keer iets moet uitvoeren.

[writser]

[mierenneukmodus]je kunt de assignments voor r en v beter omdraaien, nu deel je n eerst door acht en daarna vermenigvuldig je hem weer met acht [/mierenneukmodus]

[_Squatt_]

writser schreef op 11 december 2003 @ 21:05:
[mierenneukmodus]je kunt de assignments voor r en v beter omdraaien, nu deel je n eerst door acht en daarna vermenigvuldig je hem weer met acht [/mierenneukmodus]

Beter kijken voor je vlooienwipt

C++:

int a = 18;
int b = ( a / 8 ) * 8;

Zijn a en b nu gelijk?

edit:
De assignment voor r kan wel vervangen worden door 'int r = n % 8;', wat misschien duidelijker is

[ Voor 14% gewijzigd door _Squatt_ op 11-12-2003 21:22 ]

[Macros]

Je kan ze niet omdraaien, omdat je de afronding nodig hebt die ints geven. Je doet eigenlijk modulo delen.
Maar dat boeit allemaal niet zo, de setup is misschien 0.00005% van de tijd dat je wint.

[ Voor 31% gewijzigd door Macros op 11-12-2003 21:49 ]