Java
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.
Vor 5 Jahren hier im Blog
-
Multi-User-WebDAV, Docker, GitHub
17.11.2019
Nachdem ich mich in letzter Zeit verstärkt mit Docker und dem zugehörigen Ökosystem beschäftige, habe ich begonnen, verschiedenste Dienste in Containern zu testen um zu sehen, ob in manchen Fällen LXC oder KVM nicht doch die bessere Wahl wäre...
Weiterlesen...
Tags
Android Basteln C und C++ Chaos Datenbanken Docker dWb+ ESP Wifi Garten Geo Go GUI Gui Hardware Java Jupyter Komponenten Links Linux Markdown Markup Music Numerik OpenSource PKI-X.509-CA Python QBrowser Rants Raspi Revisited Security Software-Test sQLshell TeleGrafana Verschiedenes Video Virtualisierung Windows Upcoming...
Neueste Artikel
- Migration der Webseite und aller OpenSource Projekte
In eigener Sache...
Weiterlesen... - AutoHideToolbar für Java Swing
Ich habe eine neue Java Swing Komponente erstellt: Es handelt sich um einen Wrapper für von JToolBar abgeleitete Klassen, die die Werkzeugleiste minimieren und sie nur dann einblenden, wenn der Mauszeiger über ihnen schwebt.
Weiterlesen... - Integration von EBMap4D in die sQLshell
Ich habe bereits in einem früheren Artikel über meine ersten Erfolge berichtet, der sQLshell auf Basis des bestehenden Codes aus dem Projekt EBMap4D eine bessere Integration für Geo-Daten zu spendieren und entsprechende Abfragen, bzw. deren Ergebnisse auf einer Kartenansicht zu visualisieren.
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, muss 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 Codeberg-Repositories findet man hier.