An dieser Stelle bekam ich seltsame Ideen: Würde diese Idee des Branchless Programming eventuell auch für Sprachen gelten, die keinen direkten Maschinencode produzieren sondern einen zur Laufzeit interpretierten Bytecode - beispielsweise Java?

Ich portierte dazu den Code zunächst nach Java, was folgendes ergab:

	int max(int a, int b)
	{
		if(a>b)
			return a;
		else
			return b;
	}
	int max1(int a, int b)
	{
		int t = ((a-b) >> 31)+1;
		int u = ((b-a) >> 31)+1;
		return t*a+u*b;
	}
	public void toUpper(byte[] buf)
	{
		for(int i=0;i<buf.length;++i)
		{
			if((buf[i]>='a')&&(buf[i]<='z'))
			{
				buf[i]=(byte)(((int)buf[i])-32);
			}
		}
	}
	public void toUpper1(byte[] buf)
	{
		for(int i=0;i<buf.length;++i)
		{
			int pointedAt=(int)buf[i];
			int a=(((pointedAt-'a') >> 31)+1)*((('z'-pointedAt) >> 31)+1);
			buf[i]=(byte)(pointedAt-(32*a));
		}
	}

Anschließend verglich ich den Bytecode beider Beispiele - zunächst den für max:

  int max(int, int);
    Code:
       0: iload_1
       1: iload_2
       2: if_icmple     7
       5: iload_1
       6: ireturn
       7: iload_2
       8: ireturn

int max1(int, int); Code: 0: iload_1 1: iload_2 2: isub 3: bipush 31 5: ishr 6: iconst_1 7: iadd 8: istore_3 9: iload_2 10: iload_1 11: isub 12: bipush 31 14: ishr 15: iconst_1 16: iadd 17: istore 4 19: iload_3 20: iload_1 21: imul 22: iload 4 24: iload_2 25: imul 26: iadd 27: ireturn

Schon von der schieren Länge her scheint es kaum möglich, dass die branchless Variante hier einen Performance-Vorteil hat. Schauen wir uns noch den Bytecode der etwas komplexeren Variante an:

  public void toUpper(byte[]);
    Code:
       0: iconst_0
       1: istore_2
       2: iload_2
       3: aload_1
       4: arraylength
       5: if_icmpge     40
       8: aload_1
       9: iload_2
      10: baload
      11: bipush        97
      13: if_icmplt     34
      16: aload_1
      17: iload_2
      18: baload
      19: bipush        122
      21: if_icmpgt     34
      24: aload_1
      25: iload_2
      26: aload_1
      27: iload_2
      28: baload
      29: bipush        32
      31: isub
      32: i2b
      33: bastore
      34: iinc          2, 1
      37: goto          2
      40: return

public void toUpper1(byte[]); Code: 0: iconst_0 1: istore_2 2: iload_2 3: aload_1 4: arraylength 5: if_icmpge 50 8: aload_1 9: iload_2 10: baload 11: istore_3 12: iload_3 13: bipush 97 15: isub 16: bipush 31 18: ishr 19: iconst_1 20: iadd 21: bipush 122 23: iload_3 24: isub 25: bipush 31 27: ishr 28: iconst_1 29: iadd 30: imul 31: istore 4 33: aload_1 34: iload_2 35: iload_3 36: bipush 32 38: iload 4 40: imul 41: isub 42: i2b 43: bastore 44: iinc 2, 1 47: goto 2 50: return

Auch hier scheint es unmöglich, dass sich die Performance in der branchless-Variante steigert, da bereits der Bytecode dieser Variante deutlich länger ist. Ich habe dennoch Benchmarks durchgeführt und die haben zu einem für mich erstaunlichen Ergebnis geführt, das ich hier nicht vorenthalten möchte. Dazu habe ich jede Implementierung in einer Schleife oft wiederholen lassen und diesen Test jeweils 10 Mal wiederholt - hier zunächst die Ergebnisse für max:

00:00:00.020834
00:00:00.019635
00:00:00.019565
00:00:00.019597
00:00:00.019538
00:00:00.019665
00:00:00.019691
00:00:00.019642
00:00:00.020138
00:00:00.019596
---
00:00:00.021397
00:00:00.021162
00:00:00.021232
00:00:00.021350
00:00:00.021166
00:00:00.021156
00:00:00.021778
00:00:00.021784
00:00:00.021579
00:00:00.021609

Man sieht, dass die branchless-Variante zwar - wie erwartet - langsamer ist aber überraschenderweise scheint die Streuung der Ergebnisse deutlich geringer zu sein als in der "normalen" Variante. Dieses Ergebnis brachte mich dazu, das nicht-triviale Beispiel mit derselben Methode nochmals zu untersuchen - mit folgenden Ergebnissen:

00:00:00.350852
00:00:00.319269
00:00:00.325429
00:00:00.317016
00:00:00.312730
00:00:00.314297
00:00:00.312975
00:00:00.313555
00:00:00.314543
00:00:00.319361
---
00:00:00.357968
00:00:00.354844
00:00:00.348824
00:00:00.348372
00:00:00.351472
00:00:00.356511
00:00:00.354604
00:00:00.357167
00:00:00.355692
00:00:00.352458

Auch hier zeigt sich eine sehr viel geringere Schwankungsbreite der Ergebnisse in der branchless-Variante, die aber wieder insgesamt gesehen deutlich länger benötigt als die "normale" Variante. Damit scheint es so zu sein, dass aus Performance-Sicht die Erstellung von branchless-Varianten von Algorithmen in Java den Aufwand nicht rechtfertigt, allerdings die Anzahl bedingter Sprünge im Bytecode die Streuung von Benchmarkergebnissen deutlich erhöht.

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • IOTA oder wie eine Blase funktioniert

    17.06.2017

    Ich wurde gefragt, ob ich Einschätzungen zu Crypto-Currencies machen könnte. Speziell wurde ich nach Ethereum gefragt - einer, von der ich bereits gehört und für die ich mich bereits kurzzeitig milde interessiert hatte - und IOTA, die mir völlig unbekannt war. Ich begann mit einer Analyse der mir unbekannten und wurde überrascht.

    Weiterlesen...

Neueste Artikel

  • LinkCollections 2022 V

    Nach der letzten losen Zusammenstellung (für mich) interessanter Links aus den Tiefen des Internet für dieses Jahr folgt hier nunmehr die nächste:

    Weiterlesen...
  • Minifying elbosso.github.io

    Ich habe mir ein paar Gedanken über den Ressourcenverbrauch meiner Heimatseite im Zischennetz gemacht, um sie ien ganz klein wenig "grüner" zu gestalten...

    Weiterlesen...
  • tesseractuzneditor

    Ich habe hier bereits verschiedentlich davon berichtet, wie ich versucht habe, mich dem Thema Optical Character Regognition (OCR) zu nähern. Nach einigen interessanten Diskussionen in den vergangenen Monaten habe ich jetzt ein damit in Verbindung stehendes Projekt auf Gitlab aufgesetzt

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier.