Making Ruby’s garbage collector copy-on-write friendly, part 2

July 28, 2007 at 10:28 am · Filed under Optimization, Ruby

The marking table now uses a set instead of a full hash table. This set implementation is based on st.c from the Ruby source distribution. I removed two fields from the hash table entry structure, so my set structure uses 8 bytes per entry instead of 16 bytes per entries (excluding malloc overhead). If you’re really curious, I changed

C
  1. struct st_table_entry {
  2.     unsigned int hash;
  3.     st_data_t key;
  4.     st_data_t record;
  5.     st_table_entry *next;
  6. };

to

C
  1. struct _PointerSetEntry {
  2.         PointerSetElement element;
  3.         PointerSetEntry *next;
  4. };

To my surprise, this didn’t save as much memory as I expected. The memory saving was only 500 KB instead of the expected 3.8 MB. :(

I later found out that a significant portion of memory is used by the bucket array in the set’s structure. So I increased the set’s default load factor from 0.75 to 2.0. This reduced memory usage in my test program from 16.5 MB to 13.5 MB! Despite collisions, the effect on performance is minimal. Increasing the load factor further doesn’t seem to save memory.

For my next attempt, I will be using a memory pool for allocating the set entries. This should reduce memory fragmentation, as well as increasing performance because allocations and frees and be done in constant time. Hopefully it will also have less memory overhead than malloc.

1 Comment »

  1. Alex said,

    July 28, 2007 @ 10:00 pm

    Good luck.

RSS feed for comments on this post · TrackBack URI

Leave a Comment