[ruby-list:43857] Hashへの生成順は保障されないのか？

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43944] 順序が保証された Hash の同一性"
    on Sat, 25 Aug 2007 17:11:35 +0900, sheepman <sheepman@...> writes:

|Hash に順序が保証された場合、内容は同じだけど順序が違う Hash 同士の
|同一判定はどうなるんでしょうか。

順序は考慮されるべきではないと思います。

|Hash#== に順序は考慮されるべきではないと思いますが、順序も含めた
|同一性を判定するメソッドも欲しい気がします。HTML をパースして Hash
|を使って表した時とか。

良い名前がありますでしょうか。

|あと順序が保証された Hash を Marshal#dump,load したときに
|順序は保存されるかも気になります。

保存されます。

[Tanaka Akira-3]

In article <E1IOUbL-00081t-NN@x31>,
  Yukihiro Matsumoto <matz@...> 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]

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43954] Re: Hashへの生成順は保障されないのか？"
    on Wed, 29 Aug 2007 08:42:03 +0900, Tanaka Akira <akr@...> writes:

|思い付いたのですが、numhash の場合で、要素数が 5つ以下だった
|ら bins に key と value を詰めてしまうのはどうですかね。

そう来たか。予想の斜め上を行きますね。

|というわけで、実装して測定してみたところ、やっぱり減りました。

面白いのでコミットしていただけませんか？

[Tanaka Akira-3]

In article <E1IOW1g-0008Mi-Gd@x31>,
  Yukihiro Matsumoto <matz@...> writes:

> occur.rb? かなり人工的ですね。

試してみましたが、st のメモリ消費より heap のほうが多いですね。

key が String で、それぞれに少なくとも 20byte は消費するので、
struct st_table_entry が支配的になるとはいかないようです。
まぁ、2 word 増加の影響はみてとれますが。

1.8 だと、String のメモリ消費がさらに大きいせいか、全体とし
ての消費は順序つきの 1.9 よりも増えます。

もっと 2 word 増加の影響が目立つものがあるとしたら、key,
value が両方 Fixnum とかなアプリケーションですかねぇ。
--
[田中 哲][たなか あきら][Tanaka Akira]

[pegacorn-2]

 From: Yukihiro Matsumoto <matz@...>
 Date: Tue, 21 Aug 2007 14:31:20 +0900
 Message-Id: <E1INMKs-0000Eg-8t@x31>
/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

> In message "Re: [ruby-list:43894] Re: Hashへの生成順は保障されないのか？"
>     on Tue, 21 Aug 2007 14:13:45 +0900, SASADA Koichi <ko1@...> writes:
>
> |　勢いで入ってしまったんですが、「今後、Ruby では Hash は生成順に
> |iterate する」というのを仕様として定めてしまってもいいのか、ちょっと
> |不安になっています。
> |
> |　未定義だけど、たまたま実装がこうなっているのか、それとも Ruby は今
> |後生成順を保存するんですよ、というのか。
> |
> |　どうしたもんでしょうか。
>
> 当面は前者「未定義だけど、たまたま実装がこうなっている」で通
> しましょう。同じ理由でreverse_eachは導入しません。

http://svn.ruby-lang.org/repos/ruby/tags/v1_9_0_0/doc/NEWS
>     * Hash
>         o preserving item insertion order

保障することにしたのでしょうか？


--
pegacorn

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:44408] Re: Hashへの生成順は保障されないのか？"
    on Thu, 27 Dec 2007 20:53:40 +0900, pegacorn <subscriber.jp@...> writes:

|> 当面は前者「未定義だけど、たまたま実装がこうなっている」で通
|> しましょう。同じ理由でreverse_eachは導入しません。
|
|http://svn.ruby-lang.org/repos/ruby/tags/v1_9_0_0/doc/NEWS
|>     * Hash
|>         o preserving item insertion order
|
|保障することにしたのでしょうか？

「私たちの」1.9については保証します。JRubyの人たちもそうする
ことにしたそうです。

[pegacorn-2]

 From: Yukihiro Matsumoto <matz@...>
 Date: Thu, 27 Dec 2007 22:25:05 +0900
 Message-Id: <E1J7sjX-0007XR-0d@localhost>
/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 「私たちの」1.9については保証します。JRubyの人たちもそうする
> ことにしたそうです。

よくわからないのですが…

    まつもとさん達が開発・配布する Ruby 言語の処理系では保障するが、
    Ruby 言語として保障するわけではない。
    また、1.9 では保障するが、今後（2.0 以降）も保障するかは未定。

ということでしょうか？


--
pegacorn

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:44410] Re: Hashへの生成順は保障されないのか？"
    on Thu, 27 Dec 2007 23:22:32 +0900, pegacorn <subscriber.jp@...> writes:

|> 「私たちの」1.9については保証します。JRubyの人たちもそうする
|> ことにしたそうです。
|
|よくわからないのですが…
|
|    まつもとさん達が開発・配布する Ruby 言語の処理系では保障するが、
|    Ruby 言語として保障するわけではない。
|    また、1.9 では保障するが、今後（2.0 以降）も保障するかは未定。
|
|ということでしょうか？

  * Rubyの仕様という文書は存在しない
  * 他の処理系が厳密に従う義理はない

という前提条件で「言語として保証」がなにを意味するのかがそも
そも不明ですよね。とりあえず、2.0で順番を保証しなくなる予定
はないとだけ言っておきます。