klib
1.0.0
Klib est une bibliothèque C autonome et légère distribuée sous licence MIT/X11. La plupart des composants sont indépendants des bibliothèques externes, à l'exception de la bibliothèque C standard, et indépendants les uns des autres. Pour utiliser un composant de cette bibliothèque, il vous suffit de copier quelques fichiers dans votre arborescence de code source sans vous soucier des dépendances de la bibliothèque.
Klib vise l'efficacité et une faible empreinte mémoire. Certains composants, tels que khash.h, kbtree.h, ksort.h et kvec.h, comptent parmi les implémentations les plus efficaces d'algorithmes ou de structures de données similaires dans tous les langages de programmation, à la fois en termes de vitesse et d'utilisation de la mémoire.
Une nouvelle documentation est disponible ici qui comprend la plupart des informations contenues dans ce fichier README.
Pour l'implémentation de conteneurs génériques, klib utilise largement les macros C. Pour utiliser ces structures de données, nous devons généralement instancier des méthodes en développant une longue macro. Cela donne au code source un aspect inhabituel, voire laid, et ajoute des difficultés au débogage. Malheureusement, pour une programmation générique efficace en C dépourvue de modèle, l'utilisation de macros est la seule solution. Ce n'est qu'avec les macros que nous pouvons écrire un conteneur générique qui, une fois instancié, rivalise en efficacité avec un conteneur spécifique à un type. Certaines bibliothèques génériques en C, comme Glib, utilisent le type void* pour implémenter des conteneurs. Ces implémentations sont généralement plus lentes et utilisent plus de mémoire que klib (voir ce benchmark).
Pour utiliser efficacement klib, il est important de comprendre comment il réalise une programmation générique. Nous utiliserons la bibliothèque de tables de hachage comme exemple :
#include "khash.h"
KHASH_MAP_INIT_INT(m32, char) // instantiate structs and methods
int main() {
int ret, is_missing;
khint_t k;
khash_t(m32) *h = kh_init(m32); // allocate a hash table
k = kh_put(m32, h, 5, &ret); // insert a key to the hash table
if (!ret) kh_del(m32, h, k);
kh_value(h, k) = 10; // set the value
k = kh_get(m32, h, 10); // query the hash table
is_missing = (k == kh_end(h)); // test if the key is present
k = kh_get(m32, h, 5);
kh_del(m32, h, k); // remove a key-value pair
for (k = kh_begin(h); k != kh_end(h); ++k) // traverse
if (kh_exist(h, k)) // test if a bucket contains data
kh_value(h, k) = 1;
kh_destroy(m32, h); // deallocate the hash table
return 0;
}
Dans cet exemple, la deuxième ligne instancie une table de hachage avec unsigned comme type de clé et char comme type de valeur. m32 nomme un tel type de table de hachage. Tous les types et fonctions associés à ce nom sont des macros, qui seront expliquées plus tard. La macro kh_init() initie une table de hachage et kh_destroy() la libère. kh_put() insère une clé et renvoie l'itérateur (ou la position) dans la table de hachage. kh_get() et kh_del() obtiennent respectivement une clé et suppriment un élément. La macro kh_exist() teste si un itérateur (ou une position) est rempli de données.
Une question immédiate est que ce morceau de code ne ressemble pas à un programme C valide (par exemple, manquant de point-virgule, d'affectation à un appel de fonction apparent et de « variable » m32 apparemment non définie). Pour comprendre pourquoi le code est correct, allons un peu plus loin dans le code source de khash.h , dont le squelette ressemble à :
#define KHASH_INIT(name, SCOPE, key_t, val_t, is_map, _hashf, _hasheq)
typedef struct {
int n_buckets, size, n_occupied, upper_bound;
unsigned *flags;
key_t *keys;
val_t *vals;
} kh_##name##_t;
SCOPE inline kh_##name##_t *init_##name() {
return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t));
}
SCOPE inline int get_##name(kh_##name##_t *h, key_t k)
...
SCOPE inline void destroy_##name(kh_##name##_t *h) {
if (h) {
free(h->keys); free(h->flags); free(h->vals); free(h);
}
}
#define _int_hf(key) (unsigned)(key)
#define _int_heq(a, b) (a == b)
#define khash_t(name) kh_##name##_t
#define kh_value(h, k) ((h)->vals[k])
#define kh_begin(h, k) 0
#define kh_end(h) ((h)->n_buckets)
#define kh_init(name) init_##name()
#define kh_get(name, h, k) get_##name(h, k)
#define kh_destroy(name, h) destroy_##name(h)
...
#define KHASH_MAP_INIT_INT(name, val_t)
KHASH_INIT(name, static, unsigned, val_t, is_map, _int_hf, _int_heq)
KHASH_INIT() est une énorme macro définissant toutes les structures et méthodes. Lorsque cette macro est appelée, tout le code qu'elle contient sera inséré par le préprocessus C à l'endroit où elle est appelée. Si la macro est appelée plusieurs fois, plusieurs copies du code seront insérées. Pour éviter les conflits de noms des tables de hachage avec différents types clé-valeur, la bibliothèque utilise la concaténation de jetons, qui est une fonctionnalité du préprocesseur grâce à laquelle nous pouvons remplacer une partie d'un symbole en fonction du paramètre de la macro. En fin de compte, le préprocesseur C générera le code suivant et le transmettra au compilateur (la macro kh_exist(h,k) est un peu complexe et n'est pas développée pour des raisons de simplicité) :
typedef struct {
int n_buckets, size, n_occupied, upper_bound;
unsigned *flags;
unsigned *keys;
char *vals;
} kh_m32_t;
static inline kh_m32_t *init_m32() {
return (kh_m32_t*)calloc(1, sizeof(kh_m32_t));
}
static inline int get_m32(kh_m32_t *h, unsigned k)
...
static inline void destroy_m32(kh_m32_t *h) {
if (h) {
free(h->keys); free(h->flags); free(h->vals); free(h);
}
}
int main() {
int ret, is_missing;
khint_t k;
kh_m32_t *h = init_m32();
k = put_m32(h, 5, &ret);
if (!ret) del_m32(h, k);
h->vals[k] = 10;
k = get_m32(h, 10);
is_missing = (k == h->n_buckets);
k = get_m32(h, 5);
del_m32(h, k);
for (k = 0; k != h->n_buckets; ++k)
if (kh_exist(h, k)) h->vals[k] = 1;
destroy_m32(h);
return 0;
}
C'est le programme C que nous connaissons.
A partir de cet exemple, nous pouvons voir que les macros et le préprocesseur C jouent un rôle clé dans klib. Klib est rapide en partie parce que le compilateur connaît le type clé-valeur au moment de la compilation et est capable d'optimiser le code au même niveau que le code spécifique au type. Une bibliothèque générique écrite avec void* n'obtiendra pas une telle amélioration des performances.
L'insertion massive de code lors de l'instanciation peut nous rappeler la lenteur de compilation du C++ et l'énorme taille binaire lorsque STL/boost est utilisé. Klib est bien meilleur à cet égard en raison de sa petite taille de code et de son indépendance des composants. L'insertion de plusieurs centaines de lignes de code ne ralentira évidemment pas la compilation.
void* pour la programmation générique peut être inefficace.kvec.h .khash.h et kbtree.h parmi de nombreuses autres implémentations. Une ancienne version du benchmark est également disponible.
