[alg] Schalende data structuur over meerdere threads

[Verwijderd]

Ik was laatst bezig met de tuintopia contest. Toen kwam ik een bekend onderwerp tegen, namelijk concurrency. Multithreading is geïmplementeerd door middel van een centrale datastructuur (een max-heap). Daar zijn 8 threads tegelijk mee aan het praten. Met een mutex wordt gegarandeerd dat hele verhaal thread safe is.

Probleem: de hierboven genoemde methode schaalt slecht. Niet noodzakelijk bij 2, 4 of 8 threads, maar bij een gegeven input zal er op een gegeven moment een punt komen waarbij het zinloos is om meer threads toe te voegen (Wikipedia: Amdahl's law). Zie 2 verschillende test cases met afwijkende input voor mijn tuintopia algoritme:





De maximale speedup is gelimiteerd aan de lengte van de kritische sectie. Bij een max-heap is dat best bagger, met een miljoen elementen duurt het inserten relatief lang, laat staan 100 mil. elementen.

Discussie: wat voor truuks kunnen we toepassen om de schaling van een dergelijke datastructuur (max-heap) te verbeteren?

Er bestaan een aantal quick fixes: we kunnen meerdere elementen in één keer plaatsen of verwijderen, maar dat levert geen inherent betere schaling op. Eigenlijk moeten we de max-heap decentraal maken zodat er geen probleem met scaling kan ontstaan, maar hoe je dat voor elkaar krijgt blijft een mysterie. Hoe verbeter je in dit soort situaties dan toch de concurrency?

[_js_]

Als je niet een andere datastructuur kunt gebruiken die wat makkelijker schaalbaar is moet je al gauw de wetenschappelijke papers induiken (en dat is meestal goed te doen voor it onderwerpen, ook al heb je zelf geen wetenschappelijke ervaring)

Er staat bv wat informatie over hoe je een binary heap meer concurrent kunt maken op http://www.zurich.ibm.com/pdf/sys/adv_messaging/STMheap.pdf
Zoeken op termen die in zo'n paper gebruikt worden kan weer leiden tot meer informatie.

[pedorus]

Ik snap niet helemaal in welke context deze max-heap moet werken. Een hashmap bijvoorbeeld is redelijk eenvoudig concurrent te maken door te zorgen dat je maar op een deel van de map locked, waardoor de kans groot wordt dat de threads elkaar niet in de weg zitten.

Afhankelijk van de situatie zou dit wellicht met de max-heap ook kunnen werken. Echter, het is mij niet duidelijk welke operaties je gebruikt in welke mate, wat voor waardes in welke frequentie worden opgeslagen, en hoe erg het is als de volgorde niet exact is/in welke volgorde zaken horen te gaan.

[Verwijderd]

_js_ schreef op maandag 17 juni 2013 @ 21:39:
Als je niet een andere datastructuur kunt gebruiken die wat makkelijker schaalbaar is moet je al gauw de wetenschappelijke papers induiken (en dat is meestal goed te doen voor it onderwerpen, ook al heb je zelf geen wetenschappelijke ervaring)

Er staat bv wat informatie over hoe je een binary heap meer concurrent kunt maken op http://www.zurich.ibm.com/pdf/sys/adv_messaging/STMheap.pdf
Zoeken op termen die in zo'n paper gebruikt worden kan weer leiden tot meer informatie.

Interessant, ik had ook al geprobeerd te zoeken naar concurrente heaps, maar daar kwam niet echt iets zinvols uit. Het is in elk geval ingewikkelde stof.

pedorus schreef op maandag 17 juni 2013 @ 21:50:
Ik snap niet helemaal in welke context deze max-heap moet werken.

Geen in het bijzonder. Het is meer een gedachte experiment dan 'ik moet dit implementeren/verbeteren'. Laten we er voor dit topic van uitgaan dat de heap rond de 1 mil. elementen zweeft en elke thread 1ms nodig heeft om een 'werk' af te handelen.

Een hashmap bijvoorbeeld is redelijk eenvoudig concurrent te maken door te zorgen dat je maar op een deel van de map locked, waardoor de kans groot wordt dat de threads elkaar niet in de weg zitten.

Goed punt. Dit had ik zelf niet geimplementeerd in mijn tuintopia algoritme omdat ik mijn hoofd niet goed naar de benodigde read-write lock kon zetten. Mijn 'max heap' is eigenlijk geïmplementeerd als hash map, maar ondersteunt alleen de standaard max-heap operaties (insert item & remove max) Bovendien vermoedde ik dat deze optimalisatie niet zorgt voor significant betere scaling: bij het ophalen van de maximale waarde uit de hash table moet telkens hetzelfde segment worden gelockt.

Wat ik met dit topic vooral wil bereiken is een soort van best practice op het gebied van concurrency. In dit voorbeeld is de max-heap implementatie duidelijk de bottleneck naarmate het aantal threads toeneemt. Al dan niet door het probleem te relaxen. Zoals een max-heap welke O(1) toegang geeft tot een item 'in de buurt van' het maximum. Maar wederom rest de vraag hoe je dat in hemelsnaam netjes implementeert zodat het schaalt over het willekeurig gekozen aantal van 100 threads.

[Gomez12]

Schalen over een willekeurig aantal doe je door simpelweg een pyramide op te zetten ipv 1 centrale datastructuur.

Verdeel je 1 miljoen elementen eens over 10 subnodes en opeens heeft elke subnode maar 10 workernodes te verwerken over 100.000 items. Redden je subnodes het dan nog niet dan kan je altijd nog 10 sub-sub nodes inzetten ad infinitum.

Heb je meer processing power dan kan je bijv 5 subnodes op een extra computer knallen en langzamerhand bouw je dan je eigen "cloud".

Als ik je probleem namelijk goed begrijp is het simpelweg dat je jobs sneller klaar zijn dan je centrale node het kan verwerken.

[Verwijderd]

Gomez12 schreef op maandag 17 juni 2013 @ 23:30:
Schalen over een willekeurig aantal doe je door simpelweg een pyramide op te zetten ipv 1 centrale datastructuur.

Hie denk je dat dan te gaan doen met het voorbeeld van een max-heap? Ik had deze optimalisatie ook al bedacht, maar liep vervolgens snel stuk op de vraag hoe je dat dan wilt implementeren, als je wilt gegaranderen dat de daadwerkelijke maximum value wordt opgehaald zul je alsnog alle 'nodes' moeten beveiligen met een mutex (of op z'n minst een read-write lock).

Heb je meer processing power dan kan je bijv 5 subnodes op een extra computer knallen en langzamerhand bouw je dan je eigen "cloud".

Als ik je probleem namelijk goed begrijp is het simpelweg dat je jobs sneller klaar zijn dan je centrale node het kan verwerken.

Een probleem met slechte concurrency los je niet op door er extra machines tegenaan te gooien.

[.oisyn]

Wat is de verwachting van een gemiddelde insert, werkt dat door tot in de root van de tree of zit het er toch meestal ver onder? Wat je in dat laatste geval kunt doen is gewoon een gesorteerde array bij houden van de eerste X elementen. Elementen daar vanaf poppen kan gewoon door een read pointer atomair op te hogen. De array opnieuw populaten doe je wanneer hij leeg is of wanneer een te inserten item groter is dan het laatste item in de array. Daar is uiteraard wel een lock voor nodig, maar door de read pointer te invalidaten (en pas bij een invalid read pointer te wachten op de lock) hou je de het gros van de pops gewoon lock-free. Een andere manier is om de array te double bufferen en de read pointer gewoon naar de andere geüpdatete buffer te laten wijzen, al is het dan wel extra oppassen geblazen met race conditions. Inserten in de array is weliswaar O(n) maar dat is te overzien omdat n klein is.

[ Voor 16% gewijzigd door .oisyn op 18-06-2013 01:00 ]

[pedorus]

Verwijderd schreef op maandag 17 juni 2013 @ 23:12:
Goed punt. Dit had ik zelf niet geimplementeerd in mijn tuintopia algoritme omdat ik mijn hoofd niet goed naar de benodigde read-write lock kon zetten.

Je gebruikt c++ toch? Kijk anders eens naar tbb::concurrent_hash_map / tbb::concurrent_unordered_map in http://threadingbuildingblocks.org

Mijn 'max heap' is eigenlijk geïmplementeerd als hash map, maar ondersteunt alleen de standaard max-heap operaties (insert item & remove max)

Een hash map? Dan kun je toch niet zomaar het maximum bepalen? Of bedoel je hier calendar queue ofzo omdat de data alleen bepaalde integers is?

Wordt er ook geupdate of alleen geinsert en ge-max-removed? Dan is het eigenlijk een concurrent priority queue. Hiervoor zijn gewoon bestaande implementaties, zoals een concurrent skip list, maar ook andere. Zie bijvoorbeeld:
https://github.com/facebo...olly/ConcurrentSkipList.h
http://software.intel.com...threading-building-blocks
MSDN: concurrent_priority_queue Class

Maar wederom rest de vraag hoe je dat in hemelsnaam netjes implementeert zodat het schaalt over het willekeurig gekozen aantal van 100 threads.

Dat hangt ook van je architectuur af natuurlijk, of bijvoorbeeld bepaalde centrale atomaire operaties beschikbaar zijn. Alternatief stuur je alle informatie ergens heen en krijg je daar steeds het maximum van terug.

[H!GHGuY]

B-trees zouden ook relatief eenvoudig concurrent te maken zijn en hebben als bijkomend voordeel dat ze cache-aware gemaakt kunnen worden - zodat je bij SMP ook minder cache thrashing hebt.
Ik heb op dit moment nog zo'n "maak mijn b+ tree concurrent" opdracht op de schappen liggen, maar naar ik gelezen heb moet dit niet zo moeilijk zijn.

[Verwijderd]

.oisyn schreef op dinsdag 18 juni 2013 @ 00:56:
Wat is de verwachting van een gemiddelde insert, werkt dat door tot in de root van de tree of zit het er toch meestal ver onder? Wat je in dat laatste geval kunt doen is gewoon een gesorteerde array bij houden van de eerste X elementen. Elementen daar vanaf poppen kan gewoon door een read pointer atomair op te hogen. De array opnieuw populaten doe je wanneer hij leeg is of wanneer een te inserten item groter is dan het laatste item in de array. Daar is uiteraard wel een lock voor nodig, maar door de read pointer te invalidaten (en pas bij een invalid read pointer te wachten op de lock) hou je de het gros van de pops gewoon lock-free. Een andere manier is om de array te double bufferen en de read pointer gewoon naar de andere geüpdatete buffer te laten wijzen, al is het dan wel extra oppassen geblazen met race conditions. Inserten in de array is weliswaar O(n) maar dat is te overzien omdat n klein is.

Goede punten. Bij een write moet je echter nog steeds het gros van de datastructuur locken. Een read en write kan in bepaalde gevallen wel tegelijkertijd gebeuren met de door jouw beschreven optimalisaties.

pedorus schreef op dinsdag 18 juni 2013 @ 11:27:
Een hash map? Dan kun je toch niet zomaar het maximum bepalen? Of bedoel je hier calendar queue ofzo omdat de data alleen bepaalde integers is?

Misschien is hash map niet het juiste woord. Omdat de integers relatief dicht bij elkaar liggen bij de tuintopia case heb ik een vector van vectors. Hierdoor kan (met vector.back()) in O(1) de maximale waarde ophalen, en in O(1) amortized een element poppen. Een probleem wat ik daarmee had dat het reallocaten van de vectors vrij lang duurt, wat de concurrency gedeeltelijk om zeep helpt.

Wordt er ook geupdate of alleen geinsert en ge-max-removed? Dan is het eigenlijk een concurrent priority queue. Hiervoor zijn gewoon bestaande implementaties, zoals een concurrent skip list, maar ook andere. Zie bijvoorbeeld:
https://github.com/facebo...olly/ConcurrentSkipList.h
http://software.intel.com...threading-building-blocks
MSDN: concurrent_priority_queue Class

De operaties die ik uitvoer zijn insert en max-remove, wat dus in feite een priority queue is. Ik zal de links even doornemen.

[.oisyn]

Verwijderd schreef op dinsdag 18 juni 2013 @ 15:21:
Goede punten. Bij een write moet je echter nog steeds het gros van de datastructuur locken. Een read en write kan in bepaalde gevallen wel tegelijkertijd gebeuren met de door jouw beschreven optimalisaties.

Klopt. Je zou ook aan een producer/consumer pattern kunnen denken waarbij er een dedicated thread is die de datastructuur up to date houdt. Een thread die iets wilt inserten stopt de te inserten item dan gewoon in de insert queue (kan lockless) en gaat verder z'n ding doen.

[EfBe]

Je zou nog kunnen denken aan een fibonacci-heap: Wikipedia: Fibonacci heap die heeft de beste (amortized) performance. Het nadeel is wel dat het wellicht minder goed te parallelliseren is. Zie voor een paper over concurrent priority queues (die bouw je met heaps dus is goed te gebruiken hier denk ik) : http://www.zurich.ibm.com...rtConcurrentPrioQueue.pdf

Voor C# implementatie van fibonacci heap: https://github.com/FransB...ia/Heaps/FibonacciHeap.cs

[ Voor 8% gewijzigd door EfBe op 19-06-2013 08:55 ]

[Verwijderd]

Ik heb even een test case in elkaar gezet. De case bstaat uit 4 delen:
Een class weke voor een delay zorgt.
Een thread welke een random value in een max heap stopt, deze er weer uit trekt, en daarna even wacht.
verschillende threading implementaties
• mutex
• lock-free doublebuffer (niet helemaal lock-free, alleen bij read in de meeste gevallen. Geeft niet noodzakelijk de absolute max terug)
En verschillende max-heap implementaties:
• std::priority_queue
• hashmap achtig ding
• een null / no-op variant die niets doet.


Bij deze test is er een delay gebruikt van 0.01ms, een random value tussen de 1 en de 100, en een initiële grootte van de 'max-heap' van 1.000.000. De grafiek weergeeft het aantal operaties per seconde tov. het aantal threads. Als vergelijking staat er ook een null implementatie tussen. Mijn CPU is een i7-2820QM @ 2.0Ghz (4 cores, 8 threads).


Bij de mutex implementatie is de heap sneller met weinig threads, de hashmap sneller met veel threads. Waarom de performance van de null variant drastisch in elkaar zakt met 5 threads: ik heb geen flauw idee.



Bij de double-buffer gedeeltelijk lock free implementatie is de heap over het algemeen sneller, behalve bij 8 threads. Opvallend is dat de performance van de null versie nu inkakt bij 6 threads...

1:1 vergelijkingen:

Met een heap als achterliggende datastructuur schaalt de double-buffer implementatie stukken beter.


Met een hashmap boeit het niet zo veel.


Met een null datastructuur schaalt de double-buffer variant veel beter, omdat er maar half zo vaak wordt gelockt. (of eigenlijk 33/64 keer zo vaak).

Heeft iemand misschien een verklaring voor die laatste grafiek? Ik snap dat je X latency hebt op een memory-acquire of release vanwege de cache's, maar waarom de performance boven X threads drastisch inzakt zie ik niet.

[Zoijar]

Komt dat niet omdat hyperthreading geen echte cores zijn? Een HT quad core kan maar 4 threads rekeninsentief draaien, geen 8.

[Verwijderd]

Klopt. Maar ik zou verwachten dat door gebruik van HT het aantal 'locks per seconde' juist toeneemt. Synchroniseren met een andere thread op dezelfde core gaat natuurlijk vrijwel instant. Het is juist het synchroniseren met de L1 van een andere core wat traag zou moeten zijn.

Ik kan hier ook niet echt resources over vinden. Waar kan ik vinden hoe deze synchronisatie in het algemeen werkt? Het zal wel verschillen per microarchitectuur.

[ThomasG]

Verwijderd schreef op vrijdag 21 juni 2013 @ 18:26:
Klopt. Maar ik zou verwachten dat door gebruik van HT het aantal 'locks per seconde' juist toeneemt. Synchroniseren met een andere thread op dezelfde core gaat natuurlijk vrijwel instant. Het is juist het synchroniseren met de L1 van een andere core wat traag zou moeten zijn.

Ik kan hier ook niet echt resources over vinden. Waar kan ik vinden hoe deze synchronisatie in het algemeen werkt? Het zal wel verschillen per microarchitectuur.

Vergeet niet dat het wisselen van threads een zekere overhead oplevert. Het is dus absoluut niet zo dat je hoe meer threads je hebt, hoe efficiënter het verloopt. Je kunt niet eindig threads blijven toevoegen. Ik ken jouw implementatie niet, maar waarschijnlijk is je dataset niet groot genoeg om over zoveel threads te verdelen. Je krijgt dan bijvoorbeeld te maken dat je overhead groter wordt dan de winst die het oplevert. De 'kosten' wegen dan niet meer op tegen de 'baten.' In combinatie met hyper-threading kan dit de prestaties sterk beïnvloeden. Omdat het na de enorme val stabiel blijft, ook als je meer threads toevoegt, denk ik dat zoiets het geval is. Maar dat zal je moeten gaan testen.

[Verwijderd]

Er is geen/nauwelijks sprake van 'wisselen van threads'. Dat probleem krijg je pas als er meer processen draaien dan er (virtuele) cores aanwezig zijn, daarom stop ik bij 8.

De test case is zo opgezet dat de max-heap de enige verbinding is tussen de threads. Ik snap dat de winst afneemt naarmate er meer threads worden toegevoegd, maar niet dat je boven een bepaald aantal threads opeens waardeloze performance krijgt.

[ThomasG]

Schakel hyper-threading uit in de BIOS, en vergelijk de resultaten.

[Verwijderd]

Gelukkig kan dat bij mijn laptop



geeft vergelijkbare, maar iets minder drastische, resultaten. Vreemd. Vreemd dat de scaling zo inzakt boven 4 cores met de mutex manier van thread safeness, maar daarna niet meer.

Edit zonder de delay is de lijn gek genoeg een stuk scherper.

double buffer + no-op datastructuur

1 thread:  15.000.000 ops
2 thread:     850.000 ops
3+ thread:    500.000 - 480.000 ops

mutex + no-op datastructuur

1 thread:  18.000.000 ops
2 thread:     300.000 ops
3+ thread:    250.000 ops

Het lijkt me dat, als je boven een bepaald aantal synchronisatiepunten per tijdseenheid komt, de performance drastisch in elkaar zakt. De double buffer variant heeft half zoveel mutexen als de mutex varianten. Volgens de tabel hierboven heb je 1s / 250.000 = 4µs = 8000 clock cycles overhead per lock als je vanuit meerdere threads mutexen gaat lopen trashen. Dat lijkt mij erg veel. Te vergelijking: een RAM access op het traagste ddr1 poepRAM is een factor 10 a 50 minder. Lijkt me niet dat het synchroniseren van een cacheline zo lang mag duren...

Ik las vanmiddag dat de mutex implementatie platformafhankelijk is en er kans bestaat dat hij bij het falen van een mutex de thread meteen in sleep gooit in plaats van even kort te spinlocken. Ik zal morgen eens kijken wat er gebeurt als ik de mutexen vervang door een spinlock.

[ Voor 65% gewijzigd door Verwijderd op 22-06-2013 13:23 ]

[H!GHGuY]

Je CPU schakelt tussen hyperthreads als hij pipeline latency wil verbergen - met andere woorden, als je een memory read doet die lang duurt.

Wat je dus doet:

SMT1	SMT2
neem lock
lees data
SMT switch	SMT switch
	neem lock (-> scheduler)
	context switch
data arriveert
unlock (->scheduler)
	Context switch: resume
verdere processing	neem lock
	lees data
	SMT switch
neem lock (-> scheduler)

enzovoort enzoverder...

Met een spinning mutex zou je dus wel een behoorlijk betere performance kunnen krijgen.

[Verwijderd]

Dat is niet hoe SMT werkt, het heet niet voor niets Simultaneous multithreading. Beide threads zijn simultaan actief. Als de ene thread een ALU bewerking uitvoert kan de andere thread een FPU bewerking doen. In syntetische, non-cache dependant workloads krijg ik ~90% scaling over virtuele threads (van 4 naar 8 threads levert 90% meer performance op). De synthetische workload voert de sinusfunctie in een loopje uit en past derhalve gewoon in L1. (ik neem dan even aan dat de sin() functie uit de std library geen LUT gebruikt)

Er is geen sprake van het 'wisselen van SMT's'. De zijn tegelijkertijd actief, tenzij natuurlijk het OS slechts 1 thread per core schedule't. Het is perfect mogelijk dat 2 threads op dezelfde core tegelijkertijd dezelfde instructie willen uitvoeren. Maar als het aantal FPU's/ALU's/... (doorhalen wat niet van toepassing is) niet toereikend is daarvoor zullen de threads niet tegelijk klaar zijn met die instructie.

---

Ik heb MSDN: Critical Section Objects gevonden, dat zou identiek zijn aan een mutex, maar als de lock mislukt spint hij eerst een aantal keer voordat het OS de thread in sleep gooit.

[H!GHGuY]

I stand corrected - bij een pipeline met enkele execution resources krijg je wel die situatie, maar met meerdere kan er natuurlijk gewoon gescheduled worden - daar zat even een kortsluiting in mijn hoofd.

Enkele andere opties zijn cache thrashing doordat beide SMT threads nu met elkaar in competitie gaan, maar anderzijds denk ik dat je non-spinning mutex inderdaad teveel blockt en dus een gigantische scheduler overhead op zijn dak krijgt. Die cache thrashing lijkt me eerder bij de heap/hash van toepassing.

[Verwijderd]

Ladies and gentlemen, we got him.



Gebruik dus nooit een mutex welke een thread meteen in sleep (WaitForSingleObject) gooit wanneer het locken van een mutex mislukt, als je meer dan een paar duizend keer per seconde de mutex lockt/unlockt.

Hiermee is de slechte scaling uit de eerste grafiek van de TS ook te verklaren.

Als mutex implementatie gebruik ik QMutex op het windows platform, de critical section implementatie is een copy paste van deze bron, welke de windows InitializeCriticalSection gebruikt.


Ter volledigheid: schaling van de verschillende datastructuren/threading implementaties met het gebruik van de windows critsec en een delay van 0.01ms

De conclusie is dat het ondanks de snelle critical section alsnog zin heeft om voor (gedeeltelijk) lock-free variant te gaan. Een max-heap blijkt bovendien beter te presteren dan de hash implementatie. Een andere conclusie is dat het veel belangrijker is om een slimme mutex te gebruiken dan een goede datastructuur. Zeker als je 'work' minder dan een milliseconde duurt.

Source: https://dl.dropboxusercon...72348/code/concurrent.zip.
Benodigdheden: windows en Qt libraries in 64-bit. Vergeet niet NOMINMAX te ergens te definiëren en de debug heap uit te schakelen ( _NO_DEBUG_HEAP = 1 ). Getest met msvc11 x64, bij gebrek aan een 64-bits compilatie van Qt met mingw niet met andere compilers. Als de compiler std::atomic ondersteunt zou het moeten werken.


Edit: de resultaten hierboven zijn met een crit section zonder spin count. Met een spin count van 4k krijg ik in de test zonder delay ~2x hogere performance. Met de heap/hash erbij maakt het bijna niets uit.

Het verschil tussen een mutex en een critical section in windows, is dat een mutex inter-thread communicatie mogelijk maakt, en de crit sec. niet. Wat dat voor verschil maakt is mij onduidelijk, maar het zorgt duidelijk voor een enorm verschil in performance. Gebruik dus altijd een critical section, je kan zelf instellen wat de spin count wordt.

Jammer dat Qt alleen de mutex implementatie gebruikt, niet de critical section.

[ Voor 16% gewijzigd door Verwijderd op 22-06-2013 19:15 ]