Performance and behavior analysis of concurrent queues with iterator.

I modern utveckling av hårdvara ligger det stort fokus på att producera processorer med fler och fler kärnor. Därmed behöver även mjukvaran utvecklas för att på bästa sätt utnyttja all denna parallella potential. En stor del av detta är då att kunna dela data mellan flera parallella processer, vilket uppnås med hjälp av parallella samlingsdatatyper. En vanlig operation på samlingsdatatyper är att iterera denna. Studiens mål var att analysera prestanda och beteende hos ett flertal kända algoritmer för iteration av datasamlingen kö. Även hur olika förutsättningar kan påverka iteratorns prestanda har värderats. Några exempel på dessa förutsättningar är antalet arbetstrådar som arbetar mot kön, initial storlek hos kön samt olika pinning strategier. Initial storlek beskriver hur många element som befinner sig i kön vid experimentens start och pinning strategi beskriver vilken kärna varje tråd skall binda sig till. Vissa iterator algoritmer lämnar garantier för att det tillstånd som returneras är ett atomiskt snapshot av kön. Ett atomiskt snapshot är en ögonblicksbild av hur kön såg ut vid någon fast tidpunkt. På grund av detta har det även varit ett mål att mäta hur stor kostnaden är för att få denna garanti. Utöver detta har prestandan hos enqueue och dequeue operationerna för respektive kö testats för att få en helhetsblick över köns prestanda.För att mäta prestandan har ett benchmarkprogram implementerats. Detta benchmarkprogram förser ett gränssnitt för samtliga köer att implementera, och kan utefter detta gränssnitt testa prestandan hos kön. Programmet kör mikrobenchmarks som mäter prestandan hos varje enskild operation hos kön. Det sätt som kön pressas på under dessa benchmarks är inte realistiskt för hur kön kan tänkas användas i skarpt läge. Istället mäts prestandan vid högsta möjliga belastning. Detta görs för att enklast kunna jämföra prestandan mellan de olika köerna.I studien har prestandan hos fyra köer med iteratorer testats, experimenten är utförda i C# med .NET 4.5 i en Windows miljö. Den parallella kö som finns i .NET biblioteket var en av köerna som testades. Dels för att det är intressant att se hur väl Microsoft optimerat denna, men också för att få en utgångspunkt att jämföra med de andra testade köerna. Michael och Scotts kö har även den testats, med två stycken olika iteratorer tillagda. Dessa är Scan and Return och Double Collect. Även en parallell kö framtagen med hjälp av universella metoder för att konstruera paralllella dataobjekt från sekventiella, baserad på den immutable kö som finns i .NET biblioteket har testats. En immutable kö är en kö som inte kan modifieras efter initiering.Resultaten från utförda benchmarks visar att Michael och Scott kön med Scan and Return iteratorn är den snabbaste på iteration, med Double Collect iteratorn som tvåa. Snabbast enqueue och dequeue operationer hittas i .NET bibliotekets parallella kö. Kön som bygger på immutable visar sig vara långsammast vad gäller iteration i de flesta fall. Den är även långsammast vad gäller enqueue och dequeue operationerna i samtliga fall. Kostnaden för att få en garanti för ett atomiskt snaphot mäter vi i skillnaden mellan Scan and Return och Double Collect iteratorerna. Detta på grund av att dessa är de två snabbaste iteratorerna och Scan and Return inte lämnar garantin medan Double Collect gör det. Denna kostnad visar sig vara relativt stor, Scan and Return presterar upp emot tre gånger så snabbt som Double Collect.Med hjälp av resultaten från denna studie kan nu utvecklare göra väl informerade val vad gäller vilken kö med iterator algoritm de skall välja för att optimera sina system. Detta kanske är som viktigast vid utveckling av större system, men kan även vara användbart vid mindre.Program: Systemarkitekturutbildninge