compacting gc

compacting gc

[Richard Henderson]

One of the first things I'm going to do when you get your
via-data-structure gc going is implement a compacting collector.

I've been looking at why the Blitz wei-ku-1.ii example retains
a large footprint even after collecting hundreds of megabytes
of garbage.  It seems the answer is exceedingly poor locality.

The following is from a compiler tweaked to dump stuff at each
collection:

{GC 1003054k -> 369032k}

	[ So we collected 620MB of trash. ]

Size   Allocated        Used    Overhead
8           8192          16         176 
16            14M       4953k        201k
32            64M         59M        646k
64           280M         74M       2246k
128          135M        135M        948k
256         8192        5632          48 
512          248k         49k       1488 
1024          16k         12k         96 
2048        8192        8192          48 
208          201M         62M       1208k
40           246M         23M       2214k
Total        942M        360M       7466k

	[ This is post-gc bucket usage.  Allocated - Used indicates
	  that we have 582MB of free space still mapped. ]

 %occ      pages %total
    0      31691  26.26
   10      16112  13.35
   20      36016  29.84
   30       4293   3.56
   40        442   0.37
   50        305   0.25
   60        239   0.20
   70        327   0.27
   80        895   0.74
   90       9619   7.97
  100      20755  17.20

	[ This is a histogram of page occupancy.  It says that better
	  than 25% of all mapped pages are less than 10% full.  And
	  worse, 70% of all mapped pages are less than 30% full. ]


r~