Comment allouer des structures de taille variable de manière contiguë en mémoire?

https://stackoverflow.com/questions/1626846

06-07-2019
|

Question

J'utilise C ++ et j'ai les structures suivantes:

struct ArrayOfThese {
  int a;
  int b;
};

struct DataPoint {
  int a;
  int b;
  int c;
};

En mémoire, je souhaite avoir un ou plusieurs éléments ArrayOfTes ces derniers à la fin de chaque point de données. Il n’existe pas toujours le même nombre d’éléments ArrayOfTese par DataPoint.

Parce que j’ai un nombre ridicule de points de données à assembler puis à diffuser sur un réseau, je souhaite que tous mes points de données et leurs éléments ArrayOfThese soient contigus. Perdre de la place pour un nombre fixe d’ArrayOfTes ces éléments est inacceptable.

En C, j'aurais créé un élément à la fin de DataPoint déclaré comme ArrayOfThese d [0]; , auquel un attribut DataPoint était attribué, ainsi que suffisamment d'octets supplémentaires pour le nombre d'éléments ArrayOfThese que j'avais, et utilisé le tableau factice pour les indexer. (Bien entendu, le nombre d'éléments ArrayOfCes devrait être dans un champ de DataPoint.)

En C ++, l’utilisation de placement new et du même tableau de 0 longueurs hack est-elle la bonne approche? Si tel est le cas, placement new garantit-il que les appels ultérieurs à partir du même pool de mémoire seront alloués de manière contiguë?

La solution

Etant donné que vos structures sont des POD, vous pouvez aussi bien le faire que dans C. La seule chose dont vous aurez besoin est un casting. En supposant que n correspond au nombre d'éléments à allouer:

DataPoint *p=static_cast<DataPoint *>(malloc(sizeof(DataPoint)+n*sizeof(ArrayOfThese)));

Le placement new entre dans ce genre de choses, si vos objets ont un constructeur non trivial. Cependant, il ne garantit aucune allocation, car il ne s’alloue pas lui-même et nécessite que la mémoire ait déjà été allouée. Au lieu de cela, il considère le bloc de mémoire transmis comme un espace pour l'objet non encore construit, puis appelle le constructeur de droite pour le construire. Si vous deviez l'utiliser, le code pourrait ressembler à ceci. Supposons que DataPoint ait le membre ArrayOfThese arr [0] que vous suggérez:

void *p=malloc(sizeof(DataPoint)+n*sizeof(ArrayOfThese));
DataPoint *dp=new(p) DataPoint;
for(size_t i=0;i<n;++i)
    new(&dp->arr[i]) ArrayOfThese;

Ce qui est construit doit être détruit, donc si vous faites cela, vous devez également régler l'appel du destructeur.

(Personnellement, je recommande d'utiliser des POD dans ce genre de situation, car cela évite d'avoir à appeler des constructeurs et des destructeurs, mais ce genre de chose peut être fait de manière raisonnablement sûre si vous êtes prudent.)

Autres conseils

Etant donné que vous utilisez des structures simples sans constructeur, vous pouvez revenir à la gestion de la mémoire C:

void *ptr = malloc(sizeof(DataPoint) + n * sizeof(ArrayOfThese));
DataPoint *dp = reinterpret_cast<DataPoint *>(ptr));
ArrayOfThese *aotp = reinterpet_cast<ArrayOfThese *>(reintepret_cast<char *>(ptr) + sizeof(DataPoint));

Comme Adrian l'a dit dans sa réponse , ce que vous faites en mémoire ne doit pas nécessairement être identique à ce que vous diffusez sur le réseau. En fait, il pourrait même être bon de diviser cela clairement, car avoir un protocole de communication reposant sur une conception spécifique de vos données pose un énorme problème si vous devez ultérieurement refactoriser vos données.

La méthode C ++ pour stocker un nombre arbitraire d'éléments de manière contiguë consiste bien sûr à std :: vector . Puisque vous n'avez même pas envisagé cela, je suppose qu'il y a quelque chose qui le rend indésirable. (Avez-vous seulement un petit nombre de ArrayOfThese et craignez-vous la surcharge d'espace associée à std :: vector ?)

Bien que l’astuce consistant à sur-allouer un tableau de longueur nulle ne soit probablement pas sûre de fonctionner et puisse, techniquement, invoquer le comportement indéfini tant redouté, c’est un procédé largement répandu. Sur quelle plateforme es-tu? Sous Windows, cela se fait dans l'API Windows. Il est donc difficile d'imaginer un fournisseur livrant un compilateur C ++ qui ne le prendrait pas en charge.

S'il existe un nombre limité d'éléments ArrayOfThese possibles, vous pouvez également utiliser le truc de fnieto pour spécifier ces quelques nombres, puis new l'une des instances de modèle résultantes, en fonction du numéro d'exécution:

struct DataPoint {
  int a;
  int b;
  int c;
};

template <std::size_t sz>
struct DataPointWithArray : DataPoint {
  ArrayOfThese array[sz];
};

DataPoint* create(std::size_t n)
{
  switch(n) {
    case 1: return new DataPointWithArray[1];
    case 2: return new DataPointWithArray[2];
    case 5: return new DataPointWithArray[5];
    case 7: return new DataPointWithArray[7];
    case 27: return new DataPointWithArray[27];
    default: assert(false);
  }
  return NULL;
}

Avant C ++ 0X, le langage ne disposait que d’un modèle de mémoire non . Et avec la nouvelle norme, je ne me souviens plus de discussions sur les garanties de contiguïté.

En ce qui concerne cette question particulière, il semble que vous souhaitiez un répartiteur de pools, dont il existe de nombreux exemples. Pensez à vous! X & oi = book_result & ct = result & resnum = 2 & ved = 0CA8Q6AEwAQ # v = onepage & q = & f = false "rel =" nofollow à la suite "> Conception C ++ moderne , par Alexandrescu. La discussion sur les allocateurs de petits objets est ce que vous devriez regarder.

Je pense que boost :: variant pourrait accomplir cela. Je n'ai pas eu l'occasion de l'utiliser, mais je crois que c'est une enveloppe autour des unions, donc un std :: vector d'entre elles devrait être contigu, mais bien sûr, chaque élément prendra la plus grande des deux tailles, vous ne pouvez pas avoir un vecteur avec des éléments de tailles différentes.

Jetez un coup d’œil à comparaison entre boost :: variante et boost :: any .

Si vous souhaitez que le décalage de chaque élément dépende de la composition des éléments précédents, vous devez écrire votre propre allocateur et vos propres accesseurs.

On dirait qu’il serait plus simple d’allouer un tableau de pointeurs et de travailler avec cela plutôt que d’utiliser un placement nouveau. De cette façon, vous pouvez simplement réaffecter le tableau entier à la nouvelle taille avec un coût d'exécution peu élevé. De plus, si vous utilisez placement new, vous devez appeler explicitement les destructeurs, ce qui signifie que combiner le non-placement et le placement dans un seul tableau est dangereux. Lisez http://www.parashift.com/c++-faq-lite/dtors .html avant de faire quoi que ce soit.

ne confondez pas l'organisation des données dans votre programme et dans l'organisation des données pour la sérialisation: elles n'ont pas le même objectif.

Pour la diffusion en continu sur un réseau, vous devez prendre en compte les deux côtés du canal, l’émetteur et le destinataire: comment l’équipement récepteur différencie-t-il un DataPoint d’un ArrayOfThese? comment le côté destinataire sait-il combien d'ArrayOfCes sont ajoutés après un point de données? (à considérer également: quel est l'ordre des octets de chaque côté? Les types de données ont-ils la même taille en mémoire?)

Personnellement, je pense que vous avez besoin d’une structure différente pour la transmission en continu de vos données, dans laquelle vous ajoutez le nombre de DataPoint que vous envoyez, ainsi que le nombre d’ArrayOfThese après chaque DataPoint. Je ne voudrais pas non plus m'inquiéter de la manière dont les données sont déjà organisées dans mon programme et que je réorganise / reformate pour l'adapter à mon protocole et non à mon programme. après cela, écrire une fonction pour l'envoi et une autre pour la réception n'est pas grave.

Pourquoi ne pas demander à DataPoint de contenir un tableau de longueurs variables ArrayOfThese ? Cela fonctionnera en C ou C ++. Il y a quelques problèmes si l'une des structures contient des types non primitifs

Mais utilisez free () plutôt que delete sur le résultat:

struct ArrayOfThese {
  int a;
  int b;
};


struct DataPoint {
  int a;
  int b;
  int c;
  int length;
  ArrayOfThese those[0];
};

DataPoint* allocDP(int a, int b, int c, size_t length)
{
    // There might be alignment issues, but not for most compilers:
    size_t sz = sizeof(DataPoint) + length * sizeof(ArrayOfThese);
    DataPoint dp = (DataPoint*)calloc( sz );
    // (Check for out of memory)
    dp->a = a; dp->b = b; tp->c = c; dp->length = length;
}

Ensuite, vous pouvez l'utiliser "normalement". dans une boucle où le DataPoint connaît sa longueur:

DataPoint *dp = allocDP( 5, 8, 3, 20 );

for(int i=0; i < dp->length; ++i)
{
    // Initialize or access: dp->those[i]
}

Pourriez-vous en faire des classes avec la même superclasse puis utiliser votre conteneur stl préféré, en utilisant la superclasse comme modèle?

Deux questions:

La similarité entre ArrayOfThese et DataPoint est-elle réelle ou simplifiée pour la publication? C'est à dire. la différence réelle est-elle juste un entier (ou un nombre quelconque du même type d’articles)?
Le nombre de ArrayOfThese associé à un point de données donné est-il connu au moment de la compilation?

Si le premier est vrai, je penserais simplement à allouer simplement un tableau d’éléments autant que nécessaire pour un DataPoint + N ArrayOfTese. Je construisais ensuite un petit morceau de code pour surcharger l'opérateur [] afin de renvoyer l'élément N + 3, et surcharger a (), b () et c () pour renvoyer les trois premiers éléments.

Si le second est vrai, j'allais suggérer essentiellement ce que je vois que fnieto vient de publier, je ne vais donc pas entrer plus dans les détails.

En ce qui concerne les nouveaux emplacements de placement, cela ne garantit pas vraiment quoi que ce soit en matière d’allocation. En fait, l’idée principale en ce qui concerne les nouveaux emplacements est qu’il n’ya aucun lien avec l’allocation de mémoire. Il vous permet plutôt de créer un objet à une adresse quelconque (sous réserve des restrictions d’alignement) dans un bloc de mémoire déjà alloué.

Voici le code que j'ai fini par écrire:

#include <iostream>
#include <cstdlib>
#include <cassert>
using namespace std;

struct ArrayOfThese {
  int e;
  int f;
};

struct DataPoint {
  int a;
  int b;
  int c;
  int numDPars;
  ArrayOfThese d[0];

  DataPoint(int numDPars) : numDPars(numDPars) {}

  DataPoint* next() {
    return reinterpret_cast<DataPoint*>(reinterpret_cast<char*>(this) + sizeof(DataPoint) + numDPars * sizeof(ArrayOfThese));
  }

  const DataPoint* next() const {
    return reinterpret_cast<const DataPoint*>(reinterpret_cast<const char*>(this) + sizeof(DataPoint) + numDPars * sizeof(ArrayOfThese));
  }
};

int main() {
  const size_t BUF_SIZE = 1024*1024*200;

  char* const buffer = new char[BUF_SIZE];
  char* bufPtr = buffer;

  const int numDataPoints = 1024*1024*2;
  for (int i = 0; i < numDataPoints; ++i) {
    // This wouldn't really be random.
    const int numArrayOfTheses = random() % 10 + 1;

    DataPoint* dp = new(bufPtr) DataPoint(numArrayOfTheses);

    // Here, do some stuff to fill in the fields.
    dp->a = i;

    bufPtr += sizeof(DataPoint) + numArrayOfTheses * sizeof(ArrayOfThese);
  }

  DataPoint* dp = reinterpret_cast<DataPoint*>(buffer);
  for (int i = 0; i < numDataPoints; ++i) {
    assert(dp->a == i);
    dp = dp->next();
  }

  // Here, send it out.

  delete[] buffer;

  return 0;
}

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow