Java のように豊富なライブラリを標準で提供している開発言語を使い慣れてしまうと、ふと C に戻った時に「リストとかハッシュテーブルがないから、再実装するか...いやそれともライブラリを探してきた方がいいか...。」と嘆くこともしばしば。
そこで以前 C/C++ 言語で使用できるハッシュテーブルについて調べたものを簡単にまとめておく。
- glibc
- 言わずと知れた GNU の標準 C ライブラリ。search.h というヘッダがあり、その中にハッシュテーブルを管理できる API が提供されている。
- STL (Standard Template Library)
- C++ の標準テンプレートライブラリ。hash_map がハッシュテーブルを提供するクラス。
- GLib
- gtk+ のために設計・実装された低レベルライブラリ。GHashTable がハッシュテーブルを提供する構造体。
- Eet
- EFL に含まれるハッシュテーブルライブラリ。レジストリのように外部記憶へのシリアライズによる使用を想定しているためか IO が発生する分、他のライブラリに比べてかなり遅い。
- APR (Apache Portable Runtime)
- Apache のサポートライブラリ。ハッシュテーブルを提供する API は apr_hash* の prefix で提供される。*1
- libghthash
- 汎用ハッシュテーブルライブラリ。GLib よりもサイズがかなり小さいので静的リンクに向いてそう。
libghthash の 性能評価の頁 に簡単なベンチマークの方法が書いてあったので、そこで提供されているサンプル (libghthash, glibc, STL) に上記の他のライブラリ (GLib, Eet, APR) を追加して、実行してみた。
あと、何故か libghthash のサンプルの引数が足りずにコンパイルできなかったので、そこらへんを修正した。
int ht_init(int i_buckets, char *p_opts) { ght_fn_hash_t fn = ght_one_at_a_time_hash; int i_flags=0; /* Parse the options */ if (p_opts) { if (strcmp(p_opts, "-2") == 0) i_flags |= GHT_HEURISTICS_TRANSPOSE; else if (strcmp(p_opts, "-3") == 0) i_flags |= GHT_HEURISTICS_MOVE_TO_FRONT; else if (strcmp(p_opts, "-4") == 0) fn = ght_crc_hash; else if (strcmp(p_opts, "-5") == 0) { i_flags |= GHT_HEURISTICS_TRANSPOSE; fn = ght_crc_hash; } else if (strcmp(p_opts, "-6") == 0) { i_flags |= GHT_HEURISTICS_MOVE_TO_FRONT; fn = ght_crc_hash; } } #ifdef __CYGWIN__ if (!(p_table = ght_create(i_buckets))) #else // __CYGWIN__ if (!(p_table = ght_create(i_buckets, fn, i_flags | GHT_AUTOMATIC_REHASH))) #endif // __CYGWIN__ return -1; #ifdef __CYGWIN__ ght_set_hash(p_table, fn); ght_set_heuristics(p_table, i_flags | GHT_AUTOMATIC_REHASH); #endif // __CYGWIN__ return 0; }
GLib
#include <stdio.h> #include <glib.h> #include "bench.h" GHashTable* hashtable; void ht_usage(void) { printf("Usage:\n" "bench_glib2 dictfile textfile\n"); } int ht_init(int i_buckets, char *p_opts) { hashtable = g_hash_table_new(g_str_hash, g_str_equal); return 0; } int ht_insert(char *p_data, char *p_key) { g_hash_table_insert(hashtable, p_key, p_data); return 0; } char *ht_get(char *p_key) { return g_hash_table_lookup(hashtable, p_key); } int ht_remove(char *p_key) { return g_hash_table_remove(hashtable, p_key) ? 0 : -1; }
Eet
#include <stdio.h> #include <string.h> #include <Eet.h> #include "bench.h" Eet_File* ef; void ht_usage(void) { printf("Usage:\n" "bench_eet dictfile textfile\n"); } int ht_init(int i_buckets, char *p_opts) { eet_init(); ef = eet_open("test.eet", EET_FILE_MODE_WRITE); return 0; } int ht_insert(char *p_data, char *p_key) { eet_write(ef, p_key, p_data, strlen(p_data) + 1, 0); return 0; } char *ht_get(char *p_key) { int size; return eet_read(ef, p_key, &size); } int ht_remove(char *p_key) { return eet_delete(ef, p_key) > 0; }
APR
#include <stdio.h> #include <string.h> #include <apr_hash.h> #include "bench.h" static apr_pool_t* pool; static apr_hash_t* hash; void ht_usage(void) { printf("Usage:\n" "bench_apr dictfile textfile\n"); } int ht_init(int i_buckets, char *p_opts) { apr_initialize(); apr_pool_create(&pool, NULL); hash = apr_hash_make(pool); return 0; } int ht_insert(char *p_data, char *p_key) { apr_hash_set(hash, p_key, APR_HASH_KEY_STRING, p_data); return 0; } char *ht_get(char *p_key) { return apr_hash_get(hash, p_key, APR_HASH_KEY_STRING); } int ht_remove(char *p_key) { apr_hash_set(hash, p_key, APR_HASH_KEY_STRING, NULL); return 0; }
コンパイルと実行結果
% make all g++ -c -O3 -DNDEBUG -Wall bench_stl.cc /usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/backward/hash_map.h:59 から include されたファイル中, bench_stl.cc:28 から: /usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/backward/backward_warning.h:32:2: 警告: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting theheader for the header for C++ includes, or instead of the deprecated header . To disable this warning use -Wno-deprecated. gcc -c -O3 -DNDEBUG -Wall bench.c gcc -c -O3 -DNDEBUG -Wall bench_main.c gcc -o bench_stl.exe bench_stl.o bench.o bench_main.o -lstdc++ gcc -c -O3 -DNDEBUG -Wall bench_ght.c gcc -o bench_ght.exe bench_ght.o bench.o bench_main.o -lghthash gcc -c -O3 -DNDEBUG -Wall bench_glibc.c gcc -o bench_glibc.exe bench_glibc.o bench.o bench_main.o -lc gcc -c -O3 -DNDEBUG -Wall -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include bench_glib2.c gcc -o bench_glib2.exe bench_glib2.o bench.o bench_main.o -lglib-2.0 -lintl -liconv gcc -c -O3 -DNDEBUG -Wall bench_eet.c gcc -o bench_eet.exe bench_eet.o bench.o bench_main.o -leet -lz -ljpeg gcc -c -O3 -DNDEBUG -Wall bench_apr.c gcc -o bench_apr.exe bench_apr.o bench.o bench_main.o -lapr-0 gcc -c -O3 -DNDEBUG -Wall mean.c gcc -o mean.exe mean.o
% ./do_benchmark.sh 0drvb10.txt tarzn10.txt Running bench_glibc -0 three times to have the cache hot... 1 2 3 4 Done. Now running bench_glibc -0 10 times... 1 2 3 4 5 6 7 8 9 10 Done. The mean is 1.078333 Running bench_stl -0 three times to have the cache hot... 1 2 3 4 Done. Now running bench_stl -0 10 times... 1 2 3 4 5 6 7 8 9 10 Done. The mean is 1.478333 Running bench_glib2 -0 three times to have the cache hot... 1 2 3 4 Done. Now running bench_glib2 -0 10 times... 1 2 3 4 5 6 7 8 9 10 Done. The mean is 0.867500 Running bench_eet -0 three times to have the cache hot... 1 2 3 4 Done. Now running bench_eet -0 10 times... 1 2 3 4 5 6 7 8 9 10 Done. The mean is 3.727500 Running bench_apr -0 three times to have the cache hot... 1 2 3 4 Done. Now running bench_apr -0 10 times... 1 2 3 4 5 6 7 8 9 10 Done. The mean is 0.834167 Running bench_ght -1 three times to have the cache hot... 1 2 3 4 Done. Now running bench_ght -1 10 times... 1 2 3 4 5 6 7 8 9 10 Done. The mean is 1.180000
APR と GLib が最も速く、glibc と libghthash がそれに続く。STL は若干それらには劣り、Eet に至ってはシリアライズが目的だろうから速度は別なんだろうなという感じ。
