Jammer-Thread

Hier kann über allgemeine Themen diskutiert werden, die sonst in kein Forum passen.
Insbesondere über Szene, Games, Kultur, Weltgeschehen, Persönliches, Recht, Hard- und Software.
Benutzeravatar
marcgfx
Establishment
Beiträge: 2050
Registriert: 18.10.2010, 23:26

Re: Jammer-Thread

Beitrag von marcgfx »

bildanhang: es ist einfacher meinen eigenen vorhandenen upload-flow zu nutzen, vor allem wenn ich das bild auf verschiedenen seiten poste.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Mein Windows hat sich die ganze Zeit in China beschwert, dass es gefälscht sei. Jetzt bin ich zurück in Deutschland, und die Meldungen sind verschwunden. WTF?!

  bool isGenuineWindows() {
    if(isInChina())
      return false;
    return checkSerial();
  }
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Jonathan »

Naja, ich würde mich nicht wundern, wenn dein vorgeschlagener Algorithmus tatsächlich eine höhere Trefferrate hätte, als jede andere, noch so komplizierte Piraterie-Erkennung. :D
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Naja, das war früher mal. Die dort gekauften DVDs lassen sich hier wegen Kopierschutz und Regionalcodes nicht abspielen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: Jammer-Thread

Beitrag von CodingCat »

Ich habe die letzten Tage versucht, OpenCL Address Spaces in sämtliche C++-Verzweigungen des Clang-Frontends zu prügeln (https://github.com/tszirr/clang), um endlich uneingeschränktes C++17 zu OpenCL/Vulkan/SPIR-V kompilieren zu können. Implizite Casts, Initializer Lists und alle expliziten Casts habe ich in 3 langen Nächten durchgeackert, und dabei mehr von Compiler-Code gesehen als mir lieb ist. Unglaublich, wie unstrukturiert und redundand das da zugeht, unzählige Sonderbehandlungen, die immer wieder die gleichen Daten über Nadelöhr-Interfaces in neue Datenstrukturen zwängen. Und wenn man dann sieht, was Template-Support in diesem Code anrichtet, wird einem nur noch übel - Dependent Types, Names etc. replizieren mangels direkter Prüfbarkeit einen nicht unbedeutenden Teil der Logik direkt nochmal. Dass da noch ein Parade-Compiler der Konformität und Fehler-Diagnostik rauskommt, ist beeindruckend, die Lust auf Mitarbeit vergeht einem aber schnell. Address Spaces jetzt auch noch vom Parsen der Methoden-Attribute bis hin zum Cast des impliziten This-Arguments beim Methodenaufruf durch sämtliche Schichten und Fälle zu ziehen übersteigt jedenfalls meine Motivation.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Jonathan »

dieser Moment, wenn man sich jahrelang gefragt hat, wie Leute es schaffen, ein kniffeliges Problem elegant zu lösen, nur um herauszufinden, dass sie es absolut nicht elegant lösen... brrrr
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Respekt dafür. Wird das eure nächste große Middleware-API, in Konkurrenz zu dem Zeug, das AMD gerade so raushaut?

Ich persönlich muss übrigens sagen, dass GPGPU für mich eine einzige Katastrophe ist:
  • Was ich mit D3D 9 gemacht habe (ich bin alt), konnte man eh wegschmeißen, als D3D 10 mit seiner echten 32-Bit-Genauigkeit rauskam. (Wink zu Zudomon!)
  • Was ich mit D3D 10 gemacht habe, habe ich für Compute Shaders in D3D 11 weggeschmissen.
  • Was ich in D3D 11 gemacht habe, kann ich für D3D 12 wegschmeißen. Will lieber gleich auf Vulkan umsteigen, aber da muss ich die Shader ja von Hand kompilieren (bei D3D macht das Visual Studio für mich).
  • Ein Glück, dass ich nie was mit CUDA oder AMD APP gemacht habe, sonst würde ich vor lauter Portierungsaufwand zu nichts mehr kommen.
  • Du wirst mir natürlich jetzt sagen, dass deins für alle Zeiten funktionieren wird, aber die Erfahrung zeigt halt, dass ich in zwei Jahren wieder hier sitze und alles auf eine komplett andere API/Hardware portieren muss.
  • Die einzigen Grafikeffekte, die ich einmal schreiben konnte und heute noch original laufen, waren CPU-basiert (Meshes auf der CPU ausrechnen und so).
So verbittert das auch klingt: Ich überlege, sogar meine mittelschweren Ambient-Occlusion-Berechnungen nur noch in x86 auf der CPU zu machen. Ich kann’s einfach debuggen, brauche keine Zweitsprache/keinen anderen Compiler, es läuft Plattform- und Hardware-unabhängig, ich bin bisher bei noch keinem Projekt CPU-bound, und vor allem bedeutet fertig dann auch wirklich fertig. Habe dann zwar nur ein Zehntel der FLOPs, aber die nutzt doch eh keiner richtig aus.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: Jammer-Thread

Beitrag von CodingCat »

Krishty hat geschrieben:Respekt dafür. Wird das eure nächste große Middleware-API, in Konkurrenz zu dem Zeug, das AMD gerade so raushaut?
Nein, purer Idealismus, aber der ist damit auch schon wieder aufgebraucht. Auf OpenCL fiel die Wahl auch nur, weil Khronos dafür bereits eine vollständige Kette bis hin zu SPIR-V anbietet.
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Ace Combat 7 wird auch den völlig effektüberladenen Look der Unreal Engine bekommen.
[youtube]_zuBSUJfpBk[/youtube]
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Jammer-Thread

Beitrag von Chromanoid »

Mmh, die Wolken sehen dafür wenigstens gut aus :)

Das habe ich mal mit dem Smartphone auf nem Linienflug fotografiert. Die Unterschiede finde ich jetzt nicht gravierend.
20121007_123326.jpg
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Jammer-Thread

Beitrag von Alexander Kornrumpf »

Krishty hat geschrieben:Ace Combat 7 wird auch den völlig effektüberladenen Look der Unreal Engine bekommen.
Ich kenne das Spiel nicht, aber wenn es ein Flugsimulator ist, wird man es sowieso nicht aus den Perspektiven spielen, die hier gezeigt wurden?!
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Naja, falls sie das Chase-Cam-Railshooter-Zeug aus dem Vorgänger weiterführen, wird das Spiel so aussehen wie der Trailer, nur mit UI drüber. Jetzt wo ich nochmal drüber nachdenke, ging das eigentlich vor sechs Jahren bergab, als die Serie von Microsoft für die XBox übernommen wurde und man es „westlicher“ gestalten wollte.

Was ich jedemfalls meinte, war: „Wir schießen eine Rakete ab! Mach die Shock Diamonds in 3D. So, dass man es auch sieht! Und mach Glare drum. Ist schließlich HDR. Das muss man sehen! Und das ist Feuer, wir brauchen Hitzeflimmern. Eins, das man im Trailer sieht! Welche Effekte hat der Editor noch?“ Dieser Zwang zum Technikposing scheint jedem Unreal-Spiel inhärent zu sein.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Vermeidet den Speicher, sage ich immer. Schiebt nicht immer alles über den Stack, sage ich immer. Sogar der L1-Cache bedeutet drei Takte Wartezeit, sage ich immer. Und so sieht das dann aus wenn ich es schreibe vs. wenn es jemand anders schreibt (alles, was Speicher referenziert, grün markiert):
Speicher.png
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Jammer-Thread

Beitrag von Chromanoid »

Krishty hat geschrieben:Vermeidet den Speicher, sage ich immer. Schiebt nicht immer alles über den Stack, sage ich immer. Sogar der L1-Cache bedeutet drei Takte Wartezeit, sage ich immer. Und so sieht das dann aus wenn ich es schreibe vs. wenn es jemand anders schreibt (alles, was Speicher referenziert, grün markiert):
Bild
Wie sieht denn der Code dazu aus? Würdest Du sagen, dass Dein "Stil" von der Sprache unterstützt/befördert wird? Mittlerweile sehe ich Sprach-Features ein bisschen wie Spielmechaniken, überall gibt es kleine Belohnungen und Bestrafungen, die dann bestimmte Spielstile/Programmierstile hervorrufen. Das kann man ja insgesamt in komplexen Systemen so sehen, finde ich auch eine sehr hilfreiche Metapher, wenn es darum geht Softwareentwicklungsprozesse insgesamt zu betrachten.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Der direkte Quelltext ist recht ähnlich:

  scale = xyzFrom(1.0f, 1.0f, -1.0f);
  foo = transform(tri.a * scale, matrix);
  bar = transform(tri.b * scale, matrix);
  baz = transform(tri.c * scale, matrix);


vs.

  Vec3d scale(1, 1, -1);
  foo = (tri[0] * scale).transform(matrix);
  bar = (tri[1] * scale).transform(matrix);
  baz = (tri[2] * scale).transform(matrix);


Mein Stil (C mit freien Funktionen) wird genau so unterstützt/gefördert wie deren (C++ mit Konstruktoren und Methoden). Die Probleme bei ihnen sind
  • Sie wollen unbedingt sowohl via Array-Operator [] auf die Punkte ihrer Dreiecke zugreifen als auch via .a() .b() .c()-Methoden. Die Punkte sind intern aber nicht als Array gespeichert, darum haben sie einen Operator überladen, der dann das passende Attribut zum Index raussucht. Weil das als switch zu langsam ist, machen sie das mit Adressberechnungen. Der Compiler hat aber nur Adressen für Dinge, die im Speicher liegen.
  • Genau das selbe nochmal für die einzelnen Komponenten der Koordinaten (.y() == [1]).
  • Sie haben float und double durcheinandergeschmissen, und jetzt wird implizit konvertiert und das ist Overhead.
  • Die Operatoren und Methoden sind so tief verschachtelt, dass der Compiler irgendwann den Überblick übers Aliasing der Attribute verliert. (Jede Vektoroperation erzeugt einen neuen Vektor, ruft den Konstruktor auf, ruft ein .set() auf, kopiert es dann für die Rückgabe …)
  • Sie nutzen kein SIMD. Das ist aber nicht so schlimm; man kann saubere Befehle wie links meist auch skalar erzeugen (SIMD verbessert nur 20–40 %).
Im Grunde ist das Framework da scheiße entwickelt; sie wollten unbedingt alles generisch halten und jetzt versteht der Compiler nicht mehr, was mit den Variablen passiert.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: Jammer-Thread

Beitrag von Chromanoid »

Ah danke für die Erläuterungen!
Mmh, mir scheint das Überladen des Array-Operators scheint schnell solche Probleme hervorzurufen, oder? Durch den Operator wird evt. sogar die Erwartung geweckt, dass es damit schneller geht...
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Es erfordert zumindest das Casten des this-Zeigers zu was anderem (float *?), und ja, das kann fast kein Compiler mehr wegoptimieren.

Man könnte die Punkte intern als Array von drei floats auslegen, das wäre schon besser. Aber viele Compiler können dann auch nicht mehr optimieren, weil die Information „das, was zwei Indizes vom Anfang entfernt ist“ schwieriger durch temporäre Variablen verfolgt werden kann als „die Variable namens Z“.

Btw scheinen vor allem Mathematiker das Adressieren mit Indizes viel vertrauter zu finden als durch xyz. Wenn sie es unbedingt brauchen (gibt tatsächlich ein paar Algorithmen, in denen man Schleifen über die Komponenten haben will), sollen sie aber stattdessen lieber einen Tupel-Datentyp nutzen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Matthias Gubisch
Establishment
Beiträge: 470
Registriert: 01.03.2009, 19:09

Re: Jammer-Thread

Beitrag von Matthias Gubisch »

Von wieviel Unterschied in der der Performance reden wir hier denn eigentlich?
Bevor man den Kopf schüttelt, sollte man sich vergewissern einen zu haben
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Für 12 MiB Vertex-Daten sprechen wir von 0.007 gegen 0.031 ms. Die haben ihren Schrott-Code dann auch noch mittels einer Drittbibliothek auf alle Kerne parallelisiert, damit auch wirklich alle meine Kerne auf den Speicher warten, so wichtig war ihnen die Performance.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Scheinbar ist es unmöglich, einen Icon zu bauen, der unter Vista und höher PNG ist (hochauflösend und transparent) und unter XP trotzdem funktioniert (XP unterstützt keine PNG-Icons).

Ich dachte, ich könnte einfach zwei Versionen der 32x32-Auflösung reinpacken, einmal als PNG und einmal traditionell, und die richtige würde rausgesucht. Aber kommt die traditionelle Version zuerst, nutzen auch Vista/7/8/10 sie (anstelle der edlen). Kommt die edle Version zuerst, kann XP die Datei nicht mehr lesen.

Also letzter Versuch: Die 16x16-Version traditionell als erstes Icon speichern. In Vista/7/8/10 sieht man die ja sowieso nie, weil die Icons da nie so klein werden. Und in XP ist es dann zwar niedrig aufgelöst, aber besser als nichts. Und was passiert? XP kann den Icon nicht lesen, wenn kein lesbares 32x32 drin vorkommt; ignoriert das 16x16 und zeigt einen Platzhalter an. WTF WTF WTF

Nagut, also mache ich zwei Icons draus. Ich packe das High-Res-Icon zuerst in die EXE. Danach das XP-Icon. XP wird jawohl merken, dass das erste unlesbar ist, und dann vorspulen zum zweiten, oder? NEIN ES IGNORIERT DAS ZWEITE EINFACH. Boah fuck it


Nachtrag: Ich hab’s. Nach nur 60 Versuchen:
  • Weder XP noch neuere Windows-Versionen geben dem Icon eine zweite Chance. Wird der erste Treffer nicht erfolgreich geladen, gibt’s nen Platzhalter.
  • Man muss also bei der Auswahl der Auflösung ansetzen.
  • Im Icon-Verzeichnis gibt es einen Eintrag für die Farbtiefe. Bei PNG ist der gewöhnlich ungenutzt, weil sich die Farbtiefe aus der PNG-Datei ergibt, die eingebettet ist.
  • XP unterstützt dort kein "32", Vista und neuere Windows-Versionen schon.
  • Man legt also vier Bilder im Icon an:
    1. 32², 256 Farben, Farbtiefe "8". Dieses Symbol wird XP aussuchen. Vista und höher werden es verwerfen weil die Farbtiefe von 2. näher an der Bildschirmfarbtiefe liegt.
    2. 32², PNG, Farbtiefe "32". Dieses Symbol wird Vista/höher aussuchen. XP wird es verwerfen weil es solche Farbtiefen nicht kennt.
    3. 48² und weitere Auflösungen als PNG für Vista/höher.
  • Die Reihenfolge darf nicht verändert werden, weil XP abbricht, sobald es einem PNG begegnet.
  • warum ist der Scheiß nirgends dokumentiert
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
glassbear
Establishment
Beiträge: 324
Registriert: 08.04.2003, 18:09
Alter Benutzername: Enrico_
Echter Name: Enrico
Wohnort: San Diego
Kontaktdaten:

Re: Jammer-Thread

Beitrag von glassbear »

Krishty hat geschrieben:Vermeidet den Speicher, sage ich immer. Schiebt nicht immer alles über den Stack, sage ich immer. Sogar der L1-Cache bedeutet drei Takte Wartezeit, sage ich immer. Und so sieht das dann aus wenn ich es schreibe vs. wenn es jemand anders schreibt (alles, was Speicher referenziert, grün markiert):
Ist halt nur Gerede. Ohne bessere Ausbildung und viel bessere Lernmaterialen wird das auch so bleiben. Das ist doch mal eine Herausforderung ;)
Ich wuerde sogar dafuer bezahlen (lassen, vom Chef).
Ein Hoch auf uns Männer... Auf die Frau, die uns HAT ( oder hat, und nicht weiß, dass sie uns hat ) ...auf die Idiotinnen ... besser gesagt VOLLPFOSTINNEN ... die uns hatten und uns verloren haben ... und auf die GLÜCKLICHEN, die das Vergnügen & Glück haben werden uns kennenzulernen!
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

KB3035583: Update installs Get Windows 10 app in Windows 8.1 and Windows 7 SP1 wird bei mir wieder in den Updates eingeblendet (obwohl ich's zweimal ausgeblendet hatte).
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Visual C++ reserviert für jede lokale Variable einzigartigen Stapelspeicher; selbst, wenn sie in unterschiedlichen Scopes sind. Der Stack-Bedarf einer Funktion wächst also nicht mit den gleichzeitig genutzten lokalen Variablen, sondern mit der Summe aller Variablen in allen ifs und fors.

Erstmal fällt mir kein Grund ein, sowas zu machen, außer ich klatsche den Code für die Allokation mal schnell hin.

Zweitens wuchert die Größe der erzeugten Maschinenbefehle. Denn obwohl die nicht mehr werden, werden sie größer – Offsets von 128 B oder mehr vom Stapelzeiger müssen als 32- statt 8-Bit-Zahlen kodiert werden; Befehle zum Laden und Speichern der Werte sind dann glatt doppelt so groß. Und das, während ein großer Teil des Platzes an den niedrigen Offsets schlicht brach liegt.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
antisteo
Establishment
Beiträge: 854
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: Jammer-Thread

Beitrag von antisteo »

Krishty hat geschrieben:Visual C++ reserviert für jede lokale Variable einzigartigen Stapelspeicher; selbst, wenn sie in unterschiedlichen Scopes sind. Der Stack-Bedarf einer Funktion wächst also nicht mit den gleichzeitig genutzten lokalen Variablen, sondern mit der Summe aller Variablen in allen ifs und fors.

Erstmal fällt mir kein Grund ein, sowas zu machen, außer ich klatsche den Code für die Allokation mal schnell hin.

Zweitens wuchert die Größe der erzeugten Maschinenbefehle. Denn obwohl die nicht mehr werden, werden sie größer – Offsets von 128 B oder mehr vom Stapelzeiger müssen als 32- statt 8-Bit-Zahlen kodiert werden; Befehle zum Laden und Speichern der Werte sind dann glatt doppelt so groß. Und das, während ein großer Teil des Platzes an den niedrigen Offsets schlicht brach liegt.
Optimale statische Allocation ist genau wie bei den Registern NP-Hart. Das haben die Ingeneure erkannt und bevor sie irgendeine Greedy-Taktik benutzen, die nicht exakt arbeitet, benutzen sie lieber gar nix.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Wow.

  if(x) {
    int a;
  } else {
    int b;
  }


Da zu merken, dass a oder b nicht gleichzeitig allokiert sind, ist NP-hart?

  for(int i = 0; i < x; ++i) {
    int a;
  }
  for(int j = 0; j < y; ++j) {
    int b;
  }


Hier auch? Dann hab’ ich damals echt was verpasst. Ich dachte, Scopes wären extra für sowas da.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
antisteo
Establishment
Beiträge: 854
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: Jammer-Thread

Beitrag von antisteo »

Krishty hat geschrieben:Wow.

  if(x) {
    int a;
  } else {
    int b;
  }


Da zu merken, dass a oder b nicht gleichzeitig allokiert sind, ist NP-hart?

  for(int i = 0; i < x; ++i) {
    int a;
  }
  for(int j = 0; j < y; ++j) {
    int b;
  }


Hier auch? Dann hab’ ich damals echt was verpasst. Ich dachte, Scopes wären extra für sowas da.
Es ist für den allgemeinen Fall nicht in P, also scheinen die Entwickler von Microsoft schon eher aufgegeben zu haben :D

In Wahrheit ist das Problem extrem einfach, da man lediglich das Maximum der Stacktiefe jeder Anweisung berechnen muss. Die Stack-Bytes des letzten Scopes könnten einfach im nächsten Scope wieder verwendet werden. Problem ist, dass dieser Denkansatz die Existenz der Scopes auf der Optimierer-Ebene voraussetzt. Das ist z.B. bei LLVM auch nicht der Fall. Insbesondere könnte man sogar Optimierungen verpassen, wenn man nicht cross-scope Anweisungen umsortieren darf. Also werden alle Stack-Variablen als `alloca`s in den Code gespuckt. Die müssen dann auf dem Stack und den Registern verteilt werden. Und für diesen allgemeinen Fall ist das Problem dann wieder NP-hart.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Jammer-Thread

Beitrag von Alexander Kornrumpf »

Ist das eigentlich legal?

Code: Alles auswählen

//...
{
    int foo = 0;
    ++foo;
    goto bar;
    baz:
    ++foo; //welchen Wert hat foo?
}
{
    int foobar;
    bar:
    foobar = 1; //sind foo und foobar gleichzeitig allokiert oder nicht?
    goto baz;
}
//...
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: Jammer-Thread

Beitrag von Spiele Programmierer »

:?: Warum denkst du, dass es dann Heap wäre? Es geht doch nur darum, dass nicht gleichzeitig benötigte lokale Variablen in einer Funktion sich den selben Speicher teilen. Das hat mit beliebiger Freigabe und Allokation zur Laufzeit doch nichts zu tun.

@Optimierung unrealistisch weil NP-Hart
Interessanterweise werden die lokalen Variablen sowohl vom GCC als auch von Clang seit langem mit -O1 gefaltet. (Zum selbst ausprobieren) So schwer ist das nicht. Und selbst wenn es das wäre - Compiler sind gerade für solche Optimierungen da. Natürlich ist es unmöglich, den absolut kürzesten oder den schnellsten Code zu generieren. Aber warum sollten wir deshalb gleich aufgeben und nicht unser Bestes versuchen? "Greedy"-Algorithmen können in der Praxis häufig sehr gute Ergebnisse liefern. Wir wollen doch auch nicht die Registerallokation deaktivieren weil sie nur Greedy ist?

Zur Verteidigung des MSVC (2015) muss man allerdings anmerken, dass er bei mir in meinen Beispielcode auch den Stack zusammenfaltet. Also vielleicht bloß eine spezielle Situation in dem der Optimizer aufgrund ungünstiger Heuristiken leider versagt?
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: Jammer-Thread

Beitrag von Alexander Kornrumpf »

Spiele Programmierer hat geschrieben::?: Warum denkst du, dass es dann Heap wäre? Es geht doch nur darum, dass nicht gleichzeitig benötigte lokale Variablen in einer Funktion sich den selben Speicher teilen. Das hat mit beliebiger Freigabe und Allokation zur Laufzeit doch nichts zu tun.
Ich habe es gelöscht bis meine Frage mit dem goto geklärt ist.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

@antisteo: Ja; klar. Spätestens, wenn die Scopes unterschiedlich große Brocken allokieren und dazwischen andere Variablen sitzen, beginnen einfache Algorithmen zu fragmentieren.

LLVM nutzt einen anderen Algorithmus, da sie ja sowieso auf Static Single Assignment arbeiten. Da kann sich theoretisch jede Variable den erstbesten freien Slot suchen, so dass z.B. die Komponenten eines 3D-Vektors an getrennten Adressen liegen, je nachdem, wo gerade was frei ist. Da wieder Lokalität reinzukriegen, das ist NP-vollständig, ja.

Visual C++ hat bisher kein SSA genutzt. Sie wollten immer mal darauf umstellen; ich weiß nicht, ob das mittlerweile passiert ist. Die aktuelle Implementierung sieht mir aber, wie du sagst, nach reiner Kapitulation aus.
Alexander Kornrumpf hat geschrieben:Ist das eigentlich legal?
Nein. Visual C++ erlaubt’s trotzdem und tut weitestgehend, was du erwarten würdest; plus Warnung, dass die Initialisierung übersprungen wird. (Ein schönes Beispiel, warum wir viel zu viel Undefined Behaviour haben.)

@Spiele Programmierer: VS 2013 hat auch in den einfachsten Fällen versagt; mit 2015 müsste ich es nochmal testen. Aber was bringt das schon? Was kümmert es mich, wenn es bei Dreizeilern funktioniert, so lange mein echtes Programm nicht vernünftig optimiert wird?

Was ich aber testen muss, ist, für Größe zu kompilieren. Falls es dann geht, war es vielleicht eine bewusste Entscheidung um irgendwelche Cache-Exzentrizitäten zu umschiffen oder so.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Antworten