On 2009-10-29 09:42:58 -0400, dsimcha <dsim...@yahoo.com> said:
I've gotten underway hacking the GC to add precise heap scanning, but I
thought of one really annoying corner case that really would make things an
order of magnitude more complicated if it were handled properly: Structs and
classes that have large static arrays embedded. For example:
class Foo {
Foo next;
void*[4 * 1024 * 1024] hugeArray;
}
The problem here is that scanning this precisely would require me to either
generate a megabyte bitmask that explicitly says "scan every element of
hugeArray" or to change my bitmask data structure from a flat array to
something nested and an order of magnitude more complex to generate at compile
time.
You don't need something with nesting, but something a little more
complex yes. For instance you could replace the bitmask with an array
of integers, each telling you in turn how many words to skip and how
many words have pointers. For instance:
struct Foo {
int a;
void* b1;
void* b2;
void* b3;
int[4] c;
void*[3000] d;
}
ushort[4] fooMemoryMap = [1, 3, 4, 3000];
1 word without pointer
3 words with pointers
4 words without pointer
3000 words with pointers
Now one of the remaining problems is how to handle weak pointers. The
other problem is that this doesn't scale well if your static array
contains a struct with pointers and non-pointers. For this you'd need
to have a way to repeat a pattern (something like a rewind command in
the above stream). Both can be solved by giving a special meaning to
the most significant bit:
enum {
// For even values (non pointers)
SKIP_FLAG = 0 << ushort.sizeof*8-1;
REPEAT_FLAG = 1 << ushort.sizeof*8-1;
// for odd values (pointers)
STRONG_PTR_FLAG = 0 << ushort.sizeof*8-1;
WEAK_PTR_FLAG = 1 << ushort.sizeof*8-1;
}
Giving you this memory map for Foo:
ushort[4] fooMemoryMap = [
1 | SKIP_FLAG, // one word of non-pointers
3 | STRONG_PTR_FLAG, // three words of pointers
4 | SKIP_FLAG, // four words of non-pointers
3000 | STRONG_PTR_FLAG, // 3000 words of pointers
];
Now you can encode even a big static array of Foos in the middle of a
struct with a reasonably-sized memory map (14 bytes):
struct Bar {
Foo[500] a;
int[500] b;
}
ushort[7] barMemoryMap = [
1 | SKIP_FLAG, // one word of non-pointers
3 | STRONG_PTR_FLAG, // three words of pointers
4 | SKIP_FLAG, // four words of non-pointers
3000 | STRONG_PTR_FLAG, // 3000 words of pointers
4 | REPEAT_FLAG, // rewind 4 instructions
500 // and repeat 500 times
500 | SKIP_FLAG, // 500 words of non-pointers
];
Here, Foo's memory map just gets inserted at the right place in Bar's
memory map. No nesting or pointers or anything, just a repeat
instruction. An it takes only 14 bytes.
--
Michel Fortin
michel.for...@michelf.com
http://michelf.com/
