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.
- l'article en anglais, de moi, traduit par moi (que d'émoi !)
- les sources
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 
, 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 retLa 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 retLe 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 rewind (Mastodon) . É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 fasthm . Évalué à 9. Dernière modification le 23 mai 2017 à 19:47.
Ce journal présente frozen, une bibliothèque open-sourceLa 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 Gof (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 serge_sans_paille (site web personnel) . Évalué à 5.
Aucune idée. Je driais
gperf +Cintuitivement.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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.