Standardkonformer Hack

[Ethon]

Hoi,
spricht eigentlich dem Standard nach irgendetwas gegen diesen Hack?

struct Vector
{
    std::size_t len;
    int elements[];
};

Vector* makeVector(std::size_t len)
{
    Vector* vec = (Vector*)std::malloc(sizeof(Vector::len) + len * sizeof(int));
    vec->len = len;
    return vec;
}

std::size_t ist afaik immer so groß wie int oder ein Vielfaches davon also wird mir auch kein Padding in den Weg kommen schätze ich.

Danke & Grüße,
Ethon

[TyRoXx]

Meinst du vielleicht das?

struct Vector
{
    std::size_t len;
    int elements[1];
};

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

Vector* makeVector(std::size_t len)
{
    Vector* vec = (Vector*)std::malloc(offsetof(Vector, elements) + len * sizeof(int));
    vec->len = len;
    return vec;
}

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.

[oenone]

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

struct Vector
{
    std::size_t len;
    int *elements;
};

Vector* makeVector(std::size_t len)
{
    Vector* vec = (Vector*)std::malloc(sizeof(Vector));
    vec->len = len;
    vec->elements = (int*)std::calloc(sizeof(int), len);
    return vec;
}

Oder gleich mit Konstruktor:

struct Vector
{
    std::size_t len;
    int *elements;
    Vector(std::size_t _len)
    {
        len = _len;
        elements = new int[len];
    }
    ~Vector()
    {
        delete[] elements;
    }
}

// ...
Vector *myVector = new Vector(10);
// ...
delete myVector;

dann hättest du auch keine Memoryleaks.

[tntnet]

oenone schrieb:

Oder gleich mit Konstruktor:

struct Vector
{
    std::size_t len;
    int *elements;
    Vector(std::size_t _len)
    {
        len = _len;
        elements = new int[len];
    }
    ~Vector()
    {
        delete[] elements;
    }
}

// ...
Vector *myVector = new Vector(10);
// ...
delete myVector;

dann hättest du auch keine Memoryleaks.

Da hast Du aber den Kopierkonstruktor und das Assignment vergessen.

[oenone]

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.

[Columbo]

spricht eigentlich dem Standard nach irgendetwas gegen diesen Hack?

Nein, das ist nicht in Ordnung. 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.

[tntnet]

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.

Ich nehme an, der OP will eine Allokation sparen. Die Idee finde ich jetzt gar nicht so abwegig, wie es erst erscheint. Wie wäre es mit:

struct Vector
{
    std::size_t len;
    int elements[MAX_INT];
};

Jetzt sollte man die Struktur nicht direkt instantiieren, da sie sehr viel Speicher beanspruchen würde. Aber man könnte einen kleineren geeigneten Speicherbereich alloziieren und nur so viele Elemente in elements verwenden, wie benötigt. Aber irgendwie ist das schon ein wenig C-style.

[Columbo]

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.

[Bashar]

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.

[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.