tifyty

pure Java, what else ?

StringBuffer és StringBuilder

Az a cikk arról szól, hogy mennyivel gyorsabb a StringBuilder, mint a StringBuffer, és mikor melyiket érdemes használni. Seniorok számára nem lesz benne újdonság, talán a mérések eredménye hordoz némi tanulságot.

Amikor a Java-t tanuljuk, akkor szigorúan a fejünkbe verik, hogy a String az bizony immutable, és a string konkatenáció az ördögtől való, eszi a memóriát, másolgatja a stringet a memóriában ide-oda, új objektumokat hoz létre, és ez így igaz is. Amikor nem csak éppen két stringet akarunk konkatenálni egy Exception üzenet összerakására, amikor a program futásának már úgyis annyi, és ezért a teljesítmény sem különösebben érdekes akkor ott van a StringBuffer és a StringBuilder.

Mi különbség a kettő között?

A StringBuffer támogatja a multi-thread hívásokat, míg a StringBuilder nem. Ettől eltekintve teljesen kompatibilis a két osztály, api szinten ahol az egyik használható, ott használható a másik is. A metódusok azonban a StringBuffer-ben synchronize-áltak, és ez azt jelenti, hogy különböző szálak használhatnak biztonsággal közös buffert, de ugyanakkor minden metódushívás előtt és után a változók értékeinek szinkronizálása a memória és a processzor regiszterek és a processzor cache között megtörténik. Ez valamennyit lassít a futáson. Persze valamit, valamiért.


A StringBuffer a Java 1.0 verzióban már megjelent, míg a StringBuilder csak az 1.5-ben. Miért nem jelent meg rögtön az 1.0-ban mind a kettő, illetve miért a szinkronizált változat volt az első? Biztos válasz erre nincs, hiszen ez egy olyan döntés, amit a Java tervezői és fejlesztői hoztak, és ha csak valahol egy jegyzőkönyvben le nem írták, hogy miért döntöttek úgy, hogy a StringBuffer szinkronizált legyen, akkor valószínűleg már senki nem emlékszik rá.

De képzeljük magunkat egy pillanatra 1996. január 23. elé (ekkor jött ki az 1.0 Java), és tegyük fel a kérdést: legyen-e szinkronizált a tervezett StringBuffer minden metódusa? Mit is jelentett ekkor a szinkronizáltság? Azt amit ma? Nem egészen. Elvileg ugyan igen, de erősen máshol voltak a hangsúlyok. A szinkronizált metódusokba nem léphet be párhuzamosan két szál. Ez nem gond, mert a StringBuffer esetében ez baj is lenne. Akkor már inkább jobb, ha az egyik száll megáll, a másik meg vár, mintha egy rosszul megírt multi-thread program összekutyulja a buffert, aztán szidják a Java-t, hogy az szar. (Amúgy akkor még elég szar volt, de ez már a mellékvágány mellékvágánya lenne.) A másik dolog, hogy többprocesszoros rendszerekben a processzor cache és regiszterek szinkronizálását a memória felé el kell végezni, hogy ha a buffert egy másik processzoron futó szál piszkálta utoljára, akkor is jó állapottal tudjon a mi szálunk dolgozni. Ez akkoriban, amikor a 600MHz Alpha processzorok voltak a csúcstartók, és Linux még nyolc évre volt attól, hogy igazán elfogadhatóan fusson többprocesszoros gépen nem sok mindenkit érintett. A Java történet nem arról szólt, hogy mennyire jó, hanem arról, hogy életben marad-e egyáltalán.

Nézzük meg a gyakorlatban, hogy milyen sebesség különbségek lehetnek az egyes string kezelési megközelítések között. Vegyünk egy nagyon egyszerű példát: Vegyünk ki minden felesleges szóközt egy stringből. Más szavakkal, ahol egymás után több szóköz van, ott azokat cseréljük le egy szóközre.

Ez a feladat különösen kedves a szívemnek, mert először a BME-n jelent meg nyomtatásban a Z80 programozás jegyzetemben.

Az első megoldásban használjunk String-eket és reguláris kifejezéseket:

	public static String unspacerRegEx1(final String in) {
		String returnValue = in;
		Pattern pattern = Pattern.compile("^(.*)(\\s\\s)(.*)$");
		Matcher matcher = pattern.matcher(returnValue);
		while (matcher.find()) {
			returnValue = matcher.group(1) + " " + matcher.group(3);
			matcher = pattern.matcher(returnValue);
		}
		return returnValue;
	}

Ez a lehető legrosszabb megoldás, sem nem olvasható, sem nem hatékony. Már algoritmus szinten sem. Javítunk rajta, hogy ha nem két hanem több szóköz van egymás után, akkor azt egyszerre ismerje fel:

	public static String unspacerRegEx2(final String in) {
		String returnValue = in;
		Pattern pattern = Pattern.compile("^(.*)(\\s\\s+)(.*)$");
		Matcher matcher = pattern.matcher(returnValue);
		while (matcher.find()) {
			returnValue = matcher.group(1) + " " + matcher.group(3);
			matcher = pattern.matcher(returnValue);
		}
		return returnValue;
	}

Tovább javíthatunk a dolgon, ha nem rakjuk össze a részeredmény stringeket, hanem balról jobbra haladva érjük el az eredményt:

	public static String unspacerRegEx3(final String in) {
		String returnValue = "";
		Pattern pattern = Pattern.compile("(.*?)\\s\\s+");
		Matcher matcher = pattern.matcher(in);
		int end = 0;
		while (matcher.find()) {
			returnValue += matcher.group(1) + " ";
			end = matcher.end();
		}
		returnValue += in.substring(end);
		return returnValue;
	}

Persze továbbra is kétségeink lehetnek, hogy ez megfelelő megoldás-e, de azt várjuk, hogy lényeges sebességnövekedés érhető el, ha a string elég nagy. De még nagyobb hatékonyságnövekedést érhetünk el akkor ha megtaláljuk a reguláris kifejezésekhez használhatü replaceAll() metódust:

	public static String unspacerRegEx4(final String in) {
		Pattern pattern = Pattern.compile("\\s\\s+");
		Matcher matcher = pattern.matcher(in);
		String returnValue = matcher.replaceAll(" ");
		return returnValue;
	}

… és persze kísértést érezhetünk arra is, hogy a String osztályban definiált azonos nevű metódust használjuk:

	public static String unspacerString(final String in) {
		return in.replaceAll("\\s\\s+", " ");
	}

Ez nagyon egyszerű megoldás, tiszta, világos, olvasható. Általánosságban (és a mérési eredmények ismeretében) az is az *általános* javaslatom, hogy ezt a verziót érdemes használni és csak akkor keresni valami gyorsabbat, ha nem elég gyors a programunk és a profiler azt mondja, hogy itt van a palack nyaka. De ha ezt mondja, akkor megoldhatjuk a feladatot StringBuilder-rel is:

	public static String unspacerStringBuilder(final String in) {
		StringBuilder sb = new StringBuilder(in);
		boolean previousWasSpace = false;
		int j, i;
		for (i = 0, j = 0; i < sb.length(); i++) {
			sb.setCharAt(j, sb.charAt(i));
			boolean thisIsSpace = Character.isWhitespace(sb.charAt(j));
			if (!previousWasSpace || !thisIsSpace) {
				j++;
			}
			previousWasSpace = thisIsSpace;
		}
		sb.setLength(j);
		return sb.toString();
	}

Ez az algoritmus szépen pakolgatja a karaktereket, és ha két szóközt talál, akkor a második után nem lépteti a j target indexet, hanem rámásolja a következő karaktert (ami lehet szóköz, vagy nem szóköz, de ha szóköz, akkor megint csak nem lépteti).

Az unspacerStringBuffer kopizásától most itt eltekintünk, ugyanaz, mint a unspacerStringBuilder csak StringBuilder helyett StringBuffer-t használ. A fő program elején összeállít egy megfelelően (erre a szóra még visszatérünk) nagy stringet, és utána a parancssori argumentumnak megfelelően meghívja valamelyik metódust:

	public static void main(String[] args) {
		Long timeStart, timeEnd;
		final String testBase = "ap        le  pe                a          ch";
		final int multiplier = 1000;
		final StringBuilder sb = new StringBuilder(multiplier
				* testBase.length());
		for (int i = 0; i < multiplier; i++) {
			sb.append(testBase);
		}
		final String testString = sb.toString();
		final long loopSize = 5;
		switch (args[0]) {
		case "1":
			timeStart = System.currentTimeMillis();
			for (int i = 0; i < loopSize; i++) {
				@SuppressWarnings("unused")
				String z = unspacerRegEx1(testString);
			}
			timeEnd = System.currentTimeMillis();
			System.out.println(timeEnd - timeStart + "ms with unspacerRegEx1");
			break;
...
		}
	}
}

(A case többi ágától eltekinthetünk. A teljes program megtalálható itt becsukva:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * This class provides three different methods that remove the superfluous
 * spaces from a string.
 */
public class StringUnspacer {

	public static String unspacerRegEx1(final String in) {
		String returnValue = in;
		Pattern pattern = Pattern.compile("^(.*)(\\s\\s)(.*)$");
		Matcher matcher = pattern.matcher(returnValue);
		while (matcher.find()) {
			returnValue = matcher.group(1) + " " + matcher.group(3);
			matcher = pattern.matcher(returnValue);
		}
		return returnValue;
	}

	public static String unspacerRegEx2(final String in) {
		String returnValue = in;
		Pattern pattern = Pattern.compile("^(.*)(\\s\\s+)(.*)$");
		Matcher matcher = pattern.matcher(returnValue);
		while (matcher.find()) {
			returnValue = matcher.group(1) + " " + matcher.group(3);
			matcher = pattern.matcher(returnValue);
		}
		return returnValue;
	}

	public static String unspacerRegEx3(final String in) {
		String returnValue = "";
		Pattern pattern = Pattern.compile("(.*?)\\s\\s+");
		Matcher matcher = pattern.matcher(in);
		int end = 0;
		while (matcher.find()) {
			returnValue += matcher.group(1) + " ";
			end = matcher.end();
		}
		returnValue += in.substring(end);
		return returnValue;
	}

	public static String unspacerRegEx4(final String in) {
		Pattern pattern = Pattern.compile("\\s\\s+");
		Matcher matcher = pattern.matcher(in);
		String returnValue = matcher.replaceAll(" ");
		return returnValue;
	}

	public static String unspacerString(final String in) {
		return in.replaceAll("\\s\\s+", " ");
	}

	public static String unspacerStringBuilder(final String in) {
		StringBuilder sb = new StringBuilder(in);
		boolean previousWasSpace = false;
		int j, i;
		for (i = 0, j = 0; i < sb.length(); i++) {
			sb.setCharAt(j, sb.charAt(i));
			boolean thisIsSpace = Character.isWhitespace(sb.charAt(j));
			if (!previousWasSpace || !thisIsSpace) {
				j++;
			}
			previousWasSpace = thisIsSpace;
		}
		sb.setLength(j);
		return sb.toString();
	}

	public static String unspacerStringBuffer(final String in) {
		StringBuffer sb = new StringBuffer(in);
		boolean previousWasSpace = false;
		int j, i;
		for (i = 0, j = 0; i < sb.length(); i++) {
			sb.setCharAt(j, sb.charAt(i));
			boolean thisIsSpace = Character.isWhitespace(sb.charAt(j));
			if (!previousWasSpace || !thisIsSpace) {
				j++;
			}
			previousWasSpace = thisIsSpace;
		}
		sb.setLength(j);
		return sb.toString();
	}

	public static void main(String[] args) {
		Long timeStart, timeEnd;
		final String testBase = "ap        le  pe                a          ch";
		final int multiplier = 1000;
		final StringBuilder sb = new StringBuilder(multiplier
				* testBase.length());
		for (int i = 0; i < multiplier; i++) {
			sb.append(testBase);
		}
		final String testString = sb.toString();
		final long loopSize = 5;
		switch (args[0]) {
		case "1":
			timeStart = System.currentTimeMillis();
			for (int i = 0; i < loopSize; i++) {
				@SuppressWarnings("unused")
				String z = unspacerRegEx1(testString);
			}
			timeEnd = System.currentTimeMillis();
			System.out.println(timeEnd - timeStart + "ms with unspacerRegEx1");
			break;
		//
		// ------------------------------------------------------------------------
		//
		case "2":
			timeStart = System.currentTimeMillis();
			for (int i = 0; i < loopSize; i++) {
				@SuppressWarnings("unused")
				String z = unspacerRegEx2(testString);
			}
			timeEnd = System.currentTimeMillis();
			System.out.println(timeEnd - timeStart + "ms with unspacerRegEx2");
			break;
		//
		// ------------------------------------------------------------------------
		//
		case "3":
			timeStart = System.currentTimeMillis();
			for (int i = 0; i < loopSize; i++) {
				@SuppressWarnings("unused")
				String z = unspacerRegEx3(testString);
			}
			timeEnd = System.currentTimeMillis();
			System.out.println(timeEnd - timeStart + "ms with unspacerRegEx3");
			break;
		//
		// ------------------------------------------------------------------------
		//
		case "4":
			timeStart = System.currentTimeMillis();
			for (int i = 0; i < loopSize; i++) {
				@SuppressWarnings("unused")
				String z = unspacerRegEx4(testString);
			}
			timeEnd = System.currentTimeMillis();
			System.out.println(timeEnd - timeStart + "ms with unspacerRegEx4");
			break;
		//
		// ------------------------------------------------------------------------
		//
		case "5":
			timeStart = System.currentTimeMillis();
			for (int i = 0; i < loopSize; i++) {
				@SuppressWarnings("unused")
				String z = unspacerString(testString);
			}
			timeEnd = System.currentTimeMillis();
			System.out.println(timeEnd - timeStart + "ms with unspacerString");
			break;
		//
		// ------------------------------------------------------------------------
		//
		case "6":
			timeStart = System.currentTimeMillis();
			for (int i = 0; i < loopSize; i++) {
				@SuppressWarnings("unused")
				String z = unspacerStringBuilder(testString);
			}
			timeEnd = System.currentTimeMillis();
			System.out.println(timeEnd - timeStart
					+ "ms with unspacerStringBuilder");
			break;
		//
		// ------------------------------------------------------------------------
		//
		case "7":
			timeStart = System.currentTimeMillis();
			for (int i = 0; i < loopSize; i++) {
				@SuppressWarnings("unused")
				String z = unspacerStringBuffer(testString);
			}
			timeEnd = System.currentTimeMillis();
			System.out.println(timeEnd - timeStart
					+ "ms with unspacerStringBuffer");
			break;
		}
	}
}

)

A mérési eredmények:

verhasp:string-test verhasp$ sh target/classes/execute.sh 
112508ms with unspacerRegEx1
110590ms with unspacerRegEx2
846ms with unspacerRegEx3
105ms with unspacerRegEx4
92ms with unspacerString
30ms with unspacerStringBuilder
42ms with unspacerStringBuffer

Értékelés: látszik, hogy a StringBuilder valóban a leggyorsabb, de a String.replaceAll() sem sokkal lassabb. Igaz, hogy a háromszorosa, de mi ez a leglassabb megoldás 3000-szeres futási idejéhez képest.

Megjegyzések: a sebességet nagyon sok minden befolyásolja. Ha egy JVM-ben futtattam egymás után a teszteket, akkor előfordult, hogy az egyik metódus lefutott, elindult a második, és beütött egy GC. Ezt valamennyire kivédte, ha minden metódus hívás előtt hívott a program egy System.gc()-t de ilyenkor is sok minden befolyásolta az egyes futási időket. Külön processzként elindítva egyértelmű és világos eredményt kaptunk. Az azonban, hogy az első próbálkozások során például a unspacerRegex4 rendszeresen gyorsabb volt, mint az unspacerString, illetve kisebb méretű stringekre a StringBuilder-t használó megoldás sokkal lassabb volt, mint a unspacerRegex4 vagy unspacerString azt mutatja, hogy optimalizálni csak a tényleges futó kódot lehet, mérésekkel. Premature optimization is source of evil.

Irodalom:

2 responses to “StringBuffer és StringBuilder

  1. Richard O. Legendi július 31, 2012 3:46 du.

    Egy gyors megjegyzés: ahogy mondod is, “a sebességet nagyon sok minden befolyásolja” hasonló microbenchmarkok esetén.

    Hogy egy példát említsek: a “String z = unspacerRegEx1(testString);” utasítást a JIT simán kivághatja, mert hogy dead code, és igaza van – onnantól meg az egész kuka. Valami változót a külső scope-ban változtass az értékétől függően, majd a végén kezd vele valamit (pl. írd ki a képernyőre), ezzel be lehet csapni a dataflow analysist, hacsak nem brutál agresszívra van állítva.

    Ha ilyesmivel akarsz többet játszani, mindenképp ajánlom Brent Boyer alábbi leírását a felmerülő problémákról:

    http://www.ibm.com/developerworks/java/library/j-benchmark1/index.html

    Illetve itt bemutat egy API-t, amit pont erre a célra írtak:

    https://www.ibm.com/developerworks/java/library/j-benchmark2/

    Érdemes nem újra felfedezni ezeket a problémákat, ha van rá kész API, ami valamelyest kezeli. A dead code elimination-t például úgy kezeli, hogy Callable-t be kell csomagolnod a mérést. A GC-vel is próbál valamit kezdeni (a steady state elérésétől próbál mérni).

    My 2 cents,
    Ricsi

  2. Kofa augusztus 30, 2012 2:13 du.

    A StringBuilder/Buffer eredményeket tovább árnyalja, hogy a HotSpot képes észrevenni és elhagyni a lokális scope-ú objektumok szinkronizációit (mert másik szál úgysem fér hozzá). Továbbá érdekes, hogy régi gépeken a StringBuffer nem sokkal lassabb, mint a StringBuilder, míg újabbakon igen (és nem azért, mert a StringBuilder gyorsul, hanem mert a StringBuffer lassul – egy processzormag és cache esetén kevesebb munka a szinkronizáció, mint nyolccal).
    http://www.infoq.com/articles/java-threading-optimizations-p1
    http://www.infoq.com/articles/java-threading-optimizations-p2

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés / Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés / Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés / Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés / Módosítás )

Kapcsolódás: %s

%d blogger ezt kedveli: