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.

Kommentar hinzufügen (via ) Kommentare ansehen (via )

Kommentar hinzufügen (via ) Kommentare ansehen (via )