Prestanda

Tänkte börja med att berätta att projektet nu har återtagit sitt gamla namn Tetris Analyzer och även flyttat till GitHub. Anledningen är att det under en längre tid inte gått att ändra namn på SourceForge och att jag ville gå från Subversion till GIT. Google Code var också ett intressant alternativ men saknar stöd för GIT.

Optimera koden - första försöket
Fokus har sedan förra inlägget varit att förbättra prestandan på programmet. Efter att ha optimerat den befintliga koden var det ändå långt kvar till målbilden på 10.000 bitar per sekund. Jag bestämde mig i det läget för att leta efter en bättre algoritm. Då jag skrivit ett antal olika Tetris-varianter genom åren hade jag en ganska klar bild över hur detta kunde göras. Ambitionen nu var att prestandaoptimera koden så hårt som möjligt.

Lilla optimeringsskolan
Min erfarenhet av prestandaoptimering är att om man vill uppnå maximal prestanda och har gott om tid bör man gå till väga ungefär så här:

• Tänk förutsättningslöst och använd din fantasi, kreativitet och erfarenhet.
• Ställ dig frågan: hur skulle den snabbaste lösningen kunna se ut? Svaret på frågan kanske inte går att implementera i praktiken men är något varifrån man kan plocka idéer.
• Försök föreställa dig, eller mät om det går, vilka delar som tjänar mest på att optimeras. Svaret är nästan alltid innerlooparna då den koden genomlöps flest gånger.
• Föruträkna! Att räkna ut saker på förhand är ofta en bra strategi då den kan ta bort instruktioner från innerloopar och flytta kod till block som inte genomlöps lika ofta. Inte sällan räcker det med att göra denna föruträkning en gång, och det är inte ens säkert att den behöver göras när programmer körs utan kan i vissa fall laddas in som "färdigt data" om så skulle behövas.
• Det är ofta bra att ha nära beroenden mellan de klasser som opererar i en innerloop, vilket går emot vad man vanligtvis rekommenderar. Detta är bra då man kan hitta lösningar där klasserna kan sammarbeta och servar varandra på ett optimalt sätt. Det är bra att försöka begränsa mängden kod som är hårt optimerad då den vanligtvis är svårare att sätta sig in i och underhålla.
• Fundera kontinuerligt på om det går att förfina befintlig eller hitta en bättre algoritm och om så är fallet och det är ekonomiskt och tidsmässigt motiverat, skriv om koden! 

Optimera koden - andra försöket
Jag började med att att försöka refaktorera den befintliga koden men insåg ganska snart att den nya klasstrukturen skilde sig så mycket från det jag hade att det gick snabbare att skriva om allt från början. Endast delar av test-suiten gick att återanvända och det var endast ett fåtal klasser vars tester i stort sett var opåverkade bl.a BoardTest och GameTest (vilket var ytterligare ett argument för att skriva om i stället för att refaktorera). En gemensam nämnare för dessa tester är att de lyckats testa beteende och inte behövt bry sig om implementationsspecifika detaljer. Detta är något att sträva efter när man skriver tester!

Den nya koden inriktade sig framför allt på dessa delar:

• Optimera representationen av Board, bl.a genom att skippa hanteringen av färger som varken behövs vid uträkning av giltiga flytt eller vid evaluering av brädet (som utförs av TengstrandBoardEvaluator1) och dels genom att utföra bit-operationer som kan operera på fler "pluppar" åt gången (en bit består av fyra pluppar).
• Få en tajtare koppling mellan klasserna Piece och Board där deras inre representationer kan samverka på ett bra sätt. Lösningen här blev att skapa klassen PieceMove som kan utföra alla nödvändiga operationer mot Board. Varje instans av PieceMove är föruträknad för att jobba mot en Board av en viss storlek (normalt 10x20). Den utnyttjar även att den känner till Boards interna representation så att den kan utföra snabba AND- och OR-operationer (tajt koppling). Denna lösning utnyttjar både föruträkning och hård koppling.
• Föruträkna alla giltiga flytt och rotationer som en bit kan utföra på en tom Board av en viss storlek med givna regler (ValidPieceMovesForEmptyBoard). Regler kan t ex vara i vilken startposition biten har eller huruvida sliding* är påslagen. När denna del väl är föruträknad kan alla villkor tas bort från koden som utför förflyttning av en bit (ValidMoves).
• Använd snabbast möjliga datatyper och kollektioner vilket i Scala visar sig ofta vara Array då de kompilerar till Java arrayer (gäller för listor som inte behöver växa dynamiskt)

(*) När sliding är påslagen kan man rotera biten fritt över hela brädet men om den är avslagen kan den endast rotera och flytta sig fritt på översta raden och måste därefter droppas rakt ned till "marken".

För att summera upp det hela ska man först koncentrera sig på innerlooparna och därefter hitta en bra algoritm som stödjer detta. Använd föruträkningar och hårda kopplingar mellan klasser i innerlooparna.

Resultat
När jag körde den optimerade koden visade det sig att den nu gjorde 6.100 bitar per sekund vilket i och för sig var en fördubbling men som tyvärr inte träffade min målbild på 10.000 bitar/sek. För att ha något att jämföra med, tog jag fram en version i Java som följde exakt samma algoritm som Scala-versionen. Vid testkörning gjorde den smått imponerande 15.800 bitar per sekund! Då båda språken kör på samma JVM låg det en hund begraven någonstans! Nu började arbetet att gräva upp och avlägsna denna objudne gäst. Steg ett var att identifiera vilka delar av koden som tog längre tid i Scala än i Java.

Jag började med att mäta tidsåtgången i de olika delarna av koden och hade hela tiden Java-versionen att jämföra med. Ganska snabbt kunde jag se att huvudproblemet låg i klassen TengstrandBoardEvaluator1. Jag använde nu Jad för att decompilera Scala-versionens bytekod till Java. Till min glädje hade all användning av Array gjorts om till "riktiga" Java-arrayer. Det som ur prestandasynpunkt inte såg lika bra ut var for-looparna. Scalas for-loopar är implementerat som en intern DSL och upplevs som en naturlig del av språket, men är inte lika "lågnivå" som i Java. Jag testade då att ersätta alla for-loopar i TengstrandBoardEvaluator1 med while-satser (som efter ändringen såg ut så här). Voala! Nu exekverar programmet plötsligt i en hastighet av 14.700 bitar per sekund! Koden blev lite fulare med while-satser i stället för for-loopar men är ändå ett billigt pris att betala denna gång. En klart godkänd förbättring från de ursprungliga 2.200 bitarna per sekund.

Här följer en sammanfattning av prestandan för de olika versionerna:

Språk	Sliding på (bitar/sek)	Sliding av (bitar/sek)	Repository	Version
Scala	2.000	2.200	SourceForge	Första versionen
Scala	2.500	2.900	SourceForge	Första versionen med optimerad TengstrandBoardEvaluator
Scala	2.800	6.100	GitHub	En andra helt omskriven version, TengstrandBoardEvaluator1 ej optimerad
Scala	3.700	14.700	GitHub	En andra helt omskriven version med optimerad TengstrandBoardEvaluator1
Java	5.000	15.800	GitHub	Version i Java

Den andra varianten, den som gör 2.900 bitar per sekund, har jag lagt med för att kunna jämföra hur stor prestandaskillnad som själva omskrivningen till ny algoritm utgör. Vi kan se att programmet gått  från 2.900 till 14.700 bitar per sekund efter omskrivning till ny algoritm!

Då jag genomgående valt de snabbaste lösningarna jag hittat, har den resulterande koden inte andats så mycket Scala utan har mer sett ut som C++ eller Java. Målet framöver är att försöka höja abstraktionsnivån och få den att kännas mer som Scala!