Jouer au golf avec Dict

La question que nous allons explorer est la suivante : quelle est la vitesse d’accès maximale à un dictionnaire ?

Oui, c’est un peu bizarre comme code golf, mais soyez patient. Vous verrez, on va arriver quelque part d’intéressant. Pas nécessairement l’endroit où vous aviez prévu d’aller… mais nous y arriverons ensemble, en équipe ! Non, je plaisante. Pas besoin de travailler en équipe. Je ferai tout le travail et vous pourrez vous asseoir et me regarder.

L’ensemble du code dont nous allons parler est disponible sur GitHub.

(Notez qu’il y a plusieurs branches, “master” pour le point de départ, “fast-dict” pour le résultat final).

Les règles

Comme vous le verrez à la fin, les lois de l’univers seront bafouées. Mais cela ne veut pas dire que nous ne pouvons pas inventer nos propres lois. C’est pourquoi je vais établir des règles, la forme de base de ce à quoi le dictionnaire doit ressembler et la fonctionnalité qu’il fournira.

Je commencerai par donner une description générale de la fonctionnalité, puis je fournirai une brève déclaration en C++ de l’interface. Pour une vue complète de l’API C++, reportez-vous à la branche “master” sur GitHub. Passons maintenant à la description !

Description de haut niveau

Code C++

Je ne donnerai qu’une courte description. Vous pouvez consulter le code sur GitHub pour les détails. Le point principal qui nous intéresse est l’accès au dictionnaire, c’est donc tout ce que je vais montrer :

   // Element retrieval.
   element & operator [](const name &);
   const element & operator [](const name &) const;

Très simple, très standard. La fonction d’accès reçoit un nom et renvoie un élément. Pour aider à comprendre ce que sont les noms, voyons comment ils sont créés :

   // You need to derive from name to create a concrete name.
   // All instances of a given concrete name are equal.
   struct name
   {
      // Invalid-name, default constructor.
      name() : _name(nullptr) {}

   protected:
      // The text passed for the name by its sub-classes must be static
      // so that each address is unique.
      name(strptr n) : _name(n) {}
   };

Alors que le nom a un constructeur public par défaut, son autre constructeur est protégé. Pourquoi ? Vous verrez la raison profonde plus loin… mais cela signifie donc que toutes les instances doivent provenir de sous-classes ? Oui ! Chaque nom sera une instance d’une sous-classe de nom ! Mais quelle sous-classe ? Eh bien… toutes, bien sûr !

En fait, si vous regardez dans le repo GitHub, vous verrez que je fournis un en-tête voc.h. Cet en-tête déclare… un vocabulaire de noms. Comme il a été suggéré plus tôt, chaque nom réel est une sous-classe… une sous-classe différente pour chaque nom distinct ! Le fichier se présente comme ceci :

   namespace voc
   {
      #define MAKE_NAME(n) struct n ## _n : dak::name { n ## _n() : name(L ## #n) {} };

      MAKE_NAME(apple);
      MAKE_NAME(person);
      // etc…

      const apple_n apple;
      const person_n person;
   }

La classe d’éléments elle-même est une classe simple qui peut contenir une valeur de n’importe quel type commun. Elle n’a rien de particulier. Il serait bon que vous réfléchissiez à la vitesse à laquelle vous pourriez réaliser une telle interface de dictionnaire. Vous pouvez prendre comme point de départ la branche “master” de GitHub. S’agira-t-il de N log N ? N ?, log N ? Temps constant ? Plus rapide ? Attendez, plus rapide que le temps constant ? Qu’est-ce que cela signifierait ?

Les plis

Maintenant que nous avons établi les règles, il est temps de les plier à notre avantage. Bien sûr, comme avec tout bon arnaqueur, les règles ont été soigneusement pensées pour donner l’avantage à la maison.

Il y a notamment une bonne raison derrière la conception de la classe de noms. Vous voyez, le fait d’avoir différents types pour différents noms nous permet de subvertir le système de types C++ à notre avantage. En particulier… nous pouvons subvertir le mécanisme de surcharge des fonctions !

Souvenez-vous des fonctions d’accès aux éléments ? Que se passerait-il s’ils étaient surchargés ?

   // Element retrieval.
   element & operator [](const name &);
   const element & operator [](const name &) const;

   // Overload!!!
   inline element& operator [](const voc::rock_n&)
   inline const element& operator [](const voc::rock_n&) const

Cela signifie que nous pouvons retourner l’élément sans avoir à le chercher ! Une tricherie totale ! Mais comment retrouver l’élément si le voc::rock est accessible par la version prenant un nom simple et non un voc::rock ? Comment les éléments du dict pourraient-ils être trouvés lors d’une itération normale ? Facile ! Nous créons des éléments proxy dans la map du dictionnaire, chaque proxy reporte tout son comportement sur la copie à accès direct. En gros, nous ajoutons quelques fonctions à la classe d’éléments pour enregistrer s’il s’agit d’un proxy. Nous ajoutons également une fonction à la classe dict pour enregistrer chaque élément proxy et l’élément d’accès direct auquel il se réfère.

   struct dict
   {
   protected:
      std::map _elements;

      // Sub-classes call this during construction
      // to add the permanent proxy elements.
      void add_permanent_proxy(const name& n, element &);
   };

   struct element
   {
      bool is_proxy() const;
      bool is_permanent() const;
   };

Le résultat est que nous pouvons accéder aux éléments de notre choix au moment de la compilation ! Il suffit de sous-classer la classe dict et d’ajouter les éléments proxy qui seront accessibles sous les noms de votre choix. La classe résultante agit comme un dict, et peut être utilisée partout où un dict peut se trouver, mais si vous connaissez le véritable type de dict et le véritable nom auquel vous voulez accéder, vous obtenez un accès à la compilation grâce à l’inlining et à la surcharge des fonctions.

La torsion

Dans le domaine de la folie, nous ne nous satisferions pas de cette médiocre ruse. Cette subversion ne va pas assez loin. Nous voulons plus de vitesse ! Nous avons un accès en temps réel à notre élément, mais nous voulons un accès en temps réel à la valeur contenue dans l’élément. Est-ce même possible ? Mais oui, c’est possible !

Le tour de passe-passe que nous utiliserons consiste à sous-classer la classe d’éléments, où réside la valeur. Si nous connaissons à l’avance le type de la valeur que nous voulons conserver sous un nom, nous pouvons l’obliger à toujours avoir ce type, à être connu au moment de la compilation. Connaître le type de la valeur que nous voulons conserver sous un nom spécifique n’est pas inhabituel, c’est même typique ! C’est ainsi que nous concevons les classes, les schémas et les bases de données après tout.

Voici donc un exemple typique de cette sous-classification. (Voir la branche “fast-dict” sur GitHub pour toutes les variations fournies) :

   struct eint64 : element
   {
      operator int64&() { return _i; }
      // etc...
   };

Comme on peut le voir, elle peut inliner l’accès à la valeur réelle contenue dans l’élément. Notre sous-classe dict peut maintenant renvoyer un tel eint64 dans sa fonction surchargée d’accès à l’élément, et offrir un accès complet à la valeur directe en temps de compilation ! Comme ceci :

      inline eint64& operator [](const voc::rock_n&) { return _rock; }
      inline const eint64& operator [](const voc::rock_n&) const { return _rock; }

Pour supporter les sous-classes de l’élément, une fonction supplémentaire est ajoutée à l’élément pour lui faire savoir que le type de valeur est désormais fixe :

      bool is_fixed() const { return _fixed == fixedtype::fixed; }

La preuve

Mais je ne me contente pas de prétendre qu’il s’agit d’un accès en temps de compilation, je le prouve ! Pas seulement le prouver, mais le comparer à un accès à une structure pure. C’est exact ! Alors que la sous-classe du dictionnaire avec ses fonctions surchargées peut être utilisée comme un dict normal, et que tous ses éléments, y compris les éléments permanents, proxy, typés peuvent être trouvés par recherche normale ou par itération, elle est tout aussi rapide qu’une structure brute ! Tout aussi rapide que ceci :

   struct rock_struct
   {
      int64 rock = 42;
   };

Dans la branche “fast-dict”, il existe des tests unitaires, et parmi eux deux tests fictifs qui ont été utilisés uniquement pour comparer la génération du code du sous-dict et de la structure. J’ai capturé le code assembleur des deux, et voici le résultat et comme nous l’avons prétendu, chacun est aussi rapide que l’autre !

        d1.rock = rand();
call        qword ptr [rand]  
movsxd      rcx,eax  
mov         qword ptr [rsp+38h],rcx  
       use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

       std::wcout << d1.rock;
mov         rbx,qword ptr [d1]  
mov         rcx,qword ptr [std::wcout]  
mov         rdx,rbx  
call        qword ptr [operator<<]  

       d1.rock += rand();
call        qword ptr [rand]  
movsxd      rcx,eax  
add         rbx,rcx  
       use_rock(d1);
lea         rcx,[d1]  
mov         qword ptr [d1],rbx  
call        dak::use_rock

       std::wcout << d1.rock;
mov         rdx,qword ptr [d1]  
mov         rcx,qword ptr [std::wcout]  
call        qword ptr [operator<<]  

       use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

        d1[voc::rock] = rand();
call        qword ptr [rand]  
movsxd      rcx,eax  
mov         qword ptr [rsp+38h],rcx  
        use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

        std::wcout << d1[voc::rock];
lea         rdx,[rsp+38h]  
mov         rcx,qword ptr [std::wcout]  
call        dak::operator<<

        d1[voc::rock] += rand();
call        qword ptr [rand]  
add         eax,dword ptr [rsp+38h]  
movsxd      rcx,eax  
mov         qword ptr [rsp+38h],rcx  
        use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

        std::wcout << d1[voc::rock];
lea         rdx,[rsp+38h]  
mov         rcx,qword ptr [std::wcout]  
call        dak::operator<<

        use_rock(d1);
lea         rcx,[d1]  
call        dak::use_rock

Conclusion

Nous nous sommes mis en route sur le terrain de golf, en explorant l’accès au dictionnaire et en essayant de voir jusqu’où nous pourrions descendre sur le parcours. Et là, nous sommes allés très bas !

Mais je vous sens tendu, confus et choqué.

C’est une parodie de design, une abomination ! Dériver d’une classe dict ? Dériveriez-vous d’un std::vector, d’une std::map, d’une std::pair ? Quel genre de programmeur respectable ferait cela ? Et je serais d’accord ! (Attendez, quoi ? Qui a dit ça ?) Non, non, non, non, je serais vraiment d’accord ! Je le serais, je le serais, je le serais, sauf que…

… voyez-vous, tout dans la vie est une question de perspective. Tout tient dans la façon de percevoir le monde. Et dans la programmation, la perception est souvent une question de noms. Les noms de types, les noms de fonctions, les noms de variables. Qu’est donc qu’un nom ? Les noms façonnent notre vision du monde et, à une échelle plus humble, nos designs. Alors… et si je vous disais que dict n’est pas le vrai nom de la classe ? Que se passerait-il si nous le renommions… objet ?

Ah, l’illumination finale ! Oui, maintenant il est logique de dériver d’objet. Maintenant, il est logique que nous ajoutions des éléments permanents fixes à un objet pour qu’il contienne des valeurs de type fixe ! Ce n’est même plus un design surprenant. C’est essentiellement la façon dont un langage comme Python fonctionne sous les couvertures. En Python, chaque objet de chaque classe n’est en fait qu’un dictionnaire de valeurs indexées par des noms. Et maintenant, vous pouvez le faire directement en C++.

C’est aussi très utile. Vous n’avez plus besoin d’écrire et de réécrire du code passe-partout pour chaque structure et chaque classe. Vous pouvez avoir une seule implémentation pour tous les types, pour des choses comme la sérialisation, l’annulation/rétablissement, la recherche de données, la connexion à des éléments de l’interface utilisateur et diverses autres activités que vous pouvez sûrement imaginer. Vous l’écrivez une fois pour la classe objet dict. Chaque sous-classe hérite de l’implémentation de l’objet et toutes les données sont toujours accessibles par simple itération sur des éléments ou par recherche de nom.

N’est-ce pas fantastique ? Alors, sommes-nous arrivés à un endroit qui méritait d’être vu ?