Pourquoi éviter l’optimisation de déplacement conditionnel avec mix()+step() dans les shaders

• Dans les shaders GPU, le code qui choisit une valeur avec un opérateur ternaire ou un simple if est généralement traité comme un déplacement conditionnel (select), et non comme un branchement conditionnel
• Le remplacer par step() et un masquage arithmétique ne supprime donc aucun branchement inexistant : le postulat de cette soi-disant optimisation par suppression de branchement est erroné
• Les sorties des compilateurs AMD et Microsoft montrent des instructions de comparaison et de masque/déplacement conditionnel, sans instruction de saut ni de branchement
• La version avec step() crée un masque 0.0/1.0 puis compose le résultat avec des multiplications et des additions, ce qui ajoute des opérations inutiles par rapport à un déplacement conditionnel direct
• Les branchements GPU qui sautent de gros blocs de calcul selon une condition restent utiles, mais pour une simple sélection de valeur, il est plus sûr de vérifier le code machine généré

---

Une simple sélection de valeur n’est pas un branchement GPU

• La fonction d’exemple snap45() calcule x = abs(v.x) à partir du vecteur d’entrée, puis renvoie l’un de trois résultats vec2 au moyen de deux opérateurs ternaires
• La même logique reste valable si elle est écrite avec des instructions if classiques
• L’« optimisation » en question consiste à remplacer les opérateurs ternaires par step() et une composition pondérée
  • w0, w1 et w2 sont produits avec step()
  • res0, res1 et res2 sont calculés séparément
  • Le résultat final est composé avec w0*res0 + w1*res1 + w2*res2
• Cette transformation part de l’idée fausse que le code d’origine crée un branchement conditionnel
• Une simple sélection de valeur dans un registre ne modifie pas le pointeur d’instruction et ne provoque ni échec de prédiction, ni vidage du pipeline, ni invalidation du cache d’instructions
• Les vrais branchements GPU peuvent être rapides et utiles lorsqu’ils permettent de sauter de gros blocs de calcul selon une condition
• En revanche, dans un cas comme l’exemple, où il s’agit simplement de choisir une valeur ou un résultat de calcul, on peut considérer qu’aucun branchement n’apparaît dans le code machine généré

Ce que montrent les sorties des compilateurs

• Le code GLSL d’origine avec opérateurs ternaires est transformé par le compilateur AMD en instructions de comparaison et de masque conditionnel
  • Comparaison : v_cmp_gt_f32, v_cmp_ngt_f32
  • Masque conditionnel : v_cndmask_b32
• La sortie du compilateur Microsoft présente la même structure
  • Comparaison : lt
  • Déplacement conditionnel : movc
• Dans les deux sorties de compilateur, il n’y a aucune instruction jump/branch

Pourquoi l’approche avec step() est plus coûteuse

• L’approche basée sur step() commence par créer, via un déplacement conditionnel, un masque 0.0 ou 1.0, puis masque plusieurs résultats candidats avec des multiplications et additions
• Le code d’origine déplace directement la valeur nécessaire de façon conditionnelle ; il gaspille donc moins de travail que l’approche avec step(), qui ajoute la génération de masques et la composition arithmétique
• Sur divers matériels, la version basée sur step() peut se révéler nettement plus lente que la version d’origine
• Certains appels GLSL abs() du code d’exemple ne deviennent pas des instructions GPU séparées, mais des modificateurs d’instruction ; dans ce cas, l’appel à abs() peut être considéré comme presque gratuit
• Recommander float a = mix(b, c, step(y, x)); comme optimisation de float a = x < y ? b : c; est une mauvaise approche

[GN⁺]

Commentaires sur Hacker News

• La conclusion de l’article semble juste, mais l’argumentation aurait été plus solide si elle avait montré les résultats de génération de code des deux versions, au lieu de ne montrer que la meilleure
  La citation dit en substance : « la version présentée comme optimisée est bien plus lente que la version d’origine… elle gaspille deux multiplications et une ou deux additions… regardons le code machine généré », mais en pratique seul le bon cas, sans multiplications ni additions, est montré
  Cela prouve seulement que la bonne version est correcte, pas encore que la mauvaise est effectivement pire

  • Le point essentiel, c’est que la condition n’a pas produit de branchement réel
    Même si le code généré de l’autre version avait été montré, il n’aurait probablement paru que plus long ; il n’était pas vraiment attendu qu’il introduise un branchement, donc cela n’aurait sans doute pas apporté grand-chose
  • Le code généré pour RDNA 1 est ici : https://shader-playground.timjones.io/5d3ece620f45091678dcee...

• Ce serait bien d’avoir un bon moyen de savoir quand if force réellement un branchement et quand ce n’est pas le cas
  Si les gens utilisent mix/lerp, potentiellement plus coûteux, c’est parce qu’ils redoutent l’apparition d’un branchement, même au prix d’un léger surcoût
  C’est bien si le code le plus clair, comme v = x > y ? a : b;, fonctionne correctement en pratique, mais le fait que la même syntaxe if corresponde parfois à un branchement et parfois non reste inquiétant
  Dans les contextes où il ne faut vraiment pas brancher, on aimerait que branch-if et le if sans branchement soient deux mots-clés distincts ; le mot-clé non branchant devrait faire échouer la compilation si le compilateur ne peut pas le produire sans branchement, et le mot-clé branchant devrait émettre un avertissement si le compilateur peut finalement s’en passer

  • À l’origine, il y a une documentation confuse de NVIDIA et des compilateurs cg/CUDA
    Au départ, ils ne voulaient pas effrayer les programmeurs, donc ils ont masqué le modèle d’exécution derrière l’abstraction des « threads », puis ont continué à présenter les GPU en disant en gros « il y a énormément de threads CUDA »
    Cela a fini par créer d’étranges superstitions autour du développement GPU
    En réalité, il est souvent tout à fait souhaitable d’avoir des branches dans le code, et le branchement lui-même est rapide
    Le vrai problème, c’est que les lanes SIMD ne peuvent pas chacune partir dans une branche différente ; le compilateur émet donc souvent le code des deux côtés et masque le résultat selon la condition, au lieu de faire un branchement
    Ainsi, les calculs fondés sur les entrées du shader, les sommets, les indices de compute shader, etc., ne branchent pas réellement et s’exécutent séquentiellement avec masquage
    Dans l’exemple de l’article aussi, les deux valeurs de l’opérateur ? sont calculées, et c’est généralement pareil pour les conditions portant sur des valeurs SIMD
    Il peut exister un branchement raccourci permettant de sauter rapidement un calcul quand toutes les lanes ont la même valeur, mais en général les deux côtés, vrai et faux, sont calculés
    Seules les conditions fondées sur des registres scalaires, c’est-à-dire les constantes de shader ou les valeurs uniform, produisent de vrais branchements, et ces branchements sont très rapides
  • C’est pareil sur un CPU scalaire
    Par exemple, l’instruction CMOV a été introduite avec le cœur P6 en 1995
    Les branchements coûtent cher aussi sur les architectures scalaires, et le compilateur essaie au mieux de décider quand employer une stratégie alternative
    Il se trompe parfois, mais pas si souvent
  • Sur GPU, il faut même voir les choses à l’inverse
    Le déplacement conditionnel est le comportement par défaut, et le vrai branchement n’est qu’une optimisation de performance possible quand toute la workgroup prend uniformément la même direction
  • On peut imaginer un cas comme : a = f(z); b = g(z); v = x > y ? a : b;
    Si le coût des appels à f() et g() est relativement élevé, alors choisir entre du code conditionnel ou calculer les deux puis sélectionner le résultat devient un compromis
    Ce n’est pas un simple choix, et c’est au compilateur de trancher
  • Une telle fonctionnalité serait intéressante dans un langage de shader
    On pourrait classer toutes les fonctions du code comme branchantes / non branchantes ; une fonction marquée non branchante devrait compiler les if en déplacements conditionnels et ne pouvoir appeler que d’autres fonctions non branchantes

• Une bonne partie du mythe selon lequel « les branchements sont lents sur GPU » vient du fait qu’à l’époque de la PlayStation 3, ils l’étaient réellement
  La PS3 embarquait un GPU NVIDIA RSX et, de mémoire, la documentation annonçait un branchement en 6 cycles, mais dans les mesures réelles c’était toujours plus lent
  C’était vrai même pour des branchements parfaitement cohérents où tous les threads d’un warp suivaient le même chemin, et les branchements incohérents étaient encore plus lents car l’instruction IFEH coûtait 6 cycles et le GPU devait en plus exécuter les deux branches
  À mon avis, le mythe toujours vivant selon lequel « les branchements GPU sont lents » vient de là
  De nos jours, les branchements GPU, surtout les branchements cohérents, sont plutôt peu coûteux

  • Quand quelqu’un parle simplement de « branchement », il faut généralement comprendre branchement incohérent
    Le surcoût du mécanisme de branchement a peut-être diminué aujourd’hui, mais la contrainte physique selon laquelle le débit de chaque branche baisse en proportion du nombre de threads actifs reste inchangée
    Si les deux branches sont exécutées et que leur longueur d’instructions est comparable, la performance moyenne des deux côtés tombe au minimum de moitié
    C’est pour cela que l’idée selon laquelle les branchements sont lents sur GPU perdure, et qu’elle reste vraie en pratique
    Si possible, cela vaut la peine de faire davantage d’efforts pour reformuler le problème sans branchement
  • Les branchements cohérents sont presque « gratuits », mais les instructions supplémentaires augmentent la pression sur les registres
    La raison principale d’éviter les branchements dynamiques n’est pas tant que le branchement lui-même soit intrinsèquement lent, mais plutôt cela

• Ce type d’optimisation pour éviter les branches a déjà été efficace
  Je me souviens avoir fait du profiling sur Xbox 360 et sur de vieux GPU intégrés Intel, mais aujourd’hui il vaut mieux éviter de faire ça
  L’extraction de bits et d’autres opérations entières sont similaires
  Autrefois, les émuler avec des calculs en virgule flottante était plus rapide, mais désormais tous les GPU disposent d’opérations entières rapides

  • Je me demande dans quelle mesure l’affirmation « désormais tous les GPU disposent d’opérations entières rapides » est vraie
    Par exemple, dans l’ISA RDNA2 utilisée par la PS5 et les Xbox Series S|X, on dirait qu’on ne voit que des instructions scalaires 32 bits pour les entiers
    [0] https://www.amd.com/content/dam/amd/en/documents/radeon-tech...
  • Au moins sur les « gros » GPU, ce n’est plus un problème aussi important qu’avant, mais cet article ne parle en réalité pas d’évitement des branches en soi
    Le code présenté est déjà sans branche
    Ceux qui donnent ce conseil semblent juger qu’un code est branché simplement parce qu’il contient dans la source une construction qui ressemble à une condition, et pensent l’éviter via une optimisation

• Cet article est aussi lié : https://medium.com/@jasonbooth_86226/branching-on-a-gpu-18bf...
  « Si vous demandez à Internet comment écrire des branches sur un GPU, on pourrait croire que c’est comme ouvrir les portes de l’enfer et laisser entrer les démons. Qu’il faut les éviter à tout prix, et qu’on peut les contourner avec de drôles d’astuces mathématiques comme l’opérateur ternaire ou step(). La plupart de ces conseils sont, au mieux, dépassés, et souvent tout simplement faux. Remettons les choses au clair. »

• Les processeurs changent, et les compilateurs aussi
  Si ce genre de détails compte, le mieux est de distribuer plusieurs variantes et de choisir à l’exécution la version la plus rapide
  Je l’ai déjà dit plusieurs fois, mais il m’est arrivé de supprimer de l’assembleur écrit à la main et de le remplacer par du C banal ou quelque chose d’approchant, pour obtenir un code bien plus rapide
  Peut-être que cet assembleur était plus rapide il y a 10 ou 20 ans, mais la situation a changé aujourd’hui

  • À mon avis, déterminer à l’exécution la version la plus rapide d’un shader est très délicat
    Je ne connais pas vraiment de jeu ou de moteur qui fasse cela en pratique
    En principe, ce serait peut-être possible
    La plupart des API comme D3D, GL ou Vulkan exposent des compteurs de performance, et même si leur fiabilité varie selon le fournisseur, on pourrait créer une scène de test représentative et la rejouer plusieurs fois pour mesurer les optimisations
    Mais beaucoup de jeux utilisent des scènes générées dynamiquement et des shaders générés dynamiquement, donc le nombre de combinaisons à tester peut devenir un obstacle
    Il faudrait peut-être demander à l’utilisateur d’attendre la fin du benchmark
    Si l’on dispose du matériel, on pourrait aussi mesurer à l’avance sur plusieurs générations de GPU de chaque fournisseur et ne coder en dur que les décisions importantes, mais je ne connais pas vraiment d’infrastructure existante de ce type
  • Fait intéressant, le pilote NVIDIA fait ce genre de chose dans une certaine mesure
    Il intercepte les shaders des jeux et les remplace par des shaders personnalisés optimisés par NVIDIA
    C’est pour cela qu’on voit dans les notes de version des pilotes NVIDIA des mentions du type « optimisation pour le jeu X, exécution 40 % plus rapide »
  • Ajouter un shader supplémentaire peut rester acceptable, mais avec les API graphiques « modernes », un même shader peut parfois nécessiter des milliers de permutations, et chaque variante ajoutée double ce nombre
    On ne peut pas passer un temps infini sur chaque shader
    Il faut profiler sur le matériel visé, et si l’approche choisie devient plus lente sur un processeur hypothétique du futur, tant pis
    Il faut espérer que ce processeur sera suffisamment rapide pour que ce ne soit pas un problème

• Il me semble que l’erreur et la confusion que cet article essaie de corriger se répètent aussi ici
  L’article n’affirme pas que les branches conditionnelles sont gratuites
  À mes yeux, ce n’est même pas un article sur le coût en performance du code branché
  Son propos est que la logique conditionnelle de la forme présentée n’est pas compilée en code à branche conditionnelle
  Et qu’il ne faut pas continuer à diffuser des conseils nocifs consistant à masquer de force toute expression conditionnelle visible
  Quant au vrai code branché, il est évident que son exécution est plus complexe
  Il n’existe pas de branche gratuite, et dans des limites raisonnables, éviter les branches a de bonnes chances d’accélérer n’importe quel code
  Heureusement, le code d’origine était déjà sans branche
  Comme toujours, il n’existe pas de critère universel pour dire si une optimisation en vaut la peine
  [0] Ici, le mot « visible » est important. Il s’agit des cas où l’on ne s’intéresse pas au code généré, mais seulement au fait que le code source ne ressemble pas à une condition
  [1] Bien sûr, ce n’était pas juste de la chance. J’imagine que quelqu’un a envoyé à IQ une « amélioration » du code shader qui paraissait évidente, mais qui était fausse

• Dans ce cas, pourquoi le compilateur n’est-il pas assez intelligent pour reconnaître que la version « optimisée » est le même code ?
  Ne devrait-il pas comprendre step() et pouvoir optimiser séparément les cas step() = 0.0 et step() == 1.0 ?
  On pourrait au moins supprimer une multiplication, donc cela semblerait en général toujours bénéfique, même si cela se transformait ensuite en chargement/stockage conditionnel ou en autre chose

  • C’est peut-être effectivement le cas
    Il est tout à fait possible que certains compilateurs effectuent ce genre d’optimisation dans certains cas, mais il est aussi clairement possible d’écrire une version que le compilateur ne comprend pas
  • Un autre problème de l’optimisation, c’est qu’elle ne doit pas prendre trop de temps à essayer toutes les possibilités
    La plupart des optimisations ont lieu côté pilote, et lorsqu’elles prennent trop de temps, cela se manifeste sous forme de saccades de compilation de shader
    Je ne peux pas dire si cette optimisation précise est réellement effectuée ou non ici, mais c’est toujours un facteur à prendre en compte

• La raison pour laquelle la version « optimisée » du problème est plus lente est que la fonction step() est en réalité implémentée de cette façon :
  float step( float x, float y ) { return x < y ? 1.0 : 0.0; }
  Comment savoir si une fonction OpenGL appelle un primitive GPU, ou si elle est émulée ?

  • La seule méthode consiste à compiler le shader, comme dans l’article d’origine, puis à le désassembler et à lire l’assembleur
    Je l’ai souvent fait avec des shaders HLSL, et j’ai beaucoup appris sur le jeu d’instructions virtuel
    Par exemple, c’est intéressant de voir que le GPU a une instruction sincos, mais que les fonctions trigonométriques inverses sont émulées à la compilation
  • Pourquoi faut-il le savoir ? Cela dépend de l’objectif
    Si la performance est importante, il peut être nécessaire de le savoir
    Mais le simple fait que step soit implémentée comme une fonction de bibliothèque basée sur la condition ci-dessus, et non comme une instruction dédiée, ne dit pas à lui seul grand-chose sur les performances par rapport à une instruction dédiée ; inutile donc de trop s’obséder sur l’implémentation elle-même
    Si c’est l’architecture GPU qui vous intéresse, regardez le désassemblage, le code des pilotes open source, LLVM et la documentation ISA
  • En dehors de fonctions qu’on verrait dans de l’assembleur façon PC, je n’ai jamais vu de primitives vraiment particulières côté GPU
    Chaque fois que j’ai regardé un shader décompilé, cela ressemblait globalement à ce qu’on imagine en C
    Une spécification comme OpenGL définit le comportement de nombreuses fonctions intégrées, et l’implémentation satisfait cette spécification à l’aide d’instructions d’assembleur standard
    Il suffit de chercher un site en ligne qui décompile pour plusieurs architectures
  • C’est une bonne question qu’on retrouve souvent en programmation en général, et c’est aussi une raison clé pour laquelle il faut mesurer d’abord avant d’optimiser
    En général, il n’est même pas nécessaire de savoir comment une fonction intégrée est implémentée, ni de s’en soucier
    Si vous vous en souciez, c’est probablement que vous pensez à l’optimisation, et dans ce cas la réponse est : « mesurez et vérifiez ce qui est meilleur »
  • Le point qui m’avait troublé semble être que le terme « branchement » a un sens mieux défini, plus dépendant du matériel, que celui que j’avais appris en grandissant
    Dans le sens que j’avais appris, un if est un branchement
    Au niveau du code machine, comme le flot de contrôle est choisi à l’exécution, un saut conditionnel est par définition un branchement
    Utiliser step() ne revient pas à transformer la logique en arithmétique, mais simplement à cacher la logique à l’intérieur d’un appel de fonction de bibliothèque
    Le fait que step() soit une fonction intégrée ou une fonction apparaissant dans un article de mathématiques n’y change rien
    En mathématiques aussi, la définition de step() est littéralement conditionnelle
    Pour vraiment optimiser sans condition, il faut choisir une fonction continue proche du résultat voulu et ajuster ses paramètres pour s’en approcher autant que possible
    En général, on choisit un polynôme, on applique une méthode d’approximation itérative standard, puis on obtient une fonction f(x) sans branchement, composée uniquement d’additions, de multiplications et de constantes « étrangement spécifiques »
    Je comprends mal l’insistance de l’auteur à affirmer qu’un déplacement conditionnel n’est pas un « branchement »
    Si abs() n’est pas une instruction GPU mais devient un modificateur d’instruction gratuit, c’est grâce à la représentation des entiers en complément à deux et à la représentation flottante IEEE-754, qui permettent de traiter le bit de signe comme le bit de poids fort
    Donc abs() se résume à forcer ce bit de poids fort à 0, ou à le masquer lors de l’instruction de lecture
    En revanche, step(), n’importe quel opérateur ternaire et, à ma connaissance, les instructions de déplacement conditionnel ne sont pas de ce type de cas particulier
    Des choses comme abs(), sqrt() ou les fonctions trigonométriques de base relèvent plus ou moins de la culture générale, et pour le reste on peut se demander si c’est vraiment important
    step() doit forcément contenir une condition quelque part, et que vous la gériez vous-même, que vous la laissiez à une bibliothèque ou au matériel ne change pas sa nature fondamentale

• Je suis déjà tombé dans ce piège
  Claude ou ChatGPT proposent aussi parfois cela comme une optimisation
  Mais à chaque fois que j’ai mesuré, les performances se sont dégradées, parfois de façon assez importante

  • Rien d’étrange à cela
    Les LLM ne font que répéter ce qui se trouve dans leur corpus d’entraînement
    Si la majorité d’Internet recommande des choses fausses comme cette « optimisation » par déplacement conditionnel, les LLM feront la même recommandation
  • Les LLM répètent ce que disent les internautes, et les internautes se trompent souvent