View this PageEdit this Page (locked)Attachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

Martin's CW 3

CW 3

Collection Classes
Some collection classes OrderedCollection, Set, Array, and Dictionary. All of these collection classes understand the messages isEmpty and occurencesOf as well as do, select, collect, reject, detect:ifNone:, and inject:into:. The rest of the definition of different collection classes serves to differentiate their functionality and ability. While both are technically Bags, OrderedCollection is a more relaxed than Array as its size varies when needed. Because of this, arrays can be created with a single memory allocation but have fixed size. Therefore arrays are more usefull for speed and control while OrderedCollection is more flexible. Sets vary from OrderedCollection, Array, and others Bags in that Sets can only contain one of each object. This kind of collection is good for accumulation situations where you only want to keep track of having an object and not holding on to different instances of the same object. Dictionary is a kind of Set which references an object by a given key. The key can then be hashed to calculate a storage location for any given object. While this takes up more initial memory, it results in much faster access times. Dictionaries are good for having a collection which remains relatively static and especially when that collection is large.

On Garbage Collection
Using GC is advantageous for most casual and non-performance-critical programming. Garbage Collection removes the stress and pressure of dealing with memory allocation and freeing. In addition, using GC can lower the footprint of programs because memory which becomes unreferenced or disconnected from the running program can be freed and its space be given to another object just being created. Also, using GC can compact memory intelligently to speed up memory function runtimes. Do you think you can keep track of all of this across all of your program? No. It is not efficient to recreate these parts of functionality for every program you make. You would waste time on it, not develop a system as precise, and probably make mistakes along the way.

There are several modern methods of grabage collection used in today's programming languages. One of the classic methods is called reference counting. in this model, every time memory is allocated and referenced the running program keeps count of how many references are held by the program on the memory location. Once the number drops effectively to 0, it cannot logically be recovered by any existing variable and so the memory is effectively lost. For example, a variable can be created for an object, making its reference count 1. During several function calls local pointers can make reference to the memory and thus raise the reference count. After each function exits the reference count again lowers. Eventually all referring objects and variables are removed by going out of scope. The program can then free the memory, consolidate memory, etc.

However the scheme of reference counting has some drawbacks such as having a self-referencing variable. Even if that were specifically prevented from causing problems, then a pair of variables could point at each other, or any length of a chain of referencing variables. Looking back on this bug, any length cycle causes problems for a reference counting system. When applied to the domain of graphy theory, this is called a cycle. To leave cycles alone, it can be imagined that an effective GC could hold on to one root node representing the program and then only keep variables which are somehow linked to that root node.

This type of GC is called mark and sweep. All memory locations are treated in a node in a directed graph representing the memory use of a program. All nodes linked to the root node are marked to be kept. All unmarked nodes are then removed. The downside to this kind of algorithm is that an entire sweep can take some time and efficiently organizing the remaining memory can add to that long time. To reduce the amount of processing to recheck more-permanent allocated memory spaces, different levels of variables can be created to check less often those allocations which have lasted a long time. This differentiation is called generational GC. One way to lessen time taken by the compacting phase it to split available memory into two pieces and perform a mark. All memory to be kept is copied into the other half of all memory and its reference table entry updated. Afterward the previous memory space is either cleared or forgotten. This method can compact data much faster but requires that only half of the potential space be used at one time.

Links to this Page