Waarom een blog over de performance van arrays in java? Ze zijn bijzonder saai, en wanneer heb je ze eigenlijk nodig?

De enige (actieve) herinnering aan arrays in een echte codebase die ik heb, ging over een situatie dat je eigenlijk multiple return parameters zou willen hebben (zoals in python), of (door de taal ondersteunde) tuples (zoals in rust). Als ik nu in een review een methode met Object[] als return parameter zou zien, zou dat tot kamervragen leiden.

Niet heel erg opzienbarend

In een vorige blog had ik al geschreven over de slechte performance van java.lang.reflect.Array. In een poging daar een beter alternatief voor te maken stuitte ik op een paar onverwachte eigenaardigheden.

Arrays zijn sinds java 1.0 niet veranderd. Dat is logisch gezien het feit dat ze een standaard onderdeel zijn van de meeste talen en het feit dat java altijd backwards compatible is gebleven. En, tja, java uit die tijd, is, soms apart of anders gezegd C-achtig.

3 manieren om een multidimensionele arrays te instantieren

1. int[][] array = new int[3][2]; // ok..
2. int[] array[] = new int[2][2]; // doet denken aan C pointer notaties
3. int[][] array = new int[5][]; // WTF?

Wat betekent optie #3?

En hoe kan dit werken?

String[][][] array = new String[1][1][1];
array[0] = new String[2][1];

Ik kon het antwoord niet vinden na een paar keer googelen, maar ik stuitte wel (weer) op Jol. Nadat ik de jol-cli had geinstalleerd (werkt het best op linux), zag ik het volgende:

Jol is een tool om de internals van java objecten te bestuderen. De manier om dit te doen voor een 2-dimensionele String array te doen is:

java -jar jol-cli.jar internals "[[Ljava.lang.String;"

Wat een rare schrijfwijze! [[L en ; zijn onderdeel van de interne weergave van java objecten, maar dan met '/' in plaats van '.'. Niet toevallig is dit wel precies de manier om Class.forName te gebruiken voor arrays (want dat is wat jol doet). Ik wist het niet, dus ik neem aan jullie ook niet.

En wat is de conclusie?

In een multidimensionele array is er maar één array-lengte en dat is de ‘buitenste’

Dus String[1][1] is eigenlijk String[1][]. Elke element van de buitenste array is een 1-dimensionele array, van willekeurige lengte! Weg zijn je runtime bounds checks (C-achtig dus)! En dus kan bovenstaande code, die een array van lengte 2 toekent aan het eerste element van array[1][1][1] gewoon werken.

There are no true multi-dimensional arrays in Java, just arrays of arrays. This is why int[][] is a subclass of Object[]. If you need a large multi-dimensional int[] in Java, it is a bit more efficient to allocate a large int[] and calculate the offset yourself. However, make sure to, if possible, navigate the int[] in such a way that 64 bytes at a time can be read. That is a lot more efficient than jumping around. Heinz Kabutz

De achtergrond voor dat laatste is caching en prefetching. Gewoon RAM geheugen is traaag. Het is dankzij de L1/2/3 caches dat processoren nog een beetje presteren, als ze iets uit geheugen willen lezen. Dat gaat het best, als je in batches gelijk meer data op kan halen. De volgende read kun je het dan uit de cache halen. Dit voordeel wordt extra groot door prefetching, als de cpu probeert te voorspellen wat je next move read zal zijn. Dit zorgt dat het uitmaakt, hoe je door een n-dimensionele array loopt (n>1).

Hoe groot is eigenlijk het voordeel van CPU caching en prefetching?

Over deze vraag ben ik gestruikeld en in een konijnenhol gevallen van microbenchmarking. Uiteindelijk heb ik de metingen op mijn apple M2 allemaal opnieuw gedaan op een standaard Amazon linux AMI, vooral omdat die beter te generaliseren zijn.

Je vriend, de JIT compiler wordt je vijand als je gaat benchmarken. In eerste instantie had ik een performance verbetering van 1342%, maar dat had er waarschijnlijk mee te maken dat er code weggeoptimaliseerd werd.

Dit is de uiteindelijke code:

@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public long classicArrayGetTDLR() {
    long t = 0;
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            t += intArray[r][c];
        }
    }
    return t;
}

TDLR staat voor Top Down (buitenste loop), Left Right. Deze volgorde doorloopt eerst de binnenste array (1 rij) en gaat vervolgens naar de volgende rij. LRTD gaat voor 1 kolom door elke rij en dan naar de volgende kolom.

Amazon Intel(R) Xeon(R) CPU E5-2676 v3 @ 2.40GHz

Wow, 10x zo snel! Dat is precies wat simondev zegt. En wat ik niet kon reproduceren op mijn M2. Daar is het ongeveer een factor 2.

Caveat: Zolang je niet weet wat de performance verhouding is tussen de array lookup en de sommatie, weet je ook niet wat de percentuele performance verbetering is van prefetching tijdens het itereren.

Een ander aspect van het citaat van Kabutz is de suggestie dat je met een 1-dimensionele array meerdimensionele kunt simuleren en wellicht met betere performance. Een eerste implementatie die ik had gemaakt voor arrays met elk mogelijk aantal dimensies was niet sneller als je alleen naar TDLR kijkt.

Ok, en een specialistische voor 2 dimensies?

Zoals dit?

public int get(int row, int col) {
    return data[row * this.cols + col];
}

public void set(int row, int col, int val) {
    data[row * this.cols + col] = val;
}

Dat maakt dus niet uit.

Conclusie

Zelf je indexen berekenen heeft alleen zin als je om de één of andere reden niet van caching of prefetching gebruik kunt maken. Bijvoorbeeld als je willekeurige (niet door de cpu voorspelbare) pixels in een plaatje aan zou passen.

En write acties dan?

3 tot 4x zo snel, afhankelijk dan de implementatie. Zelf indexen berekenen is hier kennelijk wel iets sneller.

–> Mijn advies zou zijn, om zelf te testen op de doelarchitectuur (niet je eigen laptop), als je wil weten hoe het voor je organisatie uitpakt.

compiler blackholes

Hoe voorkom je dat de JIT compiler je dode benchmark code wegcompileert?

1. neem een return parameter op (zie voorbeeld)
2. gebruik compiler blackholes (vanaf java 17)

JMH zorgt dat de return parameters in een zwart gat verdwijnen. Dit voorkomt ongewenste optimalisatie, maar heeft zelf wel een eigen performance impact en als response tijden klein zijn, gaat die overheersen.

Compiler blackholes zorgen ervoor dat je benchmark code niet als dode code wordt opgeruimd, maar dat de aanroep naar de JMH blackhole wel weg-geoptimaliseerd wordt, zodat je een zo zuiver mogelijke meting krijgt.

java -Djmh.blackhole.mode=COMPILER -jar benchmark.jar

Saai??

Om terug te keren naar het begin van dit artikel. Zijn arrays saai? Ze worden niet veel gebruikt, dat wil zeggen, niet door jou! Maar in de JVM zijn ze essentieel voor String, HashMap en ArrayList, oftewel de drie meest voorkomende classes in elke JVM instantie.

Dus als je door een String, of een ArrayList zoekt, maakt het uit, hoe je dat precies doet. En het verschil is groot genoeg om je er bewust van te zijn. En het is trouwens ook precies de reden dat je vrijwel nooit een LinkedList moet gebruiken, want dan krijg je gegarandeerd nooit het voordeel van prefetching. Zie deze video van Bjarne Stroustrup over waarom het algoritmische voordeel van LinkedList achterhaald is. Een poll op LinkedIn liet zien dat 99% van de java-mensheid er nog in gelooft.

Zelf doen?

git clone https://github.com/shautvast/arraybench
mvn clean package
java -Djmh.blackhole.mode=COMPILER -jar target/benchmark.jar