Journal À table !

Bonjour Nal,

Désolé, ceci n'est pas un journal gastronomique. La table en question, c'est une table de hachage. Non, pas un billot de boucher (ni un billet de bouchot). Une vraie, écrite en C, avec un index chaîné qui conserve l’ordre d’insertion et sert de base à l’itération et au tri, comme la LinkedHashMap de Pierre Tramo, mais avec des verrous intégrés et beaucoup plus véloce. C'est cette rapidité qui m'a fait penser que ça pourrait t'intéresser.

Comme on le voit sur cette représentation graphique pour décideur pressé, malgré le poids des verrous et les chaînes aux pieds, elle tourne aussi vite que les SwissTables.

1) Dessous de table

Comme elle est sous licence CeCILL, c'est facile :

https://github.com/RaphaelPrevost/ASKL/blob/0.3.9/lib/askl_htable.c

https://github.com/RaphaelPrevost/ASKL/blob/0.3.9/lib/askl_htable.h

https://github.com/RaphaelPrevost/ASKL/blob/0.3.9/lib/arcane/htable.c

2) Je la retourne

On voit mieux les verrous, comme ça.

https://github.com/RaphaelPrevost/ASKL/blob/0.3.9/lib/askl_rwlock.c

https://github.com/RaphaelPrevost/ASKL/blob/0.3.9/lib/askl_rwlock.h

Ils sont hybrides, à la fois atomiques et dieselpthread. Mais pourquoi diable réinventer le verrou, demandera le connaisseur ? Tout simplement parce que je voulais m'amuser à permettre la promotion d'un simple verrou en lecture au grade de verrou en écriture. Ça permet de réaliser des opérations de modification ou de suppression « en passant », lorsqu'on traverse la table avec un itérateur :

    /* je veux remplacer le premier bitoniau après une clé par un bidule */
    for (it = map_at(ma_table, "clef", 4); it; it = map_next(it)) {
        if (strncmp(it->key, "clef", 4)) {
            variant bitoniau = map_set_at(it, variant_from_pointer(bidule));
            free(variant_to_pointer(bitoniau));
            /* très bien, faisons comme ça */
            it = map_break(it); break;
        }
    }

    [...]


    /* portage en C de la fonction optimisée "supprimeClefFast" (c) 2003 Pierre Tramo */
    for (it = map_each(ma_table); it; it = map_next(it)) {
        if (! strncmp(it->key, "clef", 4))
            map_remove_at(it);
    }

Le verrou en lecture est maintenu pendant la durée de vie de l'itérateur, ce qui empêche les fils d'exécution écrivains de nous tirer le tapis sous les pieds - mais ne nous empêche pas de verrouiller subrepticement en écriture, avec la coopération des autres lecteurs, le temps d'une modification ponctuelle. Impossible de faire ça sans se prendre les pieds dans le tapis avec de simples pthread_rwlocks.

3) Contre le mur

Le mur des accès mémoire bien sûr. Globalement, on s'en sort pas trop mal jusqu'à 10 millions de clés/valeurs, et on peut monter jusqu'à un facteur de charge de 90,9% sans fatiguer. Le maintien de l'index chaîné coûte 8 octets par entrée mais procure un grand confort d'utilisation, en permettant de trier dans toutes les positions et d'avoir un itérateur qui glisse tout seul. On paye encore 8 octets pour la structure variant, plus hygiénique que des pointeurs void. Au total, en comptant absolument tout, on dépense 26 octets pour chaque insertion.

4) Par tous les trous

La table utilise la technique du coucou, c'est-à-dire qu'en l'absence de place libre, on fait son trou en éjectant la clé la mieux placée. La clé ainsi outragée est aussitôt réinsérée, avec potentiellement une autre éjection à la clé si aucun emplacement n'est disponible. Ce comportement vicieux permet globalement de maintenir une bonne répartition des clés sur l'ensemble de la table.

5) Je la compile

gcc -D_ENABLE_HASHTABLE \
-O2 -std=c11 -W -Wall -Wpointer-arith -lpthread \
lib/compat/askl_compat_layer.c lib/askl_rwlock.c lib/askl_variant.c \
lib/askl_htable.c \
atable.c -o atable

Bon bah voilà Journal, ça faisait longtemps que je ne t'avais pas écrit comme ça, j'ai même dû me refaire un compte pour l'occasion. Ça fait plaisir de se retrouver autour d'une table, et c'est meilleur quand c'est partagé.

Bon Vendredi,