No doubt about it, garbage collectors are weird. No, I don't mean the helpful men and women who go from door to door collecting refuse once a week. I mean programming systems where the programmer only allocates memory, and the system decides when to free it.
Last month, Bill Venners wrote an excellent article on how garbage collectors works and a bit about how garbage collection is implemented in Sun's Java Developer's Kit (JDK). The important point is that garbage collection isn't new; it simply hasn't been so obviously present in a language targeted at such a wide programmer group before.
Also, the mythology surrounding the slowness of garbage-collected systems is just that, myth. I can show that the number of instructions executed is the same whether I call malloc() and free() or I only call malloc() and some other code calls free(). Further, I can show that a conservative garbage collector will never free something I'm currently using. The only non-zero difference in this equation is the "detection" stage in which the garbage collector finds out what is and what isn't an unreferenced piece of memory. Here I have the advantage since I know immediately that I no longer need a piece of allocated memory and thus can free it right away.
"Aha," you may say, "Chuck is against garbage collectors!" That is not correct because I have also tracked down too many bugs where I knew I wasn't going to use another piece of memory again so I freed the allocated memory, only to modify the code at some later date without that knowledge and in the process introduce a bug by using memory I had already freed. Further, the "cost" or time penalty of running a garbage collection thread (which needs only access memory) is greatly reduced on a fast processor that is spending most of its time waiting for activity on the keyboard or disk drive. In the final analysis, I prefer garbage-collected systems over non-collected systems like C much the same that I prefer C over assembly language. I can spend less time thinking about the mechanics of programming and more time concentrating on the program itself.
All that being said, why write a column on not using garbage collectors?
Like most programmers who originally used C, I am very sensitive to memory issues. Thus, I find it difficult to trust a garbage collector to manage memory better than I can. (This is different than saying a garbage collector can manage memory more accurately than I can, which is a given.) Better in this context means perhaps more efficiently. As a karate student in Los Angeles I was struck by how universal one of the fundamental principles of the martial arts was: "You don't need to block a blow that can't hit you." Applying this principle in this context becomes "You don't need to collect garbage that you don't generate."
The compelling issue
I needed a terminal -- not some surplus VT100 to hook up on my desk but a virtual terminal I could hook up to Java applications on a Web page. You see, it is one thing to talk about writing HelloWorld in Java and try to describe it on a Web page; I wanted to be able to run it on a Web page. But it isn't an applet, it's an application, the difference being that it communicates with the real world via a console interface like many computer programs do, not via a GUI/Web interface like applets do.
The solution seemed pretty obvious. If you'll recall, in my July column I showed how two applets could communicate using data channels. What I needed was a way for HelloWorld to communicate to a virtual terminal. The answer was to make it out of two applets, then apply the previously workable solution: data channels.
A data channel is an interthread communication object that allows one thread to write a series of objects to another object. I was playing around with some virtual terminal applets on the Web (see the Resources section below) and decided what I really needed was an I/O stream based on the DataChannel class. Note that I could have used PipedInputStream and PipedOutputStream, but these are only one-to-one connections. With a data channel I could connect several applications to the same terminal.
First efforts
The neat thing about object-oriented languages is that you can define an interface, implement it quickly (but stupidly) to check your ideas, and then optimize the implementation for the desired performance goals. Java I/O streams are conceptually very simple things, and to implement one you need only subclass InputStream or OutputStream and then implement a couple of very simple methods. The first implementation of DataChannelOutputStream was as follows:
package util.comm;
import java.io.OutputStream;
import java.io.IOException;
public class DataChannelOutputStream extends OutputStream {
private DataChannel dc;
public DataChannelOutputStream(String chanID) {
dc = DataChannel.getChannel(chanID);
}
public void write(int c) throws IOException {
dc.putValue(new Integer(c));
}
}
As you can see, 12 lines of code is pretty simple. The constructor takes the name of the underlying DataChannel, and the write() method simply spews integers (actually, they are bytes) into the channel. The other side, DataChannelInputStream, is a bit more complicated and shows why things are not as simple as one might hope. I'll dissect it in sections.
package util.comm;
import java.io.InputStream;
import java.io.IOException;
public class DataChannelInputStream extends InputStream
implements Runnable {
private Thread monitor;
private DataChannel dc;
private byte buffer[] = new byte[1024];
int getIndex = 0;
int putIndex = 0;
public DataChannelInputStream(String chanID) {
monitor = new Thread(this);
dc = DataChannel.getChannel(chanID, monitor, 1024);
monitor.start();
}
In the first part of the class, one thing that immediately stands out is that the input stream has to start a separate thread to monitor the data channel. The basic idea is that this monitor thread will watch the channel, pull off data as it comes across, and store it in the array named buffer. The other interesting bit is that in the previous uses of DataChannels the queue was quite small, but in this class we make it much larger. This was an early attempt at overflow management.
private boolean overflow = false;
private synchronized void add(int b) {
buffer[putIndex] = (byte) b;
putIndex = (putIndex + 1) & 1023;
if (putIndex == getIndex)
overflow = true;
notify();
}
public synchronized int read() throws IOException {
int r;
while (getIndex == putIndex)
try { wait(); } catch (InterruptedException e) { }
r = buffer[getIndex];
getIndex = (getIndex + 1) & 1023;
if (overflow)
throw new IOException("Buffer overflowed - Data Lost!");
return r;
}
In the above section we provide the required read method of all extenders of class OutputStream that are not abstract, and we provide a method add that the monitor thread will use to store data in our holding buffer. Both are synchronized so that the read method can block (using the wait() method) when there is no data to read. The buffer is simply a circular ring of 1024 bytes that gets filled as data comes in, and the add method checks to see if data is overwriting data that hasn't been read. If it is, the flag overflow is set and an IOException is thrown when the buffer overflows so that the client can know that data was lost. More on this a bit later.
public void close() throws IOException {
Thread x = monitor;
monitor = null;
dc.releaseChannel(x);
}
public void run() {
while (monitor == Thread.currentThread()) {
Object q = null;
try {
q = dc.getValue();
} catch (DataChannelException e) {
System.out.println("Got exception.");
e.printStackTrace();
continue;
}
if (q instanceof Integer) {
add(((Integer) q).intValue());
}
}
}
}
The thread management methods are the final section of DataChannelInputStream. The close method simply sets monitor to null so that the thread will exit when the channel is released. We could also catch DataChannelShutdown in the run method and exit but this works fine.
The run method is a loop that sucks data out of the DataChannel and stuffs it into the objects queuing buffer. Imagine that add is the interface for the DataChannel thread and read is the interface for the user of this object.
But weren't we talking about garbage collectors?
Purity meets practicality
As I mentioned earlier, these two classes do the job. Using them I can create an applet, open up a DataChannelOutputStream, create another applet, open up a DataChannelInputStream, and spew data all day long. However, in doing so I uncovered two issues with this implementation.
The first issue has to do with how important it is for data to get from here to there. As a communication channel, data channels have some compliance, or flexibility, to the load placed on them. However, when the data producer turns out more data than the consumer on the other end of a channel is able to process, the consumer gets DataChannelOverrun exceptions that it can elect to ignore. In a terminal's data stream; however, it is vital that all data get from the input to the output; thus you must have some way of causing the producer to wait when the pipeline is full.
The second issue is an inordinate amount of garbage production. Consider that this simple design allocates an Integer object for every byte sent through the stream, and printing out this column through a DataChannelOutputStream could generate and discard more than 30,000 objects. Those 30,000 objects can represent more than 5 megabytes of heap space. And for what? Simple coding.
Searching for a middle ground
Addressing the first issue is straightforward. The DataItem class' implementation needs to be updated to allow a DataItem object to block the writer. However, to prevent this from becoming an incompatible change to an existing interface, I added a new method, setBlocking(), to turn this behavior "on." The actual implementation required changing the insert() method in DataItem to call wait() if the queue was full, and to have the fetch() method call notify() after reading to wake up any waiting writer threads and recycling.
To facilitate reusing an object, the producer client of that object has to know when the object is free to be reused. Further, the consumer client of that object has to know who to notify when the object is no longer needed. These two properties are instantiated in the interfaces Referenced and Recyclable.
The Referenced interface is a simple reference-counting interface to do bookkeeping on the number of times the object reference has been "handed out" versus the number of times it has been "turned in." It defines three methods: addRefCount(), which increases the number of references; decRefCount, which reduces the number of references; and refCount(), which simply returns the number of references.
The Recyclable interface serves a dual purpose. It is implemented both by objects that can be recycled and by objects that can recycle recyclable objects. The two methods it defines are recycle() and recycle(Object x). For any recyclable object, one simply calls the recycle() method. When the object determines that there are no longer any references to it, it calls the recycle() method on the recyclable object that produced it and passes a pointer to itself.
If you will recall, data channels work by passing around references to objects. This makes them very efficient and general-purpose. By using interfaces for these new capabilities, the ability to reuse objects can be integrated into the DataChannel class with no impact on existing clients.
Before object reuse, the flow for the putValue() method of DataChannel was:
for every reader of this channel.
call DataItem.insert(passed object);
and the flow for getValue() was simply:
find my queue.
read the next object (block if queue is empty)
return the object.
We now modify the flow of putValue() to be:
for every reader of this channel.
if (object instanceof Referenced)
object.addRefCount();
call DataItem.insert(object);
and on getValue() we can use:
find my queue.
read the next object.
<use it>
if (object instanceof Recyclable)
object.recycle();
return;
For clients that don't pass objects that implement the new recycling paradigm, the channels work the same way they always did.
To limit the actual production of objects I needed some way to buffer writes to the data channel in an intelligent way. I/O streams have no specific boundaries for when a complete "record" of bytes are sent, thus the DataChannelOutputStream doesn't really know when to ship the bytes to the other end of the channel. However, output streams do have a flush() method, which means "ship data now!" Therefore my solution to the production problem was to create a recyclable buffer object that could be partially filled and shipped on demand to the other side of the channel. This became embodied in the StreamBuffer class.