NLJUG – Nederlandse Java User Group NLJUG – de Nederlandse Java User Group – is opgericht in 2003. De NLJUG verenigt software ontwikkelaars, architecten, ICT managers, studenten, new media developers en haar businesspartners met algemene interesse in alle aspecten van Java Technology.
Met de komst van grid computing en het oplopende aantal cores per server wordt het steeds belangrijker om taken in Java-code parallel uit te kunnen voeren. Het is één van de focus punten van Java 8. Dit vereist weer nieuwe skills van de Java-programmeur. Een beetje theoretische achtergrond kan dan helpen om door de bomen het bos weer te zien. In dit artikel wordt uitgelegd waarom snelheid belangrijk is en waarom dat niet alleen een kwestie is van een snellere computer kopen. Het artikel eindigt met de complexiteitstheorie voor single core, iets waar mensen met een informatica-opleiding meestal wel bekend mee zijn. Dit dient als basis voor een artikel in de volgende editie van Java Magazine waar dieper ingegaan wordt op werken met meerdere cores.
Belang van snelheid
We verzamelen en verwerken steeds meer data. Tegelijkertijd stellen we steeds hogere eisen aan de snelheid van software. De snelheid van software is belangrijker dan je wellicht zal vermoeden. Er zijn vele onderzoeken gedaan waarbij de snelheid van bijvoorbeeld een website wordt geanalyseerd. Keer op keer komt naar voren dat snelheid erg belangrijk is. Langzamere applicaties worden gezien als minder betrouwbaar[i], minder van kwaliteit[ii], minder interessant[iii] en minder aantrekkelijk[iv]. Ze leiden tot hogere bloeddruk[v], lagere conversie rates[vi] en hogere bailout rates[vii]. Sterker nog, in bekende onderzoeken van Google en Amazon is er een directe relatie met de omzet.
Onderzoeken Google en Amazone
– "Moving from a 10-result page loading in 0.4 seconds to a 30-result page loading in 0.9 seconds decreased traffic and ad revenues by 20%"
– "When the home page of Google Maps was reduced from 100KB to 70-80KB, traffic went up 10% in the first week, and an additional 25% in the following three".
– "Every 100 milliseconds increase in load time of Amazon.com decreased sales by 1%"
Kort door de bocht performance
Hoe zorg je voor een snelle applicatie? Een eenvoudige oplossing is snellere computers kopen. Maar dat gaat nog maar beperkt op. In onderstaande grafiek kun je zien dat de clock speed niet meer toeneemt bij nieuwere processoren. Ook de relative performance die nieuwere, complexere instructies meetelt, neemt nauwelijks nog toe. Dus een nieuwere server is niet noodzakelijk sneller. Het enige wat toeneemt is het aantal cores op de chip. Om gebruik te kunnen maken van die meerdere cores (en daarmee daadwerkelijk ook sneller worden) moet de software in staat zijn verschillende dingen tegelijk te doen (in parallel). Dat gaat niet vanzelf. Wij als programmeurs moeten dus aan de slag.
Figuur 1: CPU's over de jaren heen
Er zijn een paar technieken die daarbij kunnen helpen. Allereerst is het belangrijk op te merken dat er allerlei trucs zijn om de snelheidsbeleving te verbeteren. Grafische user interface elementen als spinners en wachtbalken kunnen helpen om de gebruiker een meer responsieve ervaring te geven. Dit artikel gaat over harde performance verbeteringen: het lijkt niet alleen sneller, maar het is ook echt sneller. Als basis voor complexere ideeën wordt eerst gekeken naar wat we kunnen doen op één enkele machine, met één enkele cpu core. Een volgend artikel gaat dieper in op hoe je meerdere machines of cores kunt gebruiken.
Afbeelding 2: "Pigs in Space"
Om de theorie wat handen en voeten te geven, gebruiken we een voorbeeld applicatie, Pigs in Space. Dit is een eenvoudige simulatie van ruimteschepen, die willekeurig rondvliegen, geïnspireerd op de Muppet Show. Een volledig werkende versie is te downloaden (zie referentiekader). Het enige wat de applicatie hoeft te doen is te voorkomen dat de ruimteschepen door elkaar heen vliegen. Daarvoor hebben we collision detection nodig. Dit is een algoritme dat kijkt of twee ruimteschepen niet dezelfde plek innemen. Om het simpel te houden is de kaart gewoon plat (2-dimensionaal).
Een manier om de collision detection te realiseren is door een kaart bij te houden, waarop schepen aangeven waar ze zich bevinden in de ruimte. Een schip kan dan zien welke plekken op de kaart al bezet zijn. Als die plek bezet is dan zal hij terug moeten (bounce).
boolean[][] map = new boolean[MAP_WIDTH][MAP_HEIGHT];
public void detectCollisions(List<Ship> ships) {
for (Ship s : ships) {
if (s.collidesWith(map)) {
s.bounce(); } s.updateMap(map);
}
}
Een andere aanpak is simpelweg alle schepen met alle schepen vergelijken.
public void detectCollisions(List<Ship> ships) {
for (int i=0; i<ships.size(); i++) {
for (int j=i+1; j<ships.size(); j++) {
Ship a = ships.get(i);
Ship b = ships.get(j);
if (a.collidesWith(b)) {
a.bounce();
b.bounce(); }
}
}
}
Maar welke van deze twee algoritmen is nu 'het beste'?
Complexiteit
De beste manier om te kiezen is door beide versies van deze taak simpelweg te laten draaien en te meten hoe lang ze erover doen. In verreweg de meeste gevallen is dit ook de beste aanpak.
Maar wat als dat niet mogelijk is? Je hebt bijvoorbeeld geen toegang tot exact dezelfde hardware als op productie, of er is überhaupt nog geen keuze gemaakt voor hardware. Misschien is de omgeving wel gevirtualiseerd en deel je de hardware met andere applicaties. Is de kopie van de database die je hebt wel realistisch? Hoe betrouwbaar is die meting dan nog? En wat als we de kaart groter willen maken, of meer ruimteschepen gaan toevoegen? Kunnen we iets fundamentelers zeggen over de snelheid van een applicatie? Iets wat onafhankelijk is van een exacte replica van een productie situatie?
Er is een tak van de informatica-wetenschap, die zich met dit probleemgebied bezig houdt. Formeel heet dat computationele complexiteitstheorie. Het idee erachter is eigenlijk verrassend simpel: je telt het aantal operaties dat je applicatie nodig heeft om een taak uit te voeren. Er wordt dus geen tijd gemeten, maar simpelweg het aantal operaties wordt geteld. En om het een beetje simpel te houden, worden alleen de interessante operaties geteld. Meestal is het zo dat de lengte van een taak afhangt van de hoeveelheid data, waarop die taak werkt. Als we een simpele formule weten te vinden, die vertelt hoeveel operaties je nodig hebt, gegeven een hoeveelheid data, dan hebben we de complexiteit van die taak te pakken. En dat is een handig handvat om iets te zeggen over de relatieve snelheid van een taak ten opzichte van een andere taak, zonder te verzanden in allerlei details.
Voorbeeld
Terug naar de twee algoritmen. Hoeveel operaties worden er in het eerste algoritme ongeveer gedaan? Ergens wordt dit stukje code aangeroepen, de lijst van schepen wordt afgelopen, voor elk schip wordt het object uit de lijst gehaald, een collidesWith() functie wordt aangeroepen, af en toe een bounce() functie en uiteindelijk de updateMap(). Dat af en toe bounce() aanroepen is maar lastig. Laten we maar gewoon het worst-case scenario aannemen, dat hij altijd aangeroepen wordt. Later zullen we zien dat dat niet uitmaakt. Eigenlijk valt het aantal operaties dus uiteen in twee gedeelten: de functieaanroep en een stuk wat per ruimteschip wordt gedaan. Als we het aantal ruimteschepen even n noemen, dan is het aantal operaties (T) dus grofweg te beschrijven als:
T = functieAanroep + n *
( ships.get + collidesWith +
bounce + updateMap )
Al die onderliggende functies hebben natuurlijk ook weer een aantal instructies nodig. Hoeveel instructies precies is niet duidelijk, maar het is in ieder geval een vast aantal, onafhankelijk van het aantal ruimteschepen. Als we al die onderliggende waarden even a en b noemen, dan wordt het een heel stuk simpeler.
T = a + n * b
Wat kunnen we hier nu mee? Nou, twee dingen worden hier duidelijk: hoe meer ruimteschepen, hoe langer het gaat duren. Twee keer zoveel ruimteschepen is bijna twee keer zo lang. En misschien iets minder duidelijk, maar als het aantal ruimteschepen maar groot genoeg is dan maakt die a niet zoveel meer uit: factor b (de collidesWith/bounce/updateMap instructies) gaat dan steeds zwaarder tellen. In de complexiteitstheorie vindt men dit nog teveel typewerk en schrijft men dit op als O(n), omdat voor grote getallen alleen die factor n nog telt. De O staat voor ordegrootte en is een veel gebruikte conventie.
Dezelfde analyse kun je toepassen op het andere algoritme. Ook daar hebben we 'opstartkosten' en een blok dat afhankelijk is van het aantal schepen. Hoe vaak wordt dat binnenste blok nu precies aangeroepen? Dat is even puzzelen, maar dat is n-1 keer de buitenste loop. De binnenste loop wordt gemiddeld n/2 keer doorlopen per iteratie van de buitenste loop.
T = functieAanroep + ships.size +
(n-1) * (n/2) * ( 2*ships.get +
collides_with + 2*bounce)
Ook hier kunnen we het versimpelen:
T = a2 + (0,5 n^2) (b2) + n b2=
a2 + b2 * n + c2 * n^2
Je ziet hier dat T er nu iets anders uitziet. Omdat dit een ander algoritme is, zijn de a's en de b's ook andere getallen, vandaar dat ze nu a2 en b2 heten. Naast een a2 en een b2, is er nu ook een derde factor bijgekomen; c2. Deze c2 is ook afhankelijk van het aantal ruimteschepen, alleen nu niet meer lineair maar kwadratisch. Of nog korter: O(n^2). Oftewel, 2x zoveel ruimteschepen betekent ongeveer 4x zoveel tijd.
Het kan nog steeds zo zijn dat dit algoritme wel sneller is dan het eerste algoritme bij een klein aantal ruimteschepen. Namelijk als de a of b van het map-gebaseerde algoritme veel groter is dan de a2 of b2 van dit object gebaseerde algoritme. Bijvoorbeeld als het initialiseren van die kaart heel veel tijd kost. Maar als het aantal toeneemt, dan zal uiteindelijk het tweede algoritme langer gaan duren. Er is altijd ergens een snijpunt, waarbij de lagere complexiteit van het eerste algoritme gaat winnen.
Keuzes
Dus welke van de twee algoritmen is nu het beste? Hebben we nu genoeg informatie om een keuze te maken? Nee, één ding missen we nog in onze analyse: het geheugengebruik. In het eerste algoritme hebben we een grote dubbele array nodig om de hele kaart in het geheugen te houden. Het tweede algoritme heeft dat niet nodig. Ook het geheugengebruik (M) kunnen we analyseren. Als we aannemen dat de kaart vierkant is met lengte m, dan zie je dat voor het eerste algoritme geldt:
M = map_width * map_height +
n*ships = O(m^2 + n)
en voor het tweede algoritme:
M = n * ships = O(n)
In een tabel ziet dat er als volgt uit:
| Tijd | Geheugen | |
| kaart-gebaseerd | O(n) | O(m^2 + n) |
| object-gebaseerd | O(n^2) | O(n) |
Nu hebben we genoeg om een keuze te maken. Of beter gezegd: nu weten we dat de keuze afhankelijk is van toekomstvisie en context. Hiermee kunnen we dus terug naar de klant.
Als we een kleine kaart hebben en weinig ruimteschepen, dan komt het neer op simpelweg meten. Al die a-tjes en b-tjes die we zojuist hebben weggelaten, die zijn dan het belangrijkst. En die zijn weer afhankelijk van allerlei details: de hardware, de JVM versie etc. Dus we moeten naar de klant en vragen om een goede schatting van de grootte van de kaart en het aantal ruimteschepen, en daarmee gaan testen.
Als de klant terugkomt met een ambitieus plan en het aantal ruimteschepen flink wil gaan uitbreiden, dan is op de langere termijn de kaart-gebaseerde keuze te rechtvaardigen. Maar als de klant met name hele grote kaarten wil hebben, dan kan object-gebaseerde collision detection nog wel eens de enige mogelijkheid worden.
Time/memory trade-off
Je ziet hier dat er eigenlijk een keuze gemaakt moet worden tussen snelheid en geheugengebruik. Dit komt heel vaak voor en wordt meestal een time/memory trade-off genoemd.
Er is een soort wetmatigheid die aangeeft dat hoe sneller het geheugen is, hoe minder je er van hebt. Dus als je als je RAM-geheugen vol raakt, dan moet je terugvallen op andere storage, zoals SSD's of HDD's. Soms gebeurt dat automatisch en soms na refactoring na een pijnlijke OutOfMemoryException. Het kan dan ineens zo zijn dat je applicatie een stuk langzamer wordt.
Aan de andere kant: als je nog geheugen overhebt, dan kun je wellicht je applicatie versnellen door dure operaties te onthouden. Bijvoorbeeld data ophalen over het netwerk of uit een database server kan langzaam zijn. Die data kan je dan ter hergebruik opslaan in een lokale cache of je kunt een deel-resultaat van een ingewikkelde berekening onthouden om die later te kunnen hergebruiken. Dat is het domein van dynamic programming.
Conclusie
Meten is weten. Het profilen van een applicatie op een situatie zo dicht mogelijk bij de productiesituatie is altijd het beste. Complexiteitsanalyse is hierbij een mooie aanvulling. Het biedt houvast wanneer profilen niet mogelijk is en het geeft inzicht wat er gaat gebeuren als de applicatiedata groeit. Het beantwoordt al een klein beetje de vraag: hoe schaalbaar is de applicatie. Om op die laatste vraag een beter antwoord te kunnen geven, moeten we ook de voorspelbare vraag van de klant kunnen antwoorden: wat als we meerdere computers gaan inzetten in plaats van al dat refactoren? En dat is een vraag voor een volgend artikel.
Referenties
http://en.wikipedia.org/wiki/Computational_complexity_theory
http://en.wikipedia.org/wiki/Dynamic_programming
https://github.com/First8/pigsinspace
http://www.first8.nl/pigsinspace-demo-jfall-2013/
[1] "What makes Web sites credible?", Fogg et al. 2001 [2] "Quality is in the Eye of the Beholder: Meeting Users' Requirements for Internet Quality of Service",Bouch, Kuchinsky, and Bhatti 2000 [3] "A psychological investigation of long retrieval times on the World Wide Web", Ramsay, Barbesi, and Preece 1998 [4] "Visitors' flow experience while browsing a Web site: its measurement, contributing factors and consequences", Skadberg and Kimmel 2004 [5] "Frustrating the user on purpose: a step toward building an affective computer", Scheirer et al. 2002 [6] "Boosting Online Commerce Profitability with Akamai", Akamai 2007 [7] "Designing Web Usability", Nielsen 2000