Posté par JaguarWan .
En réponse au journal À table !.
Évalué à 3 (+3/-0).
Comme les performances décroîssent principalement à cause des accès mémoire non servis par le cache (cache misses) lorsque la table grossit, j'ai eu l'idée d'utiliser des « pointeurs étiquetés » (tagged pointers) pour éviter de déréférencer des pointeurs menant à des emplacements qui ne correspondent pas à la clé insérée/recherchée.
Le résultat est très bon, je fais maintenant jeu égal avec khash jusqu'à ~800.000 clés et abseil ne me rattrape qu'à partir de 8 millions de clés.
Posté par JaguarWan .
En réponse au journal À table !.
Évalué à 1 (+1/-0).
Oui, à la base la table de hachage fait partie d'une bibliothèque dynamique qui comprend pas mal d'autres trucs amusants, dont un crit-bit trie et un parseur JSON. Mon intention n'est pas de « cacher » les fonctions pour les utilisateurs (elles sont documentées), mais d'éviter d'exporter ces fonctions internes pour réduire la taille du binaire résultant et permettre une meilleure compilation (notamment LTO !). Il faut voir ça un peu comme static, mais à l'échelle de la bibliothèque au lieu de l'unité de compilation.
Posté par JaguarWan .
En réponse au journal À table !.
Évalué à 4 (+4/-0).
Par curiosité, je viens de mesurer de combien je me fais défoncer par Folly. Sans surprise, Folly caracole en tête, mais j'arrive à résister jusqu'à environ 200000 clés/valeurs et surtout khash réalise une remontada remarquable à 8 millions et 10 millions de clés !
Posté par JaguarWan .
En réponse au journal À table !.
Évalué à 4 (+4/-0).
+1, c'est pas faux, j'ai absolument pas pris en compte C++ quand j'ai codé ça. Je vais remplacer public et private par autre chose. Dans le contexte, public correspond aux fonctions exportées, private aux fonctions utilisées au sein de la bibliothèque mais non exportées (__attribute__((visibility("hidden")))).
# Pointeurs étiquetés
Posté par JaguarWan . En réponse au journal À table !. Évalué à 3 (+3/-0).
Comme les performances décroîssent principalement à cause des accès mémoire non servis par le cache (cache misses) lorsque la table grossit, j'ai eu l'idée d'utiliser des « pointeurs étiquetés » (tagged pointers) pour éviter de déréférencer des pointeurs menant à des emplacements qui ne correspondent pas à la clé insérée/recherchée.
Le résultat est très bon, je fais maintenant jeu égal avec khash jusqu'à ~800.000 clés et abseil ne me rattrape qu'à partir de 8 millions de clés.
[^] # Re: #define public
Posté par JaguarWan . En réponse au journal À table !. Évalué à 1 (+1/-0).
Oui, à la base la table de hachage fait partie d'une bibliothèque dynamique qui comprend pas mal d'autres trucs amusants, dont un crit-bit trie et un parseur JSON. Mon intention n'est pas de « cacher » les fonctions pour les utilisateurs (elles sont documentées), mais d'éviter d'exporter ces fonctions internes pour réduire la taille du binaire résultant et permettre une meilleure compilation (notamment LTO !). Il faut voir ça un peu comme
static, mais à l'échelle de la bibliothèque au lieu de l'unité de compilation.# Folly furieuse
Posté par JaguarWan . En réponse au journal À table !. Évalué à 4 (+4/-0).
Par curiosité, je viens de mesurer de combien je me fais défoncer par Folly. Sans surprise, Folly caracole en tête, mais j'arrive à résister jusqu'à environ 200000 clés/valeurs et surtout khash réalise une remontada remarquable à 8 millions et 10 millions de clés !
[^] # Re: #define public
Posté par JaguarWan . En réponse au journal À table !. Évalué à 4 (+4/-0).
+1, c'est pas faux, j'ai absolument pas pris en compte C++ quand j'ai codé ça. Je vais remplacer
publicetprivatepar autre chose. Dans le contexte,publiccorrespond aux fonctions exportées,privateaux fonctions utilisées au sein de la bibliothèque mais non exportées (__attribute__((visibility("hidden")))).