[ruby-dev:31765] Re: packed st_table

なかだです。

At Sat, 8 Sep 2007 21:22:27 +0900,
Tanaka Akira wrote in [ruby-dev:31761]:
> 測ってみたところ、どうも 1要素の場合しかメモり節約の効果が見
> られないので調べてみたところ、以下のような修正が必要なようで

すいません、まだいろいろ途中だったようです。

> す。add_direct_packed の先頭のコードはよくわかりませんでした。

これは、iterationの途中でunpackしてしまうとなにかと不都合が起き
そうなので、単純に追加するようにしたんですが、foreachのほうで
チェックするほうがいいかもしれません。

[ruby-dev:31729]からの差分です。


diff -wU2 st.c st.c
--- st.c	(working copy)
+++ st.c	(working copy)
@@ -172,6 +172,6 @@
     tbl->type = type;
     tbl->num_entries = 0;
-    tbl->entries_packed = 1;
-    tbl->num_bins = 0;
+    tbl->entries_packed = size == ST_DEFAULT_INIT_TABLE_SIZE;
+    tbl->num_bins = tbl->entries_packed ? 0 : size;
     tbl->bins = calloc(size, sizeof(st_table_entry*));
     tbl->head = 0;
@@ -350,8 +350,5 @@
     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)) {
+    if (!PACKABLE(table, table->num_bins+r)) {
 	return 0;
     }
@@ -458,4 +455,6 @@
 
     *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*));
 
@@ -601,9 +600,10 @@
         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;
     }
@@ -639,4 +639,13 @@
             val = (st_data_t)table->bins[i+1];
             retval = (*func)(key, val, arg);
+	    if (!table->entries_packed) {
+		if ((ptr = table->head) != 0) {
+		    while (i > 0) {
+			ptr = ptr->fore;
+			i -= r;
+		    }
+		}
+		goto linked;
+	    }
             switch (retval) {
 	      case ST_CHECK:	/* check if hash is modified during iteration */
@@ -649,5 +658,5 @@
                 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;
@@ -658,4 +667,5 @@
 
     if ((ptr = table->head) != 0) {
+      linked:
 	do {
 	    end = ptr->fore == table->head;
@@ -712,4 +722,13 @@
             val = (st_data_t)table->bins[i+1];
             retval = (*func)(key, val, arg);
+	    if (!table->entries_packed) {
+		if ((ptr = table->head) != 0) {
+		    while (i > 0) {
+			ptr = ptr->fore;
+			i -= r;
+		    }
+		}
+		goto linked;
+	    }
             switch (retval) {
 	      case ST_CHECK:	/* check if hash is modified during iteration */
@@ -722,5 +741,5 @@
                 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;
@@ -732,4 +751,5 @@
     if ((ptr = table->head) != 0) {
 	ptr = ptr->back;
+      linked:
 	do {
 	    end = ptr == table->head;


-- 
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦