klib
1.0.0
Klib は、MIT/X11 ライセンスの下で配布されるスタンドアロンの軽量 C ライブラリです。標準 C ライブラリを除くほとんどのコンポーネントは外部ライブラリから独立しており、また相互に独立しています。このライブラリのコンポーネントを使用するには、ライブラリの依存関係を気にすることなく、いくつかのファイルをソース コード ツリーにコピーするだけで済みます。
Klib は効率性とメモリ使用量の削減を目指しています。 khash.h、kbtree.h、ksort.h、kvec.h などの一部のコンポーネントは、速度とメモリ使用量の両方の点で、すべてのプログラミング言語における同様のアルゴリズムまたはデータ構造の最も効率的な実装の 1 つです。
この README ファイルのほとんどの情報を含む新しいドキュメントはここから入手できます。
汎用コンテナーの実装のために、klib は C マクロを広範囲に使用します。これらのデータ構造を使用するには、通常、長いマクロを展開してメソッドをインスタンス化する必要があります。これにより、ソース コードが異常に見えたり、見苦しくなったりして、デバッグがさらに困難になります。残念ながら、テンプレートのない C で効率的な汎用プログラミングを行うには、マクロを使用することが唯一の解決策です。マクロを使用する場合のみ、インスタンス化されると効率の点で型固有のコンテナと競合する汎用コンテナを作成できます。 Glib などの C の一部の汎用ライブラリは、コンテナの実装にvoid*型を使用します。これらの実装は通常、klib よりも遅く、より多くのメモリを使用します (このベンチマークを参照)。
klib を効果的に使用するには、klib がどのように汎用プログラミングを実現するかを理解することが重要です。例としてハッシュ テーブル ライブラリを使用します。
#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;
}
この例では、2 行目で、キー タイプとしてunsigned 、値のタイプとしてchar使用してハッシュ テーブルをインスタンス化します。 m32このようなタイプのハッシュ テーブルに名前を付けます。この名前に関連付けられたすべての型と関数はマクロです。これについては後で説明します。マクロkh_init()ハッシュ テーブルを開始し、 kh_destroy()それを解放します。 kh_put()キーを挿入し、ハッシュ テーブル内のイテレータ (または位置) を返します。 kh_get()とkh_del()それぞれキーを取得し、要素を削除します。マクロkh_exist()反復子 (または位置) がデータで満たされているかどうかをテストします。
当面の疑問は、このコード部分が有効な C プログラムのように見えないことです (たとえば、セミコロンが欠如している、明らかな関数呼び出しへの代入、および明らかに未定義のm32 '変数')。コードが正しい理由を理解するために、 khash.hのソース コードをもう少し詳しく見てみましょう。そのスケルトンは次のようになります。
#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()は、すべての構造体とメソッドを定義する巨大なマクロです。このマクロが呼び出されると、マクロ内のすべてのコードが C プリプロセスによって呼び出された場所に挿入されます。マクロが複数回呼び出される場合、コードの複数のコピーが挿入されます。キーと値の型が異なるハッシュ テーブルの名前の競合を避けるために、ライブラリではトークン連結を使用します。これは、マクロのパラメーターに基づいてシンボルの一部を置き換えることができるプリプロセッサ機能です。最終的に、C プリプロセッサは次のコードを生成し、コンパイラに送ります (マクロkh_exist(h,k)は少し複雑で、わかりやすくするために拡張されていません)。
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 プログラムです。
この例から、マクロと C プリプロセッサが klib で重要な役割を果たしていることがわかります。 Klib が高速なのは、コンパイラーがコンパイル時にキーと値の型を認識し、型固有のコードと同じレベルまでコードを最適化できるためです。 void*で書かれた汎用ライブラリでは、そのようなパフォーマンスの向上は得られません。
インスタンス化時に大量のコードを挿入すると、STL/Boost 使用時の C++ のコンパイル速度の遅さとバイナリ サイズの巨大さを思い出すかもしれません。 Klib は、コード サイズが小さく、コンポーネントの独立性があるため、この点でははるかに優れています。数百行のコードを挿入しても、コンパイルが明らかに遅くなるわけではありません。
void*使用することが非効率である可能性がある理由に関するブログ投稿。kvec.hのパフォーマンスを評価するブログ投稿。khash.hとkbtree.hのパフォーマンスを評価するブログ投稿。古いバージョンのベンチマークも利用できます。
