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 (mitsize_t
=uint32_t
) über die Bytes einer 8GiB großen Datei iterieren kann. Da brauchts was mit größerem Wertebereich alssize_t
.Und NEIN,
size_t
ist nicht dasselbe wieunsigned int
. Heutzutage ist es meistens ist es einuint64_t
, auf 32-Bit-Systemen oft einuint32_t
(hier stimmts dann mit demunsigned int
) und auf einem kleinen Arduino-System kann es auch schonmal einuint16_t
sein. Und dennoch kann es immer Container geben, für die man mehr als einensize_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 simplenint
hier lieber sähe.
-
@CppConst sagte in size_t vs int als Index bei Interation über Container?:
unsigned int
, was jasize_t
istNein.
-
@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 (mitsize_t
=uint32_t
) über die Bytes einer 8GiB großen Datei iterieren kann. Da brauchts was mit größerem Wertebereich alssize_t
.Wo steht das in der Norm? Die Norm sieht für
Container<T>::size_type
vor, dass alle nicht negativen Werte vonContainer<T>::difference_type
, der mitContainer<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 mansize_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?
-
@CppConst verwende gsl::index.
-
@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 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 mansize_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 einenint
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 keinenint
nehmen darf - zumalsize_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 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 einenint
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, aberuint32_t
mitint32_t
ersetzen stellt kein Problem dar? Immerhin reduziert man die mögliche Dateigröße von 4GB auf 2GB, wenn man den Datentypen vonuint32_t
aufint32_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
undsize_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 vonbool 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 einemuint64_t
promoten.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 keinenint
nehmen darf - zumalsize_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_t
ist 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 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 -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 allgemeinenstd::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 gehtDann 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 einenint
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 wiestd::iter_difference_t<Iterator>
oderstd::ranges::range_difference_t<Range>
nehmen (der Typ für den imstd::random_access_iterator
-Konzeptiterator[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äziseresstd::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, aberuint32_t
mitint32_t
ersetzen stellt kein Problem dar? Immerhin reduziert man die mögliche Dateigröße von 4GB auf 2GB, wenn man den Datentypen vonuint32_t
aufint32_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 einsize_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 -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 allgemeinenstd::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 stattdessenint
einsetzt. Wesentlich ist dabei, dass Code meist sehr viel länger genutzt wird, als man denkt. Die ISO Norm garantiert nur, dassint
mindestens 16Bit groß ist. D.h. auch für Code in Anwendungen istint
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 Compilerint
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ürint
?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 beiint32_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 -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 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 allgemeinenstd::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 stattdessenint
einsetzt. Wesentlich ist dabei, dass Code meist sehr viel länger genutzt wird, als man denkt. Die ISO Norm garantiert nur, dassint
mindestens 16Bit groß ist. D.h. auch für Code in Anwendungen istint
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 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 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
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
ansetzt, dann sollte für verschiene eine Konstante sein. Da der eigentliche Wert von 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
istT*
ein Zeiger aufT
. Mit anderen Worten, einT*
kann die Adresse eines Objektes vom TypT
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 Threads oder gar 64k Threads auf einem System mit gerade einmal 64k Speicher. Völlig in Ordnung.
Naja... -3 Threads macht auch wenig Sinn