Como faço para alocar estruturas de tamanho variável de forma contígua na memória?

https://stackoverflow.com/questions/1626846

06-07-2019
|

Pergunta

Eu estou usando C ++, e eu tenho as seguintes estruturas:

struct ArrayOfThese {
  int a;
  int b;
};

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

Na memória, eu quero ter 1 ou mais ArrayOfThese elementos no final de cada DataPoint. Há não são sempre o mesmo número de elementos ArrayOfThese por DataPoint.

Porque eu tenho um número ridículo de pontos de dados de montar e, em seguida, transmitir através de uma rede, eu quero que todos os meus pontos de dados e seus elementos ArrayOfThese ser contíguo. Desperdiçando espaço para um número fixo de elementos ArrayOfThese é inaceitável.

C, teria feito um elemento no final de DataPoint que foi declarado como ArrayOfThese d[0];, alocado um DataPoint mais suficiente bytes adicionais para elementos no entanto muitas ArrayOfThese I, e utilizado a matriz fictício para indexar dentro deles. (Claro, o número de elementos ArrayOfThese teria que ser em um campo de DataPoint.)

Em C ++, é usando posicionamento novo e a mesma matriz 0-length cortar a abordagem correta? Se assim for, faz posicionamento novo garantia de que as chamadas subseqüentes para nova a partir do mesmo pool de memória irá alocar contiguously?

Solução

Uma vez que suas estruturas são PODs você pode muito bem fazê-lo tal como faria em C. A única coisa que você precisa é de um elenco. Assumindo n é o número de coisas para alocar:

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

Placement nova vem para este tipo de coisa, se os objetos têm um construtor não-trivial. Ela garante nada sobre qualquer destinação, porém, para que isso não si alocação e requer que a memória já foram alocados de alguma forma. Em vez disso, ele trata o bloco de memória passado como espaço para o objeto que ainda não tem unconstructed, em seguida, chama o construtor direito de construí-lo. Se você tivesse que usá-lo, o código pode ir assim. Suponha DataPoint tem o membro ArrayOfThese arr[0] você sugere:

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;

O que fica construído deve ficar destruído por isso, se você fizer isso você deve resolver o chamado do destructor também.

(Pessoalmente eu recomendo usar PODs neste tipo de situação, porque remove qualquer necessidade de chamar construtores e destruidores, mas esse tipo de coisa pode ser feito razoavelmente com segurança se você for cuidadoso.)

Outras dicas

Uma vez que você está lidando com estruturas simples que não têm construtores, você pode reverter para o gerenciamento de memória 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));

Como Adrian disse em sua resposta , o que você faz na memória não tem que ser o mesmo que o que você transmitir através da rede. Na verdade, pode até ser bom para claramente dividir isso, porque ter um protocolo de comunicação confiar em seus dados sejam concebidos de uma forma específica torna grande problema se você mais tarde necessidade de refazer os seus dados.

forma O C ++ para armazenar um número arbitrário de elementos de forma contígua é, naturalmente, para std::vector. Desde que você nem sequer considerar isso, presumo que há algo que torna este indesejável. (Você só tem um pequeno número de ArrayOfThese e temem o espaço sobrecarga associada std::vector?)

Enquanto o truque com o excesso de alocação de uma matriz de comprimento zero, provavelmente não é garantido para trabalho e força, tecnicamente, invocar o comportamento indefinido temida, é um difundida. Em que plataforma você está? No Windows, isso é feito na API do Windows, por isso é difícil imaginar um vendedor vendendo um compilador C ++ que não apoiaria isso.

Se houver um número limitado de possíveis acusações elemento ArrayOfThese, você também pode usar de fnieto truque para especificar os poucos números e um então new das instâncias de modelo resultantes, dependendo do número de tempo de execução:

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;
}

Antes de C ++ 0X, a língua tinha não modelo de memória para falar. E com o novo padrão, eu não me lembro de qualquer conversa de garantias de contigüidade.

No que diz respeito a esta questão particular, que soa como se o que você quer é um alocador de piscina, muitos exemplos de que existem. Considere, por exemplo, Modern design C ++ , por Alexandrescu. O alocador discussão pequeno objeto é o que você deve olhar.

Eu acho boost::variant pode fazer isso. Eu não tive a oportunidade de usá-lo, mas eu acredito que é um invólucro em torno sindicatos, e assim por um std::vector deles deve ser contíguo, mas é claro que cada item terá o maior dos dois tamanhos, você não pode ter um vetor com elementos de diferentes tamanhos.

Dê uma olhada no a comparação dos boost :: variante e boost :: qualquer .

Se você quiser o deslocamento de cada elemento a ser dependente da composição dos elementos anteriores, você terá que escrever o seu próprio alocador e assessores.

Parece que seria mais simples para alocar uma matriz de ponteiros e trabalhar com isso em vez de usar posicionamento novo. Dessa forma, você poderia simplesmente realocar toda a matriz para o novo tamanho, com pouco custo de tempo de execução. Além disso, se você usar posicionamento novo, você tem que chamar explicitamente destruidores, que meios de mistura não-colocação e colocação em uma única matriz é perigoso. Leia http://www.parashift.com/c++-faq-lite/dtors .html antes de fazer qualquer coisa.

Não confunda organização dos dados dentro do seu programa e organização de dados para serialização: eles não têm o mesmo objetivo

para streaming através de uma rede, você tem que considerar ambos os lados do canal, o envio e o lado de recepção: como é que a diferenciar lado receptor entre uma DataPoint e um ArrayOfThese? como é que o lado recebedor saber quantos ArrayOfThese são anexados após um DataPoint? (Também a considerar:? O que é a ordenação de bytes de cada lado faz tipos de dados têm o mesmo tamanho em memória)

Pessoalmente, acho que você precisa de uma estrutura diferente para a transmissão dos seus dados, em que você adicionar o número de DataPoint você está enviando, bem como o número de ArrayOfThese após cada DataPoint. i também não se preocupam com a forma como os dados já é organizado no meu programa e reorganizar / reformatação para atender meu protocolo e não meu programa. depois que escrever uma função para enviar e outro para recepção não é um grande negócio.

Por que não ter DataPoint contém uma matriz de comprimento variável de ArrayOfThese itens? Isto irá funcionar em C ou C ++. Existem algumas preocupações se qualquer struct contém tipos não-primitivos

Mas o uso free () em vez de Excluir sobre o resultado:

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;
}

Em seguida, você pode usá-lo "normalmente" em um loop onde o DataPoint sabe seu comprimento:

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

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

Você poderia fazer aqueles em classes com a mesma superclasse e, em seguida, usar o seu recipiente STL favorito de escolha, utilizando a superclasse como modelo?

Duas perguntas:

é a semelhança entre ArrayOfThese e DataPoint real, ou uma simplificação para postagem? Ou seja, é a diferença real apenas um int (ou algum número arbitrário do mesmo tipo de itens)?
O número de ArrayOfThese associados a um determinado DataPoint conhecido em tempo de compilação?

Se o primeiro é verdade, eu acho difícil sobre simplesmente alocar uma variedade de itens como muitos como necessária para uma DataPoint + N ArrayOfThese. Eu, então, construir um pouco rápido de código para operador de sobrecarga [] para que a retornar o artigo N + 3, e sobrecarregar a (), b () e c () para retornar os três primeiros itens.

Se a segunda é verdade, eu ia sugerir essencialmente o que eu vejo fnieto acabou de postar, por isso não vou entrar em mais detalhes.

Quanto posicionamento novo vai, ele realmente não garante nada sobre a alocação - na verdade, toda a idéia sobre a colocação de novo é que é completamente alheios a alocação de memória. Em vez disso, ele permite que você criar um objeto em um endereço arbitrário (sujeito a restrições de alinhamento) em um bloco de memória que já está alocado.

Aqui está o código que acabou escrevendo:

#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;
}

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow