Journal Frozen - Une alternative à gperf pour les utilisateurs de C++14 fan de constexpr

Posté par  (site Web personnel) . Licence CC By‑SA.
Étiquettes :
36
22
mai
2017

Sommaire

Ce journal présente frozen, une bibliothèque open-source, à base d'en-tête qui fournit une version rapide, non-modifiable, compatible avec une utilisation dans un contexte constexpr des bien connus std::set, std::map, std::unordered_map et std::unordered_set, pour C++14. Elle peut être utilisée comme une alternative à gperf.

Introduction

J'ai toujours trouvé frustrant qu'une variable globale déclarée const std::set<int> keys = {1, 2, 3} soit initialisée à l'exécution. Gast, elle est marquée const! Ne pourrait-on pas se contenter d'une recherche dichotomique dans un tableau constant d'entiers qui logerait tranquillement dans la section .data?

Et que dire de ça : const std::unordered_set<int> keys = {4, 5, 6} ? Sac à papier, ce serait la mort de trouver une fonction de hash sans collisions pour ces trois lascars d'entiers et de l'utiliser, au lieu de sortir l'artillerie lourde ?

Et puis cette connaissance a priori devrait même rendre la recherche de clef plus rapide, non ?

En fait, il existe déjà une solution au second problème, connu sous le doux nom de perfect minimal hashing. Vous avez peut-être déjà entendu parler de gperf. Ce logiciel répond exactement au problème : prendre une liste de valeurs, trouver une fonction de hash sans collision pour ces valeurs et générer le code C qui va bien. Ça complexifie légèrement le système de build mais ça fait le taf.

Ce journal présente une bibliothèque reposant sur les constexpr de C++14, un peu d'huile de coude et les neurones d'une personne bien plus intelligente que moi pour résoudre les deux problèmes, en initialisant la structure de de donnée à la compilation obtenant ainsi une initialisation gratuite de la structure et une recherche rapide. Laissez-moi vous présenter frozen.

std::set<> et std::map<>

std::set<> et std::map<> sont des conteneurs standards qui ont juste besoin que leurs clefs soient comparables. Le standard impose (c'est d'actualité !) que la recherche se fasse en \mathcal{O}(log(n)), et l'implémentation canonique se base sur un red-black tree afin de conserver un arbre équilibré. L'accès aux données se fait par recherche dichotomique.

Pour un ensemble constant, inutile de s'embarrasser d'un red-black tree, un bête tableau trié suffit. Le constructeur, consciencieusement marqué constexpr, se charge de trier la liste d'initialisation passée en paramètre, de la stocker dans un tableau, et ensuite la méthode count est implémentée de façon standard, en étant elle aussi marquée constexpr.

Du point de vue de l'utilisateur, la déclaration de type demande juste un paramètre de taille supplémentaire, à l'instar de std::array<T, N> par rapport à std::vector<T> :

    #include <frozen/set.h>

    constexpr frozen::set<int, 3> keys = {1, 2, 3};

    int some_user(int key) {
        return keys.count(key);
    }

Comme keys est utilisé dans un contexte non constexpr par some_user, elle ne vit pas dans le monde constexpr et du code est généré. Inspectons l'assembleur résultant:

    0000000000000000 <_Z9some_useri>:
       0:    83 ff 02                 cmp    edi,0x2
       3:    7e 10                    jle    15 <_Z9some_useri+0x15>
       5:    b8 03 00 00 00           mov    eax,0x3
       a:    83 ff 03                 cmp    edi,0x3
       d:    74 0e                    je     1d <_Z9some_useri+0x1d>
       f:    31 c0                    xor    eax,eax
      11:    0f b6 c0                 movzx  eax,al
      14:    c3                       ret
      15:    0f 94 c0                 sete   al
      18:    0f b6 c0                 movzx  eax,al
      1b:    ff c0                    inc    eax
      1d:    39 f8                    cmp    eax,edi
      1f:    0f 9e c0                 setle  al
      22:    0f b6 c0                 movzx  eax,al
      25:    c3                       ret

La recherche dichotomique est finalement déroulée, et les clefs ne sont pas stockées dans un tableau mais directement passées comme opérandes. Matre !

En jouant sur des ensembles plus grands, le déroulage de boucle combiné à l'inlining continuent à marcher correctement pour nous offrir une unique fonction dont le corps commence à gonfler dangereusement, mais sans appel de fonction ni indirection.

Détails d'implémentation

La recherche dichotomique est implémentée comme une fonction récursive, spécialisée pour la taille de la vue courante. Cela permet de tirer partie de l'information de taille disponible à la compilation, et permet de dérouler complètement la recherche. La version itérative classique, à base de while, se comporte très mal dans ce cas, alors que la version récursive inlinée se comporte très bien, du moins d'après mes tests avec Clang 5. Notons toutefois que dérouler complètement la recherche pourrait s'avérer être un mauvais choix, par exemple parce que ça stresserait trop le cache d'instruction. M'enfin, ça marche bien pour les petits ensembles, donc réjouissons nous.

    template <class T, class Compare> struct LowerBound {
      T const &value;
      Compare const &compare;
      constexpr LowerBound(T const &value, Compare const &compare)
          : value(value), compare(compare) {}

      template <class ForwardIt>
      inline constexpr ForwardIt doit(ForwardIt first,
                                      std::integral_constant<std::size_t, 0>) {
        return first;
      }

      template <class ForwardIt, std::size_t N>
      inline constexpr ForwardIt doit(ForwardIt first,
                                      std::integral_constant<std::size_t, N>) {
        auto constexpr step = N / 2;
        auto it = first + step;
        if (compare(*it, value)) {
          auto constexpr next_count = N - (step + 1);
          return doit(it + 1, std::integral_constant<std::size_t, next_count>{});
        } else {
          auto constexpr next_count = step;
          return doit(first, std::integral_constant<std::size_t, next_count>{});
        }
      }
    };
    /*...*/

std::unordered_set<> et std::unordered_map<>

Le principal intérêt de la bibliothèque frozen est de proposer une version constante de std::unordered_set<> et std::unordered_map<>. Trouver une fonction de hash sans collision pour un ensemble de clefs donné est un problème bien étudié, connu comme le perfect (éventuellement minimal) hashing. Je n'ai donc rien inventé là, j'ai juste lu (et relu (et re²lu)) ce super billet qui fournit, en plus d'explications très claires, une implémentation en Python d'un algorithme de génération de telles fonctions de hash. Il m'a donc suffit d'en écrire une version constexpr et voilà.

Globalement, l'idée de base est d'utiliser une première fonction de hash, et de remplir les buckets (seaux ?) de façon classique. On trie ensuite les buckets par nombre de collision décroissant, et pour chaque seau, on va rechercher, itérativement une fonction de hash sans collision en se basant sur une autre fonction de hash paramétrée par une graine. Dès qu'on trouve une graine qui envoie chacune de nos clefs dans un slot non utilisée, on la conserve précieusement et on passe au bucket suivant. Et ainsi de suite jusqu'à ce qu'il ne reste que des bucket à un élément, sans collision donc. On les place alors dans les slots restants. Cet algorithme utilise une table auxiliaire pour stocker les graines (un silo ?) et les positions des clefs sans conflit.

En utilisant cet algorithme, il est possible de déclarer un ensemble gelé (givré ?) de la façon suivante :

    #include <frozen/unordered_set.h>

    constexpr frozen::unordered_set<int, 3> keys = {1,2,4};

    int some_user(int key) {
        return keys.count(key);
    }

Avec la garantie que l'appel à frozen::unordered_set<int, 3>::count(int) ne provoque pas de collision.

L'assembleur correspondant à la fonction some_user nous en dit plus sur l'implémentation de cet appel :

    0000000000000000 <_Z9some_useri>:
       0:    89 f8                    mov    eax,edi
       2:    83 e0 03                 and    eax,0x3
       5:    48 8b 04 c5 00 00 00     mov    rax,QWORD PTR [rax*8+0x0]
       c:    00
       d:    48 85 c0                 test   rax,rax
      10:    78 45                    js     57 <_Z9some_useri+0x57>
      12:    48 63 cf                 movsxd rcx,edi
      15:    48 31 c8                 xor    rax,rcx
      18:    48 89 c1                 mov    rcx,rax
      1b:    48 f7 d1                 not    rcx
      1e:    48 c1 e0 15              shl    rax,0x15
      22:    48 01 c8                 add    rax,rcx
      25:    48 89 c1                 mov    rcx,rax
      28:    48 c1 e9 18              shr    rcx,0x18
      2c:    48 31 c1                 xor    rcx,rax
      2f:    48 69 c1 09 01 00 00     imul   rax,rcx,0x109
      36:    48 89 c1                 mov    rcx,rax
      39:    48 c1 e9 0e              shr    rcx,0xe
      3d:    31 c1                    xor    ecx,eax
      3f:    6b c1 15                 imul   eax,ecx,0x15
      42:    89 c1                    mov    ecx,eax
      44:    c1 e9 1c                 shr    ecx,0x1c
      47:    31 c1                    xor    ecx,eax
      49:    89 c8                    mov    eax,ecx
      4b:    c1 e0 1f                 shl    eax,0x1f
      4e:    29 c8                    sub    eax,ecx
      50:    f7 d8                    neg    eax
      52:    83 e0 03                 and    eax,0x3
      55:    eb 03                    jmp    5a <_Z9some_useri+0x5a>
      57:    48 f7 d0                 not    rax
      5a:    48 8b 0c c5 00 00 00     mov    rcx,QWORD PTR [rax*8+0x0]
      61:    00
      62:    31 c0                    xor    eax,eax
      64:    39 3c 8d 00 00 00 00     cmp    DWORD PTR [rcx*4+0x0],edi
      6b:    0f 94 c0                 sete   al
      6e:    c3                       ret

Le premier and calcule un premier hash (ultra simpliste). Cela nous donne la clef pour indexer la table auxiliaire à partir de laquelle, suivant le signe de la valeur, on calculera un autre hash (en se basant sur la graine donc) ou on ira directement chercher la clef à l'index donné. Dans les deux cas, une comparaison entre l'argument et la valeur candidate est effectuée.

Le cas string

Un candidat de choix pour les clefs de frozen est… les chaînes de caractère. Et comme std::string ne peut pas être utilisé dans un environnement constexpr et que std::string_view n'est disponible qu'à partir de C++17 (avec un constructeur constexpr !), frozen fournit une classe frozen::string qui se comporte comme une vue sur des données existantes. L'operator""_s peut être utilisé pour convertir facilement une chaîne de caractère C en frozen::string.

Bonus : Utilisation dans un contexte constant

Bien que probablement très anecdotique, l'exemple suivant a au moins le mérite d'être amusant.

    constexpr frozen::unordered_set<int, 4> UnluckyNumbers = {
        4, // from china
        9, // from japan
        17, // from Italy
        13, // Triskaidekaphobia [mot découvert grâce à MTG !]
    };

    constexpr int value = ...;
    static_assert(!UnluckyNumbers.count(value), "you're program is ill-blessed in some geographical location!");

Comparaison avec gperf

L'outil gperf propose un compilateur pour générer des fonctions de hash parfaites et minimales.

Regardons cette liste de mots, au format d'entrée de gperf qui rappelle furieusement celui de lex :


    %%
    Coeus
    Crius
    Cronus
    Hyperion
    Iapetus
    Mnemosyne
    Oceanus
    Phoebe
    Rhea
    Tethys
    Theia
    Themis
    Asteria
    Astraeus
    Atlas
    Aura
    Clymene
    Dione
    Helios
    Selene
    Eos
    Epimetheus
    Eurybia
    Eurynome
    Lelantos
    Leto
    Menoetius
    Metis
    Ophion
    Pallas
    Perses
    Prometheus
    Styx
    %%

En lançant gperf titan.in > titan.c on obtient un fichier C qui contient une fonction const char * in_word_set(const char *str, unsigned int len) qui fait ce que son nom suggère.

Le code C++ code équivalent basé sur frozen serait, en utilisant frozen::string:

    #include <frozen/unordered_set.h>
    #include <frozen/string.h>

    using namespace frozen::string_literals;

    constexpr frozen::unordered_set<frozen::string> Titans = {
        "Coeus"_s, "Crius"_s, "Cronus"_s, "Hyperion"_s,
        "Iapetus"_s, "Mnemosyne"_s, "Oceanus"_s, "Phoebe"_s,
        "Rhea"_s, "Tethys"_s, "Theia"_s, "Themis"_s,
        "Asteria"_s, "Astraeus"_s, "Atlas"_s, "Aura"_s,
        "Clymene"_s, "Dione"_s, "Helios"_s, "Selene"_s,
        "Eos"_s, "Epimetheus"_s, "Eurybia"_s, "Eurynome"_s,
        "Lelantos"_s, "Leto"_s, "Menoetius"_s, "Metis"_s,
        "Ophion"_s, "Pallas"_s, "Perses"_s, "Prometheus"_s,
        "Styx"_s,
    };

Voilà un petit code de mesure de performances :

    #include <iostream>
    #include <string>
    #include <unordered_set>
    #include <chrono>

    int main() {
        const std::unordered_set<std::string> Titans = {
            "Coeus", "Crius", "Cronus", "Hyperion",
            "Iapetus", "Mnemosyne", "Oceanus", "Phoebe",
            "Rhea", "Tethys", "Theia", "Themis",
            "Asteria", "Astraeus", "Atlas", "Aura",
            "Clymene", "Dione", "Helios", "Selene",
            "Eos", "Epimetheus", "Eurybia", "Eurynome",
            "Lelantos", "Leto", "Menoetius", "Metis",
            "Ophion", "Pallas", "Perses", "Prometheus",
            "Styx",
        };

      std::string line;
      unsigned count = 0;

      std::chrono::duration<double, std::milli> duration{0};

      while(std::cin) {
        std::getline(std::cin, line);
        auto start = std::chrono::steady_clock::now();
        if(Titans.count(line))
          count += 1;
        auto stop = std::chrono::steady_clock::now();
        duration += stop - start;
      }
      std::cout << "duration: " << duration.count() << " ms" << std::endl;
      std::cout << count << std::endl;

      return 0;
    }

Certes, ce programme est plus probablement limité par les I/O qu'autre chose, mais on ne mesure que le temps de hash ce qui nous permet d'avoir une estimation du temps nécessaire pour réaliser qu'une clef n'est pas dans l'ensemble considéré.

Et voici le résultat, en utilisant /usr/share/dict/british-english-large comme jeu de test (trivia : il y a 13 noms de titans dans ce dictionnaire) :

    +--------+-------------+
    | Moteur | Temps (ms)  |
    +========+=============+
    | std    | 57          |
    +--------+-------------+
    | gperf  | 5           |
    +--------+-------------+
    | frozen | 9           |
    +--------+-------------+

Donc frozen est à portée de gperf, et tous deux sont bien plus rapides que la version de la bibliothèque standard.

Ça reste un peu frustrant. Chance, on peut changer le générateur de fonction de hash par défaut pour les chaînes (il se base sur djb2 et FNV-1a) pour améliorer la situation. La fonction par défaut est :

    template <> struct elsa<string> {
      constexpr std::size_t operator()(string value) const {
        std::size_t d = 5381;
        for (std::size_t i = 0; i < value.size; ++i)
          d = (d * 33) + value.data[i];
        return d;
      }
      constexpr std::size_t operator()(string value, std::size_t seed) const {
        std::size_t d = seed;
        for (std::size_t i = 0; i < value.size; ++i)
          d = (d * 0x01000193) ^ value.data[i];
        return d;
      }
    };

Mais dans notre cas, on peut lui préférer :

    struct olaf {
      constexpr std::size_t operator()(frozen::string value) const {
        return value.size;
      }
      constexpr std::size_t operator()(frozen::string value, std::size_t seed) const {
        std::size_t d = seed;
        std::size_t bound = std::min(value.size, (std::size_t)2);
        for (std::size_t i = 0; i < bound; ++i)
          d = (d * 0x01000193) ^ value.data[i];
        return d;
      }
    };

    constexpr frozen::unordered_set<frozen::string, 33, olaf> Titans = {...};

Ce qui nous permet d'atteindre les mêmes performances que gperf \o/. Ce générateur est cependant moins robuste que le précédent, et donc un très mauvais choix par défaut.

Conclusion

Programmer avec des constexpr dans le mode post-C++14, c'est marrant. Ça permet d'abattre le même boulot que celui d'un générateur de code sans dépendance autre qu'un compilateur C++. Et dans notre cas, le résultat est plutôt intéressant. Juste une petite note : sur ma machine, l'utilisation de frozen avec GCC se heurte à un mur d'incompréhension et un moulinage intempestif du CPU sans bonne raison apparente, il va falloir remonter le problème !

Merci

D'abord et surtout, merci à Steve Hanov pour son super article de blog.

Et puis aux copains de QuarksLab pour leur relecture du code et de la version anglaise de ces lignes !

  • # Normalisation

    Posté par  . Évalué à 10.

    En fait, tu devrais proposer ça au comité de normalisation, c'est une fonctionnalité super intéressante je trouve. En plus, comme tu as déjà une implémentation fonctionnelle et efficace, ça montre la faisabilité du concept.

  • # Précision sur la licence

    Posté par  . Évalué à 9. Dernière modification le 23/05/17 à 19:47.

    Ce journal présente frozen, une bibliothèque open-source

    La licence est Apache License 2.0, est-ce qu'avec Frozen on peut faire du logiciel libéréééééééé, délivréééééééé ?

    La gent féminine, pas la "gente", pas de "e" ! La gent féminine ! Et ça se prononce comme "gens". Pas "jante".

  • # Temps de compilation

    Posté par  (site Web personnel) . Évalué à 4.

    Joli. (J'ai moi même pensé à faire ce genre de choses)

    Qu'est-ce qui compile le plus vite ? gperf + le compilateur C, ou le code en C++ ?

    Qu'est-ce que tu entends exactement par le fait que olaf est moins robuste ?

    • [^] # Re: Temps de compilation

      Posté par  (site Web personnel) . Évalué à 5.

      Qu'est-ce qui compile le plus vite ? gperf + le compilateur C, ou le code en C++ ?

      Aucune idée. Je driais gperf +C intuitivement.

      Qu'est-ce que tu entends exactement par le fait que olaf est moins robuste ?

      C'est un bonhomme de neige, alors il fond :-)

      En vrai, cette fonction de hash a de forte chance de toujours donner des collisions, donc elle est pas assez générique (j'aurais du écrire générique plutôt que robuste)

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.