Packed st_table

e$B$J$+$@$G$9!#e(B

e$BEDCf$5$s$K!Ve(BHashe$B$N=g=x$O$I$C$A$G$b$$$$$+$i$3$C$A$r$d$l!W$H$$$o$le(B
e$B$?$N$G!"e(Bst_tablee$B$Ne(Bentries_packede$B$r0lHL2=$7$F$_$^$7$?!#e(B

Index: st.c

— st.c (revision 13339)
+++ st.c (working copy)
@@ -61,5 +61,4 @@ static void rehash(st_table *);

#define alloc(type) (type*)malloc((size_t)sizeof(type))
-#define Calloc(n,s) (char*)calloc((n),(s))

#define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y))
== 0)
@@ -77,5 +76,5 @@ static void rehash(st_table *);
Table of prime numbers 2^n+a, 2<=n<=30.
*/
-static long primes[] = {
+static const unsigned int primes[] = {
8 + 3,
16 + 3,
@@ -110,5 +109,5 @@ static long primes[] = {

static int
-new_size(int size)
+new_size(unsigned int size)
{
int i;
@@ -120,8 +119,8 @@ new_size(int size)
return -1;
#else

  • int newsize;
  • unsigned int newsize;

    for (i = 0, newsize = MINSIZE;

  • i < (int )(sizeof(primes)/sizeof(primes[0]));
  • i < (int)(sizeof(primes)/sizeof(primes[0])) - 1;
    i++, newsize <<= 1)
    {
    @@ -146,5 +145,12 @@ stat_col()
    #endif

-#define MAX_PACKED_NUMHASH 5
+#define PACKED_RATIO(table) ((table)->type == &type_numhash ? 2 : 3)
+#define PACKED_COUNT(table, n) ((n) * PACKED_RATIO(table))
+#define PACKABLE(table, n) \

  • ((n) * PACKED_RATIO(table) <= ST_DEFAULT_INIT_TABLE_SIZE)

+#define PACKED_EQUAL(table, i, r, hash_val, key)\

  • ((® < 3 || (st_data_t)(table)->bins[(i)+2] == (hash_val)) &&\
  • EQUAL((table), (st_data_t)(table)->bins[i], (key)))
    

st_table*
@@ -161,11 +167,12 @@ st_init_table_with_size(const struct st_

 size = new_size(size);  /* round up to prime number */
  • if (size == -1) return 0;

    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->entries_packed = 1;
  • tbl->num_bins = 0;
  • tbl->bins = calloc(size, sizeof(st_table_entry*));
    tbl->head = 0;

@@ -207,8 +214,9 @@ st_clear(st_table *table)
{
register st_table_entry *ptr, *next;

  • int i;
  • unsigned int i;

    if (table->entries_packed) {
    table->num_entries = 0;

  •    table->num_bins = 0;
       return;
    

    }
    @@ -263,10 +271,12 @@ st_lookup(st_table *table, register st_d

    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;
    
  •        }
    
  •    unsigned int i, hash_val;
    
  • const unsigned int r = PACKED_RATIO(table);
  • hash_val = r > 2 ? do_hash(key, table) : key;
  • for (i = 0; i < table->num_bins; i += r) {
  •  if (PACKED_EQUAL(table, i, r, hash_val, key)) {
    
  • if (value != 0) *value = (st_data_t)table->bins[i+1];
  • return 1;
  •  }
       }
       return 0;
    

@@ -314,17 +324,45 @@ static void
unpack_entries(register st_table *table)
{

  • int i;
  • struct st_table_entry packed_bins[MAX_PACKED_NUMHASH2];
  • int num_entries = table->num_entries;
  • struct st_table_entry *packed_bins[ST_DEFAULT_INIT_TABLE_SIZE];
  • unsigned int i, num_bins = table->num_bins;
  • const unsigned int r = PACKED_RATIO(table);
  • memcpy(packed_bins, table->bins, sizeof(struct st_table_entry ) *
    num_entries
    2);
  • memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) *
    num_bins);
    table->entries_packed = 0;
    table->num_entries = 0;
  • table->num_bins = ST_DEFAULT_INIT_TABLE_SIZE;
    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]);

  • for (i = 0; i < num_bins; i += r) {
  •    st_data_t key = (st_data_t)packed_bins[i];
    
  • st_data_t value = (st_data_t)packed_bins[i+1];
  • unsigned int hash_val, bin_pos;
  • hash_val = r > 2 ? (unsigned int)packed_bins[i+2] : key;
  •    bin_pos = hash_val % table->num_bins;
    
  • ADD_DIRECT(table, key, value, hash_val, bin_pos);
    }
    }

+static int
+add_direct_packed(register st_table *table, const unsigned int r,

  •  st_data_t key, st_data_t value, unsigned int hash_val)
    

+{

  • 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)) {
  • return 0;
  • }
  • i = table->num_bins;
  • table->num_bins += r;
  • table->num_entries++;
  • table->bins[i] = (struct st_table_entry*)key;
  • table->bins[i+1] = (struct st_table_entry*)value;
  • if (r > 2) table->bins[i+2] = (struct st_table_entry*)hash_val;
  • return 1;
    +}

int
st_insert(register st_table *table, register st_data_t key, st_data_t
value)
@@ -334,20 +372,17 @@ st_insert(register st_table *table, regi

 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;
    
  •    unsigned int i, hash_val;
    
  • const unsigned int r = PACKED_RATIO(table);
  • hash_val = r > 2 ? do_hash(key, table) : key;
  •    for (i = 0; i < table->num_bins; i += r) {
    
  •  if (PACKED_EQUAL(table, i, r, hash_val, key)) {
    
  •            table->bins[i+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;
    
  • if (add_direct_packed(table, r, key, value, hash_val)) {
    return 0;
    }
  •    else {
    
  •        unpack_entries(table);
    
  •    }
    
  • unpack_entries(table);
    }

@@ -371,14 +406,11 @@ st_add_direct(st_table *table, st_data_t

 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;
    
  •    unsigned int hash_val;
    
  • const unsigned int r = PACKED_RATIO(table);
  • hash_val = r > 2 ? do_hash(key, table) : key;
  • if (add_direct_packed(table, r, key, value, hash_val)) {
    return;
    }
  •    else {
    
  •        unpack_entries(table);
    
  •    }
    
  • unpack_entries(table);
    }

@@ -392,10 +424,11 @@ rehash(register st_table *table)
{
register st_table_entry *ptr, **new_bins;

  • int i, new_num_bins;
  • unsigned int i, new_num_bins;
    unsigned int hash_val;
  • int size = new_size(table->num_bins+1);
  • new_num_bins = new_size(table->num_bins+1);
  • new_bins = (st_table_entry**)
  • xrealloc(table->bins, new_num_bins * sizeof(st_table_entry*));
  • if (size == -1) return;
  • new_num_bins = (unsigned int)size;
  • new_bins = xrealloc(table->bins, new_num_bins *
    sizeof(st_table_entry*));
    for (i = 0; i < new_num_bins; ++i) new_bins[i] = 0;
    table->num_bins = new_num_bins;
    @@ -416,5 +449,5 @@ st_copy(st_table *old_table)
    st_table *new_table;
    st_table_entry *ptr, *entry, *prev, **tail;
  • int num_bins = old_table->num_bins;
  • unsigned int num_bins = old_table->num_bins;
    unsigned int hash_val;

@@ -425,6 +458,5 @@ st_copy(st_table *old_table)

 *new_table = *old_table;
  • new_table->bins = (st_table_entry**)
  • Calloc((unsigned)num_bins, sizeof(st_table_entry*));
  • new_table->bins = calloc(num_bins, sizeof(st_table_entry*));

    if (new_table->bins == 0) {
    @@ -485,11 +517,14 @@ st_delete(register st_table *table, regi

    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];
    
  •    unsigned int i;
    
  • const unsigned int r = PACKED_RATIO(table);
  • hash_val = r > 2 ? do_hash(*key, table) : 0;
  •    for (i = 0; i < table->num_bins; i += r) {
    
  •        if (PACKED_EQUAL(table, i, r, hash_val, *key)) {
    
  •            if (value != 0) *value = (st_data_t)table->bins[i+1];
               table->num_entries--;
    
  •            memmove(&table->bins[i*2], &table->bins[(i+1)*2],
    
  •                    sizeof(struct st_table_entry*) * 
    

2*(table->num_entries-i));

  • table->num_bins -= r;
  •            memmove(&table->bins[i], &table->bins[i+r],
    
  •                    sizeof(struct st_table_entry*) * 
    

(table->num_bins-i));
return 1;
}
@@ -522,4 +557,20 @@ st_delete_safe(register st_table *table,
register st_table_entry *ptr;

  • if (table->entries_packed) {
  •    unsigned int i;
    
  • const unsigned int r = PACKED_RATIO(table);
  • hash_val = r > 2 ? do_hash(*key, table) : 0;
  •    for (i = 0; i < table->num_bins; i += r) {
    
  •        if (PACKED_EQUAL(table, i, r, hash_val, *key)) {
    
  •            if (value != 0) *value = (st_data_t)table->bins[i+1];
    
  • table->num_entries–;
  •            table->bins[i] = table->bins[i+1] = (struct 
    

st_table_entry *)never;

  •            return 1;
    
  •        }
    
  •    }
    
  •    if (value != 0) *value = 0;
    
  •    return 0;
    
  • }
  • hash_val = do_hash_bin(*key, table);
    ptr = table->bins[hash_val];
    @@ -543,5 +594,18 @@ st_cleanup_safe(st_table *table, st_data
    {
    st_table_entry *ptr, **last, *tmp;
  • int i;
  • unsigned int i;

  • if (table->entries_packed) {

  •    unsigned int j;
    
  • 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],

  •       sizeof(st_table_entry *) * r);
    
  • j++;

  •        }
    
  •    }
    
  •    return;
    
  • }

    for (i = 0; i < table->num_bins; i++) {
    @@ -565,24 +629,16 @@ st_foreach(st_table *table, int (*func)(
    st_table_entry *ptr, **last, *tmp;
    enum st_retval retval;

  • int i, end;
  • unsigned int i;

  • int end;

    if (table->entries_packed) {

  •    for (i = 0; i < table->num_entries; i++) {
    
  •        int j;
    
  • const unsigned int r = PACKED_RATIO(table);
  •    for (i = 0; i < table->num_bins; i += r) {
           st_data_t key, val;
    
  •        key = (st_data_t)table->bins[i*2];
    
  •        val = (st_data_t)table->bins[i*2+1];
    
  •        key = (st_data_t)table->bins[i];
    
  •        val = (st_data_t)table->bins[i+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:
    @@ -592,7 +648,7 @@ st_foreach(st_table *table, int (*func)(
    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--;
    
  • if (i >= (table->num_bins -= r)) return 0;
  • memmove(&table->bins[i], &table->bins[i+1],
  •  sizeof(struct st_table_entry*) * (table->num_bins-i));
               break;
           }
    

@@ -645,24 +701,17 @@ st_reverse_foreach(st_table *table, int
st_table_entry *ptr, **last, *tmp;
enum st_retval retval;

  • int i, end;
  • unsigned int i;

  • int end;

    if (table->entries_packed) {

  •    for (i = table->num_entries-1; 0 <= i; i--) {
    
  •        int j;
    
  • const unsigned int r = PACKED_RATIO(table);
  •    for (i = table->num_bins; i > 0;) {
           st_data_t key, val;
    
  •        key = (st_data_t)table->bins[i*2];
    
  •        val = (st_data_t)table->bins[i*2+1];
    
  •  i -= r;
    
  •        key = (st_data_t)table->bins[i];
    
  •        val = (st_data_t)table->bins[i+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:
    @@ -672,6 +721,7 @@ st_reverse_foreach(st_table *table, int
    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));

  • if (i >= (table->num_bins -= r)) break;
  •            memmove(&table->bins[i], &table->bins[i+1],
    
  •                    sizeof(struct st_table_entry*) * 
    

(table->num_bins-i));
break;
}

e$B$J$+$@$G$9!#e(B

At Sat, 8 Sep 2007 21:22:27 +0900,
Tanaka A. wrote in [ruby-dev:31761]:

e$BB,$C$F$$?$H$3$m!"$I$&$be(B 1e$BMWAG$N>l9g$7$+%a%b$j@aLs$N8z2L$,8+e(B
e$B$i$l$J$$$N$GD4$Y$F$
$?$H$3$m!"0J2<$N$h$&$J=$@5$,I,MW$J$h$&$Ge(B

e$B$9$$$^$;$s!"$^$@$$$m$$$mESCf$@$C$?$h$&$G$9!#e(B

e$B$9!#e(Badd_direct_packed e$B$N@hF,$N%3!<%I$O$h$/$o$+$j$^$;$s$G$7$?!#e(B

e$B$3$l$O!"e(Biteratione$B$NESCf$Ge(Bunpacke$B$7$F$7$^$&$H$J$K$+$HITET9g$,5/$-e(B
e$B$=$&$J$N$G!"C1=c$KDI2C$9$k$h$&$K$7$?$s$G$9$,!"e(Bforeache$B$N$[$&$Ge(B
e$B%A%’%C%/$9$k$[$&$,$$$$$+$b$7$l$^$;$s!#e(B

[ruby-dev:31729]e$B$+$i$N:9J,$G$9!#e(B

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;

In article [email protected],
Nobuyoshi N. [email protected] writes:

e$BEDCf$5$s$K!Ve(BHashe$B$N=g=x$O$I$C$A$G$b$$$$$+$i$3$C$A$r$d$l!W$H$$$o$le(B
e$B$?$N$G!"e(Bst_tablee$B$Ne(Bentries_packede$B$r0lHL2=$7$F$_$^$7$?!#e(B

e$BB,$C$F$$?$H$3$m!"$I$&$be(B 1e$BMWAG$N>l9g$7$+%a%b$j@aLs$N8z2L$,8+e(B
e$B$i$l$J$$$N$GD4$Y$F$
$?$H$3$m!"0J2<$N$h$&$J=$@5$,I,MW$J$h$&$Ge(B
e$B$9!#e(Badd_direct_packed
e$B$N@hF,$N%3!<%I$O$h$/$o$+$j$^$;$s$G$7$?!#e(B

ST_DEFAULT_INIT_TABLE_SIZE e$B0J30$G$be(B packed
e$B$r2DG=$K$9$k$K$O!“e(B
struct st_table e$B$Ne(B head e$B$N$H$3$m$K%5%$%:$rF~$l$l$P$$$$$O$:$Ge(B
e$B$9$,!”$d$C$F$^$;$s!#e(B

— 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;
}

e$B$G!"B,Dj7k2L$G$9$,!"0lHV8z$/$O$:$Ne(B 3e$BMWAG$Ne(B Hash
e$B$G$O0J2<$N$he(B
e$B$&$K$J$j$^$9!#e(B

e$B@aLs$7$J$$$H0J2<$N$h$&$Ke(B 199Mbytes e$B$+$+$j$^$9!#e(B

% 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

e$B@aLs$9$k$H0J2<$N$h$&$Ke(B 105Mbytes e$B$G:Q$_$^$9!#e(B

% 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

e$B$b$A$m$s!"B.EY$be(B 7.7e$BIC$+$ie(B 4.6e$BIC$K9bB.2=$7$^$9!#e(B

e$B$G$O!“e(B11word e$B$Ne(B bins e$B$+$i$”$U$l$Fe(B linked list
e$B$KJQ$o$ke(B 4e$BMWAGe(B
e$B$J$i$I$&$+!“$H$$$&$H!”@aLs$7$J$$>l9g$O0J2<$N$h$&$K$J$j$^$9!#e(B

% 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

e$B@aLs$7$?>l9g$O0J2<$N$h$&$K$J$j$^$9!#e(B

% 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

e$B$I$A$i$b;HMQ%a%b%j$,e(B 230Mbytes
e$B$G$[$\F1$8$J$N$OM=A[$I$*$j$G!"e(B
e$BB.EYDc2<$Oe(B 9.5e$BIC$+$ie(B 10.1e$BIC$H$$$&$/$i$$$G$9!#e(B

e$B$h$j8=<BE*$JNc$H$7$Fe(B REXML e$B$re(B…
e$B$H;W$C$?$N$G$9$,!"e(BREXML e$B$Oe(B
e$B:#$Oe(B character encodings differ e$B$K$h$jF0$+$J$$$h$&$J$N$G!"B,e(B
e$BDj$G$-$^$;$s$G$7$?!#$&$%$`!#e(B

In article [email protected],
Nobuyoshi N. [email protected] writes:

e$B$3$l$O!"e(Biteratione$B$NESCf$Ge(Bunpacke$B$7$F$7$^$&$H$J$K$+$HITET9g$,5/$-e(B
e$B$=$&$J$N$G!"C1=c$KDI2C$9$k$h$&$K$7$?$s$G$9$,!"e(Bforeache$B$N$[$&$Ge(B
e$B%A%'%C%/$9$k$[$&$,$$$$$+$b$7$l$^$;$s!#e(B

e$B$J$k$[$I!#$=$N>u67$O9M$($F$$$^$;$s$G$7$?!#e(B

[ruby-dev:31729]e$B$+$i$N:9J,$G$9!#e(B

2e$BMWAG$N$H$-e(B packed e$B$G$J$/$J$j$^$9!#e(B

(gdb) run -e ‘p({1=>1,2=>2})’
Starting program: /home/src/ruby/phash/phash2/ruby/ruby -e
‘p({1=>1,2=>2})’
Failed to read a valid object file image from memory.
[Thread debugging using libthread_db enabled]
[New Thread -1210640160 (LWP 18963)]
[New Thread -1211372624 (LWP 18964)]
[Switching to Thread -1210640160 (LWP 18963)]

Breakpoint 1, rb_p (obj=3083657840) at io.c:4038
4038 rb_io_write(rb_stdout, rb_obj_as_string(rb_inspect(obj)));
(gdb) p ((struct RHash)obj)->ntbl
$4 = {type = 0x81319a4, num_bins = 11, entries_packed = 0, num_entries =
2, bins = 0x8199e68, head = 0x8199e98}

@@ -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;
    }

PACKABLE e$B$NBhe(B2e$B0z?t$,LdBj$G$9$+$M!#e(B

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:31765] Re: packed st_table”
on Sun, 9 Sep 2007 17:38:29 +0900, Nobuyoshi N.
[email protected] writes:

|> e$B$9!#e(Badd_direct_packed e$B$N@hF,$N%3!<%I$O$h$/$o$+$j$^$;$s$G$7$?!#e(B
|
|e$B$3$l$O!"e(Biteratione$B$NESCf$Ge(Bunpacke$B$7$F$7$^$&$H$J$K$+$HITET9g$,5/$-e(B
|e$B$=$&$J$N$G!"C1=c$KDI2C$9$k$h$&$K$7$?$s$G$9$,!"e(Bforeache$B$N$[$&$Ge(B
|e$B%A%'%C%/$9$k$[$&$,$$$$$+$b$7$l$^$;$s!#e(B
|
|[ruby-dev:31729]e$B$+$i$N:9J,$G$9!#e(B

e$B$*G$$;$7$^$9$N$GNI$5$=$&$J;~E@$G%3%_%C%H$7$F$/$@$5$$!#e(B

e$B$J$+$@$G$9!#e(B

At Sun, 9 Sep 2007 22:50:58 +0900,
Tanaka A. wrote in [ruby-dev:31766]:

[ruby-dev:31729]e$B$+$i$N:9J,$G$9!#e(B

2e$BMWAG$N$H$-e(B packed e$B$G$J$/$J$j$^$9!#e(B

PACKABLE e$B$NBhe(B2e$B0z?t$,LdBj$G$9$+$M!#e(B

e$B$?$7$+$K!"e(BPACKED_RATIOe$B$r$+$1$A$c$$$1$^$;$s$M!#e(B

#define PACKABLE(table, n) ((n) <= ST_DEFAULT_INIT_TABLE_SIZE)

e$B$HD>$7$Fe(B[ruby-dev:31761]e$B$N%3!<%I$r;n$7$F$_$^$7$?!#e(B
st-bench3.rbe$B$,e(B3e$BMWAG!"e(Bst-bench4.rbe$B$,e(B4e$BMWAG$G$9!#e(B

./miniruby-normal st-bench3.rb
VmSize: 199740 kB

real 0m2.263s
user 0m2.104s
sys 0m0.168s

./miniruby-packed st-bench3.rb
VmSize: 105896 kB

real 0m1.261s
user 0m1.160s
sys 0m0.100s

./miniruby-normal st-bench4.rb
VmSize: 230892 kB

real 0m2.687s
user 0m2.448s
sys 0m0.248s

./miniruby-packed st-bench4.rb
VmSize: 230896 kB

real 0m2.765s
user 0m2.540s
sys 0m0.216s

3e$BMWAG$^$G$N%a%b%j@aLs$H9bB.2=$O$?$7$+$K82Cx$G$9!#BP$9$ke(B4e$BMWAG$G$Ne(B
e$BB.EYDc2<$Oe(B3%e$B<e!#e(B3%e$B$rBg$-$$$H$$k$+!"e(B3e$BMWAG$^$G$N8z2L$KBP$9$k%H%l!<e(B
e$B%I%*%U$H$
$k$+!#e(B

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:31729] packed st_table”
on Tue, 4 Sep 2007 17:43:49 +0900, Nobuyoshi N.
[email protected] writes:

|e$BEDCf$5$s$K!Ve(BHashe$B$N=g=x$O$I$C$A$G$b$$$$$+$i$3$C$A$r$d$l!W$H$$$o$le(B
|e$B$?$N$G!"e(Bst_tablee$B$Ne(Bentries_packede$B$r0lHL2=$7$F$_$^$7$?!#e(B

e$B%3!<%IFI$s$G$d$C$F$k$3$H$OM}2r$7$^$7$?!#$G!“$3$l$G$I$N$/$i$$e(B
e$B4r$7$$$s$G$7$g$&$M!#$D$^$j!“e(Bnumhashe$B$G$J$$MWAG$,e(B5e$B$D0J2<$Ne(B
st_tablee$B$,$I$l$@$1$”$k$+$H$+!”%Q%U%)!<%^%s%9>e$N>c32$OL5$$$+!"e(B
e$B$H$+$G$9$,!#e(B

In article [email protected],
Tanaka A. [email protected] writes:

e$B$h$j8=<BE*$JNc$H$7$Fe(B REXML e$B$re(B… e$B$H;W$C$?$N$G$9$,!"e(BREXML e$B$Oe(B
e$B:#$Oe(B character encodings differ e$B$K$h$jF0$+$J$$$h$&$J$N$G!"B,e(B
e$BDj$G$-$^$;$s$G$7$?!#$&$%$`!#e(B

e$B:G6a!“e(BREXML e$B$,F0$/$h$&$K$J$C$F$$$k$N$G!”;n$7$F$_$^$7$?!#e(B
(e$B$H$$$&$+!";n$7$F$b$7$g$&$,$J$$$3$H$,$o$+$C$?$H$$$&$+e(B)

RAA e$B$Ne(B all.html e$B$r$H$C$F$-$Fe(B tidy -asxml e$B$Ge(B XML
e$B$GJQ49$7$Fe(B
500kbytes e$B$/$i$$$K$J$C$?$N$re(B r13546 e$B$D$^$je(B T_OBJECT
e$B$N%Q%C%Ae(B
e$B$,$“$?$C$?>/$78e$/$i$$$Ne(B Ruby e$B$Ge(B REXML
e$B$r;H$C$F%Q!<%:$7$F$_e(B
e$B$^$7$?!#e(B
(packed st_table e$B$H$+$N%Q%C%A$O$<$s$<$s$”$F$F$^$;$se(B)

massif e$B$GF@$i$l$?%0%i%U$,e(B
http://cvs.m17n.org/~akr/diary/2007-09/r13546/massif.rexml-raa.png
e$B$G!“e(B
http://cvs.m17n.org/~akr/diary/2007-09/
e$B$K;HMQ$7$?%9%/%j%W%H$J$I$,CV$$$F$”$j$^$9!#e(B

e$B%0%i%U$r8+$k$H!"J8;zNs$,>CHq%a%b%j$NBgH>$r@j$a$F$$$^$9!#e(B

e$B$J$N$G!“%O%C%7%e$r$$$8$C$F$b$<$s$<$s8z$-$=$&$K$”$j$^$;$s!#e(B

REXML e$B$r$I$&$K$+$7$?$1$l$P!“J8;zNs$r$I$&$K$+$9$kI,MW$,$”$k$Ge(B
e$B$7$g$&!#e(B

e$BJ8;zNs$N>CHq%a%b%j$,7c$7$/?6F0$7$F$$$k$3$H$+$i$_$F!"0l;~E*$Je(B
e$BJ8;zNs$rBgNL$K@8@.$7$F$Oe(B GC e$B$G2s<}$7$F$$$k$N$G$O$J$$$+$H$$$&e(B
e$B5$$,$7$^$9!#$b$7$3$N?dB,$,@5$7$1$l$P!"0l;~E*$JJ8;zNs%*%V%8%'e(B
e$B%/%H$r$J$k$Y$/@8@.$7$J$$$h$&$K$9$k$H$$$&$N$,8z$-$=$&$G$9!#e(B