Scheme Main Memory


One of a series of tutorials about Scheme in general
and the Wraith Scheme interpreter in particular.

Copyright © 2011 Jay Reynolds Freeman, all rights reserved.
Personal Web Site: http://JayReynoldsFreeman.com
EMail: Jay_Reynolds_Freeman@mac.com.


In previous tutorials, the term "Scheme main memory" has come up now and then, so perhaps it is time to tell you a little more about what it is, what it does, and what you can do to change it and to change how it is used. The way Scheme uses memory differs from one Scheme implementation to another: What I say here is intended to apply only to Wraith Scheme.

Obviously, Scheme uses computer memory to remember things. The term "Scheme main memory" is just a label for the particular portion of memory that Scheme uses for that purpose. Wraith Scheme actually uses several separate pieces of memory for slightly different purposes; when I talk about "Scheme main memory", I am implicitly lumping them all together.

Wraith Scheme needs two large pieces of memory for general storage of the objects it creates; it needs two instead of just one because of the way its full garbage collector works. There is an entire subsequent tutorial just about garbage collection, and lots more documentation in the Wraith Scheme Help File, Dictionary, and Internals File. The general idea is that Wraith Scheme gets rid of stuff in memory that it can prove it no longer needs by starting with a brand new chunk of memory that is completely empty, then copying into it the stuff from the old memory that it still does need, and leaving the rest behind. It sort of works like what many people do when they move to a new apartment. The "left behind" memory space eventually becomes the brand new empty space for the next garage collection.

The large piece of memory that is not being used to store objects at any given time is available for other purposes until the next full garbage collection, and indeed, Wraith Scheme has plenty of uses for it. I will spare you the details here; check the other documentation that I mentioned earlier if you are interested.

Wraith Scheme also needs somewhat smaller pieces of memory for its procedure call stack (see the previous tutorial, "Tail Recursion"), and for implementing its continuation (see the subsequent tutorial, "Continuations"). For each of these purposes, it uses a piece of memory ten percent as large as either of the large pieces that are used simply for storing Scheme objects. Between those pieces and a few others, the total amount of memory that Wraith Scheme needs when you are running a single Wraith Scheme process -- that is, when you are not using Wraith Scheme's ability to do parallel Scheme processing -- is somewhat less than 2.5 times the size of one of the large pieces of memory that Wraith Scheme uses for storing objects.

The main memory size that you specify in Wraith Scheme's preferences, and that shows up in the memory-size displays in the Wraith Scheme Instrument Panel, is the size of just one of those large pieces. So if you have set Wraith Scheme's main memory size to 100 MByte in the Wraith Scheme preferences, Wraith Scheme will actually allocate somewhat less than 250 MByte for its various internal uses.

That formula is for just one Wraith Scheme process. If you are using Wraith Scheme's parallel processing capability, each additional process will require some additional memory, but not as much as the first process, because the two very large pieces of memory will be shared by all the processes. Each additional process will need its own stack and continuation memory, though, and a few small pieces besides. All in all, each additional process will require approximately one quarter as much memory as is used for either of the two large pieces.

So if you have set the main memory size in preferences to 100 MByte, and have a total of four Wraith Scheme processes running in parallel, the total memory used will not exceed 325 MByte -- a bit less than 250 MByte for the first process, as discussed above, and about 25 MByte for each additional process.

As a general rule, it is wise to keep the total Scheme main memory size used by all running Wraith Scheme processes considerably less than the size of the total physical memory -- RAM -- that is installed in your Macintosh. With more than that, the total amount of memory that all of the processes on your Macintosh are using may exceed the total amount of RAM you have, and your Macintosh will have to store some of the content of RAM to disc, for want of any other place to put it. Writing RAM out to disc and reading it back in later is called swapping; it takes a long time, and your computer will suddenly become very slow to respond when it happens.

Wraith Scheme uses the active main memory -- the big piece that it presently being used for storing things -- in a very structured way. It gets filled up like a stack, growing from one end toward the other. It doesn't start out completely empty, of course -- the non-garbage stuff from the last garbage collection gets put at the low end of the stack to begin with. Every Wraith Scheme object, in Scheme main memory or anywhere else, is completely identifiable as to what kind of object it is: All objects have a "tag" as part of them, that contains that information. So when Wraith Scheme is looking at objects in the data base, or is moving them around, there should never be any doubt about whether the object is the appropriate kind for the task at hand, or about how much space in memory is required to store it.

As new objects are added to main memory, it fills up. When there is not enough space to add the next object, Wraith Scheme does a garbage collection. If even garbage collection cannot create enough new space for the desired object, Wraith Scheme is at an impasse and will complain to you, its user. You will will either have to shut down Wraith Scheme and restart it with the preference for memory set to a larger value, or will have to declare that some objects are garbage and then let matters proceed.

Strictly, there is no way to declare that an object is garbage. What you do instead, if possible, is to find some variable whose value is a large data structure and then change its value to some data structure that is much smaller. At that point, if no other variable has the large data structure as its value, the large data structure will be garbage, and its space will be reclaimed during the next garbage collection.

By way of illustration, one of the tests I run when I am getting ready to release a new version of Wraith Scheme is to see that it behaves gracefully when memory is full. I create a variable called "a" and bind its value to the empty list, then run a tail-recursive procedure that conses small objects -- I happen to use numbers -- onto the front of "a", one at a time. I let the procedure run till memory is full, at which point Wraith Scheme complains. With the test finished, I merely evaluate

and since I have never done anything like

nothing else has any connection to the long list that used to be bound to a, so that list is now garbage. Then I evaluate

and poof! Suddenly there is lots of memory available.

Wraith Scheme actually has two kinds of garbage collectors. The other is what is called a generational garbage collector, and what happens when it is in use is a little more complicated, but the basic idea is the same: Create new objects at will till you run out of space, then do a garbage collection to reclaim space used by objects that are no longer needed.


Wraith Scheme has many enhancements to learn about how main memory is being used. In particular, look in the sections of the Wraith Scheme Help File on "Storage Management" and on "System Administration", for lists of procedures that print out various memory contents and statistics. Be careful, though -- when main memory is large and most of it is being used, some of these procedures can take a long time to run, and might try to print out literally thousands of millions of lines of output.

It is important that Wraith Scheme's main memory can be shared among Wraith Scheme processes that are running in parallel: Without shared memory, it would be difficult and time-consuming for those processes to share information and to cooperate in performing computations. They would have to send messages of some kind back and forth, and message-passing tends to be slow and clumsy. Instead, each Wraith Scheme process can look at any object in memory, or modify it, pretty much whenever it needs to. (There are also ways for one Wraith Scheme process to ask another to do something; we will get to those in a subsequent tutorial.)

The weasel-wording about "pretty much whenever it needs to" is because it won't quite do to give two Wraith Scheme processes absolutely simultaneous access to the same object in memory. If one process was trying to read an object when another process was writing out a new version of it, the reading process might get something that was partly the old version and partly the new one. Wraith Scheme isn't prepared to deal with objects that are half one kind and half another; it might crash. Or if two Wraith Scheme processes were trying to write an object at the same time, a similar chimera-like object might get written into Scheme main memory, where it would likely cause great trouble when some process tried to read it later on.

To avoid such situations, whenever two or more Wraith Scheme processes are running cooperatively in parallel, Wraith Scheme implements a locking mechanism to prevent more than one process from having access to the same object in memory at the same time. The locking mechanism is operated entirely by Wraith Scheme itself: The programmer writing Scheme code doesn't need to worry about it.

Yet parallel processing can still cause strange things to happen. For example, if two Wraith Scheme processes are trying to write out a new value of the same variable at the same time, there is no telling which of the two new values will actually get written into memory; it depends on which process is able to lock the object first. That process will write its new value into memory and then release its lock, whereupon the other process -- which has been waiting for the opportunity to lock the object -- will lock the object and overwrite the first process's new value with its own. This occurrence is an example of what is called a race condition -- what happens depends on the result of a neck-and-neck down-to-the-wire competition for who gets there first. Wraith Scheme cannot prevent such race conditions, but it can prevent the kind of messed-up invalid memory that would result if two processes were trying to access the same object at the same time.

The locking mechanism may raise concerns among those of you who are well bloodied in the difficulties of parallel processing, about another kind of problem that is known as deadlock. Deadlock is commonly seen when two children who have no manners are playing: It sometimes happens that each child has half of a favorite toy, and needs the other half in order to continue playing, yet neither child will give up what he or she already has. Thus no one gets to play. Computer programs are known for manners that make the worst of small children look angelic, and deadlocks are common among carelessly written parallel processes.

I have tried to make Wraith Scheme's locking mechanism deadlock-free by the simple expedient of making sure the locking code is written and used in such a way that no process ever needs more than one lock at a time. In the language used to describe the situation with small children, all toys are indivisible: Thus no child is ever in the position of having half a toy and needing the rest.


-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)


Wraith Face