1D ou 2D array, o que é mais rápido?

Estou precisando de representar um campo 2D (eixos x, y) e enfrento um problema: Devo usar uma matriz 1D ou uma matriz 2D?

Eu posso imaginar, que recalcular os índices para matrizes 1D (y + x * n) poderia ser mais lento do que usar matriz 2D (x, y), mas eu poderia imaginar que 1D poderia estar no cache da CPU.

Fiz algumas pesquisas no google, mas encontrei apenas páginas relativas a array estático (e afirmando que 1D e 2D são basicamente os mesmos). Mas minhas matrizes devem me dinamizar.

Então o que

  1. Mais rápido,
  2. menor (RAM)

arrays dinâmica 1D ou arrays 2D dynamics?

Obrigado 🙂

tl: dr: Você provavelmente deveria usar uma abordagem unidimensional.

Nota: Não é possível detalhar os detalhes que afetam o desempenho ao comparar padrões dynamics de armazenamento 1d ou dynamic 2d sem preencher livros, pois o desempenho do código depende de um número muito grande de parâmetros. Perfil, se possível.

1. O que é mais rápido?

Para matrizes densas, a abordagem 1D provavelmente será mais rápida, pois oferece melhor localidade de memory e menos sobrecarga de alocação e desalocação.

2. O que é menor?

O Dynamic-1D consome menos memory do que a abordagem 2D. Este último também requer mais alocações.

Observações

Eu expus uma longa resposta por baixo com várias razões, mas eu quero fazer algumas observações sobre suas suposições primeiro.

Eu posso imaginar, que recalcular índices para matrizes 1D (y + x * n) poderia ser mais lento do que usando matriz 2D (x, y)

Vamos comparar estas duas funções:

 int get_2d (int **p, int r, int c) { return p[r][c]; } int get_1d (int *p, int r, int c) { return p[c + C*r]; } 

O assembly (não-inlined) gerado pelo Visual Studio 2015 RC para essas funções (com otimizações ativadas) é:

 ?get_1d@@YAHPAHII@Z PROC push ebp mov ebp, esp mov eax, DWORD PTR _c$[ebp] lea eax, DWORD PTR [eax+edx*4] mov eax, DWORD PTR [ecx+eax*4] pop ebp ret 0 ?get_2d@@YAHPAPAHII@Z PROC push ebp mov ebp, esp mov ecx, DWORD PTR [ecx+edx*4] mov eax, DWORD PTR _c$[ebp] mov eax, DWORD PTR [ecx+eax*4] pop ebp ret 0 

A diferença é mov (2d) vs. lea (1d). O primeiro tem uma latência de 3 ciclos e um throughput máximo de 2 por ciclo, enquanto o segundo tem uma latência de 2 ciclos e um throughput máximo de 3 por ciclo. (De acordo com as tabelas de instruções – Agner Fog Como as diferenças são pequenas, acho que não deve haver uma grande diferença de desempenho decorrente do recálculo do índice. Espero que seja muito improvável que essa diferença seja o gargalo de qualquer programa.

Isso nos leva ao próximo (e mais interessante) ponto:

… mas eu poderia imaginar que 1D poderia estar no cache da CPU …

É verdade, mas o 2d pode estar no cache da CPU também. Veja The Downsides: Localidade de memory para uma explicação do porque 1d ainda é melhor.

A resposta longa, ou por que o armazenamento dynamic de dados bidimensionais (ponteiro para ponteiro ou vetor de vetor) é “ruim” para matrizes simples / pequenas.

Nota: Trata-se de arrays dynamics / esquemas de alocação [malloc / new / vector etc.]. Uma matriz 2d estática é um bloco contíguo de memory e, portanto, não está sujeita às desvantagens que vou apresentar aqui.

O problema

Para entender o motivo pelo qual uma matriz dinâmica de matrizes dinâmicas ou um vetor de vetores provavelmente não é o padrão de armazenamento de dados escolhido, é necessário entender o layout da memory dessas estruturas.

Exemplo de caso usando o ponteiro para a syntax do ponteiro

 int main (void) { // allocate memory for 4x4 integers; quick & dirty int ** p = new int*[4]; for (size_t i=0; i<4; ++i) p[i] = new int[4]; // do some stuff here, using p[x][y] // deallocate memory for (size_t i=0; i<4; ++i) delete[] p[i]; delete[] p; } 

As desvantagens

Localidade de memory

Para esta "matriz" você aloca um bloco de quatro pointers e quatro blocos de quatro inteiros. Todas as alocações não estão relacionadas e podem, portanto, resultar em uma posição de memory arbitrária.

A imagem a seguir lhe dará uma idéia de como a memory pode parecer.

Para o caso real de 2d :

  • O quadrado violeta é a posição da memory ocupada pelo próprio p .
  • Os quadrados verdes montam a região de memory p aponta para (4 x int* ).
  • As 4 regiões de 4 quadrados azuis contíguos são as apontadas por cada int* da região verde

Para o 2d mapeado no caso 1d :

  • O quadrado verde é o único ponteiro requerido int *
  • Os quadrados azuis agrupam a região da memory para todos os elementos da matriz (16 x int ).

Real 2d vs mapeado 2d layout de memória

Isso significa que (ao usar o layout esquerdo) você provavelmente observará desempenho pior do que um padrão de armazenamento contíguo (como visto à direita), devido ao armazenamento em cache, por exemplo.

Digamos que uma linha de cache seja "a quantidade de dados transferidos para o cache de uma só vez" e imaginemos um programa acessando a matriz inteira um elemento após o outro.

Se você tiver uma matriz 4 vezes 4 de valores de 32 bits adequadamente alinhada, um processador com uma linha de cache de 64 bytes (valor típico) é capaz de "um disparo" dos dados (4 * 4 * 4 = 64 bytes). Se você iniciar o processamento e os dados ainda não estiverem no cache, você enfrentará um erro de cache e os dados serão buscados na memory principal. Essa carga pode buscar a matriz inteira de uma só vez, já que ela se encheckbox em uma linha de cache, se e somente se estiver contiguamente armazenada (e alinhada corretamente). Provavelmente, não haverá mais erros ao processar esses dados.

No caso de um sistema dynamic, "real bidimensional", com localizações não relacionadas de cada linha / coluna, o processador precisa carregar cada localização de memory separadamente. Mesmo que apenas 64 bytes sejam necessários, o carregamento de 4 linhas de cache para 4 posições de memory não relacionadas levaria, na pior das hipóteses, a transferência de 256 bytes e o desperdício de 75% da largura de banda da taxa de transferência. Se você processar os dados usando o esquema 2d, você novamente (se já não estiver em cache) enfrentará um erro de cache no primeiro elemento. Mas agora, apenas a primeira linha / colum estará no cache após o primeiro carregamento da memory principal, porque todas as outras linhas estão localizadas em algum outro lugar na memory e não adjacentes ao primeiro. Assim que você atingir uma nova linha / coluna, haverá novamente uma falha de cache e a próxima carga da memory principal será executada.

Longa história curta: O padrão 2d tem uma chance maior de falhas de cache com o esquema 1d oferecendo melhor potencial de desempenho devido à localização dos dados.

Alocação / Desalocação Freqüente

  • Alocações N + 1 (4 + 1 = 5) (usando malloc, allocator :: allocate ou qualquer outro) são necessárias para criar a matriz desejada NxM (4 × 4).
  • O mesmo número de operações de desalocação apropriadas deve ser aplicado também.

Portanto, é mais caro criar / copiar tais matrizes em contraste com um esquema de alocação único.

Isso está ficando ainda pior com um número crescente de linhas.

Sobrecarga de consumo de memory

Vou sumr um tamanho de 32 bits para int e 32 bits para pointers. (Nota: Dependência do sistema.)

Vamos lembrar: queremos armazenar uma matriz int de 4 × 4, o que significa 64 bytes.

Para uma matriz NxM, armazenada com o esquema ponteiro a ponteiro apresentado, consumimos

  • N*M*sizeof(int) [dados azuis reais] +
  • N*sizeof(int*) [os pointers verdes] +
  • sizeof(int**) [a variável violeta p] bytes.

Isso faz 4*4*4 + 4*4 + 4 = 84 bytes no caso do presente exemplo e fica ainda pior quando se usa std::vector> . Ele exigirá que N * M * sizeof(int) + N * sizeof(vector) + sizeof(vector>) bytes, ou seja, 4*4*4 + 4*16 + 16 = 144 bytes no total, intead de 64 bytes para 4 x 4 int.

Além disso, dependendo do alocador usado, cada alocação única pode bem (e muito provavelmente terá) mais 16 bytes de sobrecarga de memory. (Algumas “Infobytes”, que armazenam o número de bytes alocados para propósitos de desalocação apropriada).

Isso significa que o pior caso é:

N*(16+M*sizeof(int)) + 16+N*sizeof(int*) + sizeof(int**)
= 4*(16+4*4) + 16+4*4 + 4 = 164 bytes ! _Overhead: 156%_

A parte da sobrecarga reduzirá conforme o tamanho da matriz cresce, mas ainda estará presente.

Risco de vazamentos de memory

O grupo de alocações exige um tratamento de exceção apropriado para evitar vazamentos de memory se uma das alocações falhará! Você precisará manter o controle dos blocos de memory alocados e não deve esquecê-los ao desalocar a memory.

Se new execuções de memory e a próxima linha não puderem ser alocadas (especialmente provável quando a matriz é muito grande), um std::bad_alloc é lançado por new .

Exemplo:

No exemplo new / delete mencionado acima, enfrentaremos mais algum código se quisermos evitar vazamentos no caso de exceções bad_alloc .

  // allocate memory for 4x4 integers; quick & dirty size_t const N = 4; // we don't need try for this allocation // if it fails there is no leak int ** p = new int*[N]; size_t allocs(0U); try { // try block doing further allocations for (size_t i=0; i 

Resumo

Há casos em que os layouts de memory "2d reais" se ajustam e fazem sentido (ou seja, se o número de colunas por linha não é constante), mas nos casos mais simples e comuns de armazenamento de dados 2D eles apenas aumentam a complexidade do código e reduzem o desempenho e eficiência de memory do seu programa.

Alternativa

Você deve usar um bloco contíguo de memory e mapear suas linhas para aquele bloco.

O "modo C ++" de fazê-lo é provavelmente escrever uma class que gere sua memory enquanto considera coisas importantes como

  • Qual é a regra dos três?
  • O que se entende por Aquisição de Recurso é Inicialização (RAII)?
  • Conceito de C ++: Container (em cppreference.com)

Exemplo

Para fornecer uma ideia de como essa class pode parecer, aqui está um exemplo simples com alguns resources básicos:

  • 2d-size-constructible
  • 2d-redimensionável
  • operator(size_t, size_t) para access ao elemento principal de 2d-linhas
  • at(size_t, size_t) para access ao elemento principal marcado em 2d-linhas
  • Atende aos requisitos do conceito de contêiner

Fonte:

 #include  #include  #include  #include  namespace matrices { template class simple { public: // misc types using data_type = std::vector; using value_type = typename std::vector::value_type; using size_type = typename std::vector::size_type; // ref using reference = typename std::vector::reference; using const_reference = typename std::vector::const_reference; // iter using iterator = typename std::vector::iterator; using const_iterator = typename std::vector::const_iterator; // reverse iter using reverse_iterator = typename std::vector::reverse_iterator; using const_reverse_iterator = typename std::vector::const_reverse_iterator; // empty construction simple() = default; // default-insert rows*cols values simple(size_type rows, size_type cols) : m_rows(rows), m_cols(cols), m_data(rows*cols) {} // copy initialized matrix rows*cols simple(size_type rows, size_type cols, const_reference val) : m_rows(rows), m_cols(cols), m_data(rows*cols, val) {} // 1d-iterators iterator begin() { return m_data.begin(); } iterator end() { return m_data.end(); } const_iterator begin() const { return m_data.begin(); } const_iterator end() const { return m_data.end(); } const_iterator cbegin() const { return m_data.cbegin(); } const_iterator cend() const { return m_data.cend(); } reverse_iterator rbegin() { return m_data.rbegin(); } reverse_iterator rend() { return m_data.rend(); } const_reverse_iterator rbegin() const { return m_data.rbegin(); } const_reverse_iterator rend() const { return m_data.rend(); } const_reverse_iterator crbegin() const { return m_data.crbegin(); } const_reverse_iterator crend() const { return m_data.crend(); } // element access (row major indexation) reference operator() (size_type const row, size_type const column) { return m_data[m_cols*row + column]; } const_reference operator() (size_type const row, size_type const column) const { return m_data[m_cols*row + column]; } reference at() (size_type const row, size_type const column) { return m_data.at(m_cols*row + column); } const_reference at() (size_type const row, size_type const column) const { return m_data.at(m_cols*row + column); } // resizing void resize(size_type new_rows, size_type new_cols) { // new matrix new_rows times new_cols simple tmp(new_rows, new_cols); // select smaller row and col size auto mc = std::min(m_cols, new_cols); auto mr = std::min(m_rows, new_rows); for (size_type i(0U); i < mr; ++i) { // iterators to begin of rows auto row = begin() + i*m_cols; auto tmp_row = tmp.begin() + i*new_cols; // move mc elements to tmp std::move(row, row + mc, tmp_row); } // move assignment to this *this = std::move(tmp); } // size and capacity size_type size() const { return m_data.size(); } size_type max_size() const { return m_data.max_size(); } bool empty() const { return m_data.empty(); } // dimensionality size_type rows() const { return m_rows; } size_type cols() const { return m_cols; } // data swapping void swap(simple &rhs) { using std::swap; m_data.swap(rhs.m_data); swap(m_rows, rhs.m_rows); swap(m_cols, rhs.m_cols); } private: // content size_type m_rows{ 0u }; size_type m_cols{ 0u }; data_type m_data{}; }; template void swap(simple & lhs, simple & rhs) { lhs.swap(rhs); } template bool operator== (simple const &a, simple const &b) { if (a.rows() != b.rows() || a.cols() != b.cols()) { return false; } return std::equal(a.begin(), a.end(), b.begin(), b.end()); } template bool operator!= (simple const &a, simple const &b) { return !(a == b); } } 

Observe várias coisas aqui:

  • T precisa preencher os requisitos das funções de membro std::vector usadas
  • operator() não faz nenhuma verificação "de intervalo"
  • Não há necessidade de gerenciar dados por conta própria
  • Nenhum destrutor, construtor de cópia ou operadores de atribuição necessários

Portanto, você não precisa se preocupar com o manuseio adequado de memory para cada aplicativo, mas apenas uma vez para a class que você escreve.

Restrições

Pode haver casos em que uma estrutura bidimensional dinâmica "real" seja favorável. Este é, por exemplo, o caso se

  • a matriz é muito grande e esparsa (se alguma das linhas não precisar ser alocada mas pode ser manipulada usando um nullptr) ou se
  • as linhas não têm o mesmo número de colunas (isto é, se você não tiver uma matriz, exceto uma outra construção bidimensional).

A menos que você esteja falando sobre arrays estáticos, 1D é mais rápido .

Aqui está o layout da memory de uma matriz 1D ( std::vector ):

 +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+ 

E aqui está o mesmo para uma matriz 2D dinâmica ( std::vector> ):

 +---+---+---+ | * | * | * | +-|-+-|-+-|-+ | | V | | +---+---+---+ | | | | | | | | +---+---+---+ | V | +---+---+---+ | | | | | | +---+---+---+ V +---+---+---+ | | | | +---+---+---+ 

Claramente, o caso 2D perde a localidade do cache e usa mais memory. Ele também introduz uma indireção extra (e, portanto, um ponteiro extra a seguir), mas o primeiro array tem a sobrecarga de calcular os índices, de modo que eles ficam mais ou menos iguais.

Matrizes Estáticas 1D e 2D

  • Tamanho: ambos exigem a mesma quantidade de memory.

  • Velocidade: Você pode supor que não haverá diferença de velocidade porque a memory para esses dois arrays deve ser contígua (todo o array 2D deve aparecer como um pedaço na memory, em vez de um monte de pedaços espalhados pela memory). (Isso pode ser dependente do compilador no entanto.)

Matrizes dinâmicas 1D e 2D

  • Tamanho: O array 2D exigirá um pouco mais de memory que o array 1D, porque os pointers necessários no array 2D apontam para o conjunto de matrizes 1D alocadas. (Esse pouquinho é minúsculo quando estamos falando de matrizes realmente grandes. Para pequenos arrays, o pouquinho pode ser bem grande em termos relativos).

  • Velocidade: A matriz 1D pode ser mais rápida que a matriz 2D porque a memory para a matriz 2D não seria contígua, portanto, as falhas de cache se tornariam um problema.


Use o que funciona e parece mais lógico, e se você enfrentar problemas de velocidade, refatore.

Outra diferença de matrizes 1D e 2D aparece na alocação de memory. Não podemos ter certeza de que os membros do array 2D sejam seqüenciais.

Todas as respostas existentes apenas comparam matrizes 1-D contra matrizes de pointers.

Em C (mas não em C ++) existe uma terceira opção; você pode ter uma matriz 2-D contígua que seja alocada dinamicamente e tenha dimensões de tempo de execução:

 int (*p)[num_columns] = malloc(num_rows * sizeof *p); 

e isso é acessado como p[row_index][col_index] .

Eu esperaria que isso tivesse um desempenho muito semelhante ao caso da matriz 1-D, mas isso lhe dá uma syntax mais agradável para acessar as células.

Em C ++, você pode conseguir algo semelhante definindo uma class que mantém um array 1-D internamente, mas pode expô-lo via syntax de access de matriz 2-D usando operadores sobrecarregados. Novamente, eu esperaria que tivesse desempenho similar ou idêntico ao array 1-D simples.

Isso realmente depende de como seu array 2D é implementado.

 int a[200], b[10][20], *c[10], *d[10]; for (ii = 0; ii < 10; ++ii) { c[ii] = &b[ii][0]; d[ii] = (int*) malloc(20 * sizeof(int)); // The cast for C++ only. } 

Existem 3 implementações aqui: b, c e d Não haverá muita diferença acessando b [x] [y] ou a [x * 20 + y] desde que você está fazendo o cálculo e o outro é o compilador fazendo isso por você. c [x] [y] e d [x] [y] são mais lentos porque a máquina precisa encontrar o endereço para o qual c [x] aponta e depois acessar o yth de lá. Não é uma computação direta. Em algumas máquinas (por exemplo, o AS400 que possui pointers de 36 bytes (não bits)), o access do ponteiro é extremamente lento. Tudo depende da arquitetura em uso. Em arquiteturas de tipo x86, aeb são a mesma velocidade, c e d são mais lentas que b.

Eu amo a resposta completa fornecida pelo Pixelchemist . Uma versão mais simples dessa solução pode ser a seguinte. Primeiro, declare as dimensões:

 constexpr int M = 16; // rows constexpr int N = 16; // columns constexpr int P = 16; // planes 

Em seguida, crie um alias e obtenha e defina os methods:

 template using Vector = std::vector; template inline T& set_elem(vector& m_, size_t i_, size_t j_, size_t k_) { // check indexes here... return m_[i_*N*P + j_*P + k_]; } template inline const T& get_elem(const vector& m_, size_t i_, size_t j_, size_t k_) { // check indexes here... return m_[i_*N*P + j_*P + k_]; } 

Finalmente, um vetor pode ser criado e indexado da seguinte maneira:

 Vector array3d(M*N*P, 0); // create 3-d array containing M*N*P zero ints set_elem(array3d, 0, 0, 1) = 5; // array3d[0][0][1] = 5 auto n = get_elem(array3d, 0, 0, 1); // n = 5 

Definir o tamanho do vetor na boot fornece um ótimo desempenho . Esta solução é modificada a partir desta resposta . As funções podem ser sobrecarregadas para suportar dimensões variables ​​com um único vetor. A desvantagem dessa solução é que os parâmetros M, N, P são passados ​​implicitamente para as funções get e set. Isso pode ser resolvido implementando a solução em uma class, como feito pelo Pixelchemist .