1D 또는 2D 어레이, 무엇이 더 빠릅니까?

1D 또는 2D 어레이, 무엇이 더 빠릅니까?

---

2D 필드 (x, y 축)를 표시해야합니다. 1D 배열을 배열에, 2D 배열을 배열에 있습니까?

1D 배열 (y + x * n)에 대한 설계를 다시 계산하는 것이 2D 배열 (x, y)을 사용하는 것보다 느릴 수 있습니다 1D가 CPU 캐시에있을 수 있다고 상상할 수 있습니다.

인터넷 검색을 수행했지만 정적 배열에 관한 페이지 만 찾았습니다 (1D와 2D가 기본적으로 동일 명시). 하지만 내 배열은 동적이어야합니다.

그래서 무슨 일이야

1. 더 빨리
2. 더 작음 (RAM)

동적 1D 배열 또는 동적 2D 배열?

감사 :)

---

tl; dr : 아마도 1 차원 접근 방식을 사용합니다.

참고 : 코드의 성능이 매우 많은 변수에 존재하므로 책을 채우지 않고 동적 1d 또는 동적 2d 스토리지 패턴을 사용할 때 성능에 영향을 미치는 세부 사항을 파헤칠 수 없습니다. 가능한 경우 프로필을 작성하십시오.

1. 무엇이 더 빠릅니까?

밀도가 높은 수준의 경우 1D 접근 방식은 더 나은 메모리 지역성을 제공하고 할당 및 할당 해제 오버 헤드가 적기 때문에 더 빠를 수 있습니다.

2. 무엇이 더 작다면 무엇입니까?

Dynamic-1D는 2D 접근 방식보다 약간 메모리를 사용합니다. 후자는 또한 더 많은 할당이 필요합니다.

비고

몇 가지 이유와 함께 아래에 꽤 긴 답변을 제시했지만 귀하의 가정에 대해 몇 가지 언급하고 싶습니다.

1D 배열 (y + x * n)에 대한 고급 재 계산이 2D 배열 (x, y)을 사용하는 것보다 느릴 수 있습니다 상상할 수 있습니다.

이 두 기능을 비교해 보겠습니다.

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

Visual Studio 2015 RC에서 해당 함수 (최적화가 켜진 상태)에 대해 생성 된 (인라인되지 않음) 어셈블리는 다음과 적합하지 않습니다.

?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

차이점은 mov(2d) 대 lea(1d)입니다. 전자의 지연 시간은 3 사이클이고 최대 처리량은 사이클 당 2이고 후자는 지연 시간이 2 사이클이고 최대 처리량은 사이클 당 3입니다. ( 표 에 따르면 -Agner Fog 차이 가 미미하기 때문에 계획 재 계산으로 성능 차이가 크지 않을 현상이 발생한다고 생각합니다.이 차이 자체가 어떤 프로그램에서 병목이 거의 없을 것으로 예상됩니다.

이것은 우리를 다음 (그리고 더 흥미로운) 요점으로 인도합니다.

...하지만 1D가 CPU 캐시에 존재하는 상상할 수 있습니다.

사실이지만 2d도 CPU 캐시에있을 수 있습니다. 1d가 여전히 더 나은 이유에 대한 설명 은 단점 : 메모리 지역성 을 참조하십시오 .

긴 대답 또는 동적 2 차원 데이터 저장 (포인터 대 포인터 또는 벡터 벡터)이 단순 / 행렬에 작은 대해 "나쁜"이유 입니다.

참고 : 이것은 동적 배열 / 할당 체계 [malloc / new / vector etc.]에 관한 것입니다. 정적 2D 배열은 연속적인 메모리 블록 여기에 설명 할 문제점이 없습니다.

문제

동적 배열의 동적 배열 또는 벡터의 벡터가 선택한 데이터 저장 패턴이 아닌 이유를 이해해야 할 다음 구조의 메모리 레이아웃을 이해해야합니다.

포인터 구문에 대한 포인터를 사용하는 예제 사례

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

단점

메모리 지역성

이 "행렬"은 4 개의 포인터로 구성된 1 개의 블록과 4 개의 정수로 구성된 4 개의 블록을 할당합니다. 모든 할당은 관련 이 임의의 메모리 위치가 될 수 있습니다.

다음 이미지는 메모리가 어떻게 생겼는지에 대한 아이디어를 제공합니다.

를 들어 실제 2D의 경우 :

• 보라색 사각형은 p자체적으로 차지하는 메모리 위치 입니다.
• 녹색 사각형은 p(4 개 int*)를 가리키는 메모리-domain을 조합합니다 .
• 4 개의 연속 된 파란색 사각형의 4-domain은 각 개 int*녹색-domain이 가리키는 -domain입니다.

를 들어 2D 1D 경우에 매핑 :

• 녹색 사각형은 유일한 필수 포인터입니다. int *
• 파란색 사각형은 모든 행렬 요소 (16 x int)에 대한 메모리 영역을 통합합니다 .

즉, (왼쪽 레이아웃을 사용할 때) 캐싱 등으로 연속적인 스토리지 패턴 (오른쪽에 표시됨)보다 성능이 수 있습니다.

캐시 라인이 "한 번에 캐시로 전송되는 데이터의 양"이라고 가정하고 전체에 차례로 액세스하는 프로그램을 상상해 보겠습니다.

32 비트 값으로 구성된 경우 4x4 대규모 캐시 라인 (일반 값)이있는 프로세서는 데이터 (4 * 4 * 4 = 64 바이트)를 "원샷"할 수 있습니다. 처리를 시작하고 데이터가 아직 캐시에 캐시 미스에 직면하고 데이터가 주 메모리에서 가져옵니다. 이로 드는 연속적으로 저장되고 고유하게 정렬 된 경우에만 캐시 라인에 맞기 때문에 전체 매트릭스를 한 번에 수 있습니다. 해당 데이터를 처리하는 동안 더 이상 누락이 발생하지 않을 것입니다.

각 행 / 열의 관련없는 위치가있는 동적 "실제 2 차원"시스템의 경우 프로세서는 모든 위치를 식별 적으로로드해야합니다. 64 바이트 만 필요하지만 관련없는 4 개의 메모리 위치에 4 ​​개의 캐시 라인을로드하면 최악의 경우 256 바이트 만 전송하고 75 %의 처리량을 처리 할 수 ​​있습니다. 2d 스키마를 사용하여 데이터를 처리하면 (아직 캐시되지 않은 경우) 다시 첫 번째 요소에서 캐시 미스에 직면하게됩니다. 그러나 이제는 다른 위치에있는 모든 행이 메모리의 다른 위치에있는 첫 번째 행과 첫 번째로드되지 않기 때문에 주 메모리에서 첫 번째는 나중에 첫 번째 행 / 열만 캐시에 있습니다. 새 행 / 열에 도달하자마자 다시 캐시 미스가 발생하고 주 메모리에서 다음로드가 수행됩니다.

간단히 말해서, 2d 패턴은 데이터의 지역성으로 인해 성능에 대해 더 나은 잠재력을 제공하는 1d 체계를 사용하여 캐시 가능성이 더 많이 있습니다.

빈번한 할당 / 할당 해제

• N + 1원하는 NxM (4x4)을 사용하여 생성 (new, malloc, allocator :: allocate 등을 사용하여) 최대 (4 + 1 = 5) 할당이 필요합니다.
• 동일한 수의 적절한 할당 해제 작업도 적용해야합니다.

따라서 단일 할당 체계와 달리 대량을 생성 / 복사하는 데 더 많은 비용이 발생합니다.

행 수가 증가함에 따라 더욱 악화되고 있습니다.

메모리 소비 오버 헤드

int의 경우 32 비트, 포인터의 경우 32 비트 크기로 가정하겠습니다. (참고 : 시스템 설명.)

기억하자 : 64 바이트를 의미하는 4x4 int를 저장합니다.

제시된 포인터 대 포인터 체계로 저장된 NxM 행렬의 경우

• N*M*sizeof(int) [실제 블루 데이터] +
• N*sizeof(int*) [녹색 포인터] +
• sizeof(int**) [보라색 변수 p] 바이트.

이것은 4*4*4 + 4*4 + 4 = 84현재 예제의 경우 바이트를 만들고 std::vector<std::vector<int>>. 그것은 필요 N * M * sizeof(int)+ N * sizeof(vector<int>)+ sizeof(vector<vector<int>>)즉, 바이트 4*4*4 + 4*16 + 16 = 144intead 4 × 4 INT 64 바이트의 총 바이트입니다.

또한-사용 된 할당 자에 따라-각 단일 할당은 16 바이트의 메모리 오버 헤드를 추가로 사용할 수 있습니다. (적절한 할당 해제를 위해 할당 된 바이트 수를 저장하는 일부 "Infobytes")

즉, 최악의 경우는 다음과 가변적입니다.

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

오버 헤드의 점유율은 매트릭스의 크기가 커짐에 따라 지 만 여전히 존재합니다.

메모리 누수 위험

중 하나가 실패 할 경우 메모리 누수를 방지하기 위해 할당됩니다. 할당 된 메모리 블록을 추적해야하며 메모리 할당을 해제 할 때 잊지 말아야합니다.

경우 new메모리와 다음 행의의 실행이 (특히 가능성이 매트릭스가 매우 큰 경우) 할당 할 수를 없습니다 하는가 std::bad_alloc에 의해 발생합니다 new.

예 :

언급 된 한 새 / 삭제 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<N; ++i) 
    {
      p[i] = new int[4]; // allocate
      ++allocs; // advance counter if no exception occured
    }
  }
  catch (std::bad_alloc & be)
  { // if an exception occurs we need to free out memory
    for (size_t i=0; i<allocs; ++i) delete[] p[i]; // free all alloced p[i]s
    delete[] p; // free p
    throw; // rethrow bad_alloc
  }
  /*
     do some stuff here, using p[x][y] 
  */
  // deallocate memory accoding to the number of allocations
  for (size_t i=0; i<allocs; ++i) delete[] p[i];
  delete[] p;

요약

"실제 2d"메모리 레이아웃이 적합하고 의미가있는 경우 (즉, 행당 열 수가 일정하지 않은 경우)가 가장 간단하고 일반적인 2D 데이터 저장의 경우 코드의 경우 부풀려 성능을 사용합니다. 프로그램의 메모리 효율성.

대안

연속적인 메모리 블록을 사용하고 해당 블록에 행을 매핑해야합니다.

수행하는 "C ++ 방식"은 다음과 같은 중요한 사항을이를 고려하면서 메모리를 관리하는 클래스를 작성하는 것입니다.

• 3의 법칙은 무엇입니까?
• 자원 획득은 초기화 (RAII)이란 무엇입니까?
• C ++ 개념 : 컨테이너 (cppreference.com)

예

몇 가지 기본 기능이 포함 된 간단한 예제가 있습니다.

• 2D 크기 구성 가능
• 2D 크기 조정 가능
• operator(size_t, size_t) 2D 행 주요 요소 액세스 용
• at(size_t, size_t) 확인 된 2d 행 주요 요소 액세스
• 컨테이너에 대한 개념 요구 사항

출처 :

#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>

namespace matrices
{

  template<class T>
  class simple
  {
  public:
    // misc types
    using data_type  = std::vector<T>;
    using value_type = typename std::vector<T>::value_type;
    using size_type  = typename std::vector<T>::size_type;
    // ref
    using reference       = typename std::vector<T>::reference;
    using const_reference = typename std::vector<T>::const_reference;
    // iter
    using iterator       = typename std::vector<T>::iterator;
    using const_iterator = typename std::vector<T>::const_iterator;
    // reverse iter
    using reverse_iterator       = typename std::vector<T>::reverse_iterator;
    using const_reverse_iterator = typename std::vector<T>::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<class T>
  void swap(simple<T> & lhs, simple<T> & rhs)
  {
    lhs.swap(rhs);
  }
  template<class T>
  bool operator== (simple<T> const &a, simple<T> 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<class T>
  bool operator!= (simple<T> const &a, simple<T> const &b)
  {
    return !(a == b);
  }

}

여기에서 몇 가지 사항에 유의하십시오.

• T사용 된 std::vector멤버 함수 의 요구 사항을해야 합니다.
• operator() "범위의"검사를 수행하지 않습니다.
• 데이터를 직접 관리 할 필요가 없습니다.
• 소멸자, 복사 생성자 또는 할당 연산자가 필요하지 않습니다.

따라서 각 응용 프로그램에 대해 적절한 메모리 처리에 신경 쓰지 및 작성하는 클래스에 대해 설명합니다.

제한

동적 "실제"2 차원 구조가 유리한 경우가 있습니다. 예를 들어 다음과 같은 경우입니다.

• (할당 할 수없는 경우에는 Null을 사용하여 처리 할 수 ​​없습니다).
• 행에 동일한 수의 열이 없습니다 (즉, 행렬이 전혀없고 다른 2 차원 구조가있는 경우).

---

정적 배열에 대해 이야기 하지 않는 한 1D가 더 빠릅니다 .

다음은 1D 배열 ( std::vector<T>) 의 메모리 레이아웃입니다 .

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

다음은 동적 2D 배열 ( std::vector<std::vector<T>>)에 대해서도 동일합니다 .

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

분명히 2D 케이스는 캐시 지역성을 잃고 더 많은 메모리를 사용합니다. 또한 추가 간접 지정 (따라서 추가 포인터가 따를 수 있음)을 도입하지만 첫 번째 배열에는 인덱스를 계산하는 오버 헤드가 있으므로 이러한 항목이 다소 균일 해집니다.

---

1D 및 2D 정적 배열

• 크기 : 둘 다 동일한 양의 메모리가 필요합니다.

• 속도 : 두 배열 모두에 대한 메모리가 연속적이어야하므로 속도 차이가 없다고 가정 할 수 있습니다 (전체 2D 배열은 메모리에 분산 된 덩어리가 아닌 하나의 덩어리로 표시되어야합니다). (그러나 이것은 컴파일러에 따라 다를 수 있습니다.)

1D 및 2D 동적 배열

• 크기 : 2D 배열은 할당 된 1D 배열 집합을 가리 키기 위해 2D 배열에 필요한 포인터로 인해 1D 배열보다 약간 더 많은 메모리가 필요합니다. (이 작은 비트는 우리가 정말로 큰 배열에 대해 이야기 할 때 아주 작습니다. 작은 배열의 경우 작은 비트는 상대적으로 상당히 클 수 있습니다.)

• 속도 : 2D 어레이의 메모리가 연속적이지 않기 때문에 1D 어레이가 2D 어레이보다 빠를 수 있으므로 캐시 미스가 문제가됩니다.

---

작동하고 가장 논리적으로 보이는 것을 사용하고 속도 문제에 직면하면 리팩터링하십시오.

---

기존 답변은 모두 1D 배열과 포인터 배열을 비교합니다.

C (C ++ 아님)에는 세 번째 옵션이 있습니다. 동적으로 할당되고 런타임 차원이있는 연속적인 2D 배열을 가질 수 있습니다.

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

그리고 이것은 p[row_index][col_index].

나는 이것이 1D 배열의 경우와 매우 유사한 성능을 가질 것으로 기대하지만 셀에 액세스하는 데 더 좋은 구문을 제공합니다.

C ++에서는 내부적으로 1D 배열을 유지하는 클래스를 정의하여 비슷한 것을 얻을 수 있지만 오버로드 된 연산자를 사용하여 2D 배열 액세스 구문을 통해 노출 할 수 있습니다. 다시 한 번 일반 1D 어레이와 비슷하거나 동일한 성능을 기대합니다.

---

1D 및 2D 배열의 또 다른 차이점은 메모리 할당에 나타납니다. 2D 배열의 구성원이 순차적인지 확신 할 수 없습니다.

---

2D 배열이 어떻게 구현되는지에 따라 다릅니다.

아래 코드를 고려하십시오.

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

여기에는 b, c 및 d의 세 가지 구현이 있습니다.

하나는 계산을 수행하고 다른 하나는 컴파일러가 대신 수행하기 때문에 b[x][y]또는 액세스하는 데 많은 차이가 없습니다 a[x*20 + y]. c[x][y]그리고 d[x][y]기계가하는 주소를 찾을 수 있기 때문에, 느린 c[x]다음에 점은 거기에서 y 번째 요소에 액세스 할 수 있습니다. 하나의 직접적인 계산이 아닙니다. 일부 기계 (예 : 36 바이트 (비트 아님) 포인터가있는 AS400)에서는 포인터 액세스가 매우 느립니다. 그것은 모두 사용중인 아키텍처에 달려 있습니다. x86 유형 아키텍처에서 a와 b는 속도가 같고 c와 d는 b보다 느립니다.

---

Pixelchemist가 제공하는 철저한 답변이 마음에 듭니다 . 이 솔루션의 더 간단한 버전은 다음과 같습니다. 먼저 치수를 선언합니다.

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

다음으로 별칭을 만들고 메서드를 가져오고 설정합니다.

template<typename T>
using Vector = std::vector<T>;

template<typename T>
inline T& set_elem(vector<T>& m_, size_t i_, size_t j_, size_t k_)
{
    // check indexes here...
    return m_[i_*N*P + j_*P + k_];
}

template<typename T>
inline const T& get_elem(const vector<T>& m_, size_t i_, size_t j_, size_t k_)
{
    // check indexes here...
    return m_[i_*N*P + j_*P + k_];
}

마지막으로 벡터를 생성하고 다음과 같이 인덱싱 할 수 있습니다.

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

초기화시 벡터 크기를 정의하면 최적의 성능을 얻을 수 있습니다. 이 솔루션은 이 답변 에서 수정되었습니다 . 단일 벡터로 다양한 차원을 지원하도록 함수를 오버로드 할 수 있습니다. 이 솔루션의 단점은 M, N, P 매개 변수가 암시 적으로 get 및 set 함수에 전달된다는 것입니다. 이 문제는 Pixelchemist가 수행 한대로 클래스 내에서 솔루션을 구현하여 해결할 수 있습니다 .

참고 URL : https://stackoverflow.com/questions/17259877/1d-or-2d-array-whats-faster