resueltos - Almacenamiento de vectores en C++

vector c++

Question

Deseo almacenar un gran vector de puntos d-dimensionales (d fijo y pequeño: <10).

Si defino un Point como vector<int> , creo que un vector<Point> almacenará en cada posición un puntero a un Punto.

Pero si define un Point como un objeto de tamaño fijo como: std::tuple<int,int,...,int> o std::array<int, d> , el programa almacenará todos los puntos en la memoria contigua o lo hará el nivel adicional de direccionamiento indirecto?

En caso de que la respuesta sea que las matrices evitan la indirección adicional, ¿podría esto tener un gran impacto en el rendimiento (localidad de explotación de caché) al escanear el vector<Point> ?

Answer 1

Como la dimensión es fija, le sugiero que vaya con una plantilla que use la dimensión como un parámetro de plantilla. Algo como esto:

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

Luego use un std::vector<ndpoint<...>> para una colección de puntos para un mejor rendimiento.

Answer 2

La única forma de estar 100% seguro de cómo se estructuran sus datos es implementar completamente el manejo de la memoria.

Sin embargo, hay muchas bibliotecas que implementan matrices y operaciones de matriz que puede verificar. Algunos tienen información documentada acerca de la memoria contigua, la remodelación, etc. (por ejemplo, OpenCV Mat).

Tenga en cuenta que, en general, no puede confiar en que una matriz de Puntos será contigua. Esto se debe a la alineación, al encabezado del bloque de asignación, etc. Por ejemplo, considere

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

Point array_of_points[3];

Ahora bien, si intenta ''remodelar'', es decir, itera entre los elementos de punto que transmiten el hecho de que los puntos están adyacentes en el contenedor, de lo que es más probable que falle:

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

Answer 3

Para dicho valor de d (<10), definir Point como vector<int> casi duplicará el uso de la memoria completa por std::vector<Point> y no aportará prácticamente ninguna ventaja.

Answer 4

Si define su Point como un almacenamiento contiguo de datos (por ejemplo, struct Point { int a; int b; int c; } o usando std::array ), std::vector<Point> almacenará los Point s en ubicaciones de memoria contigua , entonces su diseño de memoria será:

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

Por otro lado, si define Point como un vector<int> , entonces un vector<Point> tiene el diseño de vector<vector<int>> , que no es contiguo, ya que el vector almacena punteros a la memoria asignada dinámicamente. De modo que tiene contigüidad para Point únicos , pero no para toda la estructura.

La primera solución es mucho más eficiente que la segunda (ya que las CPU modernas adoran acceder a ubicaciones de memoria contigua).

Answer 5

vector almacenará cualquier cosa que tu tipo contenga en la memoria contigua. Entonces sí, si eso es una array o una tuple , o probablemente incluso mejor, un tipo personalizado, evitará la indirección.

En cuanto a rendimiento, como siempre, debes medirlo. No especules. Al menos en lo que se refiere al escaneo.

Sin embargo, definitivamente habrá una gran ganancia de rendimiento cuando crees esos puntos en primer lugar, porque evitarás asignaciones de memoria innecesarias para cada vector que almacene un punto. Y las asignaciones de memoria suelen ser muy caras en C ++.