Artikelempfehlungen, interessante Publikationen o.Ä.

[antisteo]

Alles was wir hier berichtet haben war nur die Spitze des Eisbergs: Bringing Clang and LLVM to Visual C++ users

Gruselgeschichten!!!!

[CodingCat]

Pflichtlektüre für alle, die über die Entwicklung einer UI nachdenken: Immediate Mode Model/View/Controller

[Chromanoid]

Danke für den Link! Darüber bin ich auf diesen einleitenden Abschnitt gestoßen, dessen Wahrheiten man sich immer wieder vor Augen führen sollte:
OOPs - nasty traps in Object Oriented Programming

Zu IMGUI: Ich bin eigentlich MVVM Fan. Der IMGUI Weg erscheint mir nicht sehr skalierbar. Wenn man sowas sieht https://github.com/AdrienHerubel/imgui/ ... le_gl3.cpp juckt es doch in den Fingern, die Aufrufe in eigene Objekte zu packen. Die Parameter der Methoden werden zu Eigenschaften, man lädt die Objekte dann aus einer Datei und man möchte nur noch das Verhalten in der Anwendung beschreiben. *Zack* man ist wieder kurz davor Events zu verwenden... Vielleicht wäre ein Weg das ganze trotzdem direkt zu steuern, statt Events einfach aus der Liste die relevanten Elemente herauszusuchen und das besondere Verhalten pro Durchlauf per Methoden-Pointer einzufügen.

[joeydee]

Auch von mir ein Dank für den Link! Den Ansatz hätte ich wahrscheinlich nie als sinnvoll erachtet. Ich war sowieso auf der Suche nach einer eigenen, extrem schlanken Simple-Gui u.a. für schnelle Prototypen, aber auch skalierbar für eigene Designs. Mit meinem bisherigen Ansatz (klassisch mit Events) war ich mehr und mehr unzufrieden; das hier vereinfacht dagegen so einiges.

[FlorianB82]

Asm.js ist zwar schon nicht mehr ganz neu, aber meiner Meinung nach trotzdem hochinteressant!

[Chromanoid]

Diskussion über IMGUI nach hier verschoben: http://zfx.info/viewtopic.php?f=7&t=3317&p=41710

[Chromanoid]

Bit Twiddling Hacks, Sean Eron Anderson
A very extensive list of operations with code for when your bits need twiddling.
[via HighScalability]

[Schrompf]

Danke. Das ist eine anscheinend aktualisierte Version der Bit Twiddling Hacks, die hier schonmal rumkamen. Einiges davon habe ich in meinem Voxelprojekt schon erfolgreich eingesetzt.

[antisteo]

Bit Twiddling Hacks, Sean Eron Anderson
A very extensive list of operations with code for when your bits need twiddling.
[via HighScalability]

Geiles Ding.
Man müsste die naiven Äquivalente dieser Code-Schnipsel mal formulieren und die LLVM so patchen, dass ein Optimierer-Pass diese Sequenzen automatisch generiert. Das würde den Code lesbarer machen, während er genau so schnell läuft.

[Schrompf]

Du meinst: Intrinsics dafür definieren? Weil der "direkte" Code für diese Bit-Hacks ja nicht wirklich schön ist und wahrscheinlich sehr schwer detektierbar sein dürfte. "Lesbar" ist das für mich nicht, weder die manuellen Versionen der Algorithmen noch die schlauen Bit-Hacks.

[Krishty]

Hm. Vieles davon wird doch schon intrinsisch umgesetzt – abs(int) nutzt Compute the integer absolute value (abs) without branching (zumindest in VS ab 2003); strlen() nutzt Determine if a word has a zero byte; usw. Die Leistung hängt auch wirklich selten davon ab, ob eine bedingte Negation in drei oder sieben Takten realisiert ist.

Ich glaube, dass das Erkennen dieser Programmsequenzen bei jeder Optimierung jedes Programms letzten Endes mehr Strom verbrauchen würde als weltweit bei der Ausführung dieser Programme damit gespart wird.

[Florian Keßeler]

Man kann es sich auch kompliziert machen. Einfach ne entsprechende Funktion mit einem aussagekräftigen Namen definieren und den Compiler optimieren lassen.

[antisteo]

Du meinst: Intrinsics dafür definieren? Weil der "direkte" Code für diese Bit-Hacks ja nicht wirklich schön ist und wahrscheinlich sehr schwer detektierbar sein dürfte. "Lesbar" ist das für mich nicht, weder die manuellen Versionen der Algorithmen noch die schlauen Bit-Hacks.

Nein. Ich meine einen Pass, der Branches anschaut, deren BasicBlocks nur wenig Code enthalten und versucht, die Branches zu eliminieren und durch Arithmetik zu ersetzen.

[Schrompf]

Weiß nicht, ob dass so groß was bringt. Ich brauche die Hacks ja primär, um gleich mehrere Voxel auf einmal zu bearbeiten. Und da macht es wirklich einen gewaltigen Unterschied, ob man achtmal jeweils ein Byte prüft oder die Einzelbytes eines uint64_t mit ein wenig Bitmagie im Ganzen bearbeiten kann.

[Krishty]

… außerdem sind Verzweigungen in vielen Fällen schneller als Datenabhängigkeiten, so lange die Bedingung halbwegs vorhersagbar ist. Man braucht also erstmal Profiling um zu wissen ob die Sprungvorhersage oder die Arithmetikleistung der Flaschenhals ist, oder ob es sowieso nichts bringt und der minimale Befehlsumfang bevorzugt werden sollte (oft Sprünge).

Die Pentium-4-Zeiten, in denen man alle Verzweigungen unter 100 Anweisungen durch Datenabhängigkeiten ersetzen musste, sind schon ein Jahrzehnt hinter uns; die Bit Twiddling Hacks braucht man nur in inneren Schleifen, die – wie Schrompfs – sehr spezielle Ziele verfolgen, oder wenn die Sprünge zu unregelmäßig werden …

[Florian Keßeler]

Schrompf, kannst du nicht einfach SSE und Autovektorisierung in deinem Compiler aktivieren? Dann sollte der solche Fälle selbst erkennen und dir gleich 16 uint8 auf einmal verwursten, ohne Mehraufwand und komische Bit Hacks. Und SSE kann man heute zumindest auf PCs allgemein als gegeben annehmen.

[Krishty]

In einer for-Schleife finden die Zugriffe sequentiell statt; via SSE parallel. Sowas wie strlen() dürfte der Compiler nicht vektorisieren, weil eines der hinteren 15 Buchstaben auf einer anderen Seite liegen könnten als der Vordere und eine Zugriffsverletzung auslösen würden, wäre der erste Buchstabe bereits 0. Man muss wissen wie Schrompfs Datenstrukturen aussehen bevor man beurteilen kann ob das automatisch vektorisierbar ist.

[Schrompf]

Dass das der Compiler automatisch könnte, warmir gar nicht in den Sinn gekommen. Ich bin leider immernoch mit Ernährungsaufträgen beschäftigt und kann den Voxelkram erst in einigen Wochen/Monaten wieder anfassen. Aber theoretisch sollte es möglich sein, weil die Schleifen bei mir ja immer feste Größen haben und die Bytes prima aligned rumliegen müssten.

[Florian Keßeler]

Krishty: http://gcc.gnu.org/projects/tree-ssa/vectorization.html

Klar, sowas wie strlen wird nicht vektorisiert (*), aber es gibt trotzdem eine Menge Möglichkeiten für den Compiler das zu tun.

€: Schamlose Werbung: http://crispybyte.wordpress.com/2013/05 ... -schritte/

(*) Nachtrag: Guck, was ich grade bei der Arbeit an etwas ganz anderem entdeckt habe: __strlen_sse42

[Krishty]

Krishty: http://gcc.gnu.org/projects/tree-ssa/vectorization.html

Klar, sowas wie strlen wird nicht vektorisiert (*), aber es gibt trotzdem eine Menge Möglichkeiten für den Compiler das zu tun.

Ja; aber in keinem Fall darf die Iterationszahl vom Inhalt der Schleifenvariablen abhängig sein. Wenn man also Sentinels benutzt (wie die Null im String) oder die Größe nicht sicher kennt, ist man aufgeschmissen. Es gibt noch „glaub mir, es ist immer ein Vielfaches von X“-#pragmas; aber einfach die Befehlsfolge im Compiler erkennen und durch Vektorversionen ersetzen ist für viele Fälle nicht und wird auch nie sein.

(*) Nachtrag: Guck, was ich grade bei der Arbeit an etwas ganz anderem entdeckt habe: __strlen_sse42

… und auch das benötigt bis zu 15 Buchstaben Padding wenn du Zugriffsverletzungen ausschließen willst – die automatische Anwendung ist also entweder auf den Stapelspeicher und User Types beschränkt oder auf die Standardbibliothek, deren Padding-Verhalten dem Compiler bekannt ist. Vertraut einfach nicht drauf.

[Spiele Programmierer]

… und auch das benötigt bis zu 15 Buchstaben Padding wenn du Zugriffsverletzungen ausschließen willst

Naja, SSE SIMD funktioniert sowieso nur auf mindestens 16 Byte ausgerichtete Daten.
Das heißt, die ersten bis zu 15 Bytes müsste man konventionell überprüfen. Danach immer in 16 Byteblöcken.
Eine Zugriffsverletzung kann nicht auftreten, weil die Pages auf 4096 Byte ausgerichtet sind. Das heißt, es sind von den 16 Byte SSE-"Datenblöcken" genau 256 in einer Page. Während lesen eines weiteren Datenblockes, können also die Pagegrenzen nicht überschritten werden.

[antisteo]

… und auch das benötigt bis zu 15 Buchstaben Padding wenn du Zugriffsverletzungen ausschließen willst

Naja, SSE SIMD funktioniert sowieso nur auf mindestens 16 Byte ausgerichtete Daten.
Das heißt, die ersten bis zu 15 Bytes müsste man konventionell überprüfen. Danach immer in 16 Byteblöcken.

Andersrum. Zuerst die SIMD-Blöcke und der Rest in einer konventionellen Schleife. Dann trifft man das Alignment besser.

Die glibc nutzt übrigens eine SSE-basierte strlen. (das sehe ich öfters in den Crash Logs)

[Spiele Programmierer]

Na, doch eben nicht. Der String ist nicht notwendigerweise auf 16 Byte aligned.
Wenn er zb. ein 4 Byte Offset besitzt und es wird zuerst in 16 Byteblöcken abgearbeitet, sind alle weiteren Blöcke unaligned. (20, 36, 52, 68, ...)
Außerdem kann dann eine Zugriffsverletzung auftreten, weil ein SSE Block über Pagegrenzen reichen kann.

[Florian Keßeler]

Die glibc nutzt übrigens eine SSE-basierte strlen. (das sehe ich öfters in den Crash Logs)

So hab ich es entdeckt ;-)

[Krishty]

… und auch das benötigt bis zu 15 Buchstaben Padding wenn du Zugriffsverletzungen ausschließen willst

Naja, SSE SIMD funktioniert sowieso nur auf mindestens 16 Byte ausgerichtete Daten.

SSE kann auch nicht-ausgerichtete Daten laden (seit Sandy Bridge auch ohne Leistungsverlust), und das benutzt die SSE 4.2-Version wohl auch. Falls man die Speicherumgebung des Strings nicht kennt, benötigt man dann Padding. Es wäre auch eine schöne Scheiße wenn strlen() plötzlich nur noch auf ausgerichteten Adressen arbeiten würde …

Andersrum. Zuerst die SIMD-Blöcke und der Rest in einer konventionellen Schleife. Dann trifft man das Alignment besser.

Welcher Rest? Du weißt doch nicht, wie lang der String ist; dann weißt du auch nicht, wo der Rest beginnt. Der SSE-Vergleich sagt dir ja, wo die Null steckt.

[Chromanoid]

40% better single-threaded performance in MariaDB, Kristian Nielsen, 20.01.2014
Ein kleines Plädoyer für Profile-Guided Optimization. Ein Follow-up: More on 40% better single-threaded performance in MariaDB

[via High Scalability]

[Krishty]

Ja; 40 % Gewinn ist, was Microsoft auch typischerweise propagiert.

Aber wenn man derart viele Instruction Cache Misses wegen virtuellen Funktionen hat: Wäre es nicht fruchtbarer, diesen offensichtlichen Fehlentwurf zu korrigieren? Weil dann geht ja schließlich alles schneller; und zwar noch mehr als PGO (das die CPU einfach zu einem Sprung in den statistisch meistgenutzten Kandidaten drängt), und in allen Kompilaten auf allen Plattformen, und ohne aufwändige Trainingsfälle.

Mein Verständnis von PGO war, dass es Optimierungen durchführt, die dem Programmierer unmöglich sind (wie das optimierte Anordnen der Funktionen im Speicher); nicht, dass es die Mülltonne hinter der Abschlussballturnhalle ist, in die man seine Fehlgeburt entsorgt.

Nachtrag: Und hat er überhaupt die Maschinenbefehle verglichen? So wie ich das sehe ist JOIN::optimize() ein 800-Zeilen-Monster. Es ist gut möglich dass GCC es schlicht auf Größe statt auf Geschwindigkeit optimiert hat damit es in den Anweisungs-Cache passt.

[Chromanoid]

Ich will da nichts verteidigen, ich fand den Artikel einfach interessant. Aber hier mal drei schnell ausgedachte Argumente, die Dir bestimmt auch klar sind :D und unabhängig von dem Versprechen gelten, dass man Verbesserungen erreicht, die man als Mensch nicht erreicht:
1. Neuschreiben kommt, wenn es schon soweit ist, selten infrage.
2. Es ist teurer besseren Code zu schreiben, als im Nachgang PGO drüber zu jagen.
3. Der Code ist Cache-freundlicher schlechter wartbar und schlechter zu verstehen.

[Krishty]

2. Es ist teurer besseren Code zu schreiben, als im Nachgang PGO drüber zu jagen.

Aber es ist günstiger, realitätsnahe Trainingsfälle zu finden, zu schreiben, zu warten, und mit dem Quelltext auszuliefern? Das ist doch der ganz typische Fall von „Die Komplexität hat es zu langsam werden lassen. Lösen wir das, indem wir ein weiteres komplexes System draufschichten!“.

Und die Lösung könnte schon so banal sein, Funktionszeiger zu setzen statt virtueller Funktionen.

[Chromanoid]

2. Es ist teurer besseren Code zu schreiben, als im Nachgang PGO drüber zu jagen.

Aber es ist günstiger, realitätsnahe Trainingsfälle zu finden, zu schreiben, zu warten, und mit dem Quelltext auszuliefern? Das ist doch der ganz typische Fall von „Es ist zu komplex geworden. Lösen wir das, indem wir ein weiteres komplexes System draufschichten!“.

Naja, dann halt: Es ist günstiger ein weiteres komplexes System (PGO) draufzuschichten, anstatt das alte sehr komplexe Problem anders zu lösen. Das mag zwar unelegant sein, in vielen Betrieben ist es aber sicher unausweichliche Realität.