Векторное хранилище в С++

Я хочу сохранить большой вектор d-мерных точек (d фиксированный и малый: < 10).

Если я определяю Point как vector<int>, я думаю, что vector<Point> будет хранить в каждой позиции указатель на Точку.

Но если define a Point как объект фиксированного размера, например: std::tuple<int,int,...,int> или std::array<int, d>, будет ли программа сохранять все точки в непрерывной памяти или будет сохраняться дополнительный уровень косвенности?

Если ответ заключается в том, что массивы избегают дополнительной косвенности, может ли это сильно повлиять на производительность (локальность использования кэша) при сканировании vector<Point>?

Ответ 1

Если вы определяете свой Point как имеющий непрерывное хранение данных (например, struct Point { int a; int b; int c; } или используя std::array), то std::vector<Point> будет хранить Point в смежных ячейках памяти, поэтому ваш формат памяти будет:

p0.a, p0.b, p0.c, p1.a, p1.b, p1.c, ..., p(N-1).a, p(N-1).b, p(N-1).c

С другой стороны, если вы определяете Point как vector<int>, тогда vector<Point> имеет макет vector<vector<int>>, который не является смежным, так как vector хранит указатели на динамически выделенную память. Таким образом, у вас есть соприкосновение для одиночных Point s, но не для всей структуры.

Первое решение намного более эффективно, чем второе (поскольку современные процессоры любят доступ к смежным ячейкам памяти).

Ответ 2

vector будет хранить все содержимое вашего типа в непрерывной памяти. Так что да, если это array или tuple или, возможно, даже лучше, настраиваемый тип, это позволит избежать косвенности.

Эффективность, как всегда, вы должны ее измерить. Не спекулируйте. По крайней мере, что касается сканирования.

Однако при создании этих точек, безусловно, будет огромный прирост производительности, потому что вы избежите ненужных распределений памяти для каждого vector, который сохраняет точку. И распределение памяти обычно очень дорого в С++.

Ответ 3

Для указанного значения d (< 10) определение Point как vector<int> почти удвоит использование полной памяти на std::vector<Point> и не принесет почти никакого преимущества.

Ответ 4

Поскольку размерность исправлена, я предлагаю вам перейти с шаблоном, который использует измерение как параметр шаблона. Что-то вроде этого:

template <typename R, std::size_t N> class ndpoint 
{
public:
  using elem_t=
    typename std::enable_if<std::is_arithmetic<R>::value, R>::type;

  static constexpr std::size_t DIM=N;

  ndpoint() = default;

  // e.g. for copying from a tuple
  template <typename... coordt> ndpoint(coordt... x) : elems_ {static_cast<R>(x)...} {
  }
  ndpoint(const ndpoint& other) : elems_() {
    *this=other;
  }

  template <typename PointType> ndpoint(const PointType& other) : elems_() {
    *this = other;
  }

  ndpoint& operator=(const ndpoint& other) {
    for(size_t i=0; i<N; i++) {
      this->elems_[i]=other.elems_[i];
    }
    return *this;
  }

  // this will allow you to assign from any source which defines the
  // [](size_t i) operator
  template <typename PointT> ndpoint& operator=(const PointT& other) {
    for(size_t i=0; i<N; i++) {
      this->elems_[i]=static_cast<R>(other[i]);
    }
  }

  const R& operator[](std::size_t i) const { return this->elems_[i]; }

  R& operator[](std::size_t i) { return this->elems_[i]; }

private:
  R elems_[N];
};

Затем используйте std::vector<ndpoint<...>> для набора точек для лучшей производительности.

Ответ 5

Единственный способ убедиться, что ваши данные структурированы на 100%, - это полностью реализовать собственную обработку памяти.

Однако существует множество библиотек, которые реализуют матрицы и операции с матрицами, которые вы можете проверить. Некоторые из них документируют информацию о непрерывной памяти, изменении формы и т.д. (Например, OpenCV Mat).

Обратите внимание, что в целом вы не можете доверять, что массив точек будет смежным. Это связано с выравниванием, заголовком блока распределения и т.д. Например, рассмотрите

struct Point {
   char x,y,z;
};

Point array_of_points[3];

Теперь, если вы попытаетесь "изменить форму", то есть перебрать между элементами Point, ретранслирующими тот факт, что точки смежны в контейнере, - скорее всего, это произойдет:

(char *)(&array_of_points[0].z) != (char *)(&array_of_points[1].x)