struct st_table_entry {
    unsigned int hash;
    st_data_t key;
    st_data_t record;
    st_table_entry *next;
};

Those are 4 fields, 4 bytes each, so the size of the struct is 16 bytes. The remaining 8 bytes are malloc() memory management overhead. Since the marking table only needs a set (and not a full hash table), one can save memory by removing the ‘record’ (value) field. The ‘hash’ field also seems redundant. So by modifying st.c I can save 8 bytes per entry, though porting Google sparse_hash is probably even more efficient. And yes, malloc overhead can be solved by using a memory pool.

Perl and Python use reference counting, so they are not affected by this problem. (Though instead they have other problems, like circular references.) The Sun JVM implementation uses generational garbage collection (a modified form of mark-and-sweep) as far as I know. I’m guessing JRuby uses JVM’s garbage collection.
Java is not at all affected by this problem. I’m not sure how copy-on-write friendly the Sun JVM is, but Java apps cannot fork and don’t need fork, because Java apps cannot corrupt memory and because Java has excellent threading support. When a Java thread crashes, the others are unaffected.

If malloc is the primary driver of this, how about chunking the table, much like Ruby does: e.g. the first time an entry is required, 100kb is put aside for it; the next chunk could be double etc..

Otherwise, this is a problem which must have been overcome before- what does Perl/Python/Java (JRuby?) do??

This is really interesting stuff- Ruby/Mongrel is quite intensive on memory, and this could be a winner.

Sure, here’s the pmap output just after forking:

13639:   ./trunk/ruby test.rb
Address   Kbytes Mode  Offset           Device    Mapping
08048000     712 r-x-- 0000000000000000 008:00006 ruby
080fa000       4 rw--- 00000000000b2000 008:00006 ruby
080fb000   16828 rw--- 00000000080fb000 000:00000   [ anon ]
b714b000    7160 rw--- 00000000b714b000 000:00000   [ anon ]
b7849000    2104 rw--- 00000000b7bdd000 000:00000   [ anon ]
b7c45000    1188 rw--- 00000000b7c45000 000:00000   [ anon ]
b7d6e000    1260 r-x-- 0000000000000000 008:00011 libc-2.5.so
b7ea9000       4 r---- 000000000013b000 008:00011 libc-2.5.so
b7eaa000       8 rw--- 000000000013c000 008:00011 libc-2.5.so
b7eac000      12 rw--- 00000000b7eac000 000:00000   [ anon ]
b7eaf000     148 r-x-- 0000000000000000 008:00011 libm-2.5.so
b7ed4000       8 rw--- 0000000000024000 008:00011 libm-2.5.so
b7ed6000       4 rw--- 00000000b7ed6000 000:00000   [ anon ]
b7ed7000      20 r-x-- 0000000000000000 008:00011 libcrypt-2.5.so
b7edc000       8 rw--- 0000000000004000 008:00011 libcrypt-2.5.so
b7ede000     156 rw--- 00000000b7ede000 000:00000   [ anon ]
b7f05000       8 r-x-- 0000000000000000 008:00011 libdl-2.5.so
b7f07000       8 rw--- 0000000000001000 008:00011 libdl-2.5.so
b7f1f000      16 rw--- 00000000b7f1f000 000:00000   [ anon ]
b7f23000     100 r-x-- 0000000000000000 008:00011 ld-2.5.so
b7f3c000       8 rw--- 0000000000019000 008:00011 ld-2.5.so
bffa4000      84 rw--- 00000000bffa4000 000:00000   [ stack ]
ffffe000       4 r-x-- 0000000000000000 000:00000   [ anon ]
mapped: 29852K    writeable/private: 27596K    shared: 0K

And this is the output after garbage collection:

13639:   ./trunk/ruby test.rb
Address   Kbytes Mode  Offset           Device    Mapping
08048000     712 r-x-- 0000000000000000 008:00006 ruby
080fa000       4 rw--- 00000000000b2000 008:00006 ruby
080fb000   18940 rw--- 00000000080fb000 000:00000   [ anon ]
b714b000    7160 rw--- 00000000b714b000 000:00000   [ anon ]
b7849000    2104 rw--- 00000000b7bdd000 000:00000   [ anon ]
b7c45000    1188 rw--- 00000000b7c45000 000:00000   [ anon ]
b7d6e000    1260 r-x-- 0000000000000000 008:00011 libc-2.5.so
b7ea9000       4 r---- 000000000013b000 008:00011 libc-2.5.so
b7eaa000       8 rw--- 000000000013c000 008:00011 libc-2.5.so
b7eac000      12 rw--- 00000000b7eac000 000:00000   [ anon ]
b7eaf000     148 r-x-- 0000000000000000 008:00011 libm-2.5.so
b7ed4000       8 rw--- 0000000000024000 008:00011 libm-2.5.so
b7ed6000       4 rw--- 00000000b7ed6000 000:00000   [ anon ]
b7ed7000      20 r-x-- 0000000000000000 008:00011 libcrypt-2.5.so
b7edc000       8 rw--- 0000000000004000 008:00011 libcrypt-2.5.so
b7ede000     156 rw--- 00000000b7ede000 000:00000   [ anon ]
b7f05000       8 r-x-- 0000000000000000 008:00011 libdl-2.5.so
b7f07000       8 rw--- 0000000000001000 008:00011 libdl-2.5.so
b7f1f000      16 rw--- 00000000b7f1f000 000:00000   [ anon ]
b7f23000     100 r-x-- 0000000000000000 008:00011 ld-2.5.so
b7f3c000       8 rw--- 0000000000019000 008:00011 ld-2.5.so
bffa4000      84 rw--- 00000000bffa4000 000:00000   [ stack ]
ffffe000       4 r-x-- 0000000000000000 000:00000   [ anon ]
mapped: 31964K    writeable/private: 29708K    shared: 0K

You’re super cool in any case (even if you fail) ! Amazing job.

Thanks.