Jouer au golf avec Dict
Le code golf est généralement axé sur la brièveté du code. Ce code golf sera un peu différent : il portera sur la taille du code, sa vitesse et son efficacité.
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
Classe C++ | But | API |
---|---|---|
element |
L’élément du dictionnaire. Contient une valeur de n’importe quel type. Par exemple : un entier, un double, du texte ou un autre dictionnaire. | Définir des valeurs, lire la valeur, réinitialiser l’élément, comparer des éléments, etc. |
name |
Une étiquette utilisé pour accéder aux éléments du dictionnaire. | Construire de nouveaux noms, comparer les noms. |
dict |
Le dictionnaire, indexé par noms, contenant des éléments. | Construction, ajout, suppression et accès. |
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 ?