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

  • Mercator-Projektion für generierte Planeten

    22.05.2017

    Nachdem ich neulich endlich auch die dreidimensionale Generierung von Spielwelten erfolgreich ausprobiert hatte, entwickelten sich notgedrungen neue Ideen für weitere Forschungen - eine davon möchte ich hier vorstellen:

    Weiterlesen...

Neueste Artikel

  • Migration von Log4J zu Logback Classic

    Nach den diversen schlimmen Nachrichten Ende letzten Jahres (Log4Shell) habe ich den Entschluss gefasst, von Log4J Abschied zu nehmen und eine andere Logging-Lösung einzusetzen.

    Weiterlesen...
  • Kuramoto in 2 Dimensionen

    Ich habe mich bereits vor einigen Wochen mit diesem System beschäftigt - nun war es an der Zeit, ein wenig zu variieren...

    Weiterlesen...
  • Meine Erfahrungen mit "Agile"

    Ich habe inzwischen in mehreren Projekten gearbeitet, die von sich behauptet haben, die agile Methodik zu nutzen und war damit nie wirklich glücklich. Jetzt kann ich die Gründe dafür beginnen, in Worte zu fassen:

    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.