1D 또는 2D 어레이, 어떤 것이 더 빠른가?

1D 또는 2D 어레이, 어떤 것이 더 빠른가?

2D 필드(ax 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 사이클이고 최대 처리량이 3 사이클이다.(지시표에 따르면 - Agner Foggregate 차이가 경미하기 때문에, 지수 재계산으로부터 발생하는 큰 성과 차이가 있어서는 안 된다고 생각한다.나는 이 차이점 그 자체가 어떤 프로그램에서 병목현상이 될지는 거의 알 수 없을 것으로 기대한다.

이것은 우리에게 다음(그리고 더 흥미로운) 요점을 제시한다.

... 하지만 CPU 캐시에 1D가 있을 수 있다는 것을 상상할 수 있었다...

맞아, 하지만 2d도 CPU 캐시에 있을 수 있어.단점 참조: 왜 1d가 더 나은지 설명하기 위한 기억의 지역성.

긴 답 또는 왜 동적 2차원 데이터 스토리지(점간-점간 또는 벡터-벡터)가 단순/소규모 매트릭스에 대해 "나쁜"지 여부.

참고: 이것은 동적 배열/할당 체계[malloc/new/vector 등]에 관한 것이다.정적 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 x 점: (4 x)int*).
• 4개의 연속적인 청색 사각형의 4개 영역은 각각이 가리키는 영역이다.int*

1d 케이스에 매핑된 2d의 경우:

• 녹색 사각형만이 필요한 포인터int *
• 파란색 사각형 앙상블은 모든 매트릭스 요소에 대한 메모리 영역(16 x)int).

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

캐시 라인이 "한 번에 캐시로 전송되는 데이터의 양"이라고 가정하고, 프로그램이 전체 매트릭스에 차례로 액세스하는 것을 상상해 보자.

만약 당신이 적절하게 정렬된 4 곱하기 4 매트릭스 32비트 값을 가지고 있다면, 64바이트 캐시 라인(일반적인 값)을 가진 프로세서가 데이터(4*4*4 = 64바이트)를 "원샷"할 수 있다.처리를 시작했는데 아직 캐시에 데이터가 없으면 캐시 누락이 발생하고 메인 메모리에서 데이터를 가져오게 된다.이 로드는 연속적으로 저장되고 적절하게 정렬된 경우에만 캐쉬 라인에 맞기 때문에 전체 매트릭스를 한 번에 가져올 수 있다.그 데이터를 처리하는 동안 더 이상의 실수는 없을 것이다.

각 행/열의 관련 없는 위치가 있는 동적 "실제 2차원" 시스템의 경우 프로세서는 모든 메모리 위치를 별도로 로드해야 한다.64바이트만 필요한 경우, 4개의 관련 없는 메모리 위치에 캐시 라인을 4개 로드하면 최악의 경우 256바이트가 전송되고 75%의 처리량 대역폭이 낭비될 수 있다.2d-scheme을 사용하여 데이터를 처리하면(이미 캐시되지 않은 경우) 첫 번째 요소에서 캐시 누락이 발생할 수 있다.그러나 이제 다른 모든 행은 메모리의 다른 어딘가에 위치하며 첫 번째 행과 인접하지 않기 때문에 첫 번째 행/컬럼만 메인 메모리에서 첫 번째 로딩 후 캐시에 저장될 것이다.새로운 행/열에 도달하는 즉시 다시 캐시 누락이 발생하고 메인 메모리에서 다음 로드가 수행된다.

요약하자면:2d 패턴은 데이터의 인접성으로 인해 더 나은 성능 잠재력을 제공하는 1d 체계로 캐시 누락 가능성이 더 높다.

빈번한 할당/할당 취소

• 만큼이나N + 1원하는 NxM(4×4) 매트릭스를 생성하려면 (4 + 1 = 5) 할당(new, malloc, allocator::allocate 또는 allocate 사용)이 필요하다.
• 또한 동일한 수의 적절한 각각의 할당 해제 작업을 적용해야 한다.

따라서 단일 할당 체계와 대조적으로 그러한 행렬을 작성/복사하는 것이 더 비용이 많이 든다.

이는 행이 늘어나면서 더욱 심해지고 있다.

메모리 소비 오버헤드

int의 경우 32비트, 포인터의 경우 32비트 크기를 지정하십시오. (참고:시스템 종속성).

기억하자:우리는 64바이트를 의미하는 4×4 매트릭스를 저장하기를 원한다.

NxM 매트릭스의 경우, 우리가 소비하는 Pointer-to-pointer 체계와 함께 저장된다.

• 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 = 144총 바이트 수, 4 x 4 인트에 대한 64 바이트 정수.

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

이는 최악의 경우는 다음과 같다는 것을 의미한다.

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.

예:

위에 언급된 new/delete 예에서, 우리는 만약의 경우에 누출을 피하고 싶다면, 몇 가지 코드를 더 직면하게 될 것이다.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 사이즈로 제작할 수 있는
• 2차원 크기
• operator(size_t, size_t)주 열?열?스?스?스?스?스?스스?주주?주주?주주?주주?주주?주주
• at(size_t, size_t) 행을 선택하십시오.
• 컨테이너에 대한 개념 요구사항 충족

출처:

#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차원 구조가 유리한 경우가 있을 수 있다.예를 들면 다음과 같다.

• 매트릭스는 매우 크고 희박하다(할당할 필요도 없지만 nullptr을 사용하여 처리할 수 있는 행이 있는 경우) 또는
• 행의 열 수가 같지 않음(즉, 다른 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 어레이보다 빠를 수 있다.

---

가장 논리적으로 보이는 것을 사용하고 속도 문제에 직면하면 리팩터링한다.

기존의 답은 모두 1-D 배열과 포인터의 배열만 비교한다.

C(C++는 아님)에는 세 번째 옵션이 있다. 동적으로 할당되고 런타임 치수가 있는 연속 2-D 어레이를 사용할 수 있다.

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

그리고 이것은 다음과 같이 접속된다.p[row_index][col_index].

나는 이것이 1-D 어레이 케이스와 매우 유사한 성능을 가질 것으로 예상하지만, 그것은 셀에 접근하기 위한 더 좋은 구문을 제공한다.

C++에서는 내부적으로 1-D 어레이를 유지하지만 과부하 연산자를 사용하여 2-D 어레이 액세스 구문을 통해 이를 노출할 수 있는 클래스를 정의함으로써 유사한 것을 달성할 수 있다.다시 한번 나는 그것이 일반 1-D 어레이와 비슷하거나 동일한 성능을 갖기를 기대한다.

메모리 할당에는 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의 3가지 구현이 있다.

접근하는 것에는 큰 차이가 없을 것이다.b[x][y]또는a[x*20 + y]하나는 당신이 계산을 하는 것이고 다른 하나는 컴파일러가 당신을 위해 계산하는 것이기 때문이다.c[x][y]그리고d[x][y] 왜냐하면 그 그 때문이다. 왜냐하면 기계는 다음 주소를 찾아야 하기 때문이다.c[x]여기서 y번째 요소를 가리킨 다음 그 요소에 접근한다.그것은 하나의 직선적인 계산이 아니다.일부 컴퓨터(예: 36바이트(비트가 아님) 포인터가 있는 AS400)에서는 포인터 액세스가 매우 느리다.그것은 모두 사용 중인 아키텍처에 달려 있다.x86형에 .

나는 픽셀케미스트가 제공하는 철저한 답변을 좋아한다.이 해결책의 더 간단한 버전은 다음과 같을 수 있다.먼저 치수를 선언하십시오.

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 매개변수가 겟 및 세트 기능에 암묵적으로 전달된다는 것이다.이는 픽셀케미스트가 한 클래스 내에서 솔루션을 구현함으로써 해결할 수 있다.

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