Slate also had a non-moving mark-sweep style allocator for its initial bootstrap for simplicity reasons. We then went for mark-sweep-compact with object pinning (which does keep an object in-place) for those on the root stack - even then it'll not be the final form of the memory-management subsystem. Both GC's are polymorphic and easily-swapped, but we haven't maintained the former. It could be revived for comparisons, possibly. In any case, you won't find terribly good locality figures unless you create a modified memory manager which moves objects around at least some of the time.

Unfortunately, C-based allocators have further restrictions beyond that mentioned that may cloud any lessons learned for others. See the essential book on the topic _Garbage Collection_. But Boehm is definite a man to ask.

On Jan 13, 2005, at 7:14 AM, Ned Konz wrote:

On Wednesday 12 January 2005 11:09 pm, Dan Ingalls wrote:

...

Partial credit:  If you have real experience with a Squeak-like system that worked this way, give some report on the fragmentation behavior experienced. References to papers with practical results in the area would also be of

interest.

Tell Ian to ask Hans Boehm. He's at HP Labs, building 3. And he's an expert in the topic. He's the author of a popular GC library for C programs; of course, it's much safer in C programs not to move things because it's sometimes hard to tell what's a pointer.

His slide show: http://www.hpl.hp.com/personal/Hans_Boehm/gc/nonmoving/index.html

A description of techniques used in the Great Circle conservative GC library (which I believe is based on Hans Boehm's work): http://www.cs.purdue.edu/homes/grr/ISMM98-grr-mps-cef.pdf

Henry Bakers' "Treadmill" algorithm appeared in the ACM SIGPLAN Notices in 1992. I think it was used in a Lisp system. http://portal.acm.org/ft_gateway.cfm? id=130862&type=pdf&coll=ACM&dl=ACM&CFID=36433663&CFTOKEN=40514639

I believe that Smalltalk/MT's GC (which is done in a separate thread and so can be paused and resumed) is a non-moving scheme. They play well with external libraries, in part because they don't move objects.

-- Ned Konz http://bike-nomad.com/squeak/

-- Brian T. Rice LOGOS Research and Development http://tunes.org/~water/

On Wed, Jan 12, 2005 at 11:09:17PM -0800, Dan Ingalls wrote:

Ian and I were talking today about simple storage management schemes and realized that Squeak's current garbage collector is "so wonderful" that it has shielded us completely from a useful piece of information.

We were specifically curious how a non-moving garbage collector would perform. For such a beast, when an object is freed it is maintained in a structure from which it can later be reallocated. Most such approaches use some form of "buddy" system to coalesce adjacent free blocks but, inevitably there is some fragmentation of memory.

So here's the instrumentation challenge: Write a log of all the allocation and release operations from running Squeak through, say, the macro benchmarks.

There's a pretty simple place to find all the allocations in the VM. Then at each GC, each unmarked object that the compactor steps over should cause an effective release operation to be logged.

Such a log could then be fed to any number of block management algorithms to get a sense of what kind of fragmentation to expect. This, in turn, would tell us what kind of trade-off exists between the memory footprint used and the time between catastrophic reorganization (ie when you have to do a full compaction).

Partial credit: If you have real experience with a Squeak-like system that worked this way, give some report on the fragmentation behavior experienced.

References to papers with practical results in the area would also be of interest.

Thanks

• Dan

For my entry in the hotly contested better-late-than-never category, I am attaching AllocationLoggingPlugin-dtl.cs, a memory allocation logging goodie. Along with the change set, I've attached the modified sqVirtualMachine.c and sqVirtualMachine.h files and corresponding diff files (I'm not sure which is most convenient). These required a new entry to permit the allocation logging plugin to register its logging function for the interpreter to use.

From the preamble:

Log memory allocation activity to a file. Caution - may create very large log files.

AllocationLogger new log: 'memory.log' while: [Array new: 2000000] AllocationLogger new log: 'memory.log' while: [Smalltalk garbageCollect] AllocationLogger new log: 'memory.log' while: [MacroBenchmarks run]

The AllocationLoggingPlugin arranges for the interpreter to log interesting memory allocation and deallocation events to an external log file. The plugin registers a logging function (#log:with:with) that is called by the object memory to record events.

Primitives are provided to open and close a log file, and to control what events are to be included in the log. Records in the log file have comma separated fields with time stamp (ioMSecs), a memory function code such as 'Alloc' or 'Free', and two integer values that pertain to the memory function. See #initializeMemoryLoggingConstants for the memory functions that can be logged.

This plugin requires an update to the sqVirtualMachine.c and sqVirtualMachine.h to define the logging function.

In sqVirtualMachine.c:

#if VM_PROXY_MINOR > 6 VM->memoryLoggingFunction= NULL; /* set by a plugin */ #endif

In sqVirtualMachine.h:

#define VM_PROXY_MINOR 7

#if VM_PROXY_MINOR > 6 /* function to be provided by a plugin */ int (*memoryLoggingFunction)(int code, int param1, int param2); #endif

Note: #allocateChunk: also contains a change for a low space interrupt fix, commented out for this AllocationLoggingPlugin distribution. The two change sets will need to be merged.

Dave