std :: vector vs normal array

Question

Estoy creando un programa que necesita ser ultrarrápido. Está ejecutando algunas cosas en la GPU usando CUDA y luego hace algunos cálculos en la CPU. Para esto, necesito convertir la estructura de GPU altamente optimizada a algo que pueda usar fácilmente en la CPU. Mi información es básicamente un gráfico presentado en una grilla. Actualmente estoy usando std :: vector para la parte de la CPU. Porque sé que es toda una sobrecarga si hago un montón de push_back() s y yo al menos sé porque sé cuántos vértices que tengo en la gráfica, ahora uso el siguiente código para esto:

new_graph.resize(blockSize * blockSize); 
for (unsigned long long y = 0; y < blockSize; y++) { 
    for (unsigned long long x = 0; x < blockSize; x++) { 
     int idx = y * blockSize + x; 
     new_graph[idx] = Vertex(x, y); 
    } 
} 

Después Agrego los bordes. Lamentablemente, no sé cuántos bordes por vértice tengo, pero sí sé que nunca será mayor que 8. Por lo tanto, I reserve() 8 en cada estándar :: vector que utilizo para los bordes.

Sin embargo, ambos parecen ser extremadamente lentos. Si utilizo una matriz normal para el gráfico en sí (básicamente, reemplazando el std :: vector externo), la mejora de velocidad en esa parte es enorme (como 10x más o menos).

Para el gráfico esto es factible, pero en realidad para los bordes no, porque hago algo de postprocesamiento en estos bordes y para esto realmente necesito algo como std :: vector, que es algo dinámico (agrego algunos bordes) .

Actualmente, convertir los datos a std :: vector es algo así como 10 veces más lento que ejecutar mi algoritmo en la GPU (que es un algoritmo MST inteligente). Esto no es realmente lo que quiero, porque ahora los gastos generales son demasiado grandes.

¿Alguien sabe lo que está pasando o cómo puedo solucionarlo?

p.s. Compilo con -O2, porque ya descubrí que eso puede marcar una gran diferencia. También lo intenté con -O3, sin diferencia real.

vértice se define como sigue:

struct Pos { 
    int x, y; 
    Pos() { 
     x = 0; 
     y = 0; 
    } 

    Pos(int x, int y) { 
     this->x = x; 
     this->y = y; 
    } 
}; 

struct Vertex { 
    Pos pos; 
    bool hidden; 
    unsigned long long newIdx; 
    Vertex() { 
     this->pos = Pos(); 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 

    Vertex(Pos &pos) { 
     this->pos = pos; 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 

    Vertex(int x, int y) { 
     this->pos = Pos(x, y); 
     this->hidden = false; 
     this->numEdges = 0; 
     this->numRemovedEdges = 0; 
    } 
    int numEdges; 
    int numRemovedEdges; 
    std::vector<Edge> edges; 
    std::vector<bool> removed; 
    std::vector<bool> doNotWrite; 
}; 

Answer 1

¿Quizás está pagando por una asignación de memoria dinámica que vector hace para reservar el espacio para sus elementos?

Incluso si reserve de manera óptima, tendrá al menos 3 asignaciones de memoria para todos y cada Vertex (uno para edges, uno para removed y uno para doNotWrite). La asignación de memoria dinámica es potencialmente costosa en relación con las cosas de alto rendimiento que está tratando de hacer aquí.

O use matrices simples antiguas que tienen la garantía de ser lo suficientemente grandes (potencialmente desperdician espacio), o un asignador de memoria especializado junto con vector, adaptados a sus necesidades específicas.

---

Además, ¿tiene acceso a los elementos en el orden de la memoria? Su ejemplo parece sugerirlo, pero ¿lo hace en todos los casos?

---

Además, ¿incluso necesita Vertex.pos? ¿No puede ser inferido desde la posición Vertex en la cuadrícula?

Answer 2

no se puede crear un objeto Vertex, memcpy los valores de x e y en él (de modo que usted no tiene que llamar al constructor para cada lazo) , luego inserte todo el Vértice en su std :: vector? Se garantiza que la memoria del vector se distribuirá como una matriz regular, por lo que puede omitir toda la abstracción y manipular la memoria directamente. No hay necesidad de cosas complicadas. Además, tal vez pueda maquetar los datos que obtiene de la GPU de tal manera que pueda memcpy bloques completos a la vez, lo que le ahorrará aún más.

Answer 3

Hay otra solución que utilicé recientemente en una situación similar. En el paquete llvm hay una clase SmallVector. Proporciona una interfaz que es bastante similar a std :: vector, pero permite mantener un número fijo de elementos en línea (de modo que a menos que el vector crezca por encima de ese límite inicial no se produzcan asignaciones de memoria adicionales). Si SmallVector intenta crecer por encima de ese tamaño inicial, se asigna el bloque de memoria y todos los elementos se mueven allí, todo en un paso transparente.

Pocas cosas que tenía que corregir en esta SmallVector:

1. menor número de elementos que se podrían poner en contexto es 2, por lo que cuando se utiliza 1 artículo en el ejemplo 99,99% de los casos hay una bastante por encima
2. el uso habitual de intercambio() para liberar memoria (SmallVector(). Swap (VEC)) no liberar memoria, así que tuve que poner en práctica yo mismo

Ver para la versión más reciente de llvm para el código fuente de la clase SmallVector

Answer 4

la estructura de datos de la CPU es extremadamente ineficiente debido a la cantidad de asignaciones dinámicas de memoria, las operaciones de asignación innecesarios, y el tamaño total de cada vértice. Antes de considerar la optimización de esta estructura, sería bueno comprender el flujo de datos entre las estructuras de datos de la CPU y las estructuras de datos de la GPU, ya que la conversión entre los dos formatos probablemente tome mucho tiempo. Esto plantea la pregunta: ¿por qué la estructura de la GPU no se usa en el lado de la CPU?

Si solo miraba esto desde el lado de la CPU y desea mantener una estructura de datos AoS, entonces 1. Simplifique la estructura de datos de Vertex. 2. Elimine toda la asignación de memoria dinámica. Cada estándar :: vector hará un dynb 3. Reemplace eliminado y doNotWrite para std :: bitset < 8>. 4. Eliminar numRemoveEdges. Esto es removed.count(). 5. Si Edge es pequeño, es posible que le resulte más rápido declarar Edge edge [8]. 6. Si decide permanecer con el vector, considere usar un asignador de grupo. 7. Reordene los elementos de datos en Vertex por tamaño para reducir el tamaño de Vertex.

Todas estas recomendaciones probablemente no sean la mejor solución para compartir datos con una GPU. Si usa un asignador de grupo y usa UVA (CUDA Linux), simplemente puede copiar los datos a la GPU con una única copia de memoria.