klib
1.0.0
Klib는 MIT/X11 라이센스에 따라 배포되는 독립형 경량 C 라이브러리입니다. 대부분의 구성 요소는 표준 C 라이브러리를 제외하고 외부 라이브러리와 독립적이며 서로 독립적입니다. 이 라이브러리의 구성 요소를 사용하려면 라이브러리 종속성을 걱정할 필요 없이 소스 코드 트리에 파일 몇 개만 복사하면 됩니다.
Klib는 효율성과 작은 메모리 공간을 위해 노력합니다. khash.h, kbtree.h, ksort.h 및 kvec.h와 같은 일부 구성 요소는 속도와 메모리 사용 측면에서 모든 프로그래밍 언어에서 유사한 알고리즘 또는 데이터 구조를 가장 효율적으로 구현하는 것 중 하나입니다.
이 README 파일의 대부분의 정보를 포함하는 새로운 문서가 여기에서 제공됩니다.
일반 컨테이너 구현을 위해 klib는 C 매크로를 광범위하게 사용합니다. 이러한 데이터 구조를 사용하려면 일반적으로 긴 매크로를 확장하여 메서드를 인스턴스화해야 합니다. 이로 인해 소스 코드가 이상해지거나 보기 흉해 보이고 디버깅이 어려워집니다. 안타깝게도 템플릿이 없는 C의 효율적인 일반 프로그래밍을 위해서는 매크로를 사용하는 것이 유일한 솔루션입니다. 매크로를 통해서만 일단 인스턴스화되면 유형별 컨테이너와 효율성 면에서 경쟁하는 일반 컨테이너를 작성할 수 있습니다. Glib와 같은 C의 일부 일반 라이브러리는 void* 유형을 사용하여 컨테이너를 구현합니다. 이러한 구현은 일반적으로 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;
}
이 예에서 두 번째 줄은 키 유형이 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/부스트를 사용할 때 C++의 느린 컴파일 속도와 거대한 바이너리 크기가 생각날 수 있습니다. Klib는 작은 코드 크기와 구성 요소 독립성으로 인해 이 점에서 훨씬 더 좋습니다. 수백 줄의 코드를 삽입한다고 해서 컴파일이 확실히 느려지는 것은 아닙니다.
void* 사용하는 것이 비효율적인 이유에 대한 블로그 게시물입니다.kvec.h 의 성능을 평가하는 블로그 게시물입니다.khash.h 및 kbtree.h 의 성능을 평가하는 블로그 게시물입니다. 이전 버전의 벤치마크도 사용할 수 있습니다.
