2003.01.04 ~10 mark-and-partial-sweep garbage collection This turned out to be an interesting hack to the mark-and-sweep gc. For some reason, TinyScheme partitions its heap into N segments of M cons cells. This appears inexplicable, as TinyScheme is hard-coded to use only 3 of the segments and refuses to use any more segments (short of an explicit procedure call to "new-segment"). I decided to use this inherent partitioning of the heap for a partial sweep mechanism. Partly inspired by incremental-style garbage collection (superset of "multi-threaded garbage collection"), the idea was to sweep one segment per Q3 frame, so that the time to sweep up all the garbage is spread out over a long time, interpersing regular Scheme processing. This depends on the sweeper recovering garbage faster than Scheme allocating space, which is most of the time (recovering up to M cells per frame, vs allocating perhaps a dozen cells per frame). Each module's vmMain() would need to call the partial sweeper once per frame or somehow ensure the sweeper gets called frequently per second. A problem is that in between partial sweeps, Scheme can still request additional cells. By default, TinyScheme does not initiate garbage collection until the heap is entirely exhausted. With this behavior, Scheme may wind up requesting cells when the sweeper has barely started, triggering another mark+sweep cycle. The free-at-exhausted behavior is also annoying as it tends to lead to lost symbols and bindings (no chance to establish a path from a root cell). As a workaround, I changed TinyScheme to initiate garbage collection after the freelist dips below a certain low mark, which is currently half a segment's size. This way, fresh objects get a chance to join the marked tree, and the allocator gets "padding" to keep Scheme satisifed as the sweeper starts. I also had the sweeper watch for "extremely tight memory situations". This would happen should Scheme allocate a very large chunk of memory right after a mark pass (just as partial sweeping start). Since sweeping when freelist hits zero tends to cause lost objects, I wanted a non-zero panic point. Should the freelist drop below the panic point, the sweeper goes into aggressive full-heap sweeping. Lacking a reference for this panic point, I chose a random number, 42. Empirically, on my K7/1200, with N=32 and M=32768 (total 1MiB), mark phase takes about 5ms, and a partial sweep of one segment takes 18ms, with a full-heap sweep taking a little under 600ms. Wishlist items: somehow automagically setting partial sweep to stop after a certain time threshold. One hack is to continually sample elapsed time, but the call to get the time (a Q3VM trap) takes up processing time. A better method would be to calculate the cells-per-ms rate, then using an appropriate number-of-cells to finish a partial sweep within time, but that method is more complicated.