[ruby-dev:31761] Re: packed st_table

In article <[e-mail]>,
  Nobuyoshi Nakada <[e-mail]> writes:

> 田中さんに「Hashの順序はどっちでもいいからこっちをやれ」といわれ
> たので、st_tableのentries_packedを一般化してみました。

測ってみたところ、どうも 1要素の場合しかメモり節約の効果が見
られないので調べてみたところ、以下のような修正が必要なようで
す。add_direct_packed の先頭のコードはよくわかりませんでした。

ST_DEFAULT_INIT_TABLE_SIZE 以外でも packed を可能にするには、
struct st_table の head のところにサイズを入れればいいはずで
すが、やってません。

--- st.c.nakada	2007-09-08 16:23:47.000000000 +0900
+++ st.c	2007-09-08 21:02:11.000000000 +0900
@@ -153,6 +153,8 @@ stat_col()
     (((r) < 3 || (st_data_t)(table)->bins[(i)+2] == (hash_val)) &&\
      EQUAL((table), (st_data_t)(table)->bins[i], (key)))
 
+static void unpack_entries(register st_table *table);
+
 st_table*
 st_init_table_with_size(const struct st_hash_type *type, int size)
 {
@@ -175,6 +177,9 @@ st_init_table_with_size(const struct st_
     tbl->num_bins = 0;
     tbl->bins = calloc(size, sizeof(st_table_entry*));
     tbl->head = 0;
+    if (size != ST_DEFAULT_INIT_TABLE_SIZE) {
+      unpack_entries(tbl);
+    }
 
     return tbl;
 }
@@ -349,10 +354,12 @@ add_direct_packed(register st_table *tab
 {
     unsigned int i;
 
+    /*
     if (table->num_bins >= ST_DEFAULT_INIT_TABLE_SIZE / r * r) {
 	table->bins = xrealloc(table->bins, sizeof(struct st_table_entry *) * (table->num_bins+r));
     }
-    else if (!PACKABLE(table, table->num_bins+r)) {
+    else */
+    if (!PACKABLE(table, table->num_bins/r+1)) {
 	return 0;
     }
     i = table->num_bins;
@@ -457,6 +464,8 @@ st_copy(st_table *old_table)
     }
 
     *new_table = *old_table;
+    if (old_table->entries_packed)
+      num_bins = ST_DEFAULT_INIT_TABLE_SIZE;
     new_table->bins = calloc(num_bins, sizeof(st_table_entry*));
 
     if (new_table->bins == 0) {
@@ -600,11 +609,12 @@ st_cleanup_safe(st_table *table, st_data
 	const unsigned int r = PACKED_RATIO(table);
         for (i = j = 0; i < table->num_bins; i += r) {
             if ((st_data_t)table->bins[i] != never && i > j) {
-		memcpy(&table->bins[j], table->bins[i],
+		memcpy(&table->bins[j], &table->bins[i],
 		       sizeof(st_table_entry *) * r);
-		j++;
+		j += r;
             }
         }
+        table->num_bins = j;
         return;
     }
 
@@ -648,7 +658,7 @@ st_foreach(st_table *table, int (*func)(
 	      case ST_DELETE:
                 table->num_entries--;
 		if (i >= (table->num_bins -= r)) return 0;
-		memmove(&table->bins[i], &table->bins[i+1],
+		memmove(&table->bins[i], &table->bins[i+r],
 			sizeof(struct st_table_entry*) * (table->num_bins-i));
                 break;
             }
@@ -721,7 +731,7 @@ st_reverse_foreach(st_table *table, int 
 	      case ST_DELETE:
                 table->num_entries--;
 		if (i >= (table->num_bins -= r)) break;
-                memmove(&table->bins[i], &table->bins[i+1],
+                memmove(&table->bins[i], &table->bins[i+r],
                         sizeof(struct st_table_entry*) * (table->num_bins-i));
                 break;
             }

で、測定結果ですが、一番効くはずの 3要素の Hash では以下のよ
うになります。

節約しないと以下のように 199Mbytes かかります。

% time ./ruby -e 'a = []; 1000000.times {|i| a << {0=>i,1=>i,2=>i} }     
print File.read("/proc/#{$$}/status")[/^VmSize.*\n/]'
VmSize:   199312 kB
./ruby -e   7.37s user 0.31s system 99% cpu 7.711 total

節約すると以下のように 105Mbytes で済みます。

% time ./ruby -e 'a = []; 1000000.times {|i| a << {0=>i,1=>i,2=>i} }     
print File.read("/proc/#{$$}/status")[/^VmSize.*\n/]'
VmSize:   105468 kB
./ruby -e   4.43s user 0.15s system 99% cpu 4.607 total

もちろん、速度も 7.7秒から 4.6秒に高速化します。

では、11word の bins からあふれて linked list に変わる 4要素
ならどうか、というと、節約しない場合は以下のようになります。

% time ./ruby -e 'a = []; 1000000.times {|i| a << {0=>i,1=>i,2=>i,3=>i} }
print File.read("/proc/#{$$}/status")[/^VmSize.*\n/]'
VmSize:   230468 kB
./ruby -e   9.09s user 0.33s system 99% cpu 9.461 total

節約した場合は以下のようになります。

% time ./ruby -e 'a = []; 1000000.times {|i| a << {0=>i,1=>i,2=>i,3=>i} }
print File.read("/proc/#{$$}/status")[/^VmSize.*\n/]'
VmSize:   230472 kB
./ruby -e   9.73s user 0.34s system 99% cpu 10.117 total

どちらも使用メモリが 230Mbytes でほぼ同じなのは予想どおりで、
速度低下は 9.5秒から 10.1秒というくらいです。

より現実的な例として REXML を... と思ったのですが、REXML は
今は character encodings differ により動かないようなので、測
定できませんでした。うぅむ。
-- 
[田中 哲][たなか あきら][Tanaka Akira]