Benchmark av String, StringBuffer samt java.util.Vector (VARNING: LÅNG!)

Hej!

Jag har blivit väldigt intresserad av att optimera Java-kod. Jag har gjort några enklare tester med bl a operationer på klasserna String och java.util.Vector. resultaten visar att man faktiskt kan spara mycket tid om man gör saker på rätt sätt, dvs att man använder rätt metod för rätt uppgift.

Dessa tester är visserligen extrema, men detta för att man ska kunna se en skillnad.

Resultaten är givetvis inte "spikade". Det beror på så många faktorer, dels hur snabb dator du har och dels hur många program du har aktiva (hur mycket processor-kraft går till andra saker). Givetvis kan även JVM:n skiljas åt i prestanda.

Det finns säkert andra saker man måste ta hänsyn till. Värden jag fick fram i testet kan ses som riktgivande.

Detta test är utförd på en iBook G4 @ 800 Mhz med 640 Mb RAM och under Mac OS X 10.3.8 och med Apples JVM 1.4.2_05.

Test 1:

Första testet gick ut på att undersöka prestanda-skillnad på skapande och användande av String-objekt och StringBuffer-objekt.

Varje test kördes 10 gånger. Resultatet för varje omgång summerades och ett medelvärde räknades ut. Alla resultat redovisas i millisekunder (ms) om inte annat anges.

1a) StringBuffer

StringBuffer buf = new StringBuffer();

for(int i = 0; i < 500; ++i)
{
	buf.append("a");
}

Resultat: 2.2 ms

1b) String

for(int i = 0; i < 500; ++i)
{
	str += "a";
}

Resultat: 31.4 ms

1c) String. Ett nytt String-objekt skapas inuti loopen.

for(int i = 0; i < 500; ++i)
{
	String a ="a";
	str += a;
}

Resultat: 58.4 ms

Här kan vi tydligt se att slår man ihop en massa String-objekt i koden så kan det löna sig att använda StringBuffer i stället. Det kan verka lite bökigt om man är van med att konkatenera Strings med +-tecknet men man korta ned exekeveringstiden för metoderna avsevärt i vissa fall.

Sedan ser vi att 1c är långsammast av dessa tre sätt. Varför? Jo, det kostar att skapa nya objekt. Det skapas ett nytt objekt under varje varv i loopen.

Glöm inte att String är immutable, dvs innehållet går inte att ändra på. Har ni t ex

String t = "hej";

t = "på dig";

så skapas det faktiskt två objekt. Så egentligen skapas det två objekt i 1c medan det bara skapas skapas i 1b.

Ni ser att loopen stannar vid värdet 500. Jag testade att ha 50000 på min dator. 1c tog hela 3337000 ms, dvs över 333 sekunder medan 1a bara tog ca 90 ms. 1C gav lite mysko värden.

Test 2 Vector.

Vector v = new Vector();

Jag lägger till 80000 element i v ("a")

2a) v.size() i for-loopen

size = v.size();
for(int i = 0; i < size; ++i)
{
			
}

Resultat: 8-10 ms

2b) v.size() utanför for-loopen

for(int i = 0; i < v.size(); ++i)
{
			
}

Resultat: 0-1 ms

Skillnaden mellan dessa två är att i 2a anropas inte Vector.size() i varje varv.
Det är bättre att anropa metoden en gång och lagra returnerade värdet i en int och använda den i loopen.

2c) Iterera loopen 10000 gånger och under varje varv ta bort första elementet.

v.remove(0);

Resultat: 8000 ms

2d) Iterera loopen 10000 gånger och under varje varv ta bort sista elementet.

v.remove(v.size() - 1);

Resultat: 10 ms

Varför så stor skillnad mellan ac och 2d?? Jo, i 2c tas första elementet bort och då måste Vectorn skyffla alla element ett steg. Tar man däremot bort det sista elementet så behöver ingen skyfflande av data ske. Implementerar ni t ex en Connection Pool för databas-objekt som ni lagrar i en vector så bör ni köra med LIFO (Last In First Out).

I 2c körde jag med v.size() för att bestämma storleken på Vectorn. Jag skulle kunna byta ut det mot t ex en räknare som minskar värdet med 1 under varje varv och anropa v.size() just innan loopen. Detta för att slippa anropa v.size() hela tiden.

Test 3 Jämförelse av Strings. Är de exakt lika?

Testerna kördes 50 gånger och i varje test itererades ett for-loop 500 000 gånger. Ett medelvärde räknades.

String a = "abcdefghijk";
String b = "abcdefghi";

3a) equals(Object)

a.equals(b);

Resultat: 36.14 ms

3b) equalsIgnoreCase(Object)

a.equalsIgnoreCase(b);

Resultat: 78.32 ms

3c) compareTo(String)

a.compareTo(b);

Resultat: 126.24 ms

3d) compareToIgnoreCase(String)

a.compareToIgnoreCase(b)

Resultat: 578.02 ms (!!)

Det blev ganska stor skillnad mellan 3a och 3d.

SLUTORD:

Detta är inte ett professionellt test, utan jag ville mer se hur man böra göra. Testerna kan säkert göras mycket bättre.

Jag tycker vi borde ha en tråd där folk kan dela ut sina tips & tricks för att snabba upp kod. Det behöver inte vara kompletta program. Det räcker oftast med endast några rader kod.

Ni får gärna kommentera. :)

Spännande! Är ju svårt att få exakta siffror på ett vanligt system, men det där är väl antagligen en fingervisning.

Rent allmänt för såväl java som i till maskinkod kompilerade språk så är det inte alltid den kortaste och vackraste koden som vinner i prestanda, utan det hänger mer på hur mycket minnet får jobba mot cachen. I sammansatta datatyper döljs ofta en hel del overhead. Vill man vara riktigt prestandatänkande är det smart att bygga koden i efter minnesblock-anpassade scope och undvika att vandra utanför scopet genom upprepande metodanrop, globala variabler och dyl. samt att helst hålla sig till primitiver. Å andra sidan väljer man antagligen inte Java för prestandans skull ;)

Intressant :)

Jag skulle vilja anmärka några saker. Först på 1b. Följande två for-loopar är nämligen identiska (sett till hur det blir efter kompilering):

// Variant 1
String str = "";
for (int i = 0; i < 500; ++i) {
    str += "a";
}
// Variant 2
String str = "";
for (int i = 0; i < 500; ++i) {
    StringBuffer bf = new StringBuffer(str);
    bf.append("a");
    str = bf.toString();
}

Alla operationer som görs på strängar med + och += resulterar i ett bröte med StringBuffers i bakgrunden, så varje varv skapar åtminstone fyra nya objekt (en StringBuffer samt en char[] som den lagrar sin data i, plus en String som även den har en char[] som data lagras i internt). Eventuellt blir StringBufferns char[] tvungen att omallokeras vid append, men det är väl en risk man får leva med, annars kan man ge en ursprunglig storlek på buffern med int-konstruktorn: StringBuffer bf = new StringBuffer(1024);

Intressant att veta kan även vara att det finns en ny variant på StringBuffer sedan 1.5, som torde vara effektivare (men inte trådsäker): StringBuilder. Den ska tydligen dela superklass med StringBuffer, men den superklassen är av okänd anledning begränsad till java.lang-paketet, så att den inte är åtkomlig utifrån.

2a vs. 2b visar ju att det faktiskt är snabbare att anropa size() i stället för att lagra undan det i en variabel, inte sant? Jag skulle gissa att med en intelligent JVM är skillnaden noll och intet. Sen ska man förstås normalt använda iteratorer i stället för indexering, om man inte har RUSKIGA prestandaproblem och loopar igenom en lång lista ofta :)
Dessutom ska man inte använda Vector längre, utan ArrayList, om man inte behöver trådsäkerheten. ArrayList är effektivare eftersom den inte är synkroniserad.

2c vs. 2d visar vikten av att använda rätt algoritm på rätt ställe. En länkad lista (eller deque, för den delen, men det finns av någon anledning inte i collectionsbiblioteket) hade gjort bättre ifrån sig i 2c utan att förlora lika mycket i 2d.

Ajdå, det är faktiskt sanbbarae att bryta ur size() ut forloopen, tyvärr så har de två värden av misstag bytt plats, dvs for-loopen med v.size() tog 8-10 ms.

Rätt så liten skillnad, om man utgår från att loopen itererade 80 000 gångern, men... :)

Jag ska senare köra lite fler tester och se hur mycket effektivare en ArrayList är.

Jag är inte så jätte insatt, hur JVM själv optimerar kod, men det är intressant.

Det känns roligt att hitta en bra lösning.

Jag gjorde en simpel test med ArrayList.
Lagrade 800000 Strings-objekt i den och plockade fram varje element i en for-loop.

Gjorde samma sak med en Vector.

Körde samma test några gånger:

Vector: 68 ms
ArrayList: 177 ms

Jag får precis motsatta siffror, om man kör ett test som inte lär kicka igång GC:n:

[gustaf-c@triton slask]$ cat bmklist.java
import java.util.*;

class bmklist{

    public static void main (String[] args){

        final String s = "foo bar";
        Vector<String> v = new Vector<String>(10);
        ArrayList<String> a = new ArrayList<String>(10);

        System.out.println("Starting Vector test...");

        long beforeV = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++){
            for (int j = 0; j < 10; j++)
                if (i % 2 == 0) // add
                    v.add(s);
                else // remove
                    v.remove(9 - j);
        }
        long afterV = System.currentTimeMillis();

        System.out.println("Starting ArrayList test...");

        long beforeA = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++){
            for (int j = 0; j < 10; j++)
                if (i % 2 == 0) // add
                    a.add(s);
                else // remove
                    a.remove(9 - j);
        }
        long afterA = System.currentTimeMillis();

        System.out.printf("Vector: %d ms\n", afterV - beforeV);
        System.out.printf("ArrayList: %d ms\n", afterA - beforeA);

    }

}
[gustaf-c@triton slask]$ java bmklist
Starting Vector test...
Starting ArrayList test...
Vector: 182 ms
ArrayList: 77 ms

Dock förlorar den listtypen som kör först alltid några millisekunder på jit:en eller nåt liknande, kör man ArrayList först och Vector sen får ArrayList oftast runt 90 ms och Vector c:a 170 ms.