|
New? Sounds simple, but lots can happen within the VisualWorks memory allocation journey which can in turn affect your application.
Have you ever wondered how the simple act of allocating an object in a smalltalk image occurs? The allocation journey starts with new or new: and ends when the object is scavenged by the Garbage Collector (GC). To understand where and how new works, you must first find it. It is not found where one would expect (perhaps hiding in Object), but rather in the class Behavior, which defines the minimum logic needed for Classes to create instances of themselves. Beyond support for the compiler and methods like allInstances, Behavior contains the methods new and basicNew. Why new is found there is a topic for another article.
new: versus new?
When a class is created, you actually indicate if the class is going to create fixed-sized non-indexed objects, or variable-sized indexed objects. To better understand this choice, let us look at the VisualWorks class definition of Text
CharacterArray subclass: #Text
instanceVariableNames: 'string runs '
classVariablesNames: ''
poolDictionaries: 'TextConstants '
category: 'Collections-Text'
Does this look like a method invocation? In fact it is. This method can be found over in the instance side of Class. It creates a class in the image that is responsible for creating instances of fixed-size objects. In this example, the instance variables string and runs contain the variable-sized information which stores and supports the text string created. To create a variable-sized object, the syntax is different:
ArrayedCollection variableSubclass: #Array
instanceVariableNames: ''
classVariablesNames: ''
poolDictionaries: ''
category: 'Collections-Arrayed'
In this case, the method invocation creates a class called Array. Instances of Array, as you know, can contain zero to many object references. Each indexable slot initially contains a reference to nil, and later to any other object you place into the array with the at:put: method. This poses a question for character strings. Do we really want to reference each character individually via a slot reference? We could, but the end result would be slow and waste memory. Many bytes of memory are required to support a reference to another object. To address this concern, we can create classes where the byte accessible slots contain not reference information to other objects, but rather the slot itself contains the data. For example:
ByteEncodedString variableByteSubclass: #MacString
instanceVariableNames: ''
classVariablesNames: ''
poolDictionaries: ''
category: 'Collection-String Support'
This class definition means that a MacString instance stores data in the slots directly. This saves space and improves performance.
Variable-sized objects like Array require an important piece of information. It is necessary to supply either the real size or a guess at the size required when an instance is created. To simplify decisions for the programmer, many classes in the image provide a new method that actually invokes new: with a default value. OrderedCollection is a profound example where new actually invokes new:5. Someone's empirical testing showed that 5 was a magic number, but do you wonder if 5 is acceptable today? Earlier Smalltalk implementations used 10!
It is important to note that variable-size objects might need to grow or shrink. Growth is handled by allocating a new bigger object, copying the slot data over, and using become: to swap references to the original object. Usually this logic is found in methods called grow and trim. Some classes such as Set implement both methods. However, not all variable-size objects allow you to grow or shrink them on demand.
To create a large fixed-size class means creating a class with lots of instances variables. Thousands in fact! This is not likely to happen, since VW limits us to 255 named instance variables. Other Smalltalk implementations allow more. But with VW, given the 255 limit, there is no thought given to error recovery for new or basicNew allocation failures. Variable-size objects are different. We only need to abuse new: with a big number.
new: an allocation journey
The curious sort might ask: "What happens if I try to allocate too much memory? Say 200MB?" In a nutshell, exceeding the amount of available memory means failure. "Okay, but can we recover?" Yes, this is possible, but first you must understand how memory is allocated. As a starting point, VW uses a set of primitives to allocate memory. These primitives are found over in the instance side of the class Behavior.
new, basicNew
Both use primitive 70 to allocate memory.
new:, basicNew:
Both use primitive 71 to allocate memory.
A third primitive 460 is used by WeakArray class>>basicNew: to allocate memory for WeakArray objects. Weak references are handled in a special way by the garbage collector.
Although memory allocation is hidden within the primitive call, it can fail. When a primitive fails in VW, it is possible to recover, since VW executes the recovery code which follows the primitive invocation. In new: or basicNew: failure is usually due to a memory allocation problem. The recovery code then calls Behavior>>handleFailedNew:size: where our journey to find some bytes begins. To understand how to get there, it is necessary to visit the class SystemError. "Why?" Because an instance of this class is returned by some primitives when you run out of memory, or encounter some other sort of fatal error. In many places, the returned instance of SystemError helps the error recovery code deal with the problem. In true Smalltalk fashion, why return a raw number when an object you can delegate to will do a better job?
SystemError is a complex class which contains logic to deal with eleven defined error conditions on behalf of the image. Each of these errors can be assigned a generic handler, but only two error handlers are actually implemented. Other error conditions are dealt with where the primitives are invoked. The two generic handlers deal with i/o errors, and with memory allocation failures. This is a good thing, since memory allocation can occur in more places than new: or basicNew: An example would be PCFilename class>>getVolumes, where the VM is allocating memory to return an Array of volume names which might lead us into a memory allocation failure.
In general, the path followed for an allocation failure is:
Behavior>>new:
Behavior>>handleFailedNew:size:
SystemError>>handleErrorFor:
[allocation failure block from ObjectMemory]
ObjectMemory class>>makeSpaceFor:
MemoryPolicy>>makeSpaceFor:
[Make space in image]
Behavior>>newNoRetry: " retry the allocation "
In Behavior>>handleFailedNew:size: a number of checks are made to see if the class is not indexable, the size argument is negative, or there isn't enough memory to fulfill the request. To test this logic, try inspecting these objects:
String new: -1.
Object new: 10.
These examples give us two error notifiers which handle different types of memory allocation problems. However, our original problem is a lack of memory. On an allocation failure, the SystemError instance is sent the message handleErrorFor:. A key idea here is to have the instance of SystemError deal with the problem. Early on, when the SystemError class was initialized, it made a call to ObjectMemory class>>initializeErrorActions which provided a block to handle allocation failure errors. Yet more delegation. This block validates the error condition, then passes the memory request off to ObjectMemory class>>makeSpaceFor: which promptly calls the current MemoryPolicy's makeSpaceFor: method.
In MemoryPolicy a somewhat complex algorithm is followed to allocate more memory for the image from the hosting OS. First, the desired size is estimated based on a minimum value and the requested target size, with the addition of a fudge factor. Then the algorithm determines whether to grow or to reclaim space. If the environment will support growth, it will be attempted, since growth is cheaper than GC work. However, this viewpoint might not be shared by the hosting OS, and excessive paging may result.
If growth is not possible due to MemoryPolicy restrictions, or because of hosting OS issues, the logic invokes a garbage collection and we endure the GC cycle. After one GC cycle, the logic checks to see if enough memory is free. If not, it invokes MemoryPolicy>>growMemoryByAtLeast: maybe two more times before giving up. Now we are in trouble, since we may not have a block of memory big enough for the original allocation request. Once returning to Behavior>>handleFailedNew:size:, the code invokes a special method called newNoRetry: to reattempt the allocation. This method mirrors the original new: but with one important feature. The error recovery is different. If primitive fails in this method, it signals a memory allocation failure, and the client gets the nasty notifier window informing him that no more memory is left.
Does VW always use this logic to grow the image? No! Both an idle loop and low space action process that run as part of the MemoryPolicy logic will attempt to grow the image and do incremental GC work before we fail within a new: primitive call. These are discussed in more detail later in the article.
This allocation failure logic is fairly new. Early precursors to VW did not contain any recovery logic for growth and retry on failures. They relied instead on the idle loop and low space process to fix memory problems. This precursor logic fails for images that have aggressive memory allocation patterns.
The experienced reader should note that Object>>primBecome: invokes handleFailedBecome: which almost mirrors the new: logic, but uses different code. During growth of an OrderedCollection this code might be executed instead of the code in new:
Tuning Memory Allocation?
Is it possible to change the logic so that memory allocation is better? Perhaps. Examine the following test case where 25 thousand 1K strings (at least 25MB) are allocated. A Windows NT machine with only 24MB of physical ram took 757 seconds to allocate all the strings. Why so long? Each time the image ran low on memory, a decision was made to grow or reclaim space. The default MemoryPolicy attempts to limit the dynamic memory size of VW to about 16MB. Each time the image grows by its default allocation size of about 1MB, the allocation logic invokes a memory compaction, thus attempting to keep the image size below the 16MB limit. This GC compaction can cause excessive paging (page thrashing), since the GC must look at each object or object header to see if it should be GCed. This end to end walk of memory leads to poor response time on machines that have less than optional vitural memory configurations.
MemoryPolicy contains the logic to enforce growth restrictions. The default policy makes it possible to alter the upper boundary, which indicates when to invoke memory compaction during the new: allocation recovery. If this boundary is altered via
ObjectMemory currentMemoryPolicy growthRegimeUpperBound: to 256MB, no memory compactions will be triggered, and the original problem code will run in only 18 seconds. Great news, but the next compacting GC will of course walk all memory, and causes excessive paging. A 99 second task in our test case. But this is a deferred event, and hopefully the original work objective was able to be completed before this event occurs. In any case, it is certainly faster than the original 757 seconds. In our example, the GC promptly frees the 25 MB of memory back to the image, not to the OS. Once VW allocates the memory from the hosting OS for OldSpace, it is never given back to the OS. You must exit and restart VW to get this memory back.
Another option is to change the default size of OldSpace allocation increments via ObjectMemory currentMemoryPolicy preferredGrowthIncrement:. If the default is changed from 1MB to 5MB, the test example can be completed in 157 seconds, since 20 odd memory compactions are avoided. If a large number is seen while inspecting ObjectMemory current oldSegments, you may want to alter your growth increment to reduce the number of incremental OldSpace segment your image allocates.
If your image suffers from excessive paging, then consider if your growthRegimeUpperBound and perferredGrowthIncrement are reasonable for the size of your machine and your application. Altering these values might dramatically change your response time. This also applies to situations where the real memory available is under 16MB. If so, the default MemoryPolicy can affect your performance due to its default characteristics of allowing the image to grow to 16+MB before doing any OldSpace GC cycles. Decreasing that limit may result in more GC events, but may also reduce your image's paging rate, which should in turn improve performance.
In conclusion, the test example shows some dramatic time improvements, and also some dramatic performance issues. In general, exceeding the amount of real memory available to the OS can be difficult to recover from. Changes to the default MemoryPolicy might improve memory allocation spike problems, but your application either needs more real memory, or should avoid the excessive memory usage and allocation spikes by rewriting your application.
Scavenge processing in the Image. A VM event only... or is it?
In my previous article, I discussed the Scavenge. The event where dead objects get garbage collected. Wouldn't it be great if you could get the GC to tell you when an object of interest gets garbage collected? Usually you want to do this to free external OS resources when the object they are attached to get GCed. A classic example is OS file handles, which need to be freed once a stream object has died. Other uses are found in the class Symbol, where the image stores unique symbols using a weak link. A weak link means your weak reference to the object won't prevent it from being GCed. As a down side, notification is made only after the object has died, meaning of course that you can't refer to the object anymore. It no longer exists. But clever programming on your part can infer sufficient context to act on the death of the object. Clever work on part of other Smalltalk implementations also allow you to have pre-death announcements, but we'll focus on VW here.
In VW, Primitive 460 is used to allocate WeakArrays. Beyond marking the object we are allocating as weak, the rest of the allocation logic follows the same path as new:. If one of the WeakArray's indexed variables is found by the GC not to be accessible by any other object than a WeakArray, then it 'dies', and you get notified in a somewhat roundabout fashion. This is done as a side-effect of the scavenge. A scavenge is not completely hidden in the VM. The event is clearly exposed, but not in ObjectMemory where one would expect to find it. An old Smalltalk adage is that "work never gets done directly - it's always someone else's responsibility". The WeakArray class provides an interface between the VM memory management and Smalltalk code. When the VM memory manager zeros an element in a WeakArray instance, it places the array on a special queue called the internal finalization queue, and at some point the VM signals the WeakArray's FinalizationSemaphore to notify us that an element within a WeakArray has suffered a death. Take note that due to timing issues, a busy new space GC may scavenge NewSpace multiple times before the #ElementExpired event is fully processed by the image. When the semaphore is signaled by the VM, a special process starts to fetch each WeakArray from the internal finalization queue to send them a changed: message with the symbol #ElementExpired . Okay, but how does this relate to ObjectMemory?
Over in ObjectMemory class>>createNewScavengeNotification we find a WeakArray was created with a one element instance of Object. This was registered as a dependent of the ObjectMemory class. ObjectMemory will of course now get a #ElementExpired event when a memory scavenge occurs, since the instance of Object it created will promptly die on the next Scavenge. Interested parties may use ObjectMemory class>>addToScavengeNotificationList: to add themselves to the dependency chain, and later use ObjectMemory
class>>removeFromScavengeNotificationList: to revoke their interest. This dependency interface allows monitoring of the Scavenge process and the memory allocation pattern of our image. Flashing icons, ringing bells etc. come to mind as methods to assist you in understanding the dynamic memory allocation patterns of your application.
When the Scavenge event occurs, ObjectMemory class>>scavengeOccurred is invoked, which then signals the IdleLoopSemaphore. This event provides a chance for the idle loop process to examine OldSpace memory usage. This process waits on the IdleSemaphore which when triggered by the scavenge invokes MemoryPolicy>>idleLoopAction. The default idleLoopAction logic first checks to see if allocation activity in Old Space is high. If this is true, then the logic checks to see if the current free memory is below a threshold. If space is low, then ObjectMemory class>>compactMemory will be called to compact the data in OldSpace. This action shows the compact memory cursor, and takes some time to complete. Finally, a decision is made by the idleLoop process to see if the Incremental GC (IGC) should run. This decision is made in MemoryPolicy>>idleLoopGCJustified where it looks at an estimate of the number of bytes moved out of Eden into a survivor space, and then perhaps to OldSpace. Only if the number exceeds a quota is an IGC called for. The IGC runs as long as things are quiet, idle, calm, etc. High activity rates on the part of other processes running in the image defeat the IGC effort. A topic for another article.
The idle loop process does OldSpace GC from time to time, but a more important process, the low space process, is also waiting for the right conditions to occur before swinging into action. As part of ObjectMemory initialization, hard and soft low memory thresholds are calculated based on the environment, and are then given to the VM. When free memory reaches these thresholds, the VM will directly signal a semaphore owned by ObjectMemory. This semaphore controls a process which has responsibility for doing incremental or aggressive GC work as well as possible image growth to fix the low space condition. This process attempts to fix memory allocation problems before the image trips over failures in new: invocations. If the hosting OS will allow it, VW will happily grow to a 512MB limit. However, I have seen reports of conditions where image growth can be blocked due to unique circumstances that prevent the allocation failure recovery code from running. Remember, it needs some memory to complete its processing.
Next time a notifier window indicates that you are out of memory, consider the work that occurred within the image before it gave up in frustration! Further thoughts on image size can be found in Derk William's article 'Taking out the Garbage' that appeared in the January 1996 issue of this publication. The issue of memory shortages due to coding problems are addressed as are helpful suggestions on how you can find the villain in your image. Memory isn't free, but it is very manageable!
At this point I feel I've addressed most of the interesting aspects on new: and NewSpace. My next article will focus on " OldSpace, a place to die".