Jammer-Thread

[Krishty]

40 Minuten gearbeitet. Sechs Schleifen von Zählern zu Iteratoren geändert, davon außerdem vier Schleifen von for zu do-while. Dadurch 23 Anweisungen gespart und 80 B Maschinentext. Langsam wird es krankhaft.

[antisteo]

40 Minuten gearbeitet. Sechs Schleifen von Zählern zu Iteratoren geändert, davon außerdem vier Schleifen von for zu do-while. Dadurch 23 Anweisungen gespart und 80 B Maschinentext. Langsam wird es krankhaft.

Mir kommt dein Optimierer immer noch spanisch vor. Wieso ist ein Iterator-Makro (theor. Klasse auf dem Stack etc.) so viel schneller als eine For-Schleife, auf die ja die Compiler noch eher getrimmt sein müssten?
Letzendlich müssten doch beide Varianten in den gleichen Zwischencode münden (was es aber bei zahlreichen deiner Beispiele nicht tut) und am Ende auch der Maschinencode ähnlich klein werden. Oder hat der MS Compiler keinen einheitlichen Zwischencode? (bzw. lässt nicht immer alle Passes über den gesamten Code laufen...)

[Krishty]

Wieso ist ein Iterator-Makro (theor. Klasse auf dem Stack etc.) so viel schneller als eine For-Schleife, auf die ja die Compiler noch eher getrimmt sein müssten?

Als Iterator benutze ich einen nackten Zeiger. Aus

    for(int j = 0; j < 100; ++j) {
        foo(array[j]);
    }

wird

    for(auto it = array; it < array + 100; ++it) {
        foo(*it);
    }

was zwei statt drei Register verbraucht; daher die Platzersparnis.

Letzendlich müssten doch beide Varianten in den gleichen Zwischencode münden (was es aber bei zahlreichen deiner Beispiele nicht tut) und am Ende auch der Maschinencode ähnlich klein werden. Oder hat der MS Compiler keinen einheitlichen Zwischencode? (bzw. lässt nicht immer alle Passes über den gesamten Code laufen...)

Das Problem an Visual Studio ist die Abwärtskompatibilität: Weil er noch aus einer Zeit stammt, in der Compiler nicht viel mehr als direkte Übersetzung gemacht haben, sind Transformationen wie if-else-zu-switch (und umgekehrt) nicht vorhanden, damit der Programmierer entscheiden kann, was in seinem Fall schneller ist. Ich vermute, dass der Programmierer im Fall der Schleifen die Wahl haben soll zwischen Decoding-Last (Zähler) und ALU-Last (Iterator). Das war IIRC auch deren Argument gegen Single-Call Site Inlining – da du selbst mit Profiling kaum Möglichkeit hast, dem Compiler Dinge mitzuteilen wie hier brauche ich jetzt mehr ALU-Leistung oder hier bitte keine Lokalität, ist ihnen ein unselbstständiger Compiler mit kalkulierbarer Maschinentexterzeugung wohl lieber als ein selbstständiger, der sich unaufhaltsam falsch entscheidet. Einfach alles zu transformieren würde wohl viel alten Code langsamer machen; und stänkern würden genau die Leute, die ihn schon von Hand optimiert haben, weil wer anders nie misst.

Du kannst ja mal ausprobieren, ob Clang die Schleifen derart transformiert.

[kaiserludi]

Dann könnt man aber doch eine Compileroption einbauen: Ist sie aus (Default) dann hält sich er Compiler mit solchen Optimierungen zurück, ist sie an, dann führt er sie selbstständig durch.

[antisteo]

Du kannst ja mal ausprobieren, ob Clang die Schleifen derart transformiert.

Die LLVM/der Clang hat bei meinem letzten Versuch noch sehr viel Zwischencode aus den Makros generiert, der am Ende dafür gesorgt hat, dass der Inline Threshold zu klein war und dass generell die Passes in der Reihenfolge, wie sie im Pass Manager waren, nicht ausgereicht haben, aus dem Iterator-Makro (std::vector) wieder einen normalen Zeigerzugriff zu machen. Wenn man den Optimierer aber 2 mal über den Code laufen lässt, kommt das Optimum heraus. Das ist ein Kritikpunkt, den ich an LLVM habe, dass die Passes fest vorgeeben sind und nicht wiederholt werden, wenn z.B. BBs zusammengeflickt werden. Das Optimum aus meiner Sicht wäre ja, dass konstant berechnende Programme gleich im Compiler ausgeführt werden und nur der Runtime-Teil in Code gepresst wird. Das brauche ich, weil ich sehr viel unnötige (=situationsbezogene) Logik einer dynamischen Programmiersprache immer mitkompiliere und darauf hoffe, dass die LLVM das schnell macht (also mein Compiler-Frontend nur Code-Schnipsel zusammenstecken muss). Das funktioniert aber von Version zu Version besser.

[Krishty]

Welche Makros? Warum std::vector? Ich dachte, es ginge darum, ob LLVM Zähler zu Iteratoren (oder umgekehrt) optimiert?

[antisteo]

Welche Makros? Warum std::vector? Ich dachte, es ginge darum, ob LLVM Zähler zu Iteratoren (oder umgekehrt) optimiert?

std::vector::iterator und so...
Oder worauf willst du hinaus?

Naja generell dass man Code entweder bequem (mit Templates) schreiben kann oder jede Anweisung handcraftet mit dem Hintergedanken, dass der Compiler eh nicht gut mit den Templates umgehen kann.

[Krishty]

Mit Iteratoren meinte ich nicht STL-Iteratoren. Auch Zeiger mit Zeigerarithmetik sind schon Iteratoren über die Arrays, auf die sie zeigen (siehe Quelltextschnippsel); das geht schon in völlig Template-losem C. STL-Iteratoren zu Zeigern optimieren schafft AFAIK auch Visual Studio seit einigen Versionen (aber die nutzen für optimierte Kompilate unterschiedlichen Quelltext).

[antisteo]

Ich hab' mal dein Codebeispiel durch den Clang gejagt und die Variante mit den Arrays generiert kürzeren Code, während die Iteratoren mehr Stack brauchen. Der Code für Arrays braucht 0x25 Bytes, während die Iteratoren 0x27 Bytes brauchen.

Code: Alles auswählen

0000000000000000 <_Z8pointersv>:
   0:	53                   	push   %rbx
   1:	31 db                	xor    %ebx,%ebx
   3:	66 66 66 66 2e 0f 1f 	data32 data32 data32 nopw %cs:0x0(%rax,%rax,1)
   a:	84 00 00 00 00 00 
  10:	8b 3c 9d 00 00 00 00 	mov    0x0(,%rbx,4),%edi
  17:	e8 00 00 00 00       	callq  1c <_Z8pointersv+0x1c>
  1c:	48 ff c3             	inc    %rbx
  1f:	83 fb 64             	cmp    $0x64,%ebx
  22:	75 ec                	jne    10 <_Z8pointersv+0x10>
  24:	5b                   	pop    %rbx
  25:	c3                   	retq   


0000000000000030 <_Z9iteratorsv>:
  30:	41 56                	push   %r14
  32:	53                   	push   %rbx
  33:	50                   	push   %rax
  34:	bb 00 00 00 00       	mov    $0x0,%ebx
  39:	41 be 00 00 00 00    	mov    $0x0,%r14d
  3f:	90                   	nop
  40:	8b 3b                	mov    (%rbx),%edi
  42:	e8 00 00 00 00       	callq  47 <_Z9iteratorsv+0x17>
  47:	48 83 c3 04          	add    $0x4,%rbx
  4b:	4c 39 f3             	cmp    %r14,%rbx
  4e:	72 f0                	jb     40 <_Z9iteratorsv+0x10>
  50:	48 83 c4 08          	add    $0x8,%rsp
  54:	5b                   	pop    %rbx
  55:	41 5e                	pop    %r14
  57:	c3                   	retq 

[Krishty]

Hier ist mein Testfall mit Zähler:

    static size_t const COUNT = 1000;
    auto array = new int[COUNT];
    int sum;
    int i = 0;
    do {
        sum += array;
    } while(++i < COUNT);
    auto volatile forceEffect = sum;
   
und hier mit Iterator:

    static size_t const COUNT = 1000;
    auto array = new int[COUNT];
    int sum;
    auto it = array;
    do {
        sum += *it;
    } while(++it < array + COUNT);
    auto volatile forceEffect = sum;

Der Maschinentext, den Visual C++ für die Version mit Zähler erzeugt:

    mov r8d,dword ptr [sum]
    xor ebx,ebx
    mov edx,ebx
main+24h:
    add r8d,dword ptr [rax]
    inc edx
    lea rax,[rax+4]
    movsxd rcx,edx
    cmp rcx,3E8h
    jb main+24h
   
Visual C++ legt also einen seperaten Iterator an – Datenverarbeitung läuft via Iterator im Instruction Decoder; Branching nebenläufig via Zähler in der ALU.
Nun für die mit Iterator:

    mov ecx,dword ptr [sum]
    lea rdx,[rax+0FA0h]
    nop word ptr [rax+rax]
main+30h:
    add ecx,dword ptr [rax]
    add rax,4
    cmp rax,rdx
    jb main+30h

Blanker Iterator ohne nebenläufigen Zähler ausschließlich auf der ALU, darum kompakterer Text. Hier wäre interessant zu wissen, warum add rax,4 statt lea rax, rax+4 emittiert wurde.

Clang habe ich nicht hier; ich habe deshalb Clang 3.0 vom GCC Explorer genommen. Ist veraltet, aber das einzige, was ich finden konnte. Hier der Maschinentext für die Version mit Zähler:

    movl   $1, %ecx
    jmp    .LBB0_1
.LBB0_2: # %._crit_edge
    movl   (%rax,%rcx,4), %esi
    incq   %rcx
.LBB0_1: # =>This Inner Loop Header: Depth=1
    addl   %esi, %edx
    cmpl   $1000, %ecx # imm = 0x3E8
    jne    .LBB0_2

Clang benutzt ausschließlich einen Zähler; sowohl für Adressierung als auch für Branching.
Und hier mit Iterator:

    leaq   4(%rax), %rcx
    leaq   4000(%rax), %rax
    jmp    .LBB0_1
.LBB0_2: # %._crit_edge
    movl   (%rcx), %esi
    addq   $4, %rcx
.LBB0_1: # =>This Inner Loop Header: Depth=1
    addl   %esi, %edx
    cmpq   %rax, %rcx
    jb    .LBB0_2

Also überführt Clang bis Version 3.0 keine Zählschleifen zu Iteratorschleifen; Visual C++ schon, was mich jetzt wirklich verblüfft hat. Allerdings nutzt Visual C++ dann Zähler und Iterator gemeinsam, weshalb die Textgröße so steigt. Ich bin überfragt, ob Zähler zusätzlich zu Iteratoren noch höhere Leistung bringen oder eher ausbremsen – hier spielen Branch Prediction, Prefetching, ALU-Last, Decoding-Last und Textgröße rein. Wäre toll, wenn das jemand mit einem vernünftigen Benchmark erforschen könnte.

[antisteo]

Schade, dass meine Uni keinen Lehrstuhl für Compilerbau hat. Sonst könnte ich das Thema dort absolvieren, das ganze Benchmarken, ein Paper rausbringen und dann mit dem Paper die LLVM-Leute davon überzeugen, Variante XYZ zu verwenden.

[CodingCat]

emplace_back() verleitet die Leute zu emplace_back(new T(...)) für Containers von unique_ptr<T>, wie ich eben in einer fremden Codebasis feststellen musste. new sollte tatsächlich nicht mehr aufgerufen werden.

[CodingCat]

VC 2013 ist da, genauso hässlich und schlecht wie seine Vorgänger.

[Krishty]

Aber … 5000 neue APIs!

[eXile]

Cross-Quote aus dem Sehenswerte-Videos-Sammelthread:

Massive virtual textures for games: Direct3D Tiled Resources (Hinweis auf 11.2-Features?)

DXGI 1.3 Improvements
Direct3D 11.2 Features
D3D11_FEATURE_DATA_D3D11_OPTIONS1

Das ist jetzt eher wenig berauschend. Benötigt übrigens „Windows 8.1 Preview“.

[kaiserludi]

• 1993 1.0, 1.5
  1994 2.0
  1995 4.0
  1996 4.2
  1997 5.0
  1998 6.0
  1999 -
  2000 -
  2001 -
  2002 7.0
  2003 7.1
  2004 -
  2005 8.0
  2006 -
  2007 -
  2008 9.0
  2009 -
  2010 10.0
  2011 -
  2012 11.0
  2013 12.0

Das erste mal seit 10 und das zweite mal seit 15 Jahren, dass eine neue Version von VC++ bzw. VS erscheint, nachdem im Vorjahr eine erschienen ist.
Ist das jetzt ein gutes Zeichen, dass sie gerade mehr tun als sonst?

[CodingCat]

VC 2013 RTM soll tatsächlich inline non-static data member initialization und = default beinhalten. Damit betreten wir mit C++11 endlich eine neue Ära, in der sich zusammengesetzte Datentypen sinnvoll definieren und in Arrays/vectors verwenden lassen. Automatisch definierte Move-Konstruktoren und -Zuweisungen bekommen wir wohl noch nicht, weil dafür erst stringent noexcept implementiert werden müsste, aber immerhin ertrinken wir nicht mehr in sinnloser Redundanz.

Kurz darauf erwähnt Herb Sutter ganz beiläufig, dass = default NOCH NICHT FÜR MOVE-FUNKTIONEN funktioniert, bis das CTP rauskommt. Dabei bräuchte man dafür nicht mal noexcept. Fazit: Zurück in die Steinzeit mit VC 2013 RTM.

Nachtrag: Wow. VC hatte ursprünglich keinen AST. Ein AST wird erst seit C++11 nach und nach eingebaut. JETZT IST ALLES KLAR. C++11 kommt für VC damit wohl tatsächlich einem Rewrite nahe. Akzeptable Template-Kompilierung steht btw. ganz am Ende der Roadmap, also vmtl. nicht vor dem nächsten Major Relase.

[kaiserludi]

also vmtl. nicht vor dem nächsten Major Relase.

Dann gilt wohl zu hoffen, dass sie in die Release-Regelmäßigkeit der 90er zurückkehren und das nächste Release 2014 kommt.

[Chromanoid]

Außen hui, innen pfui. So ist das immer bei Software :D

[Krishty]

Nachtrag: Wow. VC hatte ursprünglich keinen AST.

Ich hätte zumindest vermutet, das mit x64 einer reinkam – von Visual C++ 2008 hat die x64-Version plötzlich deutlich mehr Template-Schlamperei als Fehler gemeldet als die x86-Version; und dass bei Fehlermeldungen auf Connect üblicherweise die erste Frage x86 oder x64? war ließ auch darauf schließen, dass es sich um ein komplett neues Frontend handeln würde. For the love of god, why?!

[Krishty]

Man darf Eingabefeldern in der WinAPI keinen Standardinhalt geben.

Wird das Eingabefeld erzeugt, sendet es eine WM_COMMAND-Nachricht mit seinem vorgegebenen Inhalt, die so viel bedeutet wie: Jemand hat was in mich hineingeschrieben; reagier!

Dummerweise kommt diese Nachricht direkt nach der Erzeugung an. Ist das Eingabefeld Teil eines Dialogs, kommt es also nach der Erzeugung des Eingabefelds, aber vor der Initialisierung des Dialogs an. Zu diesem Zeitpunkt kann der Dialog noch keine Daten sinnvoll verarbeiten.

Hat man seinem Dialog also z.B. ein Vorschaufeld hinzugefügt, für das man Zwischenergebnisse speichert, muss man entweder alle diese Zwischenergebnisse synchron mit den Standardwerten initialisieren (was Single Point of Truth ziemlich gegen den Strich geht) oder die Standardwerte erst nach der Dialogerzeugung setzen (was Zombie State und Zusatzarbeit bedeutet).

Ich muss jetzt erstmal überlegen, ob das trauriger Fehlentwurf ist oder clevere Kapselung. Jedenfalls war es nicht leicht, das Problem überhaupt zu erkennen.

[Krishty]

An alle, die eine Stapelverarbeitung schreiben:

Verarbeitet die größten Aufgaben zuerst.

Nehmen wir an, ich habe zehn Aufgaben: neun, die jeweils eine Sekunde dauern; und eine, die drei Sekunden dauert. Das hier ist, wie man sie perfekt auf vier Kerne aufteilt:

    [   9   ]
    [0][3][6]
    [1][4][7]
    [2][5][8]
    0  1  2  3 -> Sekunden

Und das hier ist, wie man seine Benutzer in den Wahnsinn treibt:

    [0][4][8]
    [1][5][   9   ]
    [2][6]
    [3][7]
    0  1  2  3  4  5 -> Sekunden

Visual C++ nimmt grundsätzlich die Reihenfolge, die mir die lange Nase zeigt.

[B.G.Michi]

Eclipse CDT Indexer. Was habe ich verbrochen um dieses Stück "Software" verdient zu haben. Frisst ca 16 GB Arbeitsspeicher und findet meine Includes trotzdem nicht. Nicht mal die im selben Workspace... mit direkter Pfadangabe... "Unresolved includes (from headers in index)". Wenn mir jede einzelne Zeile meines Editorfensters rot unterringelt wird kann ich auch gleich darauf verzichten und meine Programme mit editor.exe schreiben. Nur so nebenbei: es kompiliert selbstverständlich ohne Fehler. Oder hab ich das Prinzip einer/dieser IDE einfach noch nicht verstanden?

[kaiserludi]

An alle, die eine Stapelverarbeitung schreiben:

Verarbeitet die größten Aufgaben zuerst.

Nehmen wir an, ich habe zehn Aufgaben: neun, die jeweils eine Sekunde dauern; und eine, die drei Sekunden dauert. Das hier ist, wie man sie perfekt auf vier Kerne aufteilt:

    [   9   ]
    [0][3][6]
    [1][4][7]
    [2][5][8]
    0  1  2  3 -> Sekunden

Und das hier ist, wie man seine Benutzer in den Wahnsinn treibt:

    [0][4][8]
    [1][5][   9   ]
    [2][6]
    [3][7]
    0  1  2  3  4  5 -> Sekunden

Visual C++ nimmt grundsätzlich die Reihenfolge, die mir die lange Nase zeigt.

Man sieht doch z.B an den Zeitdauerangaben für Kopiervorgänge im Explorer sehr gut, dass es oft nicht trivial ist, die Dauer eines Tasks automatisiert im vorraus halbwegs genau abzuschätzen. Weiß man aber nicht, wie lange einzelne Tasks dauern werden, so ist es unmöglich, sie an Hand ihrer Dauer optimal auf die Threads aufzuteilen.

[Krishty]

Visual C++ nimmt grundsätzlich die Reihenfolge, die mir die lange Nase zeigt.

Man sieht doch z.B an den Zeitdauerangaben für Kopiervorgänge im Explorer sehr gut, dass es oft nicht trivial ist, die Dauer eines Tasks automatisiert im vorraus halbwegs genau abzuschätzen.

Äh, doch. Es gibt in Visual C++ein Feature namens IntelliSense, das jede Datei unentwegt im Hintergrund kompiliert; und die Größe der IntelliSense-Datenbank einer Objektdatei korreliert erstaunlich gut mit der tatsächlichen Kompilierzeit. Jedenfalls gut genug um nicht die 100-zu-1-Unterschiede auftreten zu lassen, die ich bei alphabetischer Kompilierung sehe. Aufgaben nach Größe der jeweiligen IntelliSense-Datenbank sortieren; damit wären 99 % des Frusts weggeputzt.

[antisteo]

Das gwX-Projekt scheitert momentan an einer Third-Party-Library (Namentlich Physikengine Newton), bei der keine Repos-Version mehr kompilierbar ist und die veralteten, die noch zu kompilieren gingen, haben massig Bugs und unimplementierte Features.

Ich bleibe lieber bei 2D-Spielen ohne Physik. Alles schön im Browser und alle Libraries selbergeschrieben. Da hat man am wenigsten Probleme.

[Jonathan]

In CMake macht SET(my_var) genau das selbe wie UNSET(my_var)

...

[Krishty]

Abstürze beim Debugging verändern nachhaltig die Ausführungsart eures Programms:

    *** An Access Violation occurred in "C:\Users\Krishty\Desktop\source\Debug\foo.exe" :

    The instruction at 0000000073EA4F0D tried to read from an invalid address, 0000000000000010

    *** enter .exr 000000000008E090 for the exception record
    *** enter .cxr 000000000008DBA0 for the context
    *** then kb to get the faulting stack

    Unhandled exception at 0x73EA4F0D in foo.exe: 0xC000041D: Unbehandelte Ausnahme während eines Benutzerrückrufs.

und dann kommt ein Fenster

    [Window Title]
    Programmkompatibilitätsassistent

    [Main Instruction]
    Es wurde festgestellt, dass dieses Programm nicht richtig ausgeführt wird.

    Auf dieses Programm wurden Kompatibilitätseinstellungen angewendet, um das Problem zu beheben. Diese Einstellungen werden bei der nächsten Ausführung des Programms verwendet.

    Führen Sie das Programm erneut aus, wenn es nicht richtig ausgeführt wird.

    Programm: Unbekanntes Programm
    Herausgeber: Unbekannter Herausgeber

    Pfad: C:\Users\Kr…\foo.exe

    [Schließen]

    [Footer]
    Welche Einstellungen werden übernommen?

Im Jammer-Thread, weil: Das ganze ist passiert, WÄHREND EIN DEBUGGER ANGESCHLOSSEN WAR. Mein Programm wird also zukünftig mit Shims ausgeführt?! Und wie teste ich jetzt?! AAAAAAH

Besagter Fall krachte in der Callback-Funktion eines Dialogs. Auch erwähnt unter When Even Crashing Doesn’t Work auf Random ASCII.

[Krishty]

export template aus dem Standard geschmissen zu haben war der größte Fehler, den das C++-Komitee in letzter Zeit gemacht hat. Das Desaster mit den Concepts ist entschuldbar; aber weder Modulsystem noch export template zu haben macht die Übersetzungszeit für Metaprogrammierung zu einer gewaltigen Katastrophe. Ich bin sehr sehr stark geneigt, generische Programmierung mit void-Zeigern zu machen. Wie fuckin Java.

[Artificial Mind]

Alle aktuellen Betriebssystem cachen _massiv_ Dateien wenn man genug Ram hat. Auch große, komplett.
1.5 GB Datei. Komplett im Ram nach dem ersten kompletten Zugriff, nach Minuten nicht verdrängt.

Warum Jammer-Thread?
Ich kann meine Bachelorarbeit nicht vernünftig evaluieren weil ich 700MB/s (buffered filestream) bis 3.2GB/s (unbuffered filestream) Lesegeschwindigkeit von meiner HDD bekomme.

Einzige Chance: CreateFile aus der WinApi mit FILE_FLAG_NO_BUFFERING. Mal davon abgesehen, dass CreateFile hässlich und nicht plattformunabhängig ist, ist das auch noch fern ab vom Anwendungsfall.
Naja, und ich könnte es nochmal mit einem 300GB großen Datensatz versuchen. Da stehen die Chancen gut, dass es nicht gecached wird.