DivideConcept.net

le blog de divide.

FastTrigo : une bibliothèque de trigonométrie rapide

Si il y a bien un type de calcul qui revient très fréquemment dans le monde du jeu vidéo ou dans les applications techniques et scientifiques, c’est bien les fonctions trigonométriques. Dès qu’un calcul implique des vecteurs, que ce soit de la 2D, de la 3D ou même du son, ces fonctions (sin, cos, atan2 et sqrt) sont indispensables.

Malheureusement ce sont aussi des fonctions qui consomment beaucoup de temps de calcul (par rapport à une simple addition ou multiplication).
Il existe quelques approximations connues, comme le Fast inverse square root popularisé par John Carmack par exemple, mais ce genre de fonctions restent très imprécises (erreurs de 0.1% à 1%) et sont même dépassés en terme de performance par d’autres méthodes plus précises.

SpectraLayers fait énormément appels aux vecteurs et à la trigonométrie (un spectre étant intégralement composés de vecteurs 2D), je me suis donc attelé à la mise au point d’une librairie spécifique pour la version 2.
Le but de cette librairie est de gagner significativement en performance par rapport aux fonctions standard, tout en conservant un maximum de précision.

2 niveaux d’approximation sont proposés:
L’erreur maximum des fonctions FT:: varie de 0.024% à 0.06%
L’erreur maximum des fonctions FTA:: varie de 0% à 0.0007%

Une version SSE (traitement de 4 valeurs en parallèle) et Qt (pour une utilisation facile sur les classes QVector2D et QVector3D) est également proposé.

Pour les fonctions FT:: le gain en vitesse va de 2 à 8 sur Visual Studio 2012 x64 selon les fonctions et la déclinaison utilisé (normale ou SSE).
Pour les fonctions FTA:: le gain en vitesse va de 1.5 à 5 sur Visual Studio 2012 x64 selon les fonctions et la déclinaison utilisé (normale ou SSE).
Le gain peut être potentiellement plus important encore sur d’anciens compilateurs ou compilateurs x86.

La bibliothèque FastTrigo peut se télécharger ici : https://github.com/divideconcept/FastTrigo

14 commentaires pour “FastTrigo : une bibliothèque de trigonométrie rapide”

  1. Lork dit :

    Excellent, bien joué et en plus distribuée sous license libre, c’est classe.

    Juste deux toutes petites remarques:

    - Tu devrais ajouter le fichier LICENSE à ton dépôt git. Ca ne mange pas de pain et vu le nombre de licenses *bsd éviter des malentendus.

    - Enculage de mouche: en français on dit “bibliothèque” et non pas “librairie”, saloperie de faux ami.

    En tous cas c’est super, je l’utiliserai sans doute dans un prochain projet.

  2. divide dit :

    Oups, effectivement ! Faux ami corrigé.
    D’ailleurs “license” est un mot américain, en francais (et en anglais britannique) c’est “licence” ;)
    Noté pour le fichier, je vais rajouter ça au Git.
    BSD m’a paru un bon choix, à la fois répandu et très permissif, les bibliothèques LGPL et BSD m’ont bien aidés pour SpectraLayers donc à mon tour de contribuer…

  3. Lork dit :

    Ahah oui tu as raison pour l’orthographe du mot “Licence”, chacun sa déformation ;) D’ailleurs ça me fait vraiment étrange de l’écrire avec un c.

    La BSD est vraiment libre dans le sens où chacun peut décider d’implémenter le code comme bon lui semble, de façon ouverte ou non. Ca en fait couiner certains, mais c’est de la vraie liberté, on a le choix.

  4. MrHelmut dit :

    Top !

    Tu comptes la maintenir dans le seul cadre de SpectraLayers ? Parce que si tu l’étoffes avec des types et opérations à d’autres usages (je pense notamment aux Vector2,3,4, Matrix, Quaternion et les opérations associées), ce serait une pure lib optimisée pour la 3D.

  5. divide dit :

    Je veux en faire une lib le plus générique possible (par exemple j’ai rajouté le support des vecteurs 3D alors que je ne les utilise pas sur SpectraLayers).
    La prochaine extension pourrait être d’étendre à d’autres types de frameworks le support des vecteurs: pour l’instant je n’ai codé que le support pour les classes QVector2D/QVector3D de Qt, mais j’imagine qu’il y a d’autres types de classes vecteurs 2/3/4D génériques (n’hésitez pas à en suggérer).
    Je rajouterai aussi certainement une version rapide de acos dans la prochaine itération, mais à priori je m’en tiendrais aux opérations trigonométriques (les produits vectoriels et matriciels sont déjà rapides nativement).

  6. carbon14 dit :

    Bonne idée cette lib.

    Un peu la flemme de réécrire les fonctions math de base (j’avais commencé pourtant… fut un temps…) .

    Quelques questions que je m’étais posé à l’époque :
    - Que penses-tu de la représentation en entier des angles (fractions entières de 2Pi) ?
    - Idem pour l’utilisation de tables de valeurs ?
    - Tu as jeté un oeil au code généré ?

    A part ça, j’avais rencontré des difficultés pour tester mes fonctions. Je suis curieux de connaître ton protocole de test.

    Sinon reste plus que les exponentielles et deux trois trucs pour rebaptiser ta lib FastMath :)

  7. divide dit :

    J’imagine que 1/ (entiers) n’est utile que dans le cadre de 2/ (tables) et je voulais éviter autant que possible le recours à des tables. Ceci dit il faudrait que je fasse des tests de perfs, tout en sachant que le cache le plus petit (L1) d’un Core 2 Duo est de 32KB.
    Je n’ai pas regardé le code compilé, mais en ce qui concerne le portage SSE j’imagine que le code généré doit correspondre assez près aux instructions SSE utilisés, j’ai passé un certain temps à tweaker l’enchaînement des appels. A noter que les fonctions sin/cos SSE peuvent être accéléré un poil en activant un bout de code SSE4.1 désactivé par défaut (vu que le SSE4.1 n’existe que depuis les core 2 quad).
    Le protocole de test niveau valeurs est assez simple, j’ai une dizaine de valeurs random que je test et compare avec les fonctions trigonométriques standards; si ca marche c’est que j’ai rien foutu en l’air par rapport aux astuces trouvés ça et la sur différents forums.
    Pour les tests de perfs je fais tourner 20 millions de fois chaque fonction en lui faisant réutiliser ses propres valeurs de sortie en entrée, histoire que le compilateur ne s’amuse pas à zapper des appels.

  8. carbon14 dit :

    En effet, les entiers ne sont performants pour des fonctions trigo qu’avec des tables. Mais c’était les propriétés liées à cette représentation ( cyclique, linéaire ) qui m’avaient poussé à chercher de ce côté.

    Si je me souviens bien, pour sin/cos j’étais un chouïa plus performant et plus précis que le polynôme (correspondant à la config FTA) même avec des tables assez réduites.

    Par contre ça impliquait des contraintes dans l’arithmétique de base des angles et puis l’interpolation a ses limites, sans compter la table à se trimbaler. Bref j’étais arrivé à la conclusion que les entiers étaient utiles dans des cas bien spécifiques et qu’en général des flottants c’était bien mieux…

    Le code généré me sert à résoudre les cas de branching foireux, l’expansion des fonctions inline, la résolution des constantes. Le compilo a de temps en temps besoin qu’on lui explique clairement les choses. C’est devenu un réflexe pour ce genre de fonctions, du coup je pose la question.

  9. divide dit :

    A ce sujet, comment tu fais pour voir le code généré d’une fonction spécifique ?

  10. Gama dit :

    La bibliothèque a l’air de bien faire son boulot ! Par contre je serais curieux de savoir pourquoi tu as recodé un truc plutôt que d’utiliser quelque chose déjà existant (nt2, XNA maths, la vector lib d’Agner…)

  11. carbon14 dit :

    Je ne crois pas avoir vu d’option pour générer une fonction spécifique. Tu compiles un fichier source. Après pour repérer une portion de code, Visual te permets de sortir l’assembly avec le code source intercalé.

    Sinon technique du banc de test : un fichier source contenant uniquement ce qui t’intéresse.

    C’est suffisant pour mes besoins et j’ai jamais cherché plus loin.

  12. divide dit :

    Gama: Ce sont toutes des librairies généralistes qui visent à simplifier l’écriture d’opérations mathématiques, avec une bonne vitesse d’execution, mais ce n’est pas ce que je recherchais; je voulais vraiment obtenir un maximum de performances sur un petit nombre de fonctions très ciblés (sqrt, sin/cos, atan2), quitte à ne pas sortir la même précision que les fonctions ISO standards mais en restant néanmoins très proche.
    D’autre part les versions SSE de FastTrigo sont aussi basés sur les versions rapides, il ne s’agit pas juste d’un portage SIMD des sqrt/sin/cos/atan2 de base. Les librairies que tu cite (NT2, XNA, Agner..) n’ont pas l’air de mettre spécialement plus l’accent sur les fonctions trigonométriques que sur le reste (Agner précise d’ailleurs: “efficiency: poor” sur toutes les fonctions trigonométrique).

  13. neFAST dit :

    Dites les amis, vous connaissez des implémentations sse de la transformée de Hough (pour la détection de cercles) ?
    J’ai trouvé plusieurs papiers mais pas de source.

  14. divide dit :

    Je viens de faire des tests sur VS2010 x86, paradoxalement les perfs des versions non-SSE sont beaucoup plus mitigés, mais les perfs des versions SSE sont beaucoup plus importantes.
    Dans les 2 cas (VS2010 x86 et VS2012 x64) les versions FTA::SSE s’en sortent haut la main.

Laisser un commentaire

Si vous avez un compte sur WeFrag, connectez-vous pour publier un commentaire.

Vous pouvez, entre autres, utiliser les tags XHTML suivant :
<a href="" title="">...</a>,<b>...</b>,<blockquote cite="">...</blockquote>,<code>...</code>,<i>...</i>