Journal À table !

Posté par JaguarWan le 16 janvier 2026 à 12:12. Licence CC By‑SA.

Étiquettes :

jan.

2026

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.

Performances

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 ~~diesel~~pthread. 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,

# #define public

Posté par David Demelier (site web personnel) le 16 janvier 2026 à 16:54. Évalué à 5 (+3/-0). Dernière modification le 16 janvier 2026 à 16:56.
Vraiment ?

https://github.com/RaphaelPrevost/ASKL/blob/0.3.9/lib/askl.h#L171

Non mais je veux dire, un dev C qui sait faire du C comme moi. Il s'attend à quoi en voyant une déclaration de fonction qui n'est pas du C comme :
```
public variant map_set(ASKL_LinkedMap *h, const char *k, size_t l, variant v);
```
Ça n'apporte rien à part de la confusion. Je peux comprendre le besoin de faire des export DLL, mais alors il faut nommer ça de manière explicite et surtout pas avec un mot clé réservé en C++ (qui détruit donc la compatibilité)

AI is a mental disorder
Répondre
- [^] # Re: #define public
  
  Posté par JaguarWan le 16 janvier 2026 à 17:33. É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")))).
  
  Répondre
  - [^] # Re: #define public
    
    Posté par Clément V le 16 janvier 2026 à 18:05. Évalué à 7 (+6/-0).
    Il faut mettre des majuscules comme ça on sait que c'est pas un mot-clé. Et comme tu as choisi de faire du C, le language sans espace de nom, mets aussi des préfixes partout.
```
ASKL_PUBLIC ASKL_variant ASKL_map_set(ASKL_LinkedMap *h, const char *k, size_t l, ASKL_variant v);
```
    Comme ça en plus du C++, tu prends aussi en compte toutes les autres bibliothèques C/C++ (en tout cas celles qui ne s'appellent pas ASKL).
    Répondre
  - [^] # Re: #define public
    
    Posté par David Demelier (site web personnel) le 16 janvier 2026 à 23:11. Évalué à 3 (+1/-0).
    Le __attribute__ ((visibility("hidden"))) ne fonctionne que sur les bibliothèques dynamiques. Sur le papier c'est une bonne idée de vouloir exporter que ce dont on a envie mais en pratique c'est pas vraiment réalisable. Le plus simple c'est de faire un nommage qui donne pas envie d'appeler des fonctions dont on est pas censé le faire.
    
    Exemples subjectifs :
    - askl_foo_bar (API publique)
    - askl__pas_foo_bar (API privée)
    AI is a mental disorder
    Répondre
    - [^] # Re: #define public
      
      Posté par Renault (site web personnel) le 17 janvier 2026 à 00:01. Évalué à 5 (+2/-0).
      
      L'autre solution assez courante c'est d'avoir une entête privée qui n'est incluse que par le fichier source de l'API publique.
      
      Comme ça c'est clair pour tout le monde.
      
      Répondre
      - [^] # Re: #define public
        
        Posté par David Demelier (site web personnel) le 18 janvier 2026 à 10:54. Évalué à 3 (+1/-0).
        
        Ça c'est pour cacher la déclaration des fonctions pour l'utilisateur de la bibliothèque, ça ne change pas la visibilité des symboles dans la bibliothèque ce qui était l'idée originale de l'OP je pense.
        
        Si le symbole est exporté, entête privé ou non l'utilisateur de la bibliothèque peut l'appeler et parfois c'est pas ce qu'on souhaite. Alors le visibility hidden est « utile » pour les bibliothèques dynamiques mais pas les statiques. D'où l'idée plus simple de leur donner un nom explicitement privé.
        
        AI is a mental disorder
        
        Répondre
        
        [^] # Re: #define public
        
        Posté par Renault (site web personnel) le 18 janvier 2026 à 11:23. Évalué à 5 (+2/-0).
        
        Ça c'est pour cacher la déclaration des fonctions pour l'utilisateur de la bibliothèque, ça ne change pas la visibilité des symboles dans la bibliothèque ce qui était l'idée originale de l'OP je pense.
        
        Sauf que cacher les symboles internes n'a pas je pense un grand intérêt en particulier dans une bibliothèque libre.
        
        L'important c'est de séparer clairement ce qui fait parti de l'API publique et de ce qu'il ne l'est pas pour éviter des erreurs ou des modifications de l'état interne qui peuvent perturber le reste de la bibliothèque.
        
        Donc avoir un en-tête séparé avec le suffixe _p ou _private fait le job et est assez courant en pratique.
        
        entête privé ou non l'utilisateur de la bibliothèque peut l'appeler et parfois c'est pas ce qu'on souhaite.
        
        Oui enfin dans ce cas si l'appel est fait c'est que la personne cherche explicitement à faire n'importe quoi. Est-ce grave ? L'important c'est d'éviter que cela arrive par accident par quelqu'un qui aurait mal compris l'intention de l'auteur de la bibliothèque.
        
        Répondre
        
        [^] # Re: #define public
        
        Posté par pulkomandy (site web personnel, Mastodon) le 19 janvier 2026 à 09:15. Évalué à 6 (+3/-0).
        
        Sauf que cacher les symboles internes n'a pas je pense un grand intérêt en particulier dans une bibliothèque libre.
        
        ça évite que quelqu'un utilise le même symbole dans une autre partie du code et que ça déclenche un conflit.
        
        Selon le type d'édition de lien (librairie statique ou dynamique, utilisation du "symbolic linking" ou pas, activation de la link-time optimization, dlopen, …), ça peut donner des effets différents: le symbole de la librairie est utilisé à la place de celui du programme, ou l'inverse, ou ils vivent leur vie chacun de leur côté.
        
        Il y a en plus de possibles impacts sur les performances (si un symbole est exporté et peut être remplacé, cela limite les optimisations que le compilateur peut faire).
        
        Répondre
        
        [^] # Re: #define public
        
        Posté par vincent LECOQ (site web personnel) le 23 janvier 2026 à 02:30. Évalué à 3 (+1/-0).
        
        J'ai connu il y a fort longtemps un BSD (Net peut être) dont les headers de la libc (ou de termcaps je ne sais plus) sous certaines conditions contenait une variable globale nommée 'tab'
        D'un autre coté c'était mal d'appeler une de mes variables ainsi certes, m'enfin quand même …
        
        Répondre
        
        [^] # Re: #define public
        
        Posté par JaguarWan le 18 janvier 2026 à 13:40. É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.
        
        Répondre
# Folly furieuse

Posté par JaguarWan le 16 janvier 2026 à 20:06. É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 !

Répondre
# Pointeurs étiquetés

Posté par JaguarWan le 18 janvier 2026 à 16:00. É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.

Répondre

Envoyer un commentaire

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.