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

Question

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

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

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

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

Answer 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, но не для всей конструкции.

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

Answer 2

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

Answer 3

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

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

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

Answer 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<...>> для набора точек для лучшей производительности.

Answer 5

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

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

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

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

Point array_of_points[3]; 

Теперь, если вы пытаетесь «перекроить», то есть, итерацию между точечными элементами релейной защиты на том, что точки находятся рядом в контейнере - чем это, скорее всего, на провал:

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