More PC Precision Stuff

Michel Fortin michel.fortin at michelf.com
Thu Oct 29 12:08:22 PDT 2009


On 2009-10-29 09:42:58 -0400, dsimcha <dsimcha at 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.fortin at michelf.com
http://michelf.com/




More information about the Digitalmars-d mailing list