Progress On Garbage Collection

I know I haven’t posted for a while, and I blame my persistent illness for making me too lazy to work seriously. I have been working on my own brand of asynchronous copying garbage collection. Unfortunately I now realize that the method I have been developing is too inefficient, and needs to be re-done.

This leaves me with basically three choices:
The write barrier method (with an asynchronous copying collector): The write barrier method has the advantage of being able to use plain pointers for access. Unfortunately it has the unattractive problem of needed to update the addresses of pointers (since it is a copying collector), which means the collector needs to be able to safely tamper with the stack and global data in the C source to update pointer values. This can be a bit complicated, and is one of the problems my own solution was struggling with.

The handle method (with an asynchronous copying collector): In this method you don’t deal with pointers but with unique handles that you can “lock” in order to get at the memory they currently reference. This method has the advantage of being relatively simple, and safe. Unfortunately it requires frequent hash lookups of handles, which means that it is effectively both a read and write barrier method, which means it is probably too slow.

Asynchronous reference counting: In this method you push the tasks of referencing, dereferencing, and checking for cycles into their own thread, which improves speed in the mutator section of the code. The big disadvantage of this method is that it is not a copying solution.

p.s. Don’t know what a write barrier / read barrier is? Go here for a quick definition.

Four Kinds of Slow

One of the cardinal sins of a program is to be slow. Here I am not talking about sluggishness caused by a poorly optimized algorithm, but the kinds of delays caused by the language and frameworks that are somewhat beyond the programmer’s control. Languages such as Java and Lisp are often criticized by opponents as being naturally slow languages, but what such criticisms miss is that languages can be slow in four different ways, and not all of them are equally sinful, and what matters to a business application in terms of speed is different from what matters in a real time game. The four basic categories are as follows:

Universal
Universal slowness is the kind we most often associate with interpreted languages. Such a slowdown is caused because every operation has a slight overhead, and thus all parts of the program will be slowed in comparison to its native counterpart. Some see universal slowness as the most damning kind, but in reality it is the least significant, partly because it is the easiest to code around. If your program is running too slow because of the language it is written in the solution is simple, write the most computationally expensive routines in a faster language as libraries or extensions. In fact many programs could even be reduced in speed without the user noticing at all, as long as they were still able to keep up with user input.

Periodic
Periodic slowness is most often caused by garbage collection, but it could be also caused by a program having to wait on a slow network connection or having to process a batch of disk operations. Periodic slowness is usually only a problem in real-time applications, normally games, and in applications that expect a steady stream of user input. In such a program the user will experience occasional “lag”. Unfortunately there is no way to completely eliminate the cost of garbage collection. It is true that garbage collectors could be written that operated constantly and thus took an even toll on program performance, but these are much harder to write, and hence much rarer. Although there are coding techniques to reduce the time your garbage collector will take to run in some ways it is out of your hands.

Start-up
Start-up slowness is often caused when either a large run-time framework must be loaded for the program, for example Java, or when complex initialization of data or graphics must be done. The splash screens associated with some programs such a word, open office, ect are signs of this problem. The cost of start-up slowness is completely dependant on how the program is used. If the program is typically used for long periods of time then the start-up slowness is of little cost to the user, as they expect to be devoting a lot of time to using the program anyways. However if the program is designed to be a simple gadget, or something used only briefly, then start-up time is a large annoyance to the user.

Interactivity
A program can be slow to respond to user input either when it is busy with some other task, or when the framework it uses to manage the user interface is exceedingly cumbersome. Interactivity slowness is the most damning way a program can be slow, because it makes the program difficult for the user to work with. Some programs which suffer from this problem can be fixed simply by putting the user interface in its own dedicated thread. However in web applications, which may be slow to respond due to network delays, a fix to this kind of slowness may require a new way of approaching the problem.

Lets examine Dr. Scheme in these terms. Dr. Scheme has a long startup time, but since you will generally be coding for a while this is mostly irrelevant. Although Dr. Scheme incorporates Scheme, and thus the garbage collector is running, it never seems to interfere with its ability to keep up with user input. Most importantly Dr. Scheme responds to mouse clicks and typing without delay, which makes it feel like a fast program.

We can compare this to a small 2D game written in Scheme (I have been working on one). When compiled the program starts quickly, runs quickly, and responds well to the user. However it does suffer noticeably from garbage collection (occasional jerkiness). Although this is probably acceptable for a small little game it might not be for a big budget endeavor.

Design Driven Programming

We all like to talk about programming styles, but we can’t seem to agree as to what to call them. Here when I talk about design driven programming I am referring to the style in which the program is designed first, often with meticulous detail, and then coded. This contrasts sharply with the test driven style of programming (not extreme programming), where programmers create small bits of the program, test them, and then slowly put them together to form the complete program.

The Scheme and Lisp communities seem to avoid design driven development. One reason is that Scheme and Lisp make it easy to program without a finished product already in mind, and the REPL encourages programmers to design fairly independent functions which they can test and use immediately. Design driven programming also has a negative image because it is often associated with management driven programming, i.e. when your boss tells you what to do and you must follow their commands without innovation.

When I think of programming I sometimes compare it to a battle. The design driven methodology then is like a general, the lead designer, giving his troops detailed orders which they then follow out exactly. On the other hand test driven development is like the general telling his troops to go out and win the war, leaving to troops to figure things out by themselves.

If we follow this analogy a little further then we see that the biggest problem for design driven development is the unexpected. When the overall plan encounters a problem troops have to radio back to HQ for new orders, which of course takes to long, so the enemy overruns their position and the war is lost. Individual programmers, not leading such risky lives, must consult the lead designer, the design must be fixed, and then programming can resume, meaning that any design flaws lead to revisions, delays, and sometimes the need to redo parts of the overall design that were supposedly already completed. On the other hand in the test driven development unforeseen problems don’t lead to revisions or excessive delays, but it is hard to coordinate a significant number of programmers. Some soldiers go to France, some to Poland, and because they don’t coordinate their efforts the war is lost, even if they are individually all successful.

What do real general do to overcome this problem? The solution is a compromise which I call goal directed programming. A general might lay out objectives for regiments and lay down timetables, but in the field individual soldiers are given the authority to react appropriately to new situations without consulting their superiors.

The difference is probably best shown with a few examples.

	War	Programming
Design Driven	Go forward 100 meters, shoot 2 enemy soldiers, enter the building, guard both doors …	Write an process URL class, it should contain the following 3 functions …
Test Driven	Go capture the town	Create an html rendering component
Goal Driven	Proceed to hill 129, scout for enemy positions, follow the river into town …	Create an html rendering component that can take html source from either a web address, a file, or a character string. It should be able to output the results to an image file or an active window. Implement html specification 1.1, without javascript.