Выделение / доступ к 2d массиву таким образом, чтобы 2d подблоки были смежными - PullRequest
Новая
       61

Выделение / доступ к 2d массиву таким образом, чтобы 2d подблоки были смежными

3 голосов
/ 05 ноября 2019

У меня есть 2d массив SomeData* data[4096][4096]. Здесь данные соприкасаются вдоль последней координаты, так что итерация по координате y происходит быстрее, чем итерация по координате x из-за локальности памяти. Тем не менее, шаблон доступа, который у меня есть, заключается в том, что я смотрю на запись, а затем смотрю на соседних соседей в обеих координатах, то есть data [x] [y] вместе с data [x-1] [y-1], data [x+1] [y + 1] и т. Д.

Если бы я мог выделить этот массив так, чтобы небольшие 2-мерные субблоки были смежными в памяти, это ускорило бы процесс.

Я говорю, выделяю, но я подозреваю, что решение здесь состоит в том, чтобы выделить 2d массив в обычном режиме, а затем выполнить некоторую хитрость с индексацией, чтобы я получил доступ к 2d блокам непрерывно. Другими словами, я хочу некоторую функцию поиска, которая переводит координаты, но я не могу сразу увидеть, что это должно быть. 

SomeData* data[4096][4096];

SomeData* lookup(size_t x, size_t y) {
    //??? Some logic to translate x,y such that 2d blocks are accessed contiguously.
}

Массив данных гарантированно будет иметь оба измерения степенью двойки.

1 Ответ

1 голос
/ 05 ноября 2019

Допустим, у нас есть сетка nxm. Мы хотим разделить сетку на bxb-блоки. Необходимо, чтобы n% b = 0 и m% b = 0.

. Назовем общие индексы I = 0, ..., n-1 и J = 0, ..., m-1. и индексы в блоке i = 0, ..., b-1 и j = 0, ..., b-1.

Я попытался набросать макет здесь .

Учитывая I, индекс столбца блока равен (I / b), а индекс внутри блока i = I% b. Индекс строки блока равен (J / b), а индекс в блоке j = J% b.

Каждый полный блок содержит b * b элементов. Таким образом, полный ряд блоков содержит (n / b) b b = n * b элементов.

Объединение всех вместе линейного индекса элемента (I, J):

  • (I% b) [столбец в блоке, предшествующем элементу]
  • + (J% b) * b [строки в блоке, предшествующем элементу]
  • + (I / b) * b * b [столбец блоков, предшествующих блоку элемента]
  • + (J / b) * n * b [ряд блоков, предшествующих блоку элемента]

Грубый эскиз класса заблокированной сетки размера во время выполнения: 

template <typename T>
class Block_Grid
{
public:
  Block_Grid(std::size_t n, std::size_t m, std::size_t b)
  : _n(n), _m(m), _b(b), _elements(n * m)
  { 
    assert(n % b == 0);
    assert(m % b == 0);
  }

  T & operator()(std::size_t i, std::size_t j)
  {
    return _elements[index(i, j)];
  }

protected:
private:
  std::size_t index(int i, int j) const
  {
    return (i % b) 
           + (j % b) * b
           + (i / b) * b * b
           + (j / b) * n * b;
  }

  std::size_t _n;
  std::size_t _m;
  std::size_t _b;
  std::vector<T> _elements;
};

или класса размера компиляции 

template <typename T, std::size_t N, std::size_t M, std::size_t B>
class Block_Grid
{
  static_assert(N % B == 0);
  static_assert(M % B == 0);
public:
  Block_Grid() = default;

  T & operator()(std::size_t i, std::size_t j)
  {
    return _elements[index(i, j)];
  }

protected:
private:
  std::size_t index(std::size_t i, std::size_t j) const
  {
    return (i % B) + (j % B) * B + (i / B) * B * B + (j / B) * N * B;
  }

  std::array<T, N * M> _elements;
};
...