From: Tanaka Akira Date: 2007-08-29T08:42:03+09:00 Subject: [ruby-list:43954] Re: Hashへの生成順は保障されないのか？ In article , Yukihiro Matsumoto writes: > * 空間効率にはある程度関係があるが、ちゃんとベンチマークを > 取ってみないとなにも言えない。それでも、どれだけ重大かは > ケースバイケースだと思うけど。 > > * とはいえ、インスタンス変数やシンボルテーブルにまで順序を > 保証するのはやりすぎなので、それはやめる方向で。 思い付いたのですが、numhash の場合で、要素数が 5つ以下だった ら bins に key と value を詰めてしまうのはどうですかね。 bins は初期状態で 11 word で、numhash だと key == hash なの で hash は不要で、key と value だけを詰めれば 5つ入ります。 rdoc のケースだと、RubyToken::XXX のインスタンスが非常に多く て、それらのインスタンス変数はオブジェクトにつき 3つか 4つで す。 詰めてしまえば、それらのオブジェクトで struct st_table_entry をぜんぶ省略することができて、順序のために struct st_table_entry に追加された 2 word をなくせる、というか、そ れどころではなくメモリを節約できるはずです。なお、配列に並べ た場合は順序を表現するのにメモリ消費は不要です。 というわけで、実装して測定してみたところ、やっぱり減りました。 測定結果は http://cvs.m17n.org/~akr/diary/2007-08/13128-packed/ においてありますが、単純にメモリ量を時間で積分した結果 (グラ フの左上に書いてある値) だけを並べれば、 * 順序なし: 87,647,894,851,653 bytes x ms * 順序あり: 93,889,120,371,269 bytes x ms * 順序あり packed: 57,660,530,905,540 bytes x ms ということで、順序なしに比べても 65% 程度に減っています。まぁ、 いかに無駄にメモリを使っていたかということでしょうか。 なお、配列に並べているので線形探索ですが、整数を 5つ比較する くらいならきっとたいして遅くないに違いない、と思い込んで、速 度は測ってません。速度のオーダについていえば、5 という固定さ れた最大が決まっているので、O(1) のままです。 あと、struct st_table にフラグが必要になりますが、bitfield をつかって 1bit ひねり出して、サイズの増加を防いでいます。 そのかわり num_bins が 1bit 減っていますが、32bit マシンであ れば、(sizeof(struct st_table_entry *) が 4 なので) アドレス 空間全体のサイズの制限のほうが強く、表現に十分な bit 数が残っ ています。 Index: include/ruby/st.h =================================================================== --- include/ruby/st.h (リビジョン 13128) +++ include/ruby/st.h (作業コピー) @@ -31,7 +31,8 @@ struct st_table { const struct st_hash_type *type; - int num_bins; + unsigned int entries_packed : 1; + int num_bins : sizeof(int) * 8 - 1; int num_entries; struct st_table_entry **bins; struct st_table_entry *head; Index: st.c =================================================================== --- st.c (リビジョン 13128) +++ st.c (作業コピー) @@ -145,6 +145,8 @@ } #endif +#define MAX_PACKED_NUMHASH 5 + st_table* st_init_table_with_size(const struct st_hash_type *type, int size) { @@ -162,6 +164,7 @@ tbl = alloc(st_table); tbl->type = type; tbl->num_entries = 0; + tbl->entries_packed = type == &type_numhash && size/2 <= MAX_PACKED_NUMHASH; tbl->num_bins = size; tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); tbl->head = 0; @@ -205,6 +208,11 @@ register st_table_entry *ptr, *next; int i; + if (table->entries_packed) { + table->num_entries = 0; + return; + } + for(i = 0; i < table->num_bins; i++) { ptr = table->bins[i]; table->bins[i] = 0; @@ -253,6 +261,17 @@ unsigned int hash_val, bin_pos; register st_table_entry *ptr; + if (table->entries_packed) { + int i; + for (i = 0; i < table->num_entries; i++) { + if ((st_data_t)table->bins[i*2] == key) { + if (value !=0) *value = (st_data_t)table->bins[i*2+1]; + return 1; + } + } + return 0; + } + hash_val = do_hash(key, table); FIND_ENTRY(table, ptr, hash_val, bin_pos); @@ -291,12 +310,47 @@ table->num_entries++;\ } while (0) +static void +unpack_entries(register st_table *table) +{ + int i; + struct st_table_entry *packed_bins[MAX_PACKED_NUMHASH*2]; + int num_entries = table->num_entries; + + memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * num_entries*2); + table->entries_packed = 0; + table->num_entries = 0; + memset(table->bins, 0, sizeof(struct st_table_entry *) * table->num_bins); + for (i = 0; i < num_entries; i++) { + st_insert(table, (st_data_t)packed_bins[i*2], (st_data_t)packed_bins[i*2+1]); + } +} + int st_insert(register st_table *table, register st_data_t key, st_data_t value) { unsigned int hash_val, bin_pos; register st_table_entry *ptr; + if (table->entries_packed) { + int i; + for (i = 0; i < table->num_entries; i++) { + if ((st_data_t)table->bins[i*2] == key) { + table->bins[i*2+1] = (struct st_table_entry*)value; + return 1; + } + } + if ((table->num_entries+1) * 2 <= table->num_bins && table->num_entries+1 <= MAX_PACKED_NUMHASH) { + i = table->num_entries++; + table->bins[i*2] = (struct st_table_entry*)key; + table->bins[i*2+1] = (struct st_table_entry*)value; + return 0; + } + else { + unpack_entries(table); + } + } + hash_val = do_hash(key, table); FIND_ENTRY(table, ptr, hash_val, bin_pos); @@ -315,6 +369,19 @@ { unsigned int hash_val, bin_pos; + if (table->entries_packed) { + int i; + if ((table->num_entries+1) * 2 <= table->num_bins && table->num_entries+1 <= MAX_PACKED_NUMHASH) { + i = table->num_entries++; + table->bins[i*2] = (struct st_table_entry*)key; + table->bins[i*2+1] = (struct st_table_entry*)value; + return; + } + else { + unpack_entries(table); + } + } + hash_val = do_hash(key, table); bin_pos = hash_val % table->num_bins; ADD_DIRECT(table, key, value, hash_val, bin_pos); @@ -365,6 +432,11 @@ return 0; } + if (old_table->entries_packed) { + memcpy(new_table->bins, old_table->bins, sizeof(struct st_table_entry *) * old_table->num_bins); + return new_table; + } + if ((ptr = old_table->head) != 0) { prev = 0; tail = &new_table->head; @@ -411,6 +483,21 @@ st_table_entry **prev; register st_table_entry *ptr; + if (table->entries_packed) { + int i; + for (i = 0; i < table->num_entries; i++) { + if ((st_data_t)table->bins[i*2] == *key) { + if (value != 0) *value = (st_data_t)table->bins[i*2+1]; + table->num_entries--; + memmove(&table->bins[i*2], &table->bins[(i+1)*2], + sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); + return 1; + } + } + if (value != 0) *value = 0; + return 0; + } + hash_val = do_hash_bin(*key, table); for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) { @@ -479,6 +566,40 @@ enum st_retval retval; int i, end; + if (table->entries_packed) { + for (i = 0; i < table->num_entries; i++) { + int j; + st_data_t key, val; + key = (st_data_t)table->bins[i*2]; + val = (st_data_t)table->bins[i*2+1]; + retval = (*func)(key, val, arg); + switch (retval) { + case ST_CHECK: /* check if hash is modified during iteration */ + for (j = 0; j < table->num_entries; j++) { + if ((st_data_t)table->bins[j*2] == key) + break; + } + if (j == table->num_entries) { + /* call func with error notice */ + retval = (*func)(0, 0, arg, 1); + return 1; + } + /* fall through */ + case ST_CONTINUE: + break; + case ST_STOP: + return 0; + case ST_DELETE: + table->num_entries--; + memmove(&table->bins[i*2], &table->bins[(i+1)*2], + sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); + i--; + break; + } + } + return 0; + } + if ((ptr = table->head) != 0) { do { end = ptr->fore == table->head; @@ -525,6 +646,39 @@ enum st_retval retval; int i, end; + if (table->entries_packed) { + for (i = table->num_entries-1; 0 <= i; i--) { + int j; + st_data_t key, val; + key = (st_data_t)table->bins[i*2]; + val = (st_data_t)table->bins[i*2+1]; + retval = (*func)(key, val, arg); + switch (retval) { + case ST_CHECK: /* check if hash is modified during iteration */ + for (j = 0; j < table->num_entries; j++) { + if ((st_data_t)table->bins[j*2] == key) + break; + } + if (j == table->num_entries) { + /* call func with error notice */ + retval = (*func)(0, 0, arg, 1); + return 1; + } + /* fall through */ + case ST_CONTINUE: + break; + case ST_STOP: + return 0; + case ST_DELETE: + table->num_entries--; + memmove(&table->bins[i*2], &table->bins[(i+1)*2], + sizeof(struct st_table_entry*) * 2*(table->num_entries-i)); + break; + } + } + return 0; + } + if ((ptr = table->head) != 0) { ptr = ptr->back; do { -- [田中 哲][たなか あきら][Tanaka Akira]