Boujour à tous,

Pour encourager le compilateur à vectoriser, sur des conteneurs contigus de vec2 ou vec3, j'utilise une petite arithmétique de pointeur. Vous allez certainement me dire que c'est moche et pas très safe.
Y a t-il d'autres manières de faire ?
Ce que j'aime bien avec ma solution c'est que je peux accéder à mes éléments soit par l'objet (si je veux modifier un élément parmi d'autres), ou alors tout en bloc pour optimiser. (le contexte est un ECS avec pas mal d'éléments à mettre à jour à chaque frame).

https://quick-bench.com/q/uRq6oQNUu7CD8dGBKs7B4FnzGug

#include <vector>
#include <iostream>

struct vec3{float x; float y; float z;};
vec3 operator+(vec3 const& a, vec3 const& b)
{
    return vec3{a.x+b.x, a.y+b.y, a.z+b.z};
}
 
int main()
{
    std::vector<vec3> v1 {{0.,1.,2.},{3.,4.,5.},{6.,7.,8.}};
    std::vector<vec3> v2 {{8.,7.,6.},{5.,4.,3.},{2.,1.,0.}};
    std::vector<vec3> v3(3);
    
    for(unsigned i = 0; i < v1.size(); ++i)
    {
        v3[i] = v1[i] + v2[i];
    }
    
    // ou alors (2,4 fois plus rapide)
     
    for(float* i1 = &v1[0].x, *i2 = &v2[0].x, *i3 = &v3[0].x; i1 <= &v1.back().z; ++i1, ++i2, ++i3)
    {
        *i3 = *i1 + *i2;
    }
    
    for(auto e : v3)
        std::cout << '{'<< e.x << ',' << e.y << ',' << e.z << "} ";
        std::cout << std::endl;
}

Question subsidiaire : préférez-vous OpenMP ou std::experimental::simd (je n'ai pas encore essayé ce dernier, mais ça semble plus compliqué).
Merci de l'aide que vous pourrez apporter.

-
Edité par Umbre37 30 avril 2024 à 11:07:31

Sans avoir regardé le code assembleur généré, tu n'aurais pas un problème dans la premier cas avec le fait d'utiliser une structure complexe comme std::vector ? (Essaie avec std::array ou un C-array). Et il faudrait aussi vérifier si tu n'as pas une copie de vec3 dans le premier cas.

C'est le problème classique des SOA vs AOS. Si cela a un impact important, je dirais que cela fait parti des codes unsafe acceptables.

@gbdivers Bonjour et merci de ta réponse.

Dans les deux cas ce sont des AOS - Array Of Structures, ou alors on ne s'est pas compris.
Comment peut-on éviter la copie du vec3 ? à part avec de l'expression programming template (etp) je ne sais pas comment faire, parce qu'il faudra bien au final que x y et z soient dans le std::vector. En plus l'etp compliquerait bcp les choses pour des perfs qui seraient les même qu'avec ma solution avec pointeurs je pense.

J'ai dupliqué le code avec des std::array, cela donne des perfs intermédiaires. https://quick-bench.com/q/pOWoCqm_ZTlG5-oyKzX_JLVF-34
par ailleurs, j'ai essayé #pragma omp simd, mais ça ne change rien, le O3 optimise déjà à fond ici j'imagine.

-
Edité par Umbre37 30 avril 2024 à 8:55:06

Meme question. As-tu comparé les codes ASM?

Il n'est pas rare de voir les mesures perturbées par plein de choses (alignement des fonctions, précision de quickbench -- j'ai entendu plus de bien de nanobench, tout en y constatant de sacrées instabilités aussi)

Aussi, si je ne me trompe pas, tu mesures aussi l'allocation du vecteur résultat.

Ce qui me fait penser que perso je préfère écrire mes boucles sur des span et sortir l'aspect mémoire du bench.

Aussi, parce que tes vecteurs 3D sont sur des floats (et non des doubles), prends les par valeur sur linux (ABI itanium) => tout passera dans des registres https://godbolt.org/z/asheda9h7 (après, ici tout est inliné, ça ne fera pas de différence)

EDiT: Je n'avais pas vu, mais tu as un UB -> vector.reserve au lieu de resize...

EDIT2: Effectivement, c'est comme si les compilos ne pouvaient pas dérouler correctement sur toutes les composantes. Limite je me pose la question si des additions sur un truc de taille paire (vec4) ne pourrait pas etre mieux optimisé. Histoire de complètement remplir les registres simd (d'où l'idée de passer à du SoA --> au lieu d'une seule composante position3D, peut-etre 3 composantes position-x, -y et -z.

Et je préfère https://github.com/xtensor-stack/xsimd

-
Edité par lmghs 30 avril 2024 à 14:31:22

Umbre37 a écrit:

Dans les deux cas ce sont des AOS - Array Of Structures, ou alors on ne s'est pas compris.

Dans Vector_ptr, tu manipules au final 3 tableaux de float, c'est equivalent a :

struct soa {
    float i1[N*3], i2[N*3], i3[N*3];
};

(chaque pointeur i1, i2 et i3 parcourent les x, y, z. des vec3)

Umbre37 a écrit:

J'ai dupliqué le code avec des std::array, cela donne des perfs intermédiaires. https://quick-bench.com/q/pOWoCqm_ZTlG5-oyKzX_JLVF-34

Je dirais comme lmghs : utilise un span<float>. Il faut regarder pourquoi le compilateur n'optimise pas pareil, mais si la solution est du traficotage du code, pour le rendre illisible et immaintenable, ta solution de parcourir les floats n'est pas si mal. A mon avis, il faut juste la rendre plus clean (par exemple avec span)

@lmghs Merci bcp pour les conseils. Je ne connaissais pas xsimd. Je ne suis pas assez calé pour lire l'assembleur, autrement je le ferais.

Oui je mesure l'allocation du résultat, c'est vrai, mais c'est plus compliqué de faire autrement.
Tu as raison pour l'alignement des vec3, avec des vec4 c'est très différent : https://quick-bench.com/q/zlIOWkqlVwmdfdM8hrgif5ZiNvE

Edit : je ne connais pas goblot. Apparement le passage par valeur est meilleur ici, mais comme tu l'avais prédit l'inlining supprime la différence : https://quick-bench.com/q/j2nPjHKDeYUNJKAPUooaz9OkVN0

Je reviens avec un test sur des span tout à l'heure.

@gbdiver "Dans Vector_ptr, tu manipules au final 3 tableaux de float, c'est equivalent a :"
oui c'est vrai ! je ne l'avais pas vu comme ça.

Edit 2 :
J'ai essayé d'utiliser span et de sortir l'allocation des vecteurs de la boucle, (j'espère que c'est ce à quoi vous pensiez)

https://quick-bench.com/q/56UW8JdYZDtU9n6m_3DfIn5OfbE

-
Edité par Umbre37 30 avril 2024 à 17:55:36

>Oui je mesure l'allocation du résultat, c'est vrai, mais c'est plus compliqué de faire autrement.

Pas vraiment. Crée le vecteur résultat avant la boucle sur les états.

> span...

Mais pourquoi des reinterpret_cast?

L'idée est que tu as une fonction de calcul spécifiée pour des span

void add_classic(std::span<Vec3 const> a, std::span<Vec3 const> b, std::span<Vec3> res)
{
    assert(a.size() == b.size()); // pareil pour res
    for (std::size_t i=0; i < a.size() ; ++i)
        res[i] = a[i] + b[i];
}

Ha! Purée! Je viens de comprendre la version où tu prends tous les vecteurs à plat... (et le reinterpret_cast -- pas sur qu'il soit légal :/) Oui. C'est normal que ça soit plus rapide. Et tant qu'il n'y a pas de padding, on est bon.

Si tu fais sauter le type vec3, et qu'au final, tu as une matrice à plat, ton optim sera parfaitement valable.

lmghs a écrit:

(et le reinterpret_cast -- pas sur qu'il soit légal :/)

Et tant qu'il n'y a pas de padding, on est bon.

Sauf erreur de ma part, seul les cast vers et depuis char* sont légaux. Le reste est implémentation dépendant. Donc il faut blinder pour etre sur que le code est valide. En particulier, etre sur de l'alignement et du padding. Pour ce que j'ai vu, c'est ok ici, mais il ne faut pas hésiter a mettre des static_assert (ou if constexpr) pour garantir que les suppositions faites sur le layout des structures.

Et n'hesite pas a activer -Wpadded https://clang.llvm.org/docs/DiagnosticsReference.html#wpadded 

-
Edité par gbdivers 30 avril 2024 à 17:50:46

@lmgh"Pas vraiment. Crée le vecteur résultat avant la boucle sur les états."

oui pardon, je ne sais pas pourquoi j'ai mis l'allocation dans la boucle. Voici avec modification :

https://quick-bench.com/q/x7P1tJWS3JJV5LDZOFrRL_yjU-g

@lmgh"C'est normal que ça soit plus rapide. Et tant qu'il n'y a pas de padding, on est bon"

Oui! et encore, tant que le padding est régulier, ça devrait encore marcher !

@lmgh"Si tu fais sauter le type vec3, et qu'au final, tu as une matrice à plat, ton optim sera parfaitement valable."

Super c'était exactement ce que je cherchais.

@gbdivers, "etre sur de l'alignement et du padding"
en fait, tant que le padding est régulier, et dans un vector c'est obligatoire, je crois que c'est bon, non ? au pire on additionne dans les trous et ça ne changera rien. Ou alors comment ferais-tu ? 

struct alignas(16) vec3 {float x, y, z;}; // ??

Je ne sais pas si ça arrange mes affaires ?

Le reinterpret_cast n'est pas obligatoire, on peut faire

std::span<float> span1(&v1[0].x, v1.size() * 3);

-
Edité par Umbre37 30 avril 2024 à 18:15:10

C'est amusant que span_ptr soit un peu plus que vector_ptr. Je sais pas a quoi c'est du. Il faudrait voir le code asm en détail.

Juste par curiosité : même avec des struct vec2{float x,y;}; la version vector_obj est toujours aussi mauvaise... Pourtant facile à aligner. Par contre avec le span il le voit. Je ne sais pas pourquoi.

https://quick-bench.com/q/vITiXnr7Bqm1E8cJQ1VJekwLUbQ

-
Edité par Umbre37 30 avril 2024 à 18:47:06

J'imagine que c'est l'implementation de std::vector qui n'est pas correctement comprise et donc optimisé par le compilo.

@lmghs

Du coup, je regarde la doc de xsimd. https://xsimd.readthedocs.io/en/latest/api/dispatching.html
Je voudrais pourvoir choisir dynamiquement la meilleure version, car je ne sais pas dans quel environnement l'application sera utilisée.
J'ai du mal à comprendre la fin. Faut-il ajouter une ligne dans le hpp par architecture que je veux supporter ?

extern template float sum::operator()<xsimd::avx2, float>(xsimd::avx2, float const*, unsigned);

Ainsi qu'un fichier .cpp ?

// compile with -mavx2
#include "sum.hpp"
template float sum::operator()<xsimd::avx2, float>(xsimd::avx2, float const*, unsigned);

faut-il implémenter toutes les architectures ? Ou alors y a-t-il moyen de gérer cela automatiquement ?
Pour un jeu vidéo, que faut-il viser pour un usage large ? est-ce que avx, avx2 et sse2 suffisent ?
Merci de votre aide.

-
Edité par Umbre37 7 mai 2024 à 10:47:45

> Faut-il ajouter une ligne dans le hpp par architecture que je veux supporter ?

C'est comme ça que je le comprends. Et chaque spécialisation devra être compilée avec le flag ad'hoc. Avec des macros, il y a moyen d'y avoir qu'un seul fichier. Genre

///spe-smid.cpp

#include "quivabien"

template float sum::operator()<xsimd::ARCHI, float>(xsimd::ARCHI, float const*, unsigned);

Et coté Makefile

spe-simd-avx2.o: spe-simd.cpp
    $(CXX) ... -DARCHI=avx2 -mavx2 -o spe-simd-avx2.o spe-simd.cpp

Suivant si tu utilises CMake, xmake... il doit peut être y avoir moyen pour déclarer automatiquement ces targets avec une boucle sur les archis que tu veux supporter.

Après, il me semblait que cela faisait déjà longtemps que le target par défaut des compilos était see4.1 (ou c'est sse2? J'ai un doute.). Pas sur qu'il y ait un intérêt à viser SSE2. Après, je ne sais pas s'il peut y avoir des choses plus pertinentes pour AMD.

Mesure au passage les boucles que tu optimiserais de la sorte. Pour un bench de produit scalaire dernièrement, je n'avais pas de différence entre avx et avx2 p.ex.

@lmghs
Merci bcp pour les conseils.
Je n'utilise qu'un makefile, mais ça ne sera pas trop compliqué avec des scripts/macros de compiler automatiquement pour les quelques architectures cible.

Umbre37 a écrit:

faut-il implémenter toutes les architectures ? Ou alors y a-t-il moyen de gérer cela automatiquement ?
Pour un jeu vidéo, que faut-il viser pour un usage large ? est-ce que avx, avx2 et sse2 suffisent ?

Sauf si tu es une grosse boite de jeux vidéos, tu n'auras pas les ressources matériels pour tester tes différentes implémentations sur les différentes plateformes. Il faut rester réaliste.

lmghs a écrit:

Mesure au passage les boucles que tu optimiserais de la sorte. Pour un bench de produit scalaire dernièrement, je n'avais pas de différence entre avx et avx2 p.ex.

Comment faire ? je n'ai qu'un seul ordinateur. Comment comparer divers environnements d'exécution ?

-
Edité par Umbre37 7 mai 2024 à 17:59:24

Avoir plusieurs ordinateurs.

A partir du moment où tu fais des optimisations spécifiques a du matériel particulier, tu n'as pas d'autres choix que de tester sur plusieurs matériels. Il existe des plateforme de build en ligne ou tu demandes a des amis. Ou tu reste sur une implémentation générique.

Ma machine supporte jusqu'au AVX2. Du coup pour des tests, j'ai compilé un meme fichier n fois, à chaque fois avec des options de compilation différentes, pour produire des fonctions aux noms différents (merci les macros). Dans les tests (nanobind), je fais référence aux diverses fonctions optimisées en normal/avx/avx2/fma, et j'observe ensuite si mes versions de gcc et clang produisent des différences.

Pour le simd, c'est pareil, chaque spécialisation est compilée avec les options qui vont bien, et je linke tout le monde à la fin pour les comparer avec nanobind.

Ok merci pour vos retours. C'est vrai que je suis tout seul. Je compte bien faire des tests sur les pc des amis et de la famille, mais ça restera limité.

D'après votre expérience ce serait pas raisonnable de juste faire confiance au dispatching de xsimd ? au pire, on n'y gagne rien, au mieux il vectorise et et les perfs font x2, x4... non ?

D'expérience, de mauvaises optimisations peuvent diminuer les performances, en cassant les caches, en sérialisant les taches, etc. Pour des choses aussi simple qu'une simple vectorisation d'addition, le risque est faible, mais cela va dependre de ce que tu veux faire.

Et considérer la portion que tu optimises. Meme faire x1000 sur un bout de code qui ne prend que 5% du temps d'exécution global, tu ne gagneras jamais plus que ces 5%. As-tu évalué combien de temps tu passes sur ces opérations? Est-ce ton poste le plus élevé pour atteindre le nombre de calculs que tu vises entre 2 rafraîchissements de frames? (ou autre métrique)

Rien que le passage à du SoA pour des mises à jour de positions a des chances qu'il faille commencer à regarder les autres points à optimiser. Non?

@gbdivers @lmghs oui a priori ce qui prend le plus de temps c'est de parcourir et mettre à jour les components de l'ecs dans les boucles à chaque frame. Donc la vectorisation est pertinente. D'autant plus que je n'arrive pas à multithreader, j'ai peut-etre pas la bonne méthode, mais la gestion des thread fait perdre le gain espéré. Mais c'est un autre sujet.
En tout cas merci beaucoup pour votre aide.

-
Edité par Umbre37 7 mai 2024 à 22:59:58