size_t vs int als Index bei Interation über Container?



  • Da ja size_t von size in Container wie std::vector zurück gegeben wird, nutze ich in letzter Zeit den Datentyp oft auch für Interationsvariablen in Schleifen, denn das ist kürzer zu schreiben als unsigned int, was ja size_t ist. 2.) int macht ja nur Sinn wenn man auch negative Werte braucht.

    Wie handhabt ihr das so?



  • Standard ist für mich:

    for (const auto& e : container)
    

    Damit hat man keine Probleme, selbst bei einem Container maximaler Größe.

    ... wenn ich einen Index benötige, dann

    for (int i = 0; ...
    

    falls es sich um Anwendungs-Code handelt, wo ich den Code gut lesbar halten will und ich sicher sein kann, dass ich keinen größeren Wertebereich benötige. Container, die in einer Größenordnung unter 1GiB Speicher benötigen sind ja eher die Regel.

    Wenn ich Bibliotheks-Code scheibe, dann

    for (decltype(container)::size_type i = 0; ...
    

    oder sowas wie

    // random_access_range container
    for (std::ranges::range_difference_t<decltype(container)> i = 0; ...
    

    Damit sind auch (durchaus erlaubte) Container abgedeckt, die nicht mit einem std::size_t indiziert werden. Man stelle sich einen Container vor, mit dem man z.B. auf einem 32-Bit-System (mit size_t = uint32_t) über die Bytes einer 8GiB großen Datei iterieren kann. Da brauchts was mit größerem Wertebereich als size_t.

    Und NEIN, size_t ist nicht dasselbe wie unsigned int. Heutzutage ist es meistens ist es ein uint64_t, auf 32-Bit-Systemen oft ein uint32_t (hier stimmts dann mit dem unsigned int) und auf einem kleinen Arduino-System kann es auch schonmal ein uint16_t sein. Und dennoch kann es immer Container geben, für die man mehr als einen size_t braucht (s.o.).



  • Vielen Dank für die sehr kompetente Antwort.

    Ich bin auf den size_t Gedanken gekommen wegen der Compiler-Warnmeldung immer wenn ich in einer Schleife einen Index brauche.
    warning C4267: 'initializing': conversion from 'size_t' to 'int', possible loss of data



  • Ja, solche Warnungen gibt es bedauerlicherweise, wenn man den Code mit einem simplen int möglichst unkompliziert halten will. Bjarne hat genau dazu mal was geschrieben:

    https://www.stroustrup.com/bs_faq2.html#simple-program

    Yes, I know that I could declare i to be a vector<double>::size_type rather than plain int to quiet warnings from some hyper-suspicious compilers, but in this case,I consider that too pedantic and distracting.

    Wie man das letztendlich machen will, muss man selbst entscheiden. Erstmal überlegen, ob man wirklich einen Index braucht - viele Probleme lassen sich auch ohne einen solchen lösen und ein Range-Based-For wird keine solchen Warnungen erzeugen.

    Ansonsten nimm halt decltype(container)::size_type - ich muss zugeben, dass ich letztendlich auch meistens versuche, sämtliche Compiler-Warnungen zu eliminieren und das so machen würde - auch wenn ich einen simplen int hier lieber sähe.



  • @CppConst sagte in size_t vs int als Index bei Interation über Container?:

    unsigned int, was ja size_t ist

    Nein.



  • @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    Damit sind auch (durchaus erlaubte) Container abgedeckt, die nicht mit einem std::size_t indiziert werden. Man stelle sich einen Container vor, mit dem man z.B. auf einem 32-Bit-System (mit size_t = uint32_t) über die Bytes einer 8GiB großen Datei iterieren kann. Da brauchts was mit größerem Wertebereich als size_t.

    Wo steht das in der Norm? Die Norm sieht für Container<T>::size_type vor, dass alle nicht negativen Werte von Container<T>::difference_type, der mit Container<T>::Iterator::difference_type identisch sei muss, aufgenommen werden können, und alle Iteratoren sind nur Abstraktionen von Pointern. Dazu gibt es eine ganze Reihe von Anforderungen, die es nicht erlauben, dass es Iteratoren gibt, die Daten z.B. aus einer Datei nachladen, weil das die Bedingungen (konstante Ausführungszeiten für i++ u.ä.) für Iteratoren verletzen würde.

    Daher können Container nur auf dem allozierbaren Speicher existieren, und deshalb kann man alle Elemente eines beliebigen Containers mit size_t erreichen. Das garantiert die zugrunde liegende C Laufzeitumgebung des Systems.

    @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    https://www.stroustrup.com/bs_faq2.html#simple-program

    Yes, I know that I could declare i to be a vector<double>::size_type rather than plain int to quiet warnings from some hyper-suspicious compilers, but in this case,I consider that too pedantic and distracting.

    Solche Faulheit öffnet die Tür für undefiniertes Verhalten, daher ist int niemals zu verwenden. Wenn man es sich einfach machen will, dann nimmt man size_t, da passen alle Typen rein, die möglich sind und man kann garantiert über alle Elemente eines Random Access Containers iterieren.

    Nachtrag:
    Wie groß size_t ist, hängt davon ab, welches data model dem Betriebssystem zu Grunde liegt. UNIX/Linux nutzt seit der Normierung in der Single UNIX Specification ILP32 und LP64 für das 32Bit bzw. 64Bit Laufzeitmodell. Ältere UNICES haben da noch andere data models genutzt. UNICOS nutzte zum Beispiel SILP64, und war das erste 64Bit UNIX überhaupt und erschien bereits 1985.



  • @john-0 sagte in size_t vs int als Index bei Interation über Container?:

    konstante Ausführungszeiten für i++ u.ä

    Wo steht das in der Norm?





  • @manni66 sagte in size_t vs int als Index bei Interation über Container?:

    @john-0 sagte in size_t vs int als Index bei Interation über Container?:

    konstante Ausführungszeiten für i++ u.ä

    Wo steht das in der Norm?

    Das steht z.B. in N4681 §23.3.4.13, und auf diesen Iterator-Typ bezog ich meine Aussage, weil das in Bezug auf for sonst auch keinen Sinn ergibt.

    The random_access_iterator concept adds support for constant-time advancement with +=, +, -=, and -,
    as well as the computation of distance in constant time with -. Random access iterators also support array
    notation via subscripting.



  • Haha, da habe ich ja was los getreten, also doch immer size_t nehmen. Meitens komme ich ja ohne Laufvariable aus, aber manchmal ist es halt doch von nöten, oder ich weiß mir nicht anders zu helfen.



  • @john-0 sagte in size_t vs int als Index bei Interation über Container?:

    Dazu gibt es eine ganze Reihe von Anforderungen, die es nicht erlauben, dass es Iteratoren gibt, die Daten z.B. aus einer Datei nachladen, weil das die Bedingungen (konstante Ausführungszeiten für i++ u.ä.) für Iteratoren verletzen würde.

    Daher können Container nur auf dem allozierbaren Speicher existieren, und deshalb kann man alle Elemente eines beliebigen Containers mit size_t erreichen. Das garantiert die zugrunde liegende C Laufzeitumgebung des Systems.

    Konstante Ausführungszeit halte für kein überzeugendes Argument dafür, dass Container nur auf "allozierbarem Speicher existieren" können. Selbst für einen Iterator, der eine E-Mail versendet, mit der ein Mitarbeiter für den kommenden Tag damit beauftragt wird, das nächste Türchen im Advendskalender zu öffnen und das Ergebnis dann per berittenem Boten zurückzuschicken kann i++ in O(1)\mathcal{O}(1) liegen - da geht sicher auch ein Dateizugriff 😉 ... gibt es da noch mehr Gründe? Du deutetest ja sowas an.

    Ich bin jetzt nicht jemand, der den Standard auswendig herunterbeten kann, aber ich kann mir nur schwer vorstellen, dass man es zugelassen hat, dass ein so wunderschön abstraktes Konzept wie Iteratoren auf solch konkrete Dinge wie Speicher oder Typen wie size_t festgenagelt wird.

    @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    https://www.stroustrup.com/bs_faq2.html#simple-program

    Yes, I know that I could declare i to be a vector<double>::size_type rather than plain int to quiet warnings from some hyper-suspicious compilers, but in this case,I consider that too pedantic and distracting.

    Solche Faulheit öffnet die Tür für undefiniertes Verhalten, daher ist int niemals zu verwenden. Wenn man es sich einfach machen will, dann nimmt man size_t, da passen alle Typen rein, die möglich sind und man kann garantiert über alle Elemente eines Random Access Containers iterieren.

    Die Motivation ist nicht Faulheit, sondern simpler Code mit wenig "Rauschen" für simple Probleme. Klar nimmt man keinen int wenn man nicht weiss wie gross der Container werden kann, besonders in "Bibliothekscode". In Anwendungscode hingegen löst man allerdings oft sehr konkrete Probleme mit bekannten Eigenschaften, für die ich einen int für vollkommen in Ordnung halte. Z.B. für eine Liste mit Telefonnummern, unter denen eine Person erreichbar ist, eine Liste mit an das Programm übergebenen Parametern oder einen Index in einen mathematischen Vektor.

    Ferner ist potentiell undefiniertes Verhalten nicht immer eine böse Sache, wenn man sicherstellen kann, dass das Programm nicht in diesen Zustand gelangen kann - entweder explizit durch einen entsprechenden Typen, oder implizit durch den Programmkontext. UB ist schliesslich auch immer für den Compiler eine Gelegenheit simpleren Code zu erzeugen, da er davon ausgehen darf, dass UB einfach nicht auftritt (Schönes Beispiel wie der eigentlich so wunderbar definierte Unsigned-Überlauf den Compiler zwingen kann, viel umständlicheren Code zu erzeugen - ausgerechnet an einer kritischen Stelle im Code: https://www.youtube.com/watch?v=yG1OZ69H_-o&t=39m16s).

    ich sag ja nicht dass man immer ohne Nachzudenken int nehmen soll, aber es darf ruhig die erste Wahl sein, solange man weiss wann man eben keinen int nehmen darf - zumal size_t meines erachtens (s.o., bin ja noch nicht überzeugt) eben auch nicht immer die richtige Wahl ist, und jenseits davon wirds echt unleserlich und eher was für Bibliotheks-Code.



  • @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    Konstante Ausführungszeit halte für kein überzeugendes Argument dafür, dass Container nur auf "allozierbarem Speicher existieren" können. Selbst für einen Iterator, der eine E-Mail versendet, mit der ein Mitarbeiter für den kommenden Tag damit beauftragt wird, das nächste Türchen im Advendskalender zu öffnen und das Ergebnis dann per berittenem Boten zurückzuschicken kann i++ in O(1)\mathcal{O}(1) liegen - da geht sicher auch ein Dateizugriff 😉 ...

    Bei all diesen Dinge ist der Zugriff nicht mehr O(1) sondern variablen und von vielen Randbedingungen abhängig.

    Iteratoren sind eine Abstraktion des Konzepts Zeiger, so dass einfacher wird generische Algorithmen in C++ zu schreiben. Das steht so auch in der Norm. In vielen Lehrbüchern oder Tutorials sind viele der Feinheiten aus der Norm nicht erwähnt. Man sollte sich davor hüten, Annahmen darüber zu machen, wenn man die Norm nicht selbst gelesen hat.

    … gibt es da noch mehr Gründe? Du deutetest ja sowas an.

    Gültige Iteratoren lassen sich immer dereferenzieren. Wenn ich da an einen potentiellen File-Iterator denke, dann kann ich doch nicht garantieren, dass dieser in der Lage ist beim Anwendungen des Derefenzierungsoperators auch Speicher zu allozieren, um den Dateiblock auch landen zu können. Dadurch verletzt man die Garantie für Iteratoren. Denn für die gilt, ist ein Iterator gültig, dann kann man ihn auch derefenzieren. In diesem hypothetischen Fall, hätte ich das Problem, dass der Rechner out-of-mem sein kann, weil man versucht über den Inhalt einer Datei zu iterieren, die deutlich größer ist als das RAM oder noch schlimmer der Adressraum des Systems. Ich weiß ja nicht, wie gut Du mit der UNIX API vertraut bist, aber mittels mmap kann man schon lange Dateien in den Adressraum einspiegeln, so dass immer ein Puffer mit Dateiinhalt gefüllt ist, aber eben nur Dateien die maximal so groß sind, dass sie die Grenzen des Adressraums nicht überschreiten. Will man nun ein neues Konzept Dateiinhalt-Iterator einführen, müsste dieser normale Iteratoren haben, mit denen ich über den Speicherinhalt des Systems iterieren kann, und dann bräuchte man diese speziellen Eigenschaft, dass bei Bedarf noch weitere Blöcke aus dem Storage adressiert werden können. Das kann man sicherlich modellieren, aber ich sehe bisher nichts in der Norm, dass das für die normalen Iteratoren erlauben würde.

    Dann kommt das Thema Allokatoren noch ins Spiel, auch die spielen eine Rolle bei der Definition von size_type eines Containers.

    Ich bin jetzt nicht jemand, der den Standard auswendig herunterbeten kann, aber ich kann mir nur schwer vorstellen, dass man es zugelassen hat, dass ein so wunderschön abstraktes Konzept wie Iteratoren auf solch konkrete Dinge wie Speicher oder Typen wie size_t festgenagelt wird.

    Nein, das ist nicht auf size_t festgenagelt. Man darf definitiv kleinere Datentypen für C++ Container verwenden, wenn das der Allokator es erlaubt.

    Die Motivation ist nicht Faulheit, sondern simpler Code mit wenig "Rauschen" für simple Probleme. Klar nimmt man keinen int wenn man nicht weiss wie gross der Container werden kann, besonders in "Bibliothekscode". In Anwendungscode hingegen löst man allerdings oft sehr konkrete Probleme mit bekannten Eigenschaften, für die ich einen int für vollkommen in Ordnung halte. Z.B. für eine Liste mit Telefonnummern, unter denen eine Person erreichbar ist, eine Liste mit an das Programm übergebenen Parametern oder einen Index in einen mathematischen Vektor.

    Da werden wieder massenweise Annahmen gemacht, die dann nicht wirklich garantiert sind. Wer garantiert Dir, dass in einem mathematischen Programm niemand Indizes benutzt die größer sind als 32Bit? Simples Beispiel man lädt Messdaten etwa vom LHC und macht da z.B. eine Fourieranalyse, und schon wird das mit 32Bit als Index ein Problem. Solche Mikrooptimierungen bringen nichts, und sorgen früher oder später nur für Probleme.

    Das führt dann immer wieder zu Problemen. Dazu bringt eine Mikrooptimierung durch kleinere Indizes bei modernen CPUs faktisch nichts mehr. Theoretisch kannst Du nur auf x86 CPUs da überhaupt einen Vorteil daraus ziehen, während bei den RISC CPUs das ohnehin nichts bringt. Schlimmer noch die kleinen Indizes sorgen dafür, dass bei Zugriff auf den Index im Speicher abgelegt das Aligment suboptimal ist, und somit das Laden und Speichern länger dauert, und der Compiler dann ggf. Füllbytes einfügt, so dass noch nicht einmal Speicher gespart wird. Wenn man den Index nur im Register hat, spielt die kleinere Größe gleich gar keine Rolle mehr. Man hat durch den kleineren Index nur Nachteile und keinerlei Vorteil.

    Ferner ist potentiell undefiniertes Verhalten nicht immer eine böse Sache, wenn man sicherstellen kann, dass das Programm nicht in diesen Zustand gelangen kann - entweder explizit durch einen entsprechenden Typen, oder implizit durch den Programmkontext.

    Wie gesagt, die meisten Annehmen sind nur mutmaßlich korrekt, und das führte in der Vergangenheit immer wieder zu Problemen die dann mit sehr teurer Softwarewartung repariert werden mussten.

    UB ist schliesslich auch immer für den Compiler eine Gelegenheit simpleren Code zu erzeugen, da er davon ausgehen darf, dass UB einfach nicht auftritt (Schönes Beispiel wie der eigentlich so wunderbar definierte Unsigned-Überlauf den Compiler zwingen kann, viel umständlicheren Code zu erzeugen - ausgerechnet an einer kritischen Stelle im Code: https://www.youtube.com/watch?v=yG1OZ69H_-o&t=39m16s).

    Ohje, das sind so Fälle da rollst mir die Fußnägel hoch, auch wegen der Argumentation. Wegen der Datenstruktur kann ich in der Routine kein size_t nehmen, aber uint32_t mit int32_t ersetzen stellt kein Problem dar? Immerhin reduziert man die mögliche Dateigröße von 4GB auf 2GB, wenn man den Datentypen von uint32_t auf int32_t reduziert. Die Argumentation im Vortrag ist für mich gar nicht stichhaltig.

    Schauen wir uns den erzeugten Code doch mal genauer an. Dazu habe ich folgende Sourcedatei geschrieben, die anstatt des konkreten Typs ein Define an der Stelle enthält, so dass man bequem über die Kommandozeile den Code ändern kann in dem man int32_t, uint32_t und size_t einsetzt. Compiler ist g++ 11.1.0 für x86-64 und g++-10.2.0 für aarch64, -O3 als Optimizerflag

    #include <cstdint>
    #include <cstdlib>
    
    bool mainGtU (INTTYPE i1, INTTYPE i2, uint8_t* block) {
        uint8_t c1, c2;
    
        c1 = block[i1]; c2 = block[i2];
        if (c1 != c2) return c1 > c2;
        i1++; i2++;
    
        c1 = block[i1]; c2 = block[i2];
        if (c1 != c2) return c1 > c2;
        i1++; i2++;
    
        return true;
    }
    

    x86-64 uint32_t

        movl    %esi, %eax
        movl    %edi, %ecx
        movzbl  (%rdx,%rax), %eax
        cmpb    %al, (%rdx,%rcx)
        jne .L5
        leal    1(%rsi), %ecx
        addl    $1, %edi
        movl    $1, %eax
        movzbl  (%rdx,%rcx), %ecx
        cmpb    %cl, (%rdx,%rdi)
        je  .L1
    .L5:
        seta    %al
    .L1:
        ret
    

    x86-64 int32_t

        movslq  %esi, %rax
        movslq  %edi, %rcx
        movzbl  (%rdx,%rax), %eax
        cmpb    %al, (%rdx,%rcx)
        jne .L5
        addl    $1, %edi
        addl    $1, %esi
        movl    $1, %eax
        movslq  %esi, %rsi
        movslq  %edi, %rdi
        movzbl  (%rdx,%rsi), %ecx
        cmpb    %cl, (%rdx,%rdi)
        je  .L1
    .L5:
        seta    %al
    .L1:
        ret
    

    x86-64 size_t

        movzbl  (%rdx,%rsi), %eax
        cmpb    %al, (%rdx,%rdi)
        jne .L5
        movzbl  1(%rdx,%rsi), %ecx
        movl    $1, %eax
        cmpb    %cl, 1(%rdx,%rdi)
        je  .L1
    .L5:
        seta    %al
    .L1:
        ret
    

    Was wir hier sehen, dass der g++ 11.1.0 nur im Falle size_t genauso gut ist wie der Compiler aus dem Vortrag. Ich hoffe Du wirst mir zustimmen, dass ich eine optimierte Version für x86-64 der Funktion verwenden darf in dem ich von

    bool mainGtU (uint32_t i1, uint32_t i2, uint8_t* block);
    // zu
    bool mainGtU (size_t i1, size_t i2, uint8_t* block);
    

    wechsele. Denn jeden uint32_t kann man problemlos zu einem uint64_tpromoten.

    Nun der Output für aarch64
    uint32_t

            ldrb    w4, [x2, w0, uxtw]
            ldrb    w3, [x2, w1, uxtw]
            cmp     w4, w3
            beq     .L2
            cset    w0, hi
            ret
            .p2align 2,,3
    .L2:
            add     w0, w0, 1
            add     w1, w1, 1
            ldrb    w3, [x2, w0, uxtw]
            ldrb    w0, [x2, w1, uxtw]
            cmp     w3, w0
            cset    w0, hi
            csinc   w0, w0, wzr, ne
            ret
    

    aarch64 int32_t

            ldrb    w4, [x2, w0, sxtw]
            ldrb    w3, [x2, w1, sxtw]
            cmp     w4, w3
            beq     .L2
            cset    w0, hi
            ret
            .p2align 2,,3
    .L2:
            add     w0, w0, 1
            add     w1, w1, 1
            ldrb    w3, [x2, w0, sxtw]
            ldrb    w0, [x2, w1, sxtw]
            cmp     w3, w0
            cset    w0, hi
            csinc   w0, w0, wzr, ne
            ret
    

    aarch64 size_t

            ldrb    w4, [x2, x0]
            ldrb    w3, [x2, x1]
            cmp     w4, w3
            beq     .L2
            cset    w0, hi
            ret
            .p2align 2,,3
    .L2:
            add     x0, x2, x0
            add     x2, x2, x1
            ldrb    w1, [x0, 1]
            ldrb    w0, [x2, 1]
            cmp     w1, w0
            cset    w0, hi
            csinc   w0, w0, wzr, ne
            ret
    

    D.h. hier sieht man gleich gar keinen wesentlichen Unterschied im Code mehr abgesehen von den offensichtlichen Unterschieden was die Größe des Datentyps betrifft. Lohnt es sich für x86-64 spezifische Optimierungen die Kontrakte in der Software zu brechen? (Dateigröße von maximal 4GB auf 2GB reduziert!) Dazu gibt es auch noch eine Variante für x86-64 die mir die Kontrakte nicht bricht und genauso effizienten Code wie aus dem Bespiel liefert.

    ich sag ja nicht dass man immer ohne Nachzudenken int nehmen soll, aber es darf ruhig die erste Wahl sein, solange man weiss wann man eben keinen int nehmen darf - zumal size_t meines erachtens (s.o., bin ja noch nicht überzeugt) eben auch nicht immer die richtige Wahl ist, und jenseits davon wirds echt unleserlich und eher was für Bibliotheks-Code.

    size_tist nie falsch, es mag unter bestimmten Umständen nicht so schnell sein, aber das trifft im wesentlichen nur für x86 bzw. x86-64 zu.



  • @john-0 sagte in size_t vs int als Index bei Interation über Container?:

    @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    Konstante Ausführungszeit halte für kein überzeugendes Argument dafür, dass Container nur auf "allozierbarem Speicher existieren" können. Selbst für einen Iterator, der eine E-Mail versendet, mit der ein Mitarbeiter für den kommenden Tag damit beauftragt wird, das nächste Türchen im Advendskalender zu öffnen und das Ergebnis dann per berittenem Boten zurückzuschicken kann i++ in O(1)\mathcal{O}(1) liegen - da geht sicher auch ein Dateizugriff 😉 ...

    Bei all diesen Dinge ist der Zugriff nicht mehr O(1) sondern variablen und von vielen Randbedingungen abhängig.

    Du weisst schon, dass die Komplexität in O\mathcal{O}-Notation keine Aussage darüber trifft, wie lange du letztendlich auf dein Ergebnis warten musst, sondern wie schnell die Funktion der Laufzeit in Abhängigkeit von der Problemgröße wächst? Die konstante Laufzeit darf beliebig gross sein, sofern sie unabhängig von der Anzahl der Elemente einen beliebigen (auch sehr großen) konstanten Wert nicht überschreitet.

    Ferner ist auch der Zugriff auf den Arbeitsspeicher von "variablen und von vielen Randbedingungen abhängig" - wenn auch in einer kleineren Größenordnung. Speichertakt, Chipdesign, Temperatur, aktueller dynamischer CPU-Takt. Das sind alles Parameter die für das asymptotische Verhalten eines Algorithmus irrelevant sind, genau wie die mittlere Zugriffszeit auf eine Festplatte.

    Iteratoren sind eine Abstraktion des Konzepts Zeiger, so dass einfacher wird generische Algorithmen in C++ zu schreiben. Das steht so auch in der Norm. In vielen Lehrbüchern oder Tutorials sind viele der Feinheiten aus der Norm nicht erwähnt. Man sollte sich davor hüten, Annahmen darüber zu machen, wenn man die Norm nicht selbst gelesen hat.

    Ich habe nicht abgestritten, dass sie Zeiger abstrahieren - auch wenn ich sie eher für eine Verallgemeinerung von Zeigern halte. Ich habe lediglich Zweifel geäußert, dass man daraus ableiten kann, dass die Daten unbedingt alle im Adressraum der CPU liegen müssen. Bei einem std::contiguous_iterator könnte ich das nachvollziehen, bei einem allgemeinen std::random_access_iterator jedoch nicht.

    … gibt es da noch mehr Gründe? Du deutetest ja sowas an.

    Gültige Iteratoren lassen sich immer dereferenzieren. Wenn ich da an einen potentiellen File-Iterator denke, dann kann ich doch nicht garantieren, dass dieser in der Lage ist beim Anwendungen des Derefenzierungsoperators auch Speicher zu allozieren, um den Dateiblock auch landen zu können. Dadurch verletzt man die Garantie für Iteratoren. Denn für die gilt, ist ein Iterator gültig, dann kann man ihn auch derefenzieren. In diesem hypothetischen Fall, hätte ich das Problem, dass der Rechner out-of-mem sein kann, weil man versucht über den Inhalt einer Datei zu iterieren, die deutlich größer ist als das RAM oder noch schlimmer der Adressraum des Systems.

    Sicher, dass ein Iterator beim dereferenzieren keine Exception werfen darf und wirklich immer einen erfogreichen Zugriff garantieren muss? Davon bin ich nicht wirklich überzeugt, vor allem wenn ich mir z.b. einen std::filesystem::directory_iterator anschaue, der durchaus implementationsspezifische Exceptions werfen darf.

    Das mag für bestimmte Iteratoren zutreffen, wie den eines std::vector, wenn das aber wirklich für alle Iteratoren gelten muss, dann erachte ich das eher als Designschwäche, welche die Allgemeingültigkeit von Iteratoren zu sehr einschränkt. Warum soll ich nicht auf einem 64KiB RAM Mikrocontroller mit Iteratoren Einträge in einer viel größeren Datenbank durchlaufen können? Da bau ich mir dann lieber meine eigenen Iteratoren ("mit Black Jack und Nutten!" - Bender) mit denen das geht 😉

    Dann kommt das Thema Allokatoren noch ins Spiel, auch die spielen eine Rolle bei der Definition von size_type eines Containers.

    Ich glaube nicht, dass ein Container (beliebige) Allokatoren unterstützen muss, auch wenn es die Standard-Container tun, oder?

    Die Motivation ist nicht Faulheit, sondern simpler Code mit wenig "Rauschen" für simple Probleme. Klar nimmt man keinen int wenn man nicht weiss wie gross der Container werden kann, besonders in "Bibliothekscode". In Anwendungscode hingegen löst man allerdings oft sehr konkrete Probleme mit bekannten Eigenschaften, für die ich einen int für vollkommen in Ordnung halte. Z.B. für eine Liste mit Telefonnummern, unter denen eine Person erreichbar ist, eine Liste mit an das Programm übergebenen Parametern oder einen Index in einen mathematischen Vektor.

    Da werden wieder massenweise Annahmen gemacht, die dann nicht wirklich garantiert sind.

    Dito. Du machst auch jede Menge Annahmen, wozu der Code alles verwendet werden könnte, obwohl ich vielleicht nur Code für flache Vektoren/Matrizen schreibe, die man auf den Stack legen kann und mit denen lediglich geometrische Probleme gelöst werden sollen.

    Wer garantiert Dir, dass in einem mathematischen Programm niemand Indizes benutzt die größer sind als 32Bit? Simples Beispiel man lädt Messdaten etwa vom LHC und macht da z.B. eine Fourieranalyse, und schon wird das mit 32Bit als Index ein Problem. Solche Mikrooptimierungen bringen nichts, und sorgen früher oder später nur für Probleme.

    Die Idee dahinter sind nicht "Mikrooptimierungen", sondern wie ich schrieb "simpler Code für simple Probleme". Auch habe ich klar unterschieden zwischen "Bibliothekscode", der nicht wissen kann, wofür er eingesetzt werden wird und "Anwendungscode", mit dem sehr konkrete, klar umrissene Probleme gelöst werden. Ob mans glaubt oder nicht, C++ wird manchmal nicht nur dazu eingesetzt, Bibliotheken zu schreiben.

    Ferner habe ich auch geschreiben, dass man wissen muss, wann ein int nicht ausreichend ist. Wenn ich also eine allgemeine Bibliothek schreibe oder ein Programm, dass LHC-Datensätze verarbeitet, dann werde ich natürlich so etwas wie std::iter_difference_t<Iterator> oder std::ranges::range_difference_t<Range> nehmen (der Typ für den im std::random_access_iterator-Konzept iterator[index] definiert sein muss - range.begin()[index]).

    Das führt dann immer wieder zu Problemen. Dazu bringt eine Mikrooptimierung durch kleinere Indizes bei modernen CPUs faktisch nichts mehr. [...]

    Wie gesagt, es geht mir in erster Linie um klaren, gut lesbaren Code - size_t lasse ich duchgehen, aber ein präziseres std::ranges::range_difference_t<Range> sorgt beim Lesen des Codes nur für unnötiges Rauschen, wenn es sich lediglich um ein Stück trivialen Code für ein sehr konkretes Problem handelt.

    Ferner ist potentiell undefiniertes Verhalten nicht immer eine böse Sache, wenn man sicherstellen kann, dass das Programm nicht in diesen Zustand gelangen kann - entweder explizit durch einen entsprechenden Typen, oder implizit durch den Programmkontext.

    Wie gesagt, die meisten Annehmen sind nur mutmaßlich korrekt, und das führte in der Vergangenheit immer wieder zu Problemen die dann mit sehr teurer Softwarewartung repariert werden mussten.

    Schonmal an die Wartungskosten gedacht, die man hat, wenn sich jede triviale Codezeile zur Telefonnummernverwaltung wie ein Abschnitt aus dem Quellcode der Standardbibliothek liest? Nichts gegen in jedem Kontext korrekten Code - den schreibe ich auch - allerdings nur dort wo es notwendig ist.

    UB ist schliesslich auch immer für den Compiler eine Gelegenheit simpleren Code zu erzeugen, da er davon ausgehen darf, dass UB einfach nicht auftritt (Schönes Beispiel wie der eigentlich so wunderbar definierte Unsigned-Überlauf den Compiler zwingen kann, viel umständlicheren Code zu erzeugen - ausgerechnet an einer kritischen Stelle im Code: https://www.youtube.com/watch?v=yG1OZ69H_-o&t=39m16s).

    Ohje, das sind so Fälle da rollst mir die Fußnägel hoch, auch wegen der Argumentation. Wegen der Datenstruktur kann ich in der Routine kein size_t nehmen, aber uint32_t mit int32_t ersetzen stellt kein Problem dar? Immerhin reduziert man die mögliche Dateigröße von 4GB auf 2GB, wenn man den Datentypen von uint32_t auf int32_t reduziert. Die Argumentation im Vortrag ist für mich gar nicht stichhaltig.

    Du solltest dich nicht so sehr an dem konkreten Beispiel aufhängen. Das Thema der Vortragspassage ist viel allgemeiner - Wide Contracts vs Narrow Contracts und dass das je nach Umständen Auswirkungen auf den erzeugten Code haben kann. Der Wide Contract der unsigned Integer mit ihrem wohldefinierten Überlaufverhalten hat eben hier in dieser konkreten Konstellation den Compiler gezwungen, zusätzlichen Code einzufügen, damit diese Garantie eingehalten werden kann - obwohl die Datenstruktur und der Algorithmus so aufgebaut sind, dass dieser Fall nie eintritt. Was man daraus mitnehmen kann ist, dass man vielleicht nicht immer die Zusagen des Wide Contracts einfordern muss, wenn sie vom Kontext (Algorithmus/Datenstruktur) her nicht erforderlich sind.

    Schauen wir uns den erzeugten Code doch mal genauer an [...]

    Wie gesagt, häng dich nicht so sehr an dem konkreten Code auf - es geht darum, dass man nicht jedem Fall die maximalen Garantien vom Compiler einfordern muss, sondern dass ein fußnägelaufrollendes UB je nach Kontext sogar ein Vorteil sein kann, weil es dem Compiler mehr Freiheiten bietet - natürlich sofern man garantieren kann, dass es ohnehin nicht auftritt, solange das Programm nicht bereits an anderer Stelle "kaputt" ist.

    Dazu habe ich folgende Sourcedatei geschrieben [...]

    Das ist auf jeden Fall mal interessant, dieses konkrete Problem nochmal mit aktuellen Compilern gebaut zu sehen 😉

    Lohnt es sich für x86-64 spezifische Optimierungen die Kontrakte in der Software zu brechen? (Dateigröße von maximal 4GB auf 2GB reduziert!)

    Du weisst doch gar nicht, ob sich das überhaupt auf die unterstützte Dateigröße auswirkt - oder habe ich da was übersehen? Ein "Block" kann doch in dem Dateiformat eine feste Größe haben. Hat er nicht sogar in dem Vortrag erwähnt, dass das 64KiB-Blöcke sind, oder trügt mich meine Erinnerung?

    Ein Dateiformat ist übrigens auch noch so ein Beispiel, wo ich garantieren kann, dass meine Indizes in den Speicher nicht mehr als einen int benötigen - wenn das Dateiformat da z.B. Limits auferlegt und so eine Funktion nur Blöcke dieser Größe gefüttert bekommen kann. Ein größerer Block kann nur aus einer kaputten Datei oder von kaputtem vorangegangenen Code stammen und das sollte tunlichst vorher abgefangen werden, bevor ich anfange, darauf zu arbeiten. Da rettet mich dann ein size_t auch nicht mehr, wenn ich auf fehlerhaften Daten arbeite.



  • Qt nutzt für Indizes int. Der Compiler will size_t. In Rust wird size_t verwendet. Java nutzt int, weil die kein unsigned haben.
    Ich finde size_t sauberer.



  • Mit einiger Verzögerung, da ich mir die Zeit nehmen musste die Stellen herauszusuchen.

    @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    Du weisst schon, dass die Komplexität in O\mathcal{O}-Notation keine Aussage darüber trifft, wie lange du letztendlich auf dein Ergebnis warten musst, sondern wie schnell die Funktion der Laufzeit in Abhängigkeit von der Problemgröße wächst?

    Nein, da die ISO Norm hier gar nicht die O-Notation verwendet, und sie wie von Dir in diesem Kontext interpretiert auch keinerlei Sinn ergibt. Wenn man nur ein Objekt holen will, kann der Aufwand gar nicht auf die Anzahl der Objekte bezogen sein. Aber es macht einen Unterschied, ob man das n-te Objekt aus einem Vektor holen will oder das n-te Objekt aus einer Liste, darum geht es.

    Ich habe nicht abgestritten, dass sie Zeiger abstrahieren - auch wenn ich sie eher für eine Verallgemeinerung von Zeigern halte. Ich habe lediglich Zweifel geäußert, dass man daraus ableiten kann, dass die Daten unbedingt alle im Adressraum der CPU liegen müssen. Bei einem std::contiguous_iterator könnte ich das nachvollziehen, bei einem allgemeinen std::random_access_iterator jedoch nicht.

    Die Zitate („kursiv“ gekennzeichnet und Kürzungen mit …) sind alle aus N4861, dem letzten freien Draft vor der Verabschiedung der C++20 Norm, die Hervorhebungen sind von mir.

    Demnach sollte man 23.3.1 §1 „Iterators are a generalization of pointers that allow a C ++ program to work with different data structures (for example, containers and ranges) in a uniform manner. …“, §2 „Since iterators are an abstraction of pointers, their semantics are a generalization of most of the semantics of pointers in C ++ . …“. Dann ist noch die Paragraphen §7, §8, §9, §10 und §11 beachten, „ … Values of an iterator i for which the expression *i is defined are called dereferenceable. … Iterators can also have singular values that are not associated with any sequence. … Results of most expressions are undefined for singular values; … Dereferenceable values are always non-singular.“, „Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges. A range is an iterator and a sentinel that designate the beginning and end of the computation, or an iterator and a count that designate the beginning and the number of elements to which the computation is to be applied.“, „An iterator and a sentinel denoting a range are comparable. A range [i, s) is empty if i == s; otherwise, [i, s) refers to the elements in the data structure starting with the element pointed to by i and up to but not including the element, if any, pointed to by the first iterator j such that j == s.“, „A sentinel s is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == s. If s is reachable from i, [i, s) denotes a valid range.“ und „A counted range i + [0, n) is empty if n == 0; otherwise, i + [0, n) refers to the n elements in the data structure starting with the element pointed to by i and up to but not including the element, if any, pointed to by the result of n applications of ++i. A counted range i + [0, n) is valid if and only if n == 0; or n is
    positive, i is dereferenceable, and ++i + [0, --n) is valid.

    23.3.4.13 § 1 „The random_access_iterator concept adds support for constant-time advancement with +=, +, -=, and -, as well as the computation of distance in constant time with -. Random access iterators also support array notation via subscripting.

    Nach 22.2.1 Tabelle 73 haben Container folgende Eigenschaften
    .begin(), .end(), .cbegin() und .cend() müssen konstantes Laufzeitverhalten haben, analog dazu verhalten sich die Reverse Iterator Funktionen.

    Gültige Iteratoren lassen sich immer dereferenzieren.

    Sicher, dass ein Iterator beim dereferenzieren keine Exception werfen darf und wirklich immer einen erfogreichen Zugriff garantieren muss?

    Ich schrieb von gültigen Iteratoren, d.h. Iteratoren aus einer valid range, diese kann man immer dereferenzieren, und bei einem Random Access Iterator muss man in konstanter Zeit (siehe Einleitung) dereferenzieren können.

    Ich glaube nicht, dass ein Container (beliebige) Allokatoren unterstützen muss, auch wenn es die Standard-Container tun, oder?

    Man hat immer eine Abhängigkeit vom Allokator, entweder implizit vom Standard Allokator, oder wie bei den Standard Container explizit über die Allokator-Schnittstelle.

    Dito. Du machst auch jede Menge Annahmen, wozu der Code alles verwendet werden könnte, obwohl ich vielleicht nur Code für flache Vektoren/Matrizen schreibe, die man auf den Stack legen kann und mit denen lediglich geometrische Probleme gelöst werden sollen.

    Es geht um den Punkt, dass man bei der Verwendung von size_t garantiert funktionierenden Code bekommt, und das nicht der Fall ist, wenn man stattdessen int einsetzt. Wesentlich ist dabei, dass Code meist sehr viel länger genutzt wird, als man denkt. Die ISO Norm garantiert nur, dass int mindestens 16Bit groß ist. D.h. auch für Code in Anwendungen ist int keine gute Wahl, da man es nur dann einsetzen darf, wenn man wirklich weiß, dass der Code niemals mehr als 64kiB Adressraum braucht.

    Für UNIX ist int 32Bit groß definiert, mittlerweile ist ILP32 und LP64 für UNIX festgelegt. Früher gab es mit UNICOS eine SILP64 Plattform. Aber das ist ja nicht die einzige Plattformen die es noch gibt. Historisch gab es einem ziemlich übel Mischmasch. Und ich kenne es noch, dass auf einer Plattform der eine C Compiler int als 16Bit definierte, während der andere 32Bit nutzte. Ja, das machte so richtig Spass, da die Systeme schon einige MB RAM hatten.

    Die Idee dahinter sind nicht "Mikrooptimierungen", sondern wie ich schrieb "simpler Code für simple Probleme".

    Simpler Code ist für mich Code, bei dem ich nicht darüber nachdenken muss, welche Randbedingungen erfüllt sein müssen, damit er gültig ist und das macht was er tun soll. Der Verständnisaufwand für size_t ist doch wohl nicht größer als für int?

    Du solltest dich nicht so sehr an dem konkreten Beispiel aufhängen. Das Thema der Vortragspassage ist viel allgemeiner - Wide Contracts vs Narrow Contracts und dass das je nach Umständen Auswirkungen auf den erzeugten Code haben kann. Der Wide Contract der unsigned Integer mit ihrem wohldefinierten Überlaufverhalten hat eben hier in dieser konkreten Konstellation den Compiler gezwungen, zusätzlichen Code einzufügen, damit diese Garantie eingehalten werden kann - obwohl die Datenstruktur und der Algorithmus so aufgebaut sind, dass dieser Fall nie eintritt. Was man daraus mitnehmen kann ist, dass man vielleicht nicht immer die Zusagen des Wide Contracts einfordern muss, wenn sie vom Kontext (Algorithmus/Datenstruktur) her nicht erforderlich sind.

    Die Codebeispiele die ich angeführt hatte, zeigen doch sehr eindeutig, dass der Vortrag sich hier im Rahmen der Mikrooptimierung bewegt noch dazu in einem speziellem Sonderfall. Der Witz ist doch gerade, dass size_t auch auf x86-64 hier den optimalen Code viel wahrscheinlicher generiert, während es bei int32_t nur unter optimalen Bedingungen erfolgt. Und auf RISC spielt das gleich gar keine Rolle mehr. Wichtig ist, dass der Code das macht was er soll, und danach kommt erst die Ausführungsgeschwindigkeit.

    Ergo, Kontrakte für systemspezifische Optimierungen zu ändern ist keine gute Sache.



  • @john-0 sagte in size_t vs int als Index bei Interation über Container?:

    Mit einiger Verzögerung, da ich mir die Zeit nehmen musste die Stellen herauszusuchen.

    @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    Du weisst schon, dass die Komplexität in O\mathcal{O}-Notation keine Aussage darüber trifft, wie lange du letztendlich auf dein Ergebnis warten musst, sondern wie schnell die Funktion der Laufzeit in Abhängigkeit von der Problemgröße wächst?

    Nein, da die ISO Norm hier gar nicht die O-Notation verwendet, und sie wie von Dir in diesem Kontext interpretiert auch keinerlei Sinn ergibt. Wenn man nur ein Objekt holen will, kann der Aufwand gar nicht auf die Anzahl der Objekte bezogen sein. Aber es macht einen Unterschied, ob man das n-te Objekt aus einem Vektor holen will oder das n-te Objekt aus einer Liste, darum geht es.

    Es geht bei der Query-Komplexität von Containern immer nur um ein Element, dass man dort herausholt. Diese wird in Abhängigkeit von nn angeben, welche die Gesamtanzahl der Elemente im Container ist. Selbstverständlich ist der "Aufwand auf die Anzahl der Objekte" bezogen.

    Ich bin zwar immer offen dafür, dass ich eventuell selbst etwas missverstanden habe, in diesem Fall muss ich dir aber raten, dein Verständnis von "konstante Laufzeit" und Komplexität von Algorithmen noch einmal zu hinterfragen. Du bist hier auf jedem Fall auf dem Holzweg. Welche "andere Definition" von sollte denn die ISO-Norm bitteschön verwenden und wo kann ich die finden?

    Im Labor hat man bereits SSDs auf Zugriffszeiten und Datenraten gebracht, die herkömmlichem Arbeitsspeicher bedrohlich nahe kommen und den RAM vergangener Generationen bereits übertrumpfen. Warum sollte der Zugriff auf eine Datenstruktur in einem solchen Speicher, der immer noch unabhängig von der Anzahl der Objekte und in jeder Hinsicht schneller ist als der RAM eines älteren Rechners ist, auf einmal nicht mehr konstant sein? Hat ein und derselbe Algorithmus etwa "konstante Laufzeit", wenn er auf einem aktuellen Rechner läuft, aber nicht mehr, wenn man ihn auf einem C64 oder einem Mikrocontroller ausführt?

    Ich habe nicht abgestritten, dass sie Zeiger abstrahieren - auch wenn ich sie eher für eine Verallgemeinerung von Zeigern halte. Ich habe lediglich Zweifel geäußert, dass man daraus ableiten kann, dass die Daten unbedingt alle im Adressraum der CPU liegen müssen. Bei einem std::contiguous_iterator könnte ich das nachvollziehen, bei einem allgemeinen std::random_access_iterator jedoch nicht.

    Die Zitate („kursiv“ gekennzeichnet und Kürzungen mit …) [...] ie Hervorhebungen sind von mir.
    [...]
    Nach 22.2.1 Tabelle 73 haben Container folgende Eigenschaften
    .begin(), .end(), .cbegin() und .cend() müssen konstantes Laufzeitverhalten haben, analog dazu verhalten sich die Reverse Iterator Funktionen.

    Es fällt mir schwer die "Hervorhebungen" zu finden. Ich sehe hier auf den ersten Blick nichts, dass erfordert, dass die Objekte im RAM liegen. "Verallgemeinerung" (Generalization) von Pointern bedeutet nicht, dass die Iteratoren in den RAM verweisen müssen. Eine Verallgemeinerung ist eine Obermenge und RAM-Pointer sind lediglich eine konkrete Ausprägung davon. Die verwendeten Ausdrücke wie "pointed to by the iterator" bedeutet m.E. nicht, dass das "Pointer in den RAM" sein müssen, sondern das es sich um allgemeine Verweise auf ein Objekt handelt. Das kann auch ein indirektes Handle sein, oder auch ein "file pointer".

    Falls es dir hier um das "constant time" gehen sollte, dann fußt das hier alles auf deinem Missverständnis, was dieser Ausdruck letztendlich bedeutet (s.o.).

    Gültige Iteratoren lassen sich immer dereferenzieren.

    Sicher, dass ein Iterator beim dereferenzieren keine Exception werfen darf und wirklich immer einen erfogreichen Zugriff garantieren muss?

    Ich schrieb von gültigen Iteratoren, d.h. Iteratoren aus einer valid range, diese kann man immer dereferenzieren, und bei einem Random Access Iterator muss man in konstanter Zeit (siehe Einleitung) dereferenzieren können.

    In deinen zitierten Ausschnitten aus dem Standard heisst es es lediglich "Values of an iterator i for which the expression *i is defined are called dereferenceable". Ich sehe da nichts davon, dass diese Operation auch erfolgreich sein muss und keine Exceptions werfen darf. Deine Argumentation, auf die ich mir hier bezog war allerdings: "Gültige Iteratoren lassen sich immer dereferenzieren. Wenn ich da an einen potentiellen File-Iterator denke, dann kann ich doch nicht garantieren, dass dieser in der Lage ist beim Anwendungen des Derefenzierungsoperators auch Speicher zu allozieren, um den Dateiblock auch landen zu können. Dadurch verletzt man die Garantie für Iteratoren."

    Das finde ich wenig überzeugend, und die Sache mit dem "constant time" hatten wir ja oben bereits.

    Ich glaube nicht, dass ein Container (beliebige) Allokatoren unterstützen muss, auch wenn es die Standard-Container tun, oder?

    Man hat immer eine Abhängigkeit vom Allokator, entweder implizit vom Standard Allokator, oder wie bei den Standard Container explizit über die Allokator-Schnittstelle.

    Beim impliziten Standard-Allokator setzt du voraus, dass der Speicher für alle existierenden Container-Objekte mit diesem reserveriert worden sein muss und die Objekte deshalb nicht in einer Datei liegen können - sehe ich das richtig? Das halte ich für einen Zirkelschluss.

    Dito. Du machst auch jede Menge Annahmen, wozu der Code alles verwendet werden könnte, obwohl ich vielleicht nur Code für flache Vektoren/Matrizen schreibe, die man auf den Stack legen kann und mit denen lediglich geometrische Probleme gelöst werden sollen.

    Es geht um den Punkt, dass man bei der Verwendung von size_t garantiert funktionierenden Code bekommt, und das nicht der Fall ist, wenn man stattdessen int einsetzt. Wesentlich ist dabei, dass Code meist sehr viel länger genutzt wird, als man denkt. Die ISO Norm garantiert nur, dass int mindestens 16Bit groß ist. D.h. auch für Code in Anwendungen ist int keine gute Wahl, da man es nur dann einsetzen darf, wenn man wirklich weiß, dass der Code niemals mehr als 64kiB Adressraum braucht.

    Das hatten wir doch schon alles! Natürlich halte ich es auch für sinnvoll, wenn es die Umstände erfordern die entsprechenden Datentypen zu nehmen. Aber nicht jeder Code braucht diese Garantien ... weiteres Beispiel aus Code, mit dem ich gerade zu tun habe:

    Webservice(
        std::string_view address,
        std::uint16_t port,
        int nthreads = 1
    );
    

    Schnell geschrieben, schnell zu lesen und zu verstehen. Kein Grund für 26412^{64-1} Threads oder gar 64k Threads auf einem System mit gerade einmal 64k Speicher. Völlig in Ordnung.

    Ansonsten: Können wir es vielleicht dabei bewenden lassen? Wir haben ja durchaus jede Menge Überschneidungen in unseren Ansichten. In Code, wo die Größe wirklich relevant ist bin ich ja auch auf deiner Seite. Ich sehe C++ allerdings auch als Stroustrups "simplere Sprache", die damit kämpft, sich an die Oberfläche zu buddeln. Ich bin tatsächlich so jemand, der C++-Code bevorzugt, der wie ein Python-Skript geschrieben wurde, sofern es an der Stelle Sinn macht und der Code korrekt ist. An anderen Stellen - dort wo es relevant ist - bin ich dann allerdings auch sehr penibel, konsultiere den Wortlaut des Standards und schreibe Code wie ein Standardbibliotheksentwickler.



  • @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    Es geht bei der Query-Komplexität von Containern immer nur um ein Element, dass man dort herausholt. Diese wird in Abhängigkeit von nn angeben, welche die Gesamtanzahl der Elemente im Container ist. Selbstverständlich ist der "Aufwand auf die Anzahl der Objekte" bezogen.

    Der Punkt ist, dass diese Operationen unabhängig von der Anzahl der Elemente im Container sind, sie müssten damit immer konstant sein, wenn es da nicht reale Computerhardware gäbe auf der das nicht mehr der Fall ist. Bei einem C64 oder IBM AT mit PC-DOS hast Du noch so ein Laufzeitverhalten, aber eben nicht mehr auf einem modernen Computer. Allerdings kann man bei Ausführen des Programms im Arbeitsspeicher eines modernen Computers eine feste unveränderliche obere Schranke für die Laufzeit angeben, so dass man hier von konstanter Laufzeit in erster Näherung reden kann.

    Wesentlich ist, dass das bei Deiner Vorstellung eines Containers der Daten aus dem Storage lädt nicht mehr der Fall ist. Das Laufzeitverhalten wird unkalkulierbar, weil es von anderen externen Parametern abhängt, die man gar nicht unter Kontrolle hat, d.h. eine solche obere Schranke für das Laufzeitverhalten kann man dann nicht mehr angeben.

    Hat ein und derselbe Algorithmus etwa "konstante Laufzeit", wenn er auf einem aktuellen Rechner läuft, aber nicht mehr, wenn man ihn auf einem C64 oder einem Mikrocontroller ausführt?

    Nein, umgekehrt ergibt das Sinn. An einem simplen Beispiel lässt sich das leicht erörtern, die Matrixmultiplikation quadratischer Matrizen mit der Formel

    C=AB mit cik=j=1maijbjk.C = A\cdot B\text{ mit } c_{ik}=\sum_{j=1}^m a_{ij}\cdot b_{jk}\text{.}

    Dieser Algorithmus hat bei quadratischen Matrizen eine Komplexität von O(n³). Wenn man das auf einem C64 oder IBM PC ausführt, dann wird da keinerlei Abhängigkeit von der Problemgröße existeren, außer der bekannten O(n³) Abhängigkeit. Wenn man aber die Formel

    cTn3nc\approx\frac{\sqrt[3]{T_n}}{n}

    ansetzt, dann sollte cc für verschiene nn eine Konstante sein. Da der eigentliche Wert von cc relativ egal ist, habe ich die Ergebnistabelle so skaliert, dass der niedrigste Wert gleich 1 ist.

    size	spez Laufzeit
    16	1,14118468408542
    24	1,04282597767106
    32	1
    48	1,0492199705436
    64	1,03587393791552
    75	1,08767104902218
    96	1,02854398033415
    100	1,01211927133676
    128	1,08737318855509
    150	1,02044288201782
    200	1,04338402455406
    250	1,01339194787795
    256	1,30887894974164
    260	1,0155664470191
    275	1,01962347140481
    295	1,02158487669401
    350	1,0287511876156
    400	1,1984233409584
    450	1,12343549672648
    512	1,37962375396019
    525	1,53057896775454
    550	1,82663814427042
    592	2,01808118993491
    605	2,0134661186662
    620	2,11137155915238
    750	2,2714862766382
    1024	2,28530794416235
    

    Ganz offensichtlich ist die Konstante gar nicht konstant, sondern ist veränderlich mit dem Problemgröße. Wir sehen, dass das in vielen Fällen das Speichermodell, was für die Berechnung der Komplexität angenommen wird, nicht mehr der Realität entspricht. Wenn Du sehen willst, wie man die Matrixmultiplikation bei Computern mit Cachehierachien auch mit O(n³) wachsen lassen kann, dann such nach einem Artikel von Kazushige Goto. Das ist der ursprüngliche Autor von der GotoBLAS.

    Beim impliziten Standard-Allokator setzt du voraus, dass der Speicher für alle existierenden Container-Objekte mit diesem reserveriert worden sein muss und die Objekte deshalb nicht in einer Datei liegen können - sehe ich das richtig? Das halte ich für einen Zirkelschluss.

    Ich weiß ja nicht wie Du auf diesen Gedankengang kommst, da ein solcher hypothetischer „Iterator“ natürlich mit dem Standardallokator und den Filesystemfunktionen von C++ umsetzbar wäre. Es geht mir um einen ganz anderen Aspekt. Der Standardallokator setzt ein unterkomplexes Speichermodell voraus, und das entspricht nun einmal nicht mehr der Realität. Für viele Programme ist das ausreichend gut, aber halt nicht für alle. Da muss man dann auf Libraries wie die hwloc-Library setzen, die die Speicherkomplexität so abbildet, dass man portabel immer optimale Algorithmen umsetzen kann.

    Ansonsten: Können wir es vielleicht dabei bewenden lassen?

    Es gibt einen Punkt an den wir unterschiedlicher Meinung sind Zeiger. Ich zitiere hier einfach mal Stroustrup selbst: deutsche Übersetzung, 2. Auflage, ISBN 3-89319-386-3, Seite 61 §2.3.5

    Für die meisten Typen T ist T* ein Zeiger auf T. Mit anderen Worten, ein T* kann die Adresse eines Objektes vom Typ T enthalten. …

    Für eine andere Auslegung des Begriffs Zeigers, hätte ich gerne eine zitierfähige Quellenangabe.



  • @Finnegan sagte in size_t vs int als Index bei Interation über Container?:

    Aber nicht jeder Code braucht diese Garantien ... weiteres Beispiel aus Code, mit dem ich gerade zu tun habe:

    Webservice(
        std::string_view address,
        std::uint16_t port,
        int nthreads = 1
    );
    

    Schnell geschrieben, schnell zu lesen und zu verstehen. Kein Grund für 26412^{64-1} Threads oder gar 64k Threads auf einem System mit gerade einmal 64k Speicher. Völlig in Ordnung.

    Naja... -3 Threads macht auch wenig Sinn 😉


Anmelden zum Antworten