A very powerful efficiency hack.

Charles Fiterman cef at geode.geodesic.com
Wed Jun 12 17:49:53 UTC 1996

In working on garbage collection I discovered a very
powerful efficiency hack. Let me state the original
form and then generalize.

We had to scan pages for pointers. Instead of taking
them in simple list order I took two passes. First
take each page descriptor and discover if the page
is in ram. If it is then scan and mark as scanned.
On the second pass scan the pages not scanned in the
first pass. This eliminates all kinds of paging, compared
to many difficult code hacks it is really awesome.

Now the generalization. There are all kinds of collections
which have a prefered order of scan for efficiency. That is
you need a method which says do_quickly [some method] which
applies the method to all the members in an undefined order
which is assumed to be chosen for efficiency alone.

More information about the Self-interest mailing list