3. Unterschied Templates und Generics?

Unterschied Templates und Generics?


  • @dgfgfd: Kovarianz und Kontravarianz

    0
  • T

    hustbaer schrieb:

    Arcoth schrieb:

    hustbaer schrieb:

    Also abgesehen von dem ganzen Zeugs was man generell mit Java (auch ohne Generics) machen kann was mit (Standard) C++ nicht geht. Also Garbage Collection, Reflection usw.

    Wo waere GC ueberhaupt sinnvoll? Reicht shared ownership nicht aus?

    So wie ich das mitbekommen habe gibt es viele lock-free Algorithmen die mit GC recht schön umsetzbar sind aber ohne GC nur unter viel Schmerzen und/oder mit zusÀtzlichem Overhead. ABA Problem und so.
    👍

    Und warum nimmt man dafĂŒr keine GC? Nur weil keiner im Standard ist heißt, das ja nicht daß es keinen gibt.

    0

  • hustbaer schrieb:

    Arcoth schrieb:

    hustbaer schrieb:

    Also abgesehen von dem ganzen Zeugs was man generell mit Java (auch ohne Generics) machen kann was mit (Standard) C++ nicht geht. Also Garbage Collection, Reflection usw.

    Wo waere GC ueberhaupt sinnvoll? Reicht shared ownership nicht aus?

    So wie ich das mitbekommen habe gibt es viele lock-free Algorithmen die mit GC recht schön umsetzbar sind aber ohne GC nur unter viel Schmerzen und/oder mit zusÀtzlichem Overhead. ABA Problem und so.

    Bin kein Experte auf dem Gebiet aber mir macht es doch immer den Anschein, dass all diese "schönen" Umsetzungen so funktionieren, dass die Existenz eines "GC" mit genau den richtigen Eigenschaften angenommen wird, sodass die ganze eigentliche KomplexitĂ€t des Problems in diesem "GC" verschwindet. Wenn man's genau nimmt, geht es in der Regel nie wirklich um GC, sondern eigentlich um das Management der Lebensdauer von Objekten, die aus einer Datenstruktur entfernt wurden, aber potentiell noch nebenlĂ€ufig gerade von jemandem verwendet werden. Das ist eigentlich ein Problem, das völlig orthogonal – wenn nicht sogar antigonal – ist zu GC...

    Wir sagen halt: Es gibt ein Orakel, das hinreichend perfekt, völlig reentrant und ohne Overhead feststellt, welches Objekt genau wann zu zerstören ist, zeigen, dass wir XYZ dann lock-free machen können – wenn man den ĂŒblichen Counter-Hack fĂŒr das ABA Problem als "korrekte Lösung" definiert, versteht sich – und fertig ist die Kiste. Bis jetzt hat mich noch keiner dieser Algos beeindruckt...

    Tyrdal schrieb:

    hustbaer schrieb:

    Arcoth schrieb:

    hustbaer schrieb:

    Also abgesehen von dem ganzen Zeugs was man generell mit Java (auch ohne Generics) machen kann was mit (Standard) C++ nicht geht. Also Garbage Collection, Reflection usw.

    Wo waere GC ueberhaupt sinnvoll? Reicht shared ownership nicht aus?

    So wie ich das mitbekommen habe gibt es viele lock-free Algorithmen die mit GC recht schön umsetzbar sind aber ohne GC nur unter viel Schmerzen und/oder mit zusÀtzlichem Overhead. ABA Problem und so.
    👍

    Und warum nimmt man dafĂŒr keine GC? Nur weil keiner im Standard ist heißt, das ja nicht daß es keinen gibt.

    Der Standard wurde mit C++11 und 14 sogar extra angepasst, um GC Support theoretisch zu erlauben...

    0

  • dot schrieb:

    Bin kein Experte auf dem Gebiet aber mir macht es doch immer den Anschein, dass all diese "schönen" Umsetzungen so funktionieren, dass die Existenz eines "GC" mit genau den richtigen Eigenschaften angenommen wird, sodass die ganze eigentliche KomplexitÀt des Problems in diesem "GC" verschwindet.

    Soweit ich weiss garantiert z.B. die JVM genau diese Annahmen. Und natĂŒrlich macht das den GC komplexer. Genau so wie inlining den C++ Compiler komplexer macht (und natĂŒrlich jeden anderen Compiler der Inlining macht, also quasi jedes "brauchbare" Compiler-Backend ĂŒberhaupt, inklusive Hotspot & Co.). In beiden FĂ€llen ist es ein grosser Benefit: man hat ein System das komplex ist, und sehr sehr viele Projekte die dadurch vergleichsweise sehr einfach gut Performance erreichen können.

    dot schrieb:

    Wenn man's genau nimmt, geht es in der Regel nie wirklich um GC, sondern eigentlich um das Management der Lebensdauer von Objekten, die aus einer Datenstruktur entfernt wurden, aber potentiell noch nebenlĂ€ufig gerade von jemandem verwendet werden. Das ist eigentlich ein Problem, das völlig orthogonal – wenn nicht sogar antigonal – ist zu GC...

    Ich weiss nicht genau wie ich darauf jetzt antworten soll...
    Der GC ist dafĂŒr zustĂ€ndig MĂŒll wegzurĂ€umen. DafĂŒr muss er wissen welche Objekte noch referenziert werden. Und wenn er als Teil eines Systems funktionieren muss welches Threads "hat" und es explizit erlaubt Referenzen ohne extra Synchronisierung einfach so zu verbiegen, dann muss er halt auch damit klarkommen. Und wenn Referenzen in Registern gehalten werden dĂŒrfen auch damit und und und. Ich verstehe also nicht wieso das "nicht mit dem GC zu tun" haben soll 😕

    dot schrieb:

    Wir sagen halt: Es gibt ein Orakel, das hinreichend perfekt, völlig reentrant und ohne Overhead feststellt, welches Objekt genau wann zu zerstören ist, zeigen, dass wir XYZ dann lock-free machen können – wenn man den ĂŒblichen Counter-Hack fĂŒr das ABA Problem als "korrekte Lösung" definiert, versteht sich – und fertig ist die Kiste. Bis jetzt hat mich noch keiner dieser Algos beeindruckt...

    Ich bin mir nicht sicher ob ich den Satz so 100% verstehe.

    Aber egal. ABA ist ja auch nicht das einzige Problem.
    Ein weiteres ist z.B. hier beschrieben: https://en.wikipedia.org/wiki/Hazard_pointer
    Und ja, klar kann man Hazard Pointer verwenden. Ist aber auch nicht schön oder einfach, und auch alles andere als gratis.

    NatĂŒrlich gibt es auch noch andere Möglichkeiten das zu lösen. z.B. kann man "atomic operations" fĂŒr shared_ptr verwenden. Wenn man sich dann aber anguckt wie diese implementiert sind, dann wird man sehen dass hier ĂŒblicherweise Lock-Pools verwendet werden. Weil man sie auf den meisten CPUs einfach nicht ohne Locks umsetzen kann. Man mĂŒsste dazu gleichzeitig:
    - Nen Zeiger aus dem Speicher laden (bzw. bei shared_ptr sogar zwei Zeiger, was aber das kleinste Problem, da man sie direkt nebeneinander ablegen kann -- und bei intrusive_ptr kÀme man wirklich mit einem Zeiger aus)
    - PrĂŒfen ob er NULL ist, und wenn nicht...
    - Einen ĂŒber diesen Zeiger erreichbaren ZĂ€hler inkrementieren
    Mit Transactional Memory sollte das gehen, aber ohne wĂŒsste ich nicht wie man das lock-free hinbekommen soll.

    Dadurch vernichtet man die "lock-free-heit" der Implementierung und gleichzeitig auch jede Chance darauf dass die Implementierung performancemÀssig mithalten kann.

    0

  • Tyrdal schrieb:

    Und warum nimmt man dafĂŒr keine GC? Nur weil keiner im Standard ist heißt, das ja nicht daß es keinen gibt.

    Der GC muss beweisen können dass ein Objekt nicht mehr referenziert wird bevor er es wegrÀumt. Vor C++11 kann er das definitiv nicht ohne Support der Implementierung (Compiler, ...). Bzw. meiner Meinung nach kann er es nichtmal mit Support des Compiler.

    Ein Problem ist dabei z.B. dass C++ es erlaubt Zeugs per memcpy, memmove bzw. auch mittels unsigned char* rumzukopieren. Damit kann man völlig standardkonforme Programme bauen, in denen zwischendurch ZustÀnde existieren wo nirgends (Speicher, Register, ...) Bytemuster existieren die einem Zeiger auf Bereich X entsprechen oder auch nur Àhnlich sehen. Aber trotzdem danach wieder - auch ganz legan und standardkonform - ein Zeiger auf Bereich X rekonstruiert und verwendet wird. Wenn der GC X dazwischen dann wegrÀumt ... wÀre das blöd.

    Wobei das konstruierte Beispiele sind, die vermutlich in der RealitĂ€t selten bis gar nicht auftreten werden. Wenn man diese ignoriert, sowie sich auf eine Unzahl von Eigenheiten der C++ Implementierung verlĂ€sst und einige mutige Annahmen trifft, dann kann man schon einen mehr oder weniger gut "funktionierenden" GC fĂŒr C++ basteln. Gibt es ja auch, z.B. den Boehm GC. WĂŒrde ich aber nicht verwenden wollen.

    Was genau hier mit C++11/14/1z geĂ€ndert wurde weiss ich nicht. Ich habe es aber so verstanden dass die neuen Standars es nur der C++ Implementierung einfacher machen selbst einen GC zu integrieren bzw. freiwillig ein Interface fĂŒr einen externen GC zur VerfĂŒgung zu stellen. Das wĂŒrde heissen dass man immer noch nicht ohne (optionalen) Support des Compilers einen GC dazubasteln kann.

    0

  • hustbaer schrieb:

    dot schrieb:

    Wenn man's genau nimmt, geht es in der Regel nie wirklich um GC, sondern eigentlich um das Management der Lebensdauer von Objekten, die aus einer Datenstruktur entfernt wurden, aber potentiell noch nebenlĂ€ufig gerade von jemandem verwendet werden. Das ist eigentlich ein Problem, das völlig orthogonal – wenn nicht sogar antigonal – ist zu GC...

    Ich weiss nicht genau wie ich darauf jetzt antworten soll...
    Der GC ist dafĂŒr zustĂ€ndig MĂŒll wegzurĂ€umen. DafĂŒr muss er wissen welche Objekte noch referenziert werden. Und wenn er als Teil eines Systems funktionieren muss welches Threads "hat" und es explizit erlaubt Referenzen ohne extra Synchronisierung einfach so zu verbiegen, dann muss er halt auch damit klarkommen. Und wenn Referenzen in Registern gehalten werden dĂŒrfen auch damit und und und. Ich verstehe also nicht wieso das "nicht mit dem GC zu tun" haben soll 😕

    Automatisches AufrĂ€umen unreferenzierter Objekte ist eine mögliche Lösung, aber das eigentliche Problem hier hat lediglich mit Garantien bezĂŒglich der Lebensdauer von Objekten zu tun und das ist ein zu GC völlig orthogonales Problem; GC an sich gibt einem normalerweise ĂŒberhaupt keine Garantien bezĂŒglich ob und wann Objekte zerstört werden. Und der Preis fĂŒr GC ist mir persönlich mitunter viel zu hoch. Und dabei meine ich nicht nur irgendwelchen Performanceoverhead, sondern vor allem die Tatsache, dass die Verwendung eines GC sĂ€mliche Garantien bezĂŒglich Objektlebensdauern als Opfer fordert, was eine jede solche Sprache einfach nur verkrĂŒppelt. In vielen FĂ€llen gibt es elegantere Lösungen wie z.B. dieser RCU Kram im Linux Kernel. Und abgesehen davon ist lock-free sowieso nicht die Lösung als die es immer angepriesen wird. Im Gegenteil. Mag sein, dass ich da nur einen Extrem zu sehen bekomme weil ich mit GPUs zu tun hab, aber meiner Erfahrung nach skalieren lock-free Algorithmen einfach hoffnungslos aus Prinzip nicht. Das Grundproblem scheint mir, dass praktisch alle lock-free Algos die wir heute so haben (zumindest die, mit denen ich bisher zu tun hatte) optimistisch sind, d.h. auf der Annahme basieren, dass Operationen selten interferieren. Dann können wir unsere Operationen clever so designen, dass bei parallelen Modifikationen nur eine erfolgreich ist und der Rest fehlschlĂ€gt ohne zu einem undefinierten Zustand zu fĂŒhren und dann wieder versucht werden kann. Das funktioniert vielleicht ganz toll so lange du 4 Threads hast. Sobald du ein paar hundert Threads hast, die alle gleichzeitig eine Datenstruktur benutzen wollen, kannst du das knicken weil allein der Memory Transfer durch fehlgeschlagene und wiederversuchte Operationen das Ganze gegen die Wand fĂ€hrt...

    0

  • Erstmal vorweg: Ich bin auch nicht unbedingt der grösste Fan von Systemen mit GC. Speziell nicht von bestehenden gerne verwendeten Implementierungen wie JVM oder .NET. Ich sehe allerdings auch StĂ€rken. Und keinen Sinn darin diese zu ignorieren oder niederzureden damit ja nix gutes dran sein kann.

    dot schrieb:

    Automatisches AufrÀumen unreferenzierter Objekte ist eine mögliche Lösung,

    Was jetzt genau das ist was ich behauptet habe, oder?

    dot schrieb:

    aber das eigentliche Problem hier hat lediglich mit Garantien bezĂŒglich der Lebensdauer von Objekten zu tun und das ist ein zu GC völlig orthogonales Problem;

    Er... nein. Es ist definitiv nicht völlig orthogonal. Mag jetzt sein dass du ohne weitere ErklÀrung eine sehr spezielle Interpretation von "Lebensdauer von Objekten" verwendest, aber nichtmal wenn ich davon ausgehe dass du deterministische Finalisierung meinst...
    Viele Objekte haben (im C++ Standard Sinne des Wortes) "triviale" Finalizer. Also auf Deutsch: keine. In einem System mit GC hat das "verschwinden" solcher Objekte keine beobachtbaren Effekte. Das Objekt muss existieren so lange es verwendet werden kann, und verwendet werden kann es so lange es referenziert wird. (Bzw. auch weniger lang, wenn man beweisen kann dass die Referenz ab Punkt X sicher nicht mehr verwendet wird. Nur da es ja keine beobachtbaren Effekte gibt wenn das Objekt "zerstört wird" (verschwindet)... ist es egal dass man es frĂŒher wegrĂ€umen könnte.)

    Und dass das den GC betrifft ist hoffentlich klar, denn der darf natĂŒrlich nichts tun was diese Garantie ("ein Objekt existiert so lange es verwendet werden kann") "zerstört".
    NatĂŒrlich kann man das auch ohne GC lösen, z.B. indem man Speicher einfach gar nicht freigibt. Nur das ist selten praktikabel, und wenn man einen GC verwendet, dann betrifft es ihn. Ganz massiv. Und dann zu sagen es wĂ€ren völlig orthogonale Prinzipien ist IMO einfach falsch.

    Falls ich dich falsch verstanden habe, bitte beschreib genauer was du meinst. Einfach nur zu wiederholen was du bereits geschrieben hast bringt mir nix, ich hab' deinen Beitrag sowieso schon 3x gelesen, ein 4. oder 5. mal wird dann nix bringen. 🙂

    dot schrieb:

    GC an sich gibt einem normalerweise ĂŒberhaupt keine Garantien bezĂŒglich ob und wann Objekte zerstört werden.

    Doch, klar. Also konkrete, praktikable Implementierungen tun das. NĂ€mlich dass sie Objekte nicht zu frĂŒh zerstören. Was auch immer jetzt mit "zerstören" gemeint ist (Freigabe des Speichers bzw. Finalisierung). Das ist vielleicht nicht die Garantie die du dir wĂŒnscht (deterministische Finalisierung ala C++ Destruktoren?), aber es ist eine sehr wichtige Garantie, denn ohne sie wĂ€re jedes System mit GC IMO völlig unbrauchbar.

    dot schrieb:

    Und der Preis fĂŒr GC ist mir persönlich mitunter viel zu hoch. Und dabei meine ich nicht nur irgendwelchen Performanceoverhead, sondern vor allem die Tatsache, dass die Verwendung eines GC sĂ€mliche Garantien bezĂŒglich Objektlebensdauern als Opfer fordert, was eine jede solche Sprache einfach nur verkrĂŒppelt.

    Jain.
    GC muss ja nicht unbedingt heissen dass man nicht trotzdem bestimmte Dinge deterministisch machen kann. Ich kenne zwar auch keine Sprache die da wirklich gut brauchbaren Support dafĂŒr hat, aber es spricht grundsĂ€tzlich nix dagegen. Im Prinzip kannst du aber jederzeit ne C++ Implementierung mit GC machen, wo der GC sich einfach nur darum kĂŒmmert den Heap zu verwalten. Also keine Finalizer o.Ă€. Damit könnte man Objekte mit trivialem Dtor dann einfach vom GC collecten lassen - und hĂ€tte damit auch das was man benötigt um bestimmte Dinge "lock free" zu implementieren. FĂŒr einfache POD-structs mĂŒsste man dann nĂ€mlich nimmer delete/free aufrufen, und das reicht fĂŒr viele Sachen schon.

    dot schrieb:

    In vielen FÀllen gibt es elegantere Lösungen wie z.B. dieser RCU Kram im Linux Kernel.

    RCU ist doch das beste Beispiel fĂŒr etwas was mit GC deutlich einfacher und vermutlich auch deutlich effizienter wird 😕

    dot schrieb:

    Und abgesehen davon ist lock-free sowieso nicht die Lösung als die es immer angepriesen wird. Im Gegenteil.

    Es war auch nur ein Beispiel. Ein weiteres hast du ja selbst gerade gebracht: RCU. Wobei man eine RCU-Implementierung die readerseitig keinerlei Synchronisierung erfordert auch als spezialisierten mini-GC bezeichnen könnte.

    dot schrieb:

    Das Grundproblem scheint mir, dass praktisch alle lock-free Algos die wir heute so haben (zumindest die, mit denen ich bisher zu tun hatte) optimistisch sind, d.h. auf der Annahme basieren, dass Operationen selten interferieren. Dann können wir unsere Operationen clever so designen, dass bei parallelen Modifikationen nur eine erfolgreich ist und der Rest fehlschlĂ€gt ohne zu einem undefinierten Zustand zu fĂŒhren und dann wieder versucht werden kann. Das funktioniert vielleicht ganz toll so lange du 4 Threads hast. Sobald du ein paar hundert Threads hast, die alle gleichzeitig eine Datenstruktur benutzen wollen, kannst du das knicken weil allein der Memory Transfer durch fehlgeschlagene und wiederversuchte Operationen das Ganze gegen die Wand fĂ€hrt...

    Nur wenn sich dabei hÀufig Writer in die Quere kommen. Wenn primÀr gelesen wird ...
    Und das selbe Problem hast du bei RCU genau so. Wenn da recht oft geschrieben wird skaliert das ganz schlecht.

    0
  • ?

    SideWinder schrieb:

    Können Templates eigentlich co/contravariance?

    Nein, aber das können Java Generics auch nicht (warum auch immer, es gibt eigentlich keinen technischen Grund).

    Was man allerdings mit Templates nicht kann sind virtuelle Methoden:

    #include <iostream>

class Fass {
public:
  template <class T>
  virtual void quiek (T t) = 0;
};

class Ramelucke : public Fass {
public:
  template <class T>
  void quiek (T t) {
    std::cout << t << std::endl;
  }
};

int main (void) {
  Fass* r = new Ramelucke ();
  r->quiek("Hallo Welt");
  delete r;
}

    wird dir nicht compilieren, das Analogon in Java

    class VirtualTemplate {
    static abstract class Fass {
        abstract <T> void quiek (T t);
    }
    static class Ramelucke extends Fass {
	public Ramelucke () {}
	<T> void quiek (T t) {
	    System.out.println(t);
	}
    }

    public static void main (String[] args) {
	Fass a = new Ramelucke ();
	a.quiek("Hallo Welt");
    }
}

    tuts :3

    Achso, und was auch nur die Wenigsten wissen ist, dass C++-Schablonen lazy ausgewertet werden. Hier ist ein schönes RÀtsel dazu: http://tinyurl.com/gsw8xle

    0

  • Dein Kritikpunkt macht ueberhaupt keinen Sinn; um virtuelle Templates zu unterstuetzen, muesste ein JIT compiler zur runtime dabei sein und auch noch Fehler entsprechend behandeln koennen, was fundamental C++' Natur widerspricht. Aber wir brauchen dieses Feature gar nicht. I.e. es ist nicht so, das wir es ergaenzen koennten: wir brauchen es gar nicht.

    Was Java kann, kann C++ auch, entweder mit virtuellen Funktionen oder type erasure, aber oft (immer?) kann man das auch eleganter loesen.

    0
  • S

    𝔑&#120094 schrieb:

    SideWinder schrieb:

    Können Templates eigentlich co/contravariance?

    Nein, aber das können Java Generics auch nicht (warum auch immer, es gibt eigentlich keinen technischen Grund).

    Danke fĂŒr die Info, ja, aber ich setzte statt "Java" auch immer "C#" ein 😉

    Wie es in diesem Thread schon wieder um den GC gehen kann ist mir allerdings ein RĂ€tsel...

    MfG SideWinder

    0
Anmelden zum Antworten