¿qué es más rápido?

[Enrique Nieloud]

Hola gente!,

Esto no es un acertijo de los de Daniel, sino que es posta.

Tenés 

    template <class T>
    struct Point
    {
        T x;
        T y;
    };

Color32 sample(uchar d, uint32 x, uint32 y, const ImgRGBA&) {

  // analiza una porción de la imagen y retorna un color32

}

donde Color32 es un eufemismo para int32.

Así es la función ahora.

Ahora si quiero que sample me retorne 3 Point<int> además del Color32.

¿qué me conviene más: recibir 3 ref a Point<int> ó una sola ref a std::vector<Point<int>> ?

opcion 1)

Color32 sample(uchar d, uint32 x, uint32 y, const ImgRGBA&, Point<int>& p1, Point<int>& p2, Point<int>& p3);

opcion 2)

Color32 sample(uchar d, uint32 x, uint32 y, const ImgRGBA&, vector<Point<int>>& pts);

opción 3) (1) y (2) son malísimas, y ustedes dirán.

Me interesa que "sample" sea lo más performante que se pueda porque se invoca 1 vez por píxel en una imagen de m x n.

les mando un saludo a todos

[Carlos Bederián]

Puramente desde performance, mientras el compilador (al que le pasaste algo más que -O0) pueda hacer inlining da todo más o menos igual. Lo que importa es el layout en memoria y ver que nada impida que se vectorice. Generalmente para estas cosas es mejor data-driven programming.

--
--
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
---
Has recibido este mensaje porque estás suscrito al grupo "CyC++ Buenos Aires" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a cppba+un...@googlegroups.com.
Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAJmrmc9X6fOApHzDFtMpMyub%2BnWUnyUsFgHYrZxxviC2F23OVA%40mail.gmail.com.

[Carlos Bederián]

Ah, incluso sin hacer demasiados malabares para tener inlining, hoy en día usando LTO también puede quedar rápido.

[Enrique Nieloud]

gracias Carlos. Voy a tratar de testear y luego les cuento.

Luego de que les escribí, me quedé pensando, y me imaginé que tendría que ser mucho peor usar un vector porque tiene un comportamiento mucho más complejo, constructor/destructor, y pre-alocar memoria del vector.

Respecto al data driven, la verdad nunca le presté la atención que se merece.

Estaría bueno leer algo del tema (enfocado desde el punto de vista de c++).

Otra duda que me surgió en estos días es la siguiente:

el bucle doble que invoca al sample (la versión simple actual) es algo así:

for y 1 to image_height {

   for x to image_width {

     sample(d, x, y, imgRef)

   }

}

Cuestión que para paralelizar dividí el height en partes y lo hice con threads.

 

Por ejemplo con tres threads:

1. procesa [0..height/3], 

2. procesa [height/3+1..2*height/3] 

3. procesa [2*height/3+1..height]

Bueno, lo que me pareció raro es que la mejor velocidad la obtuve dividiendo solo en tres!!!!

Yo me hubiera imaginado en un pentium, un redimiento con al menos 6 procesos concurrentes, pero no.

Ni idea de la razón.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAOsYsg-6b5%2B1wA7vFapxcmRCvK6iynhEFpwLEHjRnDwX1fcGKA%40mail.gmail.com.

[Jorge Atala]

En mi opinion, en este tipo de problemas, vas mejorar mucho mas la performance vectorizando primero y metiendo hilos despues. Tenes que buscar que tu algoritmo acceda a los datos de manera tal de disminuir los cache miss al maximo posible en los bucles (por ejemplo, asegurandote que estas recorriendo la matriz de colores secuencialmente en memoria). Habria que entender la estructura de imgRef (asumo tres matrices, pero puede ser una con los colores de cada pixel contiguos) y en que influye el parametro d como para pensar otras optimizaciones. 

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAJmrmc_ODLm0%2B2fdjp3ae1t_NWSi0YrFvHWZvcqTWh%2B27cBoCQ%40mail.gmail.com.

[Enrique Nieloud]

Hola,

On Mon, Aug 3, 2020 at 8:50 PM Jorge Atala <alan...@gmail.com> wrote:

En mi opinion, en este tipo de problemas, vas mejorar mucho mas la performance vectorizando primero y metiendo hilos despues.

gracias, lo voy a tratar de tener en cuenta.

 

Tenes que buscar que tu algoritmo acceda a los datos de manera tal de disminuir los cache miss al maximo posible en los bucles (por ejemplo, asegurandote que estas recorriendo la matriz de colores secuencialmente en memoria). Habria que entender la estructura de imgRef (asumo tres matrices, pero puede ser una con los colores de cada pixel contiguos)

Es memoria contigua de 4 bytes por pixel. (RGBA)

Hago lo posible por acceder memoria secuencial, pero, bueno, no siempre puedo.

El tema es cómo medir el porcentaje de caché misses. 

Encontré esto:

https://stackoverflow.com/questions/10082517/simplest-tool-to-measure-c-program-cache-hit-miss-and-cpu-time-in-linux

bueno, gracias 

[Nicolás Brailovsky]

Agrego a lo ya dicho sobre medir y vectorizar: en la opcion 2, en vez de usar un vector seguramente sea mejor pensar en un array.

--

--
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
---
Has recibido este mensaje porque estás suscrito al grupo "CyC++ Buenos Aires" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a cppba+un...@googlegroups.com.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAJmrmc9_dTpm7JKgbSK0BEnNmXOu0uUqVTyBkEwinyiYVHAFSg%40mail.gmail.com.

[Daniel Gutson]

El mar., 4 ago. 2020 7:58 a. m., Nicolás Brailovsky <nicola...@gmail.com> escribió:

Agrego a lo ya dicho sobre medir y vectorizar: en la opcion 2, en vez de usar un vector seguramente sea mejor pensar en un array.

Es lo que estaba por sugerir. Cero alocación dinámica que es lo costoso del constructor, y te provee algo más civilizado qie las 3 referencias.

Sin embargo las tres referencias, si son const& como lo debe ser el array, también debería ser igual de rápido.

Lo bueno del array es que podés ponerle un typedef con un nombre significativo.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAEAM5bETok_ChpYbCS1qgwsekckanMMteLpPoiB%2BosS7kJXgjA%40mail.gmail.com.

[RFOG]

Y digo yo... ¿Son valores RGB los que hay que pasar? ¿Pasar un entero de 32 bits masqueando cada valor (y de hecho, al final, en la memoria de vídeo, eso será eso mismo: un entero de 32 bits)?

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-3WG-BDTPSdR5mH%2Bw1cTyn_217M37iPZhg4ggpgfpj6Dg%40mail.gmail.com.

[Daniel Gutson]

El mar., 4 ago. 2020 10:06 a. m., RFOG <rafael....@gmail.com> escribió:

Y digo yo... ¿Son valores RGB los que hay que pasar? ¿Pasar un entero de 32 bits masqueando cada valor (y de hecho, al final, en la memoria de vídeo, eso será eso mismo: un entero de 32 bits)?

Y por qué no bit fields entonces?

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAN0rX-1terLaoXQBZJgkKDkmfbRAuD%2Bpk5y2jke4DK73B3tbXg%40mail.gmail.com.

[RFOG]

Pues eso mismo. ARGB son 4 bytes = 32 bits. Se supone que el procesador deber de currar internamente bien con bytes dentro del mismo. Tomará una dword y luego internamente los ciclos máquina deben ser cortos, y si se mete en un CUDA o similar, debe volar.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/CAFdMc-13v1LFCtzrnNXtA33aqyn%2BvokwXvvQy37tgGrfSeJjHQ%40mail.gmail.com.

[Jorge Atala]

Basandome en que decis que lees secuencialmente y que dividir en chunks y agregar mas hilos no mejora la performance, pienso que tu problema es memory bound, ahi perf te va a ayudar mucho para probar estrategias de acceso a la memoria, viendo los stats de cache miss principalmente. Para retornar los tres puntos, me quedaria con una estructura que contenga los tres puntos y que conceptualmente representen el significado de esos tres puntos, algo como:

template <class T>

struct Concept

{

  Point<T> a;

  Point<T> b;

  Point<T> c;

};

y trabajo con una referencia pasada como argumento en sample. Si es solo una coleccion de puntos, quedate con un array, es lo mas simple y rapido. KISS :D.

[Alejandro]

Hola; un poco tarde, pero aunque no se mencionó la "copy elision" (https://en.cppreference.com/w/cpp/language/copy_elision) vale la pena:

En este caso se podría echar mano de la NRVO ("named return value optimization), que no es obligatoria pero no hay compilador real que no la aplique, creo.

En este caso se podría crear una struct con los 4 elementos que se van a devolver, algo como:

template <class T>

struct Res {

    int32_t i;

    Point<T> p1;

    Point<T> p2;

    Point<T> p3;

};

Entonces quedaría:

Res<int> sample(uchar d, uint32 x, uint32 y, const ImgRGBA&) {

[Fernando Cacciola]

Hola Enrique,

¿Podés usar el GPU? Porque si queres ganar en performance *significativamente* tenes que usar CUDA en lugar de C++.

Ahora bien, si no tenés un GPU, o tu programa no puede depender de eso, lo que dijo Alejandro tiene que ser lo mejor.

En cuanto a los dividir el height en 3 o más... lo que pasa es que lo que importa es el número de cores. En este caso, lo mejor es usar un Thread Pool bien hecho, que tenga el tamaño adecuado para el sistema donde está corriendo, y luego hace Height/threads_en_el_pool.

--
--
¿Eres miembro de "CyC++ Buenos Aires" verdad? Si no lo eres, has recibido este mesaje por error.
En caso de duda visita "http://groups.google.com/group/cppba"
---
Has recibido este mensaje porque estás suscrito al grupo "CyC++ Buenos Aires" de Grupos de Google.
Para cancelar la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a cppba+un...@googlegroups.com.

Para ver esta conversación en el sitio web, visita https://groups.google.com/d/msgid/cppba/1cd86a10-8a37-4938-9c1d-92834e217162o%40googlegroups.com.

--

Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com