Standardkonformer Hack

Ethon

TyRoXx schrieb:

Meinst du vielleicht das?

GCC kompiliert das auch so, vermutlich ist eine Extension? Keinen anderen Compiler zum Testen.

TyRoXx schrieb:

Um ganz sicher zu gehen, dass Padding beachtet wird, könntest du offsetof nehmen

Kannte ich garnicht, danke.

TyRoXx schrieb:

len * sizeof(int) kann übrigens überlaufen, also führen len > (std::numeric_limits<size_t>::max() / sizeof(int)) zu UB, sobald auf Elemente des Vectors zugegriffen wird. Die Addition mit offsetof(Vector, elements) kann auch noch überlaufen.

Stimmt.

So wäre es wohl korrekter... Was willst du denn erreichen?

Ich habe habe nur einen Zeiger Platz. Deine Lösung könnte ich auch durch "new std::vector<int>(len)" ersetzen. Nur finde ich es unsinnig 2 Allokationen zu benötigen wenn das Ziel ja nur ein zusammenhängender Speicherbereich + die Länge ist - gerade weil der Code sehr oft ausgeführt wird. Es ist einfach eine trivial umzusetzende Optimierung.

oenone schrieb:

Das war nur als kleines Beispiel gemeint. Ich weiß ja nicht, was der OP damit überhaupt vor hat. Sieht eher aus, als wolle er sein C-Wissen in C++ einsetzen.

Es ist nicht ganz schön aber komplett gekapselt also imho okay.

Arcoth schrieb:

Aber man könnte einen kleineren geeigneten Speicherbereich alloziieren und nur so viele Elemente in elements verwenden, wie benötigt.

Nein, das geht nicht; ist nicht standardkonform. Die Lebenszeit eines POD-Objektes beginnt, wenn Speicher mit der richtigen Ausrichtung und Groesse dafuer alloziert wurde. Das waere dann nicht der Fall.

Hmm blöd. Schränkt der C++-Standard da explizit den C-Standard ein? In C ist diese Optimierung ja relativ häufig zu sehen, auch in "seriösem" Code.

Ich denke mal das ist ein Fall von "garantiert isses nicht aber bevor das nicht klappt friert die Hölle ein"?

Marthog

Ich denke auch, dass es funktioniert, aber keine Sicherheit garantiert ist.

Der Vorteil ist, dass man eine Allokation spart. Insgesamt wuerde ich das aber nur in sehr geschwindigkeitskritischen Bereichen anwenden, wenn man schon die anderen Optimierungsmoeglichkeiten ausgeschoepft hat.
Ausserdem sollte man Speicherallokation und -freigabe das noch in einen Smart-pointer kapseln und alles mehrfach auf Sicherheit ueberpruefen.

cooky451

Dass man eine Optimierung oft sieht heißt nicht dass sie standardkonform ist, viele, insbesondere "x86-only" Programmierer, interessieren sich nicht die Bohne für den Standard.

Abgesehen davon erscheint mir diese Optimierung aber auch mehr als zweifelhaft. Hast du's mal ausprobiert und gemessen? Weil letztlich dürfte der Unterschied zwischen einem "Pointer zu Size + Vector" und Size + "Pointer zu Vector" ziemlich marginal sein, bei beidem braucht man nur eine Allokation und wenn man immer auf dem gleichen Vector rumfuchtelt ist da eh schon alles in Registern.

Für Verkettete Listen dagegen dürfte diese Optimierung ziemlich cool sein, man denke da an eine Liste von Strings:

struct node
{
    node* next;
    char* s;
};

vs

struct node
{
    node* next;
    char s[1];
};

Joa, das könnte schon schneller sein. Und mit polymorphen Objekten könnte man da bestimmt auch was zusammen basteln. Aber ob man das auch konform hinbekommt, da bin ich mir nicht so sicher.

Columbo

Bashar schrieb:

Arcoth schrieb:

Da das Objekt ein POD ist, fängt seine Lebenszeit an sobald Speicher mit der richtigen Ausrichtung alloziert wurde. Das ist hier allerdings nicht sichergestellt.

Wieso nicht? malloc liefert einen Zeiger, der für jeden Typ passend ausgerichtet ist.

Oh. Die Referenz sagt

If allocation succeeds, returns a pointer to the lowest (first) byte in the allocated memory block that is suitably aligned for any scalar type.

Aber der C-Standard sagt: malloc liefert einen Zeiger auf eine fundamental ausgerichtete Speicheradresse. Es gibt jedoch keine Garantie dass die Klasse nicht over-aligned ist... aber du hast Recht, das ist sie hundertprozentig (die ist ja ziemlich klein, wahrscheinlich 8 Byte). Dann muss die Referenz revidiert werden, die hat mich etwas verwirrt.
( std::align ist dann hier auch nicht noetig)

Dass man eine Optimierung oft sieht heißt nicht dass sie standardkonform ist

Aber GCC hat sie verwendet, IIRC. Oder kann dem das egal sein?

Ethon

Abgesehen davon erscheint mir diese Optimierung aber auch mehr als zweifelhaft. Hast du's mal ausprobiert und gemessen? Weil letztlich dürfte der Unterschied zwischen einem "Pointer zu Size + Vector" und Size + "Pointer zu Vector" ziemlich marginal sein, bei beidem braucht man nur eine Allokation und wenn man immer auf dem gleichen Vector rumfuchtelt ist da eh schon alles in Registern.

Das Problem ist dass "Size + "Pointer zu Vector"" nicht funktioniert da ich nur einen Zeiger Platz habe. Dh. wenn ich die Größe nicht in einem Rutsch mitallokiere dann brauche ich auf jeden Fall 2 Allokationen.

camper

Ethon schrieb:

Hoi,
spricht eigentlich dem Standard nach irgendetwas gegen diesen Hack?
struct Vector
{
    std::size_t len;
    int elements[];
};

Zulässig in C (6.7.2.1/18), nicht dagegen in C++. Mit elements[1] (und dann Verwendung bis zu der Größe, die mit malloc reserviert wurde) besteht kein Problem in C oder C++. Der reservierte Speicher hat keinen deklarierten Typ, das Einzige, was man in dieser Hinsicht ggf. unterlassen sollte, wäre Vector selbst als Zuweisungselement zu verwenden (ist wahrscheinlich kein wirkliches Problem, aber der Standard ist in diesem Bereich sehr gräulich).

Columbo

Mit elements[1] (und dann Verwendung bis zu der Größe, die mit malloc reserviert wurde) besteht kein Problem in C oder C++.

Das ist UB (letzer Satz §5.7/5)?

camper

Arcoth schrieb:

Mit elements[1] (und dann Verwendung bis zu der Größe, die mit malloc reserviert wurde) besteht kein Problem in C oder C++.

Das ist UB (letzer Satz §5.7/5)?

Inwiefern? Die betreffende reservierte Speicherstelle bekommt ja nicht auf magische Weise den effektiven Typ Vector (in Abwesenheit einer Zuweisung oder eines placement-new).

Columbo

camper schrieb:

Inwiefern?

Du deklarierst ein Array der Größe 1. Es hat 1 Element. Der Ausdruck elements[7] o.ä. resultiert demnach in undefiniertem Verhalten, völlig unabhängig davon, wie viel Speicher du reservierst - weil das per Definition äquivalent ist zu *(elements + 7) , und dieser Ausdruck wiederum eine Addition enthält die laut dem genannten Standardparagraph UB erzeugt - weil der Ursprüngliche Zeiger, das decay-te elements , und der resultierende Zeiger, elements + 7 , nicht auf Elemente desselben Arrays verweisen.

Die betreffende reservierte Speicherstelle bekommt ja nicht auf magische Weise den effektiven Typ Vector (in Abwesenheit einer Zuweisung oder eines placement-new).

Speicherstellen haben keine Typen. Objekte liegen an bestimmten, hintereinanderliegenden Bytes im Speicher; und die Lebenszeit eines Objektes beginnt sobald ... den Rest kennst du ja. placement-new ist hier demnach gar nicht nötig, schließlich hat Vector eine triviale Initialisierung.

Nathan

Es gibt jedenfalls unter C eine Extension für genau diesen Anwendungsfall:
https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
Mir ist jetzt nur nicht ganz klar, ob die auch für C++ gilt.

hustbaer

Arcoth schrieb:

Die Lebenszeit eines POD-Objektes beginnt, wenn Speicher mit der richtigen Ausrichtung und Groesse dafuer alloziert wurde.

Wo findet man das im Standard?

ps:

Arcoth schrieb:

weil der Ursprüngliche Zeiger, das decay-te elements , und der resultierende Zeiger, elements + 7 , nicht auf Elemente desselben Arrays verweisen.

Sondern?
Erklär mal auf welches Array der eine und auf welches Array der andere zeigt.

Ethon

Fällt jemandem ein Szenario ein in dem das schief gehen könnte?
Ich hätte da höchstens die Idee eines hypothetischen Compilers der Bound checking bei vorhandener Größeninformation macht. Was aber vermutlich auch nicht konform wäre.

hustbaer

Vorweg: dass ich zu dem Thema im Standard nachgesehen habe ist schon einige Zeit her. Es ist möglich dass mich meine Erinnerung betrügt oder ich was falsch verstanden habe.

----

Ich behaupte dass eine vernünftige Auslegung des Standards garantiert dass es funktionieren muss.
Dummerweise hab' ich aber auch den Eindruck dass der Standard diesbezüglich sehr sehr vage/implizit/lückenhaft ist.

IIRC macht die Array-Zeiger-Additions-Regel auf die sich Arcoth bezieht bei POD-Arrays deren Speicher nicht über new T[] besorgt wurde überhaupt keinen Sinn. Bzw. ist total unglücklich formuliert.

Gemeint ist dass die Addition verboten ist, wenn dabei eine Adresse entsteht, die ausserhalb des Speicherblocks liegt in dem die ursprüngliche Adresse liegt.
Und mit "Speicherblock" meine ich einfach das Ding das irgendwo mal "am Stück" angefordert wurde, über malloc(), operator new, new POD[] - was auch immer.
Weil da dann u.U. kein Speicher gemappt ist, und manche CPUs es nicht mögen wenn man solche Adressen erzeugt und in so einem Fall einen Trap (Fault) erzeugen. Auch wenn man die Adresse eben nur erzeugt oder von einem Register in ein anderes schupft, ohne wirklich einen Load auf die Adresse zu machen.
(Und mit "gemeint ist" meine ich: das ist der *Grund* warum es diese Regel gibt.)

Bezogen auf diese Regel ist also alles was innerhalb eines über malloc angeforderten Blocks liegt als "das selbe Array" anzusehen (passendes Alignment vorausgesetzt).

camper

hustbaer schrieb:

Arcoth schrieb:

Die Lebenszeit eines POD-Objektes beginnt, wenn Speicher mit der richtigen Ausrichtung und Groesse dafuer alloziert wurde.

Wo findet man das im Standard?

3.8/1 - allerdings ist das für die aufgeworfene Frage irrelevant. Die Legalität von Zeigerarithmetik hängt nicht von der Lebensdauer von Objekten ab, sondern nur davon, dass entsprechender Speicher zur Verfügung steht.

struct foo
{
    int x;
    int elems[1];
};

struct bar
{
    int x;
    int elems[1000];
};

...
foo* p = (foo*)std::malloc(sizeof(bar));
p->elems[100] = 42;                         // (1)
reinterpret_cast<bar*>(p)->elems[100] = 42; // (2)
p->elems < reinterpret_cast<bar*>(p)->elems; // (3)

@Arcoth: UB oder nicht?

Columbo

Wo findet man das im Standard?

§3.8 schrieb:

The lifetime of an object of type T begins when:
— storage with the proper alignment and size for type T is obtained, and
— if the object has non-trivial initialization, its initialization is complete.

Gemeint ist dass die Addition verboten ist, wenn dabei eine Adresse entsteht, die ausserhalb des Speicherblocks liegt in dem die ursprüngliche Adresse liegt.
Und mit "Speicherblock" meine ich einfach das Ding das irgendwo mal "am Stück" angefordert wurde, über malloc(), operator new, new POD[] - was auch immer.

If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

Erklär mal auf welches Array der eine und auf welches Array der andere zeigt.

Darum geht es gar nicht. Sie können beide gar nicht auf dasselbe Array-Objekt zeigen, weil die entsprechenden Membervariablen ( elements ) nur ein Element halten.

Columbo

camper schrieb:

struct foo
{
    int x;
    int elems[1];
};

struct bar
{
    int x;
    int elems[1000];
};

...
foo* p = (foo*)std::malloc(sizeof(bar));
p->elems[100] = 42;                         // (1)
reinterpret_cast<bar*>(p)->elems[100] = 42; // (2)
p->elems < reinterpret_cast<bar*>(p)->elems; // (3)

@Arcoth: UB oder nicht?

~~Soweit ich sehen kann, ja. (1) ist der genannte Additionsfall.~~
(2) ist ein Aliasverstoß.
(3) ist noch ein Aliasverstoß.
Edit: Lass mich mal nachdenken.

hustbaer

§3.8 schrieb:

The lifetime of an object of type T begins when:
— storage with the proper alignment and size for type T is obtained, and
— if the object has non-trivial initialization, its initialization is complete.

Dann entstehen bei malloc(1000) auch gleichzeitig alle int-Arrays die in dem von malloc() zurückgegebenen Block (passend aligned) Platz haben.

Du musst dir also nur ein passendes Array aussuchen das beide Elemente enthält.

Columbo

Du musst dir also nur ein passendes Array aussuchen das beide Elemente enthält.

Funktioniert das tatsächlich?

Weil nicht jedes Array von beliebiger Größe ein Member von Vector ist, oder?

hustbaer

Wieso sollte es ein Member von Vector sein müssen?

Columbo

hustbaer schrieb:

Wieso sollte es ein Member von Vector sein müssen?

Weil du darauf als Member zugreifst!? Der Member ist nämlich ein Array von Größe genau 1.