Goodbye Far Clipping Plane.

Posted on September 6, 2010 by William Woody

I really wanted to write this up as a paper, perhaps for SigGraph. But I’ve never submitted a paper before, and I don’t know how worthy this would be of a SigGraph paper to begin with. So instead, I thought I’d write this up as a blog post–and we’ll see where this goes.

Introduction

This came from an observation that I remember making when I first learned about the perspective transformation matrix in computer graphics. See, the problem basically is this: the way the perspective transformation matrix works is to convert from model space to screen space, where the visible region of screen space goes from (-1,1) in X, Y and Z coordinates.

In order to map from model space to screen space, typically the following transformation matrix is used:

(Where fovy is the cotangent of the field of view angle over 2, aspect is the aspect ration between the vertical and horizontal of the viewscreen, n is the distance to the near clipping plane, and f is the distance to the far clipping plane.)

As objects in the right handed coordinate space move farther away from the eye, the value of z increases to -∞, and after being transformed by this matrix, as our object approaches f, z_s approaches 1.0.

Now one interesting aspect of the transformation is that the user must be careful to select the near and far clipping planes: the greater the ratio between far and near, the less effective the depth buffer will be.

If we examine how z is transformed into z_s screen space:

And if we were to plot values of negative z to see how they land in z_s space, for values of n = 1 and f = 5 we get:

That is, as a point moves closer to the far clipping plane, z_s moves closer to 1, the screen space far clipping plane.

Notice the relationship as we move closer to the far clipping plane, the screen space depth acts as 1/z. This is significant when characterizing the accuracy of the representation of an object’s distance and the accuracy of the z_s representation of that distance for drawing purposes.

If we wanted to eliminate the far clipping plane, we could, of course, derive the terms of the above matrix as f approaches ∞. In that case:

And we have the perspective matrix:

And the transformation from z to z_s looks like:

IEEE-754

There are two ways we can represent a fractional numeric value. We can represent it as a fixed point value, or we can use a floating point value. I’m not interested here with a fixed point representation, only with a floating point representation of numbers in the system. Of course not all implementations of OpenGL support floating point mathematics for representing values in the system.

An IEEE 754 floating point representation of a number is done by representing the fractional significand of a number, along with an exponent.

Thus, the number 0.125 may be represented with the fraction 0 and the exponent -3:

What is important to remember is that the IEEE-754 representation of a floating point number is not accurate, but contains an error factor, since the fractional component contains a fixed number of bits. (23 bits for a 32-bit single-precision value, and 52 bits for a 64-bit double-precision value.)

For values approaching 1, the error in a floating point value is determined by the number of bits in the fraction. For a single-precision floating point value, the difference from 1 and the next adjacent floating point value is 1.1920929E-7, which means that as numbers approach 1, the error is of order 1.1920929E-7.

We can characterize the error in model space given the far clipping plane by reworking the formula to find the model space z based on z_s:

We can then plot the error by the far clipping plane. If we assume n = 1 and z_s = 1, then the error in model space z_ε for objects that are at the far clipping plane can be represented by:

Graphing for a single precision value, we get:

Obviously we are restricted on the size of the far clipping plane, since as we approach 10⁹, the error in model space grows to the same size as the model itself for objects at the far clipping plane.

Clearly, of course, setting the far clipping plane to ∞ means almost no accuracy at all as objects move farther and farther out.

The reason for the error, of course, has to do with the representation of the number 1 in IEEE-754 mathematics. Effectively the exponent value for the IEEE-754 representation is fixed to 2^-1 = 0.5, meaning as values approach 1, the fractional component approaches 2: the number is effectively a fixed-point representation with 24 bits of accuracy (for a single-precision value) from 0.5 to 1.0.

(At the near clipping plane the same can be said for values approaching -1.)

All values in the representation range of IEEE-754 points have the same feature: as we approach the value, the representation is similar to if we had picked a fixed-point representation with 24 (or 53) bits. The only value in the IEEE-754 range which actually exhibits declining representational error as we approach that value is zero.

In other words, for values 1-ε, accuracy is fixed to the number of bits in the fractional component. However, for values of ε approaching 0, the exponent can decrease, allowing the full range of bits in the fractional component to maintain the accuracy of values as we approach zero.

With this observation we could in theory construct a transformation matrix which can set the far clipping plane to ∞. We can characterize the error for a hypothetical algorithm that approaches 1 (1-¹/_z) and one that approaches 0 (¹/_z):

Overall, the error in model space of 1-¹/_z approaches the same size as the actual distance itself in model space as the distance grows larger: ^err/_z approaches 1 as z grows larger. And the error grows quickly: the error is as large as the position in model space for single precision values as the distance approaches 10⁷, and the error approaches 1 for double precision values as z approaches 10¹⁵.

For 1/z, however, the ratio of the error to the overall distance remains relatively constant at around 10^-7 for single precision values, and around 10^-16 for double-precision values. This suggests we could do away without a far clipping plane; we simply need to modify the transformation matrix to approach zero instead of 1 as an object goes to ∞.

Source code:

The source code for the above graph is:

public class Error
{
    public static void main(String[] args)
    {
        double z = 1;
        int i;
        
        for (i = 0; i < 60; ++i) {
            z = Math.pow(10, i/3.0d);
            
            for (;;) {
                double zs = 1/z;
                double zse = Double.longBitsToDouble(Double.doubleToLongBits(zs) - 1);
                double zn = 1/zse;
                double ze = zn - z;

                float zf = (float)z;
                float zfs = 1/zf;
                float zfse = Float.intBitsToFloat(Float.floatToIntBits(zfs) - 1);
                float zfn = 1/zfse;
                float zfe = zfn - zf;

                double zs2 = 1 - 1/z;
                double zse2 = Double.longBitsToDouble(Double.doubleToLongBits(zs2) - 1);
                double z2 = 1/(1-zse2);
                double ze2 = z - z2;

                float zf2 = (float)z;
                float zfs2 = 1 - 1/zf2;
                float zfse2 = Float.intBitsToFloat(Float.floatToIntBits(zfs2) - 1);
                float zf2n = 1/(1-zfse2);
                float zfe2 = zf2 - zf2n;
                
                if ((ze == 0) || (zfe == 0)) {
                    z *= 1.00012;   // some delta to make this fit
                    continue;
                }

                System.out.println((ze/z) + "t" + 
                        (zfe/zf) + "t" + 
                        (ze2/z) + "t" + 
                        (zfe2/zf));
                break;
            }
        }
        
        for (i = 1; i < 60; ++i) {
            System.out.print(""1e"+(i/3) + "",");
        }
    }
}

We use the expression Double.longBitsToDouble(Double.doubleToLongBits(x)-1) to move to the previous double precision value (and the same with Float for floating point values), repeating (with a minor adjustment) in the event that floating point error prevents us from propery calculating the error ratio at a particular value.

A New Perspective Matrix

We need to formulate an equation for z_s that crosses -1 as z crosses n, and approaches 0 as z approaches -∞. We can easily do this by the observation from the graph above: instead of calculating

We can simply omit the 1 constant and change the scale of the ²ⁿ/_z term:

This has the correct property that we cross -1 at z = -n, and approach 0 as z approaches -∞.

From visual inspection, this suggests the appropriate matrix to use would be:

Testing the new matrix

The real test, of course, would be to create a simple program that uses both matrices, and compares the difference. I have constructed a simple program which renders two very large, very distance spheres, and a small polygon in the foreground. The large background sphere is rendered with a diameter of 4×10¹² units in radius, at a distance of 5×10¹² units from the observer. The smaller sphere is only 1.3×10¹² units in radius, embedded into the larger sphere to show proper z order and clipping. The full sphere (front and back) are drawn.

The foreground polygon, by contrast, is approximately 20 units from the observer.

I have constructed a z-buffer rendering engine which renders depth using 32-bit single-precision IEEE-754 floating point numbers to represent z_s. Using the traditional perspective matrix, the depth values become indistinguishable from each other, as their values approach 1. This results in the following image:

Notice the bottom half of the sphere is incorrectly rendered, as is large chunks of the smaller red sphere.

Using the new perspective matrix, and this error does not occur in the final rendered product:

The code to render each is precisely the same; the only difference is the perspective matrix:

public class Main
{
    /**
     * @param args
     */
    public static void main(String[] args)
    {
        Matrix m = Matrix.perspective1(0.8, 1, 1);
        renderTest(m,"image_err.png");
        
        m = Matrix.perspective2(0.8, 1, 1);
        renderTest(m,"image_ok.png");
    }

    private static void renderTest(Matrix m, String fname)
    {
        ImageBuffer buf = new ImageBuffer(450,450);
        m = m.multiply(Matrix.scale(225,225,1));
        m = m.multiply(Matrix.translate(225, 225, 0));
        
        Sphere sp = new Sphere(0,0,-5000000000000d,4000000000000d,0x0080FF);
        sp.render(m, buf);
        
        sp = new Sphere(700000000000d,100000000000d,-1300000000000d,300000000000d,0xFF0000);
        sp.render(m, buf);
        
        Polygon p = new Polygon();
        p.color = 0xFF00FF00;
        p.poly.add(new Vector(-10,-3,-20));
        p.poly.add(new Vector(-10,-1,-19));
        p.poly.add(new Vector(0,0.5,-22));
        p = p.transform(m);
        p.render(buf);
        
        try {
            buf.writeJPEGFile(fname);
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Notice in the call to main(), we first get the traditional perspective matrix with the far clipping plane set to infinity, then we get the alternate matrix.

The complete sources for the rendering test which produced the above images, including custom polygon renderer, can be found here.

With this technique it would be possible to render correctly large landscapes with very distant objects without having to render the scene twice: once for distant objects and once for near objects. To use this with OpenGL would require adjusting the OpenGL pipeline to allow the far clipping plane to be set to 0 instead of 1 in z_s space. This could be done with the glClipPlane call.

Conclusion

For modern rendering engines which represent the depth buffer using IEEE-754 (or similar) floating point representations, using a perspective matrix which converges to 1 makes little sense: as values converge to 1, the magnitude of the error is similar to that of a fixed-point representation. However, because of the nature of the IEEE-754 floating point representation, convergence to 0 has much better error characteristics.

Because of this, a new perspective matrix than the one commonly used should have better rendering accuracy, especially if we change the far clipping plane to ∞.

By using this new perspective matrix we have demonstrated a rendering environment using 32-bit single-precision floating point values for a depth buffer which is capable of representing in the same scene two objects whose size differs by 11 orders of magnitude. We have further shown that the error in representation of the z_s depth over the distance of an object should remain linear–allowing us to have even greater orders of magnitude difference in the size of objects. (Imagine rendering an ant in the foreground, a tree in the distance, and the moon in the background–all represented in the correct size in the rendering system, rather than using painter’s algorithm to draw the objects in order from back to front.)

Using this matrix in a system such as OpenGL, for rendering environments that support floating point depth buffers, would be a matter of creating your own matrix (rather than using the built in matrix in the GLU library), and setting a far clipping plane to z_s = 0 instead of 1.

By doing this, we can effectively say goodbye to the far clipping plane.

Addendum:

I’m not sure but I haven’t seen this anywhere else in the literature before. If anyone thinks this sort of stuff is worthy of SigGraph and wants to give me any pointers on cleaning up and publishing, I’d be greatful.

Thanks.

On Memory and Memory Management

Posted on September 4, 2010 by William Woody

This will be a bit of an introductory article on memory, written in part for my wife and for anyone else who may find such an introduction useful.

In The Beginning…

In the beginning there was RAM, random access memory. A microprocessor which could execute instructions would be attached to that RAM, which could be accessed by special instructions which operated on the contents of that memory.

Some microprocessors (for example, the Z-80) used special instructions which would use two 8-bit integer registers (such as register D and E) to form a 16-bit address into RAM, or would use special registers (the IX and IY index registers) to access memory. Others (such as the 68000 CPU) would have a bank of dedicated address registers which are used to access memory.

Writing software in this era was simple: you would define the location of various objects that would be stored in memory, and you would use those locations to access the stored data.

In today’s modern parlance all objects are fixed and global. There is no allocating objects or releasing those; that came later. Instead, there is just picking the size of the records (or structures) stored in memory, and making sure there is enough space left in RAM for your stack.

Since early microprocessors only had a very small and limited amount of memory, this is fine. Embedded development with toolchains such as the Small Device C Compiler, which can compile code for the HC08 series of CPUs, don’t generally provide any way to allocate memory; instead, you declare all of your objects as global structures.

As an example, a program I’ve been tinkering with on the Arduino platform (and I really believe every high school student who wants to get into programming needs one) emulates a calculator with no memory. The memory declaration looks something like:

/*  Calculator Storage in RAM */
Double GDisplay;
Double GInput;
Double GScratch;
boolean GIsInput;
boolean GIsClear;

When compiled it will compile into an assembler statement that may look something like:

.EQU GDisplay = 0x0100
.EQU GInput = 0x0108
.EQU GScratch = 0x0110
.EQU GIsInput = 0x0118
.EQU GIsClear = 0x0119

Fixed allocation of memory structures also makes sense with certain types of game development, where performance and reliability of the code path is essential. For example, a 3D game such as the early game Descent could store for each level the size of the rendering map and the maximum number of records needed to process and render a level regardless of your location in the maze. Then, when the level loads, the proper amount of memory can be obtained using a function call similar to sbrk, which tells the operating system that you need a fixed amount of RAM, then partition the contents up yourself.

Various compiled games also use this technique, where the game is specified by a specialized game specification language. By being able to walk through all potential states in a game, it would be possible to determine the maximum memory footprint for that game, then request the fixed amount of memory for storage. This technique is used by Zork, amongst other things.

Fixed allocation of memory can also be used for certain high-performance applications where accuracy and speed and stability are paramount. For example, software handling incoming click requests in a search advertising system may wind up handing millions (or even billions) of click requests per minute–given that each click request can be designed as a fixed-sized record (or a record with a maximum known size), click requests can be accumulated into a fixed size array with certain summary data accumulated in global variables during store. Then, when a maximum time (or a maximum number) is reached, the formatted buffer and summary data can be spilled into a single write request into upstream systems which may only need the summary data.

Then Came The Heap.

Not all programs work well with the fixed allocation of objects. Sometimes you need a linked list of objects, or a heap list, or other more complex data structures where you cannot know a priori the number of records you will be handling.

Heap processing more or less works the same regardless of the programming language: there is a mechanism by which you can request a chunk of memory at a given size, and another call to release that memory. Sometimes there is a call that allows you to resize that memory block; resizing a memory block can be handled by releasing the old block and allocating a new one, copying the contents from one location to another.

Heap allocation works by using a large chunk of RAM dedicated to that heap, and, on a request for a chunk of memory, reserves it in RAM. There are many ways this can be done; the easiest to explain is the greedy algorithm, which reserves the first chunk of memory that can be found.

Allocated memory requires some bookkeeping information so the memory allocation code can know how to handle this chunk of memory: is it allocated, how big is the chunk that is reserved. So when you allocate memory, generally additional space is reserved prior to the address pointer with bookkeeping data; this is then used to resize memory (if resizing is allowed), and to know how much memory to mark as free when the free routine is called.

A simple malloc() and free()

We can easily implement a simple malloc and free routine to illustrate how a typical heap may work. We’ll make two assumptions, which are common to today’s modern processors. First, all allocated memory will be aligned (for efficiency sake) on a 16-byte boundary. (Some processors address things on 16-byte boundaries far more efficiently.) Second, we will use a four byte bookkeeping object which gives the size of the memory allocated, along with a 1 bit flag indicating if the area of memory is free or still allocated. Because we know all memory is aligned on a 16 byte boundary we know the least significant bit of the 32-bit length will never be used, so we use that bit for the free flag; this way we only need to use 4 bytes for our bookkeeping data.

By sketching out the code for a simple malloc() and free() we can also illustrate some of the interesting bugs that can come up while using the heap, such as accidentally using memory that was freed previously.

Footnote: We use ‘uint8_t’ to refer to 8-bit bytes, and ‘uint32_t’ to refer to 32-bit bytes. Because on most modern operating systems, memory can be addressed on a byte boundary, we can add or subtract from an address pointer by converting that pointer to a pointer to a byte object. For example:

a = (uint32_t *)(((uint8_t *)a) + 3);

The expression above will add 3 to the address register in ‘a’, pointing three bytes in from where it was pointing before.

Notice if we were doing this for a microprocessor with 16-bit addresses, we could use a uint16_t, or 2 byte integer, for the bookkeeping area instead.

Before we can use the memory, we must initialize the memory heap area to note that the entire heap is free. This means we need to set up a bookkeeping header that indicates that all of memory (minus the area for bookkeeping) is free. We also need to make sure the free memory itself is aligned on a 16 byte boundary–which means we must waste the first 12 bytes of memory. More advanced memory allocation schemes may make use of that area for other bookkeeping information, but for now we simply waste the memory.

When initialized our RAM area will look like:

Our initialization routine will look like:

/*	initialize_ram
 *
 *		Given the block of ram memory, we mark the entire 
 *	block as free. We do this by setting up free block 16 
 *	bytes in; we do this so that the first allocated block
 *	will be aligned on a 16 byte boundary. This wastes the
 *	bottom 12 bytes of memory which could, for a more
 *	sophisticated system, be used for other stuff.
 *
 *		We have GRam point to the first byte of RAM, and
 *	RAMSIZE is the size of the RAM area being managed.
 */

void initialize_ram()
{
	/* Find the location of the bookkeeping block for this.
	 * The address is 12 bytes in; 16 bytes for alignment 
	 * minus 4 bytes for the bookeeping area
	 */
	
	uint32_t *bookkeeping = (uint32_t *)(((uint8_t *)GRam) + 12);
	
	/*
	 *	Now mark the memory as free. The free size is 16
	 *	bytes smaller than the max ram size, and mark it
	 *	as free. We assume RAMSIZE is divisible by 16.
	 */
	
	*bookkeeping = (RAMSIZE - 16) | 1;
	
	/*
	 *	And finally mark the end bookkeeing block. Because of the way
	 *	we allocate memory, the top 4 bytes must be specially
	 *	marked as a reserved block. That's so we know we have
	 *	hit the top.
	 */
	
	bookkeeping = (uint32_t *)(((uint8_t *)GRam) + RAMSIZE - 4);
	*bookkeeping = 4;		// marked as reserved 4 bytes.
}

Free is simple. Because our convention is that a block of memory is considered free if the least significant bit of the 32-bit bookkeeping area is set, free simply sets that bit.

/*	free
 *
 *		Free memory. This works by finding the bookkeeping block
 *	that is 4 bytes before the current pointer, and marking the
 *	free bit.
 */

void free(void *ptr)
{
	/*
	 *	Subtract 4 bytes from the current pointer to get the
	 *	address of the bookkeeping memory
	 */
	
	uint32_t *bookkeeping = (uint32_t *)(((uint8_t *)ptr) - 4);
	
	/*
	 *	Mark the memory as free by setting the lowest bit
	 */
	
	*bookkeeping |= 1;
}

Most of the meat of our memory management system will be in the alloc call. This has to scan through all the free blocks, finding the first chunk of memory that can be reserved. We also, by convention, return NULL if there is no memory left that can be allocated.

The first thing our allocation routine does is find out how big a chunk of memory we need to reserve. Because we must guarantee everything is aligned on a 16-byte boundary, this means a request for 2 bytes must reserve 16 bytes; that way, the next allocation request will also be aligned correctly. (More sophisticated memory management systems may know enough to subdivide memory for smaller allocation requests; we don’t do that here.)

So we must calculate the size, including the extra 4 bytes needed for our bookkeeping block:

	/*
	 *	Step 1: Change the size of the allocation to align
	 *	to 16 bytes, and add in the bookkeeping chunk that
	 *	we allocate. Our pointer will return the first
	 *	byte past the bookkeeping memory.
	 */
	
	size = size + 4;		// Add bookkeeping
	if (0 != (size % 16)) size += 16 - (size % 16);	// align

Next, we need to scan through memory from the first block in memory, searching for a collection of free blocks which are big enough for us to reserve for our requested block.

	/*
	 *	Step 2: scan to find a space where this will fit.
	 *	Notice that we may have to piece together multiple
	 *	free blocks, since our free doesn't glue together
	 *	free blocks.
	 */
	
	ptr = (uint32_t *)(((uint8_t *)GRam) + 12);
	end = (uint32_t *)(((uint8_t *)GRam) + RAMSIZE);
	while (ptr < end) {
		if (0 == (1 & *ptr)) {
			/* Lowest bit is clear; this is allocated memory. */
			/* The bookkeeping area holds the total size of the */
			/* allocated area in bytes; thus, we can skip to */
			/* the next block by adding the bookkeeping area */
			/* to the current block. */
			ptr = (uint32_t *)(((uint8_t *)ptr) + *ptr);
		} else {
			/*
			 *	This area is free. Note that this is found, then
			 *	start scanning free areas until we piece together
			 *	something big enough to fit my request
			 */
			
			found = ptr;
			asize = *ptr & ~1UL;		// Get the size, clearing free bit
			ptr = (uint32_t *)(((uint8_t *)ptr) + (*ptr & ~1UL));	// next block
			while ((asize < size) && (ptr < end)) {
				if (0 == (1 & *ptr)) {
					/* We bumped against an allocated block of memory */
					/* Exit this loop and continue scanning */
					break;
				}
				
				/* Block is free. Add it up to this block and continue */
				asize += *ptr & ~1UL;
				ptr = (uint32_t *)(((uint8_t *)ptr) + (*ptr & ~1UL));	// next block
			}
			if (asize = end) return NULL;		// Could not find free space

This gets a bit complicated.

First, we set ptr and end to point to the start block and the end of memory, respectively. Next, we walk through while our pointer has not reached the end, looking for free memory.

Now our free() routine simply marks the memory as free; it doesn’t gather up blocks of free memory and glue them together. So our allocation routine has to do the job. When we first encounter a free block, we note how much memory the free block represents in asize, and we put the start of that free block in found. We then continue to scan forward until we either piece enough memory together to satisfy the size we need, or until we find a reserved block which prevents us from using this chunk of free memory.

If we run out of memory: that is, if the pointer ptr goes past end, then we can’t satisfy this request, so we return NULL.

Now that we’ve found a chunk of memory that satisfies our request, we piece together the free blocks, breaking the last free block in the list of free blocks if needed.

When this chunk of code is reached, found points to the start of our free memory, and ptr points to the last free block in the list of free blocks that may need to be split.

We write the correct bookkeeping data to mark the memory as allocated, and if that is shy of the end of the free blocks, we then write a free block bookkeeping mark:

	/*
	 *	Step 3: mark the block as allocated, and split the last free block
	 *	if needed
	 */
	
	*found = size;						// mark the size we've allocated.
	if (size < asize) {
		/* We have more than enough memory. Split the free block */
		/* First, find the pointer to where the free block should go */
		ptr = (uint32_t *)(((uint8_t *)found) + size);
		
		/* Next, mark this as a free block */
		ptr = (asize - size) | 1;
	}

This works correctly because asize is the total size of the range of free blocks we just glued together, so (uint8_t *)found + asize will point to the next block of memory past the free memory we just found.

Now that we’ve peeled off a chunk of memory, we need to return the memory itself. Up until now our pointers have been pointing at the first byte of the 4-byte bookkeeping record; the memory we’re allocating is just past that 4 byte record. So we need to return the first byte of our allocated memory itself:

	
	/*
	 *	The found pointer points to the bookkeeping block. We need to
	 *	return the free memory itself, which starts with the first byte
	 *	past the bookkeeping mark.
	 */
	
	return (void *)(((uint8_t *)found) + 4);

Putting our alloc routine together we get:

/*	alloc
 *
 *		Allocate the requested memory by scanning the heap
 *	of free blocks until we find something that will fit.
 *	We then split the free blocks and return the allocated
 *	memory.
 *
 *		If we are out of memory, we return NULL.
 */

void *alloc(uint32_t size)
{
	uint32_t *ptr;
	uint32_t *end;
	uint32_t *found;
	uint32_t asize;
	
	/*
	 *	Step 1: Change the size of the allocation to align
	 *	to 16 bytes, and add in the bookkeeping chunk that
	 *	we allocate. Our pointer will return the first
	 *	byte past the bookkeeping memory.
	 */
	
	size = size + 4;		// Add bookkeeping
	if (0 != (size % 16)) size += 16 - (size % 16);	// align
	
	/*
	 *	Step 2: scan to find a space where this will fit.
	 *	Notice that we may have to piece together multiple
	 *	free blocks, since our free doesn't glue together
	 *	free blocks.
	 */
	
	ptr = (uint32_t *)(((uint8_t *)GRam) + 12);
	end = (uint32_t *)(((uint8_t *)GRam) + RAMSIZE);
	while (ptr < end) {
		if (0 == (1 & *ptr)) {
			/* Lowest bit is clear; this is allocated memory. */
			/* The bookkeeping area holds the total size of the */
			/* allocated area in bytes; thus, we can skip to */
			/* the next block by adding the bookkeeping area */
			/* to the current block. */
			ptr = (uint32_t *)(((uint8_t *)ptr) + *ptr);
		} else {
			/*
			 *	This area is free. Note that this is found, then
			 *	start scanning free areas until we piece together
			 *	something big enough to fit my request
			 */
			
			found = ptr;
			asize = *ptr & ~1UL;		// Get the size, clearing free bit
			ptr = (uint32_t *)(((uint8_t *)ptr) + (*ptr & ~1UL));	// next block
			while ((asize < size) && (ptr < end)) {
				if (0 == (1 & *ptr)) {
					/* We bumped against an allocated block of memory */
					/* Exit this loop and continue scanning */
					break;
				}
				
				/* Block is free. Add it up to this block and continue */
				asize += *ptr & ~1UL;
				ptr = (uint32_t *)(((uint8_t *)ptr) + (*ptr & ~1UL));	// next block
			}
			if (asize = end) return NULL;		// Could not find free space
	
	/*
	 *	Step 3: mark the block as allocated, and split the last free block
	 *	if needed
	 */
	
	*found = size;						// mark the size we've allocated.
	if (size < asize) {
		/* We have more than enough memory. Split the free block */
		/* First, find the pointer to where the free block should go */
		ptr = (uint32_t *)(((uint8_t *)found) + size);
		
		/* Next, mark this as a free block */
		ptr = (asize - size) | 1;
	}
	
	/*
	 *	The found pointer points to the bookkeeping block. We need to
	 *	return the free memory itself, which starts with the first byte
	 *	past the bookkeeping mark.
	 */
	
	return (void *)(((uint8_t *)found) + 4);
}

We can now use this code to illustrate some interesting things about heap memory allocation.

First, notice how free() simply marks the memory as free, but without overwriting the memory. This is why the following code, while quite illegal, can still work:

int error1()
{
	/* Allocate some memory and initialize it */
	int *someWord = (int *)alloc(sizeof(int));
	*someWord = 5;
	
	/* Free the memory */
	free(someWord);
	
	/* Now access the freed memory */
	return *someWord;
}

This is not guaranteed to work. Far from it, it’s illegal to access memory that was released after it was released–you don’t know what is going to happen to that chunk of memory. But in most cases, it’s simply marked as no longer reserved–but the values are still there in memory.

And this becomes a problem if the memory is reallocated to some other pointer which does something else with the memory:

int error2()
{
	/* Allocate some memory and initialize it */
	int *someWord = (int *)alloc(sizeof(int));
	*someWord = 5;
	
	/* Free the memory */
	free(someWord);
	
	/* Allocate some other memory */
	int *someOtherWord = (int *)alloc(sizeof(int));
	*someOtherWord = 6;
	
	/* Now access the freed memory */
	return *someWord;
}

What makes bugs like this very frustrating to find is that, in general, the patterns of allocs and frees are not quite so uniform. It can be quite unpredictable; for example, while the above probably will cause 6 to be returned using our version of alloc and free, the following may or may return 5 or 6 or even some other value, depending on how memory has been fragmented in the past:

int error3()
{
	/* Allocate some memory and initialize it */
	int *someWord = (int *)alloc(sizeof(int));
	*someWord = 5;
	
	/* Free the memory */
	free(someWord);
	
	/* Allocate some other memory */
	int *someOtherWord = (int *)alloc(sizeof(28));
	*someOtherWord = 6;
	
	/* Now access the freed memory */
	return *someWord;
}

Because the size of the second allocation is different than the first, it may or may not use the previously allocated memory.

Second, over time memory can fragment. Fragmentation can cause things to slow down over time, and they can even put you in the situation where after doing a bunch of small allocations and frees, you may still have plenty of memory left–but no block is large enough to put your request.

Different memory management methods attempt to resolve this problem using various techniques, of course–and on most modern operating systems there is plenty of memory so fragmentation is unlikely.

As an aside, sometimes it is useful to allocate a whole bunch of tiny little objects and release them all at once. For example, a 3D rendering program may dynamically allocate a whole bunch of objects during rendering–but free them only after the entire image is drawn on the screen.

To do this you can allocate large chunks of memory, then subdivide the memory as needed, keeping the large allocated chunks of memory in a linked list, so when it comes time to free all of memory, the free operation can be done in one call.

Another interesting thing to point out is that memory has to be explicitly allocated or freed. We are just one step above address registers in the microprocessor; our heap is something we must manually maintain. If we set a pointer to a new address, and we don’t free the memory that our pointer used to be pointing to, the free() routine has no idea that our memory must be freed.

In C and C++ this is the status quo: you must explicitly allocate or free memory. C++ adds the concept of ‘new’ and ‘delete’ which call a class constructor after the memory is allocated and the class destructor before the memory is freed; however, memory must still be explicitly allocated or freed.

In a world where there is only global memory, auto (stack-based) memory and heap memory this works okay. But once we start talking about object-oriented programming it is natural for us to talk about two pointers pointing to the same object in memory. And knowing when that object should be freed() becomes far more complicated than in the traditional procedural-based allocation scheme where we guarantee by convention that only one pointer holds onto a chunk of memory at a time.

And there are two ways we can solve this problem: resource counting and garbage collection.

Garbage Collection

Garbage collection is a technique whereby the operating system will automatically find memory that is no longer being used. The advantage of garbage collection is that you don’t have to remember to call free(). The disadvantage is that garbage collection can be computationally expensive and hard to get right.

There are several ways to handle garbage collection. The technique I’ll outline here is the simple mark and sweep technique to find (and mark) all memory that is currently being used, then sweeping through and freeing memory that is not marked.

Essentially it works like this.

With each allocated chunk of memory, we also reserve a bit used to mark that memory. From our allocator above, we could use the second to least significant bit to represent marking. We need a mark routine to mark the memory as such:

/*	mark
 *
 *		This marks memory. This marks the pointer by flipping the mark
 *	bit
 */

void mark(void *ptr)
{
	if (ptr == NULL) return;
	
	/*
	 *	Subtract 4 bytes from the current pointer to get the
	 *	address of the bookkeeping memory
	 */
	
	uint32_t *bookkeeping = (uint32_t *)(((uint8_t *)ptr) - 4);
	
	/*
	 *	Mark the memory by setting the second lowest bit
	 */
	
	*bookkeeping |= 2;
}

The first step to garbage collection is to do the mark phase: to mark all of the memory that is currently referred to by other chunks of memory in our system. To do this we use a ptr variable which points at the current block; as we sweep forward across all the blocks in the system, if we find a block that is marked, we then try to find all the pointers in that block, and mark them. This repeated marking continues until we no longer have any new memory blocks that need to be marked.

After we’ve done this marking, we sweep, freeing all blocks of memory that is not marked.

The hard part of any memory collection mechanism is to know in global memory and on the stack which are the address pointers and which are not. Languages such as Java keep class information around to allow the garbage collector to know exactly which things in memory refer to address pointers. Other languages, such as C, do not maintain this information–and so the garbage collector effectively “guesses.”

We assume in our code we have three methods: one which will mark all pointers in global memory and on the stack, another which returns the number of pointers inside an allocated memory object, and a third which returns the pointers in an allocated memory object.

/*	allocGC
 *
 *		Allocate but with a garbage collector. We do the mark/sweep phase
 *	on memory. We rely upon two other calls: a call to mark all pointers in
 *	global memory and on the stack, and a call which can tell us within an
 *	allocated chunk of memory which are the pointers by marking them.
 *
 *		In both cases we assume the mark routine will call mark() above
 *	to mark the memory as in use
 */

void *allocGC(uint32_t allocLen)
{
	uint32_t *ptr;
	uint32_t *end;
	uint32_t *tmp;
	uint32_t *tmp2;
	uint16_t len,i;

	/*
	 *	Try to allocate
	 */
	
	ptr = alloc(allocLen);
	
	/*
	 *	Out of memory?
	 */
	
	if (ptr == NULL) {
		/*
		 *	Out of memory; do garbage collection. First, clear the mark
		 *	bits for allocated memory
		 */
		
		ptr = (uint32_t *)(((uint8_t *)GRam) + 12);
		end = (uint32_t *)(((uint8_t *)GRam) + RAMSIZE);
		while (ptr < end) {
			*ptr &= ~2UL;		// clear second least bit
								// move to next block in memory
			ptr = (uint32_t *)(((uint8_t *)ptr) + (*ptr & ~1UL));
		}
		
		/*
		 *	Now ask to mark memory on the stack and in global heap space
		 */
		
		markGlobalStack();
		
		/*
		 *	Run through and mark all references. We rely upon the 
		 *	routines numPointersInAllocBlock and pointerInAllocBlock
		 *	to return the pointers inside a block
		 */
		
		ptr = (uint32_t *)(((uint8_t *)GRam) + 12);
		while (ptr < end) {
			/*
			 *	If this pointer is marked, then find all the pointers that
			 *	are inside this pointer, and mark them, moving the pointer
			 *	backwards to the earliest unmarked object
			 */
			
			if (0 != (*ptr & 2)) {
				/*
				 *	Memory marked. Find all the pointers inside
				 */
				
				tmp2 = ptr;
				len = numPointersInAllocBlock(ptr);
				for (i = 0; i  tmp2) tmp2 = tmp;
						*tmp &= 2;
					}
				}
				
				/*
				 *	We may have moved tmp2 before ptr; this means we need
				 *	to pick up sweeping from tmp2, since we have a pointer
				 *	pointing backwards in memory
				 */
				
				ptr = tmp2;
			}
			
			/*
			 *	Move to next block
			 */
			
			ptr = (uint32_t *)(((uint8_t *)ptr) + (*ptr & ~1UL));
		}
		
		/*
		 *	Now that we've gotten here, we need to free all allocated memory
		 *	that is not marked
		 */
		
		ptr = (uint32_t *)(((uint8_t *)GRam) + 12);
		while (ptr < end) {
			if (0 == (0x3 & *ptr)) {		// allocated, unmarked?
				*ptr |= 1;					// mark as freed
			}
			/*
			 *	Move to next block
			 */
			
			ptr = (uint32_t *)(((uint8_t *)ptr) + (*ptr & ~1UL));
		}
		
		/*
		 *	Now try again
		 */
		
		ptr = alloc(allocLen);
	}
	return ptr;
}

Essentially our garbage collector starts by sweeping all memory and clearing the mark bit.

We start by marking all the objects (using markGlobalState) that are pointed to by objects on the stack, or by objects in global memory:

Now we start in the loop to run through the blocks. Our ptr routine searches for the next marked block of memory, and then marks all the blocks that object points to:

We continue to mark foward, moving the pointer backwards only if we encounter a pointer to an earlier block in memory that is currently unmarked. This rewinding of the pointer is necessary to handle backwards pointing references without having to rewalk all of the blocks from the start of the heap:

(Because this pointer refers to something before the previous pointer, we move our pointer backwards:)

Once we’re done–and this is guaranteed to complete because there is only a finite number of objects, and we only rewind the pointer when something is unmarked–we then sweep through all of memory, marking as free objects we were unable to reach. We know these objects are freed because we could not reach them:

Reference Counting

Garbage collection is very difficult to do correctly. You need to have a method, no matter in what state you’re in, to know where the pointers are, and what they point to. And you have to have a way to look inside of every object and know what chunks of memory in the heap are pointers, in order to correctly mark things.

In other words, you need to provide markGlobalState, numPointersInAllocBlock, and pointerInAllocBlock or the equivalent.

An easier way to track the pointers pointing to an object is by tracking a reference count associated with each object. This requires some work on the part of the developer; in fact, it requires that you explicitly call routines similar to alloc and free to keep track of the reference count to a collection of objects. On the other hand, it doesn’t require a lot of work to get working correctly. And this technique has been adopted by Microsoft’s COM system and Apple’s Objective-C on the Macintosh or iOS operating systems.

(Yes, I know the latest versions of Objective C on the Macintosh provide garbage collection. However, you can still do reference counting, and you must do reference counting on iOS.)

Reference counting is extremely easy to do. Essentially it involves having the objects you want managed via reference counting internally store a reference count. Newly allocated objects set the reference count to 1, and if the reference count reaches zero, the object frees itself.

In C++ we can easily declare a base object for reference counting:

class BaseObject
{
	public:
					BaseObject();
		
		void			Retain();
		void			Release();
		
	protected:
		virtual		~BaseObject();

	private:
		uint32_t		fRefCount;
};

Our base class stores a reference count, called fRefCount. When we allocate our object, we first set the reference count to 1:

BaseObject::BaseObject()
{
	fRefCount = 1;
}

We then need to mark something as retained: meaning there is a new pointer pointing to the same object. The retain method can be written:

void BaseObject::Retain()
{
	++fRefCount;
}

Releasing the object then decrements the count, and if the count reaches zero, frees the object:

void BaseObject::Release()
{
	if (0 == --fRefCount) {
		delete this;
	}
}

In Objective C (but not on Microsoft COM) we have an additional method, called “autorelease”, which adds the object to an NSAutoreleasePool, which automatically calls release when the pool is drained, either explicitly or implicitly at the end of each event loop. In C++ we can do something similar by extending our base class by adding an array of object pointers:

class BaseObject
{
	public:
					BaseObject();
		
		void			Retain();
		void			Release();
		void			AutoRelease();
		
		static void	Drain();
		
	protected:
		virtual		~BaseObject();

	private:
		uint32_t		fRefCount;
		static std::vector gPool;
};

We then add an AutoRelease and a Drain methods:

void BaseObject::AutoRelease()
{
	gPool.push_back(this);
}

void BaseObject::Drain()
{
	/* Run through our array of objects */
	int i,len = gPool.size();
	for (i = 0; i Release();
	}
	/* Now erase the array */
	gPool.clear();
}

Notice that simple assignment of pointers doesn’t actually call Retain or Release anymore than it automatically called alloc() and free() described earlier. Instead, we must use a coding convention to know when we should Retain, when we should Release, and (if present) when we should AutoRelease.

The Microsoft COM rules are quite simple: if a function call returns a pointer, you must release that pointer in your routine when you are no longer using it. So, for example, suppose we have a routine GetThing() which returns a BaseObject:

BaseObject *GetThing()
{
	return new BaseObject();
}

Then a caller must in turn release the value:

void UseBaseThing()
{
	BaseObject *obj = GetThing();
	
	/* Do some stuff to this */
	
	obj->Release();
}

Now if the routine GetThing is returning a reference to an object that it is storing in memory, then when the object is returned, the routine’s return value “owns” the reference to that global object, but the ownership must continue to be held locally. So you would use Retain:

BaseObject *gPtr;

BaseObject *GetThing()
{
	gPtr->Retain();
	return gPtr;
}

And similarly, if the caller function wants to hold onto the pointer (say, by storing it in a global variable), rather than call retain we simply keep ownership of the pointer:

BaseObject *gPtr2;

void UseBaseThing()
{
	BaseObject *obj = GetThing();
	/* Store object; don't release it--we still own the reference. */
	gPtr2 = obj;
}

The rule is quite simple: if a pointer is returned, the pointer must be released. But it adds complexity: it means you must constantly be calling the ‘Release’ method all the time, and that can become quite cumbersome.

On the other hand, and the key point to all of this, is that the retain and release rules are simple–and they are local: you don’t need to know how any other module in the system works, you only need to know what to do locally.

Apple gets around the problem of constantly having to release objects (and retain objects that are held locally) by introducing the -autorelease method.

On the Macintosh (and iOS), the rules are given on Apple’s web site. The two rules are:

(1) You gain ownership of an object only if you create it (using -alloc or any method that starts with ‘new’, or contains ‘copy’), or if you explicitly retain the object.

(2) You release or autorelease the object when you no longer need to hold ownership of the object.

Using these two rules, we wind up writing less code–but things can get a little more complicated. In our example above, our ‘GetThing’ routine, because it does not start with ‘new’, would simply return the object:

BaseObject *gPtr;
+ (BaseObject *)getThing
{
	return gPtr;
}

If we were allocating this object (as in our first example), we would, because of the naming convention either rename our method to ‘newThing’:

+ (BaseObject *)newThing
{
	return [[BaseObject alloc] init];
}

Or we would need to make sure that ownership is not passed up by marking the object as autorelease:

+ (BaseObject *)getThing
{
	return [[[BaseObject alloc] init] autorelease];
}

In fact, this pattern is so common you’ll find yourself typing “alloc] init] autorelease]” nearly on autopilot.

The call “UseBaseThing” is similarly changed, depending on how we’re using it. If we don’t hold onto a reference to the object, we would not need to call ‘release’ because we aren’t hanging onto the object:

+ (void)useBaseThing
{
	BaseObject *obj = [BaseObject getThing];
	
	/* Do some stuff to this */
	/* Notice we don't release this object */
}

And if we are hanging onto the object, we must retain the object:

+ (void)useBaseThing
{
	BaseObject *obj = [BaseObject getThing];
	gPtr2 = [obj retain];
}

Likewise, if we are calling newThing, we’d be getting ownership back from the call–so we would need to release it as appropriate. So, our examples would be:

+ (void)useBaseThing
{
	BaseObject *obj = [BaseObject newThing];
	
	/* Do some stuff to this */

	[obj release];
}

And, if holding the object, we already have ownership, so we don’t need to release it:

+ (void)useBaseThing
{
	BaseObject *obj = [BaseObject getThing];
	gPtr2 = obj;
}

Notice in all of the above, simply assigning or copying pointers around in a pointer doesn’t actually do anything on its own. A pointer is simply like an integer, but with the integer referring to an address in memory. In all of this evolution from fixed locations in RAM to garbage collection and object reference counting, we have never changed the immutable fact that simply copying or adding values to an address doesn’t affect how heap memory is handled. Garbage collection takes place after an object is no longer pointed to–and sometimes objects that are no longer referenced by a pointer can live for a very long time.

There are other subtleties that can take place here: different versions of memory management tools may do different things when a chunk of memory is allocated or freed. Some test tools may even store the location in a program where an object is allocated, so if there is an unbalanced alloc/free cycle, the line of code in error can be discovered easily. And there are many flavors of garbage collection out there which each behave differently, though ultimately result in the same end.

Further, with reference counting, cycles of objects can easily be created which cause the objects to linger long after those objects are no longer actually in use. It’s why it is important to think about cycles of pointers, especially when developing UIView objects which may hold references to other UIViews to perform certain operations.

In fact, a very common bug is to create one UIView that refers to another:

@class BView;
@interface AView : UIView
{
	BView *view;
}

@property (retain) BView *view;
@end

@interface BView : UIView
{
	AView *view;
}

@property (retain) AView *view;
@end

The problem here is that if AView and BView are part of the same view hierarchy, and are assigned to each other, then when the view hierarchy is released, AView and BView retain each other–preventing the memory from being reclaimed even though it is no longer being used.

In cases like this, when a third object holds two others which refer to each other–in this case, implicitly, by the UIWindow holding all of the views in the view hierarchy–it is better if only an unretained reference is held to these objects instead:

@class BView;
@interface AView : UIView
{
	BView *view;
}

@property (assign) BView *view;
@end

@interface BView : UIView
{
	AView *view;
}

@property (assign) AView *view;
@end

Assignment is not ownership, and when the window is released, AView and BView will both be released successfully.

Hopefully this brief overview of memory management, from setting fixed locations in RAM to heaps to garbage collection and reference counting, will give you a good idea of how memory management actually works–and what the pitfalls are.

The key takeaways should be:

(1) Assigning pointers is not ownership. Simply writing Pointer *a = b; doesn’t actually grant ownership to ‘a’ when it points to ‘b’. You must, unless in a garbage collection environment, explicitly ask for and release ownership.

(2) If not using reference counting, the assumption is that only one pointer actually “owns” an object. For object-oriented programming this is too strict a restriction, and thus we must either introduce garbage collection or establish reference counting and conventions on how references are counted.

(3) For reference counting systems, there are (to my knowledge) two conventions for reference counting: the Microsoft COM convention, and the Apple Objective-C convention. You must also be aware of cyclical ownership references: if you accidentally grant ownership that turns into a cycle or ring of ownership, objects may leak because they mutually refer to each other, without actually being used anywhere else.

Four features from Java which are really cool.

Posted on September 2, 2010 by William Woody

There are, in my opinion, four basic language features in Java which make the language extremely cool–in that they allow IDE developers and software developers to quickly and easily deploy tools which make working with Java very easy.

I wanted to point out these features in the hope that future languages (or future extensions to other existing languages such as C++ or Objective C) could incorporate these features, in order to make those language ecosystems better overall.

Now there are a lot of things that are cool about Java. The standard RTL, so there is a standard way to create multiple threads, do file I/O, networking or other similar things is quite cool. (I’m used to the days of early versions of Pascal or C where it was anybody’s guess how to do these things.) But in my estimation the following four features have made the overall Java ecosystem quite friendly compared to other languages.

1. Reflection.

Java’s reflection system is quite complete, allowing full introspection for any given object of the class of that object, the interfaces it implements, the base class it extends, the methods it implements and the fields that are contained in that class. With methods you can introspect the parameters and the return values. You can even dynamically, using the reflection system, construct objects on the fly and invoke methods on the fly.

Java’s reflection system is far more powerful than similar systems in Objective C (which, by design, cannot really allow introspection of the methods implemented by a class, since methods are just messages and there is no strong association of implemented messages), or in C++ (which really only allows you to discover the class of an object, and that’s it.)

Later versions of Java even provide an annotation mechanism by which classes can be annotated or marked with special flags, so during introspection different classes can be handled in different ways.

This level of reflection allows one to construct a complete dynamic serialization library, serializing and deserializing objects without ever needing the object to know what is being done to it.

And because the reflection information is contained (as a first class, well documented data structures) inside a compiled .class file, it is not all that difficult to compile a Java file, then introspect the .class file and provide information about that class. By using this it is possible for an IDE to automatically determine, for example, which methods in an abstract class need to be implemented by a child class, and automatically write the missing method calls for you. I suspect in fact this is how the Eclipse functions to create a new class, populating the methods that need to be implemented, is performed.

I use that all the time.

2. Proxying.

Java also has the ability to, given an interface class declaration, create a proxy class which provides an implementation of that interface, redirecting the method calls to another object.

Proxying is a very powerful mechanism which allows remote procedure calls to be implemented with just a few lines of code. Proxying also allows other very powerful techniques to be implemented, such as using interface methods to define the constant values in a property file, and automatically associate variables in a dynamically loaded configuration file.

While proxying is a bit of a one-trick horse, it provides a tremendous amount of power that, combined with reflection, allows you to do RPC without having to create a RMI language specification and compiler to build the client and server components. You can infer the parameters with reflection and redirect with proxying.

3. Exception Stack Introspection.

Of course most languages have exceptions. What makes Java really cool is the ability to dump the function call stack when an exception is thrown. This is an extremely powerful mechanism because it allows you to know precisely what was thrown and where it was thrown from. And most of the time, knowing what happened and where gives you a huge clue as to why something went wrong.

In fact, I’d say the biggest mistake I’ve ever seen a Java programmer make is to re-throw an exception without setting the cause parameter of the re-thrown exception. For example, I’ve seen the following:

try {
    // A whole bunch of complicated crap with calls
    // into thousands of lines of error-prone methods.
    ...
}
catch (Exception someException) {
    throw new StandardException("All hell broke loose.");
}

Then I see the following:

com.chaosinmotion.mything.StandardException: All hell broke loose.
	at com.chaosinmotion.mything.Test.doSomething(Test.java:19)
	at com.chaosinmotion.mything.Test.main(Test.java:32)

And I want to murder the developer who couldn’t be bothered to add an ‘initCause’ call to the rethrown exception.

4. Inner classes and anonymous classes

To me, these both have the same net effect: they give the developer the ability to define a class inside another class, which has access to the parameters of the outer class, which can then be used as a form of closure. And closures are cool because they allow a callback function or method invocation to have access to the immediate lexical environment where the functioning requiring the closure to be invoked.

For example, suppose we have a method call that takes an interface, where the method in that interface is called for each list of objects in a system:

    private interface Callback
    {
        void object(Collection l);
    }

    private void getAllObjects(Callback callback)
    {
        ....
    }

We can gather up all of the objects in a single list using an anonymous inner class in a function call:

    private List gatherAll()
    {
        final ArrayList n = new ArrayList();
        
        getAllObjects(new Callback() {
            public void object(Collection l)
            {
                n.addAll(l);
            }
        });
        
        return n;
    }

While Java’s implementation of anonymous functions may not meet the strict criteria of closures, in that you do not get full read/write access to all the stack variables within the function where the anonymous class is declared (thanks to the Funarg Problem), read-only access to mutable objects gets us close enough that it doesn’t really make much difference.

Closure-like functionality is such a cool language feature that Apple added it to the latest version of Objective C. Something like the above could be done by declaring a method -getAllObjects: which takes a block–a reference to a function with closure:

	- (void)getAllObjects:(void (^)(NSArray *))callback;

Then calling it with a block that accumulates the results:

    - (NSMutableArray *)gatherAll
    {
        NSMutableArray *n = [[[NSMutableArray alloc] init] autorelease];

        [self gatherAllObjects: ^(NSArray *param) {
            [n addObjectsFromArray:param];
        }];

        return n;
    }

The reason for me picking these four features is simple: I believe if other languages were extended to provide these features, then it would not only make the languages themselves more useful, but if they were provided, they would also allow the ecosystem of IDEs and compilers to become more useful as well. Reflection is extremely important to the ecosystem of IDEs: by being able to parse some sort of data structure during development that gives full inspection of the various components of a class or collection of function calls, it would make automatic code generation far easier to create. Better yet, if compilers for a given language could standardize on an intermediate “story of your compile” like structure that also gives line numbers for compiled objects (as is provided in Java class files with debugging turned on), it would make it extremely easy to automatically generate code on the fly during development.

And every language has an undue amount of bookkeeping stuff that needs to be written which make those languages cumbersome to use. C++, for example, requires all methods to be described in two separate places: once in the header file, and again with the method code. Imagine an IDE which could automatically generate the code declarations based on the header declarations, leaving you to only fill in the blanks. Or an IDE which could automatically add the required methods from the abstract class method declarations in an abstract C++ class.

Scroll FlowCover to a specified panel.

Posted on September 2, 2010 by William Woody

I thought for some reason this code was in FlowCover. It’s not, so here it is.

The following routine, if added below -startAnimation: will cause the tiles to scroll to the specified tile, with pos specified from 0 to the max-1 tile.


- (void)runToPos:(int)pos
{
	int max = [self numTiles]-1;
	if (pos  max) pos = max;
	
	startOff = offset;
	startSpeed = sqrt(fabs(pos - startOff) * FRICTION * 2);
	if (pos < startOff) startSpeed = -startSpeed;
	
	runDelta = fabs(startSpeed / FRICTION);
	startTime = CACurrentMediaTime();
	
	NSLog(@"startSpeed: %lf",startSpeed);
	NSLog(@"runDelta: %lf",runDelta);
	timer = [NSTimer scheduledTimerWithTimeInterval:0.03
					target:self
					selector:@selector(driveAnimation)
					userInfo:nil
					repeats:YES];
}

The way this works is to calculate the flick speed necessary to run the animation to the specified position, and runs the animation.

Time Zones are a pain in the ass.

Posted on September 1, 2010 by William Woody

Some interesting links I found that discuss time zones:

Complete timezone information for all countries. – Just as the label says

The official US time (NIST & USNO) – Displays the current time in the 10 major time zones in the United States.

Time Zone Converter – Allows a search of the various time zones in the world.

What makes time zone conversions a pain in the ass is that each jurisdiction has control over its own timezone. In some places (like California) we’re on Pacific Standard Time/Pacific Daylight Time, period, thankyouverymuch, haveaniceday.

But in places like Indiana, where every blasted county has it’s own ideas as to if it is in Central Standard Time, or Eastern Standard Time, and if the cows there can tolerate the shift between daylight savings time–well, the tz database becomes a hot mess, with things like “America/Indiana/some-random-place” littered throughout. On the other hand, most of that hot mess boils down to “this week, Knox County Indiana has decided to switch time zones from central to eastern”–which, for a UI timezone picker, doesn’t really matter. The fine folks of Knox County can just pick “Central” or “Eastern” and be done with it.

Sometimes the easiest sounding thing, like “pick a time zone”, becomes a royal pain in the neck. And even easier things like “what time is it in GMT at my location” become royally hard. It’s like that, when local politics gets involved.

There is nothing new under the sun.

Posted on August 30, 2010 by William Woody

Well, the rant on TechCrunch has gone global: Tech’s Dark Secret, It’s All About Age.

Excuse me while I throw in my two cents, as a 44 year old software developer.

Pretty much all of the useful stuff in Computer Science was invented by the 1960’s or 1970’s. Very little is out there today that is really “new”: MacOS X, for example, is based on Unix–whose underpinnings can be traced back to 1969, with most of the core concepts in place by the early 1980’s.
Even things like design patterns and APIs and object oriented programming stem from the 70’s and 80’s. Sure, the syntax and calling conventions may have changed over the years, but the principles have stayed the same.

For example, take the MVC model first discussed formally 20 years ago. The ideas behind that weren’t “invented” then; the MVC papers from Talgent simply codify common practices that were evolving in the industry well before then. One can find traces of the ideas of separating business logic from presentation logic in things like Curses, or in Xerox Parc’s work from the 1970’s. I remember writing (in LISP) calendrical software for Xerox as a summer intern at Caltech, using the principles of MVC (though not quite called that back then) in 1983.

Or even take the idea of the view model itself. The idea of a view as a rectangular region in display space represented by an object which has a draw, resize, move, mouse click handler and keyboard focus handler events can be found in InterLisp, in NextStep, in Microsoft Windows, on the Macintosh in PowerPoint; hell, I even wrote a C++ wrapper for MacOS 6 called “YAAF” which held the same concepts. The specific names of the specific method calls have changed over the years, but generally there is a draw method (doDraw, -drawRect:, paint, paintComponent, or the like), a mouse down/move/up handler, a resize handler (or message sent on resize), and the like.

The idea never changes; only the implementation.

Or hell, the Java JVM itself is not new: from P-machines running a virtual machine interpreter running Pascal to the D machine interpreter running InterLisp, virtual machine interpreters running a virtual machine has been around longer than I’ve been on this Earth. Hell, Zork ran on a Virtual Machine interpreter.
I suspect one reason why you don’t see a lot of older folks in the computer industry is because of self-selection. Staying in an industry populated by Nihilists who have to reinvent everything every five years or so (do we really need Google Go?) means that you have to be constantly learning. For some people, the addiction to learning something new is very rewarding. For others, it’s stressful and leads to burnout.
Especially for those who are smart enough to constantly question why we have to be reinventing everything every five years, but who don’t like the constant stress of it–I can see deciding to punt it all and getting into a job where the barbarians aren’t constantly burning the structures to the ground just because they can.

I know for a fact that I don’t see a lot of resumes for people in their 40’s and 50’s. I’m more inclined to hire someone in their 40’s as a developer than someone in their 20’s, simply because you pay less per year of experience for someone who is older. (Where I work, there is perhaps an 80% or 90% premium for someone with 4 or 5 times the experience–a great value.)

But I also know quite a few very smart, bright people who decided they just couldn’t take the merry-go-round another time–and went off to get their MBA so they could step off and into a more lucrative career off the mental treadmill.

I have to wonder, as well, where I would be if I had children. Would I have been able to devote as much time reading about the latest and greatest trends in Java development or Objective C or the like, if I had a couple of rug-rats running around requiring full-time care? (I probably would have, simply because I’d rather, on the whole, read a book on some new technology than read the morning paper. I would have probably sacrificed my reading on history and politics for time with my children.)
There is also this persistent myth that older people have familial obligations and are less likely to want to work the extra hours “needed to get the job done.” They’re less likely to want to pull the all-nighters needed to get something out the door.
But in my experience, I have yet to see development death marches with constant overnighters paid off in pizza that didn’t come about because of mismanagement. I don’t know another industry in the world where mis-managing the resource sizing, and demanding your workers work overtime to compensate for this failure to do proper managerial resource sizing and advanced development planning is seen as a “virtue.”

And I suspect the older you get, the less likely you are to put up with the bullshit.

Having seen plenty of product make it to market–and plenty not make it to market, and having lived through several all nighters and product death marches, I can see a common theme: either a product’s sizing requirements were mismanaged, or (far more commonly) upper management is incapable of counting days backwards from a ship date and properly assessing what can be done.

The project I’m on, for example, was given nearly a year to complete. And Product Management pissed away 7 of those months trying to figure out what needs to be done.

The younger you are, the less likely you are to understand that three months is not forever, and if you need to have something in customer hands by December, you have to have it in QA’s hands by September or October–which means you have to have different modules done by July. It’s easy if you don’t have the experience to understand how quickly July becomes December to simply piss away the time.

So I can’t say that it’s a matter of older people not being willing to do what it takes–if upper management also was willing to do what it takes, projects would be properly sized and properly planned. No, it’s more a matter of “younger people don’t have the experience to do proper long-term planning to hit deadlines without working overtime,” combined with “younger people don’t have the experience to call ‘bullshit’.”
There is also, as an aside, a persistent myth that it takes a certain type of intelligence or a certain level of intelligence to be successful in the software industry.
I’m inclined to believe more in the 10,000 hour rule: if you practice something for 10,000 hours, you will become successful at that thing.

Intelligence and personality could very well help you gain that 10,000 hours: the first few hours of learning how to write software or learning a new API or a new interface can be quite annoying and stressful. But if you persist, you will get good at it.

Which means IQ and personality, while perhaps providing a leg up, doesn’t guarantee success.

It’s why I’m inclined also to want to favor more experienced and older developers who have persisted with their craft. If we assume a 6 hours of actual development work (with the other 2 on administrative stuff), then a work year only has 1,500 hours–meaning 10,000 hours takes about 7 years to accumulate. Assuming you start out of college at 21, this means that anyone under the age of 28 will not have sufficient experience to be good at their craft.

And that assumes they practiced their craft rather than just going through the motions.

The whole “it’s all about ageism” in the tech industry is an interesting meme–simply because it’s far more complicated than that.

GWT Weirdness Of The Day.

Posted on August 25, 2010 by William Woody

On the project I’m working on, I noticed that, for whatever reason, it was now taking up to 3 minutes to start a web site running under GWT. That is, from hitting the “Debug” button and opening the web site in the browser, to seeing the web site actually up and running, was taking just shy of three minutes, with most of that time with the Spinning Beach Ball Of Death™.

I finally figured out what was happening. The first clue came from hitting ‘pause’ on the Daemon Thread labeled “Code server for myProject from Safari DMP…”, and noticing a lot of time being spent walking around inside the source kit for resources.

And noticing a lot of that time was spent in a bunch of .svn folders.

I think what was going on is that, for some reason or another, a lot of crud had accumulated in a number of random hidden folders associated with subversion. I don’t know if this is normal or abnormal behavior for Subversion; I just know there was a bunch of crap floating around there–and GWT was spending several minutes walking around the directory structure.

Blowing away the entire source kit and checking it all out fresh from Subversion reduced the startup time to less than 5 seconds. And it greatly improved the performance of the browser in the debugger as well: rollovers which were taking a while to get detected now are fast and responsive.

I suspect all the crud in my source directory was creating a lot of crap for the debugger to deal with, creating a substantial slowdown that got cleared right up.

Tools in Eclipse I wish were in Xcode for Objective-C and C++.

Posted on August 24, 2010 by William Woody

1. Override and implement methods.

It’d be nice if there was some way to indicate that the Objective-C and C++ class could automatically generate the proper header modifications in a C++ or Objective-C class declaration, and create an empty method call in the source file, to override a virtual method (in C++) or a message (in Objective C) in it’s parent class.

2. Implement methods.

Similarly it would be nice if there was some way to simply write the C++ or Objective-C header, then have the method or message body automatically generated from the header in the source file.

3. Implement missing abstract methods/protocol methods.

And similarly it would be nice if there was some way for an IDE to determine that you have a class which needs to extend and implement a number of abstract methods or protocols, and automatically insert them into the header or source file.

4. Generate core methods (C++)

In C++, there are a few methods that you need to implement if your class is to participate in the C++ STL as a key, as a sortable object, or as an array object. It’d be nice if there was a mechanism to automatically generate the necessary method definitions and (if possible) even attempt to divine reasonable defaults for these methods in the same way that Eclipse will automatically generate equals() and hashCode().

Java is a very verbose language. But most modern IDEs hide this verbosity by providing a number of tools to automatically generate the “bookkeeping code.” For example, in Eclipse, if you declare a class that implements an interface, Eclipse will offer to automatically fill in the missing method declarations for you. So it’s an easy matter of simply declaring the interface, and letting Eclipse to the tedious cut and paste work.

Most languages are verbose in their own ways. Objective-C and C++ are verbose in that they require you to declare your methods in two places. Synchronizing between those two places is a pain in the neck.

Of course in Java once you build a class file parser it’s trivial to build code to walk the method tree for an interface or an object, and automatically generate template code. What’s missing is a similar interface to an Objective-C or C++ parser to automatically generate the parse trees necessary for automatic code generation. In each of the cases above, it wouldn’t even require a full parse tree–just enough of the parse tree to understand the C++ or Objective-C class declaration objects. (Meaning you would only need to parse the class or @interface declarations.)

I can daydream, can’t I?

Interesting MacOS Java Links

Posted on August 13, 2010 by William Woody

Java Integration Document.

The classes used to hook into Finder.

Testing to see if you’re running on MacOS X, so you can set up your LAF to resemble a Macintosh application.

It’s interesting that it doesn’t take a lot of work to get a working application that has the correct look and feel on MacOS X 10.5 or later. Too bad most Java developers don’t seem to put in the extra work–because if they did, they’d have something that looks exactly like every other application on the Macintosh platform instead of refugees from the UI wasteland that is Linux.

I like Java as a programming language. I like Java a lot. Too bad Java has been inundated with a metric-shitload of useless and over-engineered frameworks that really don’t add any value. (I’m looking at you, Spring…)

Things to remember: table-layout

Posted on August 10, 2010 by William Woody

By default a table in HTML wants to do all sorts of auto-magic reflowing stuff–which is a pain in the ass if you want to explicitly set the width of the columns via GWT (or JavaScript). But if you set the CSS attribute table-layout to fixed, column widths are honored. Wrap each of the items in the content area with ‘overflow:hidden’ and ‘white-space:nowrap’, and if the text associated with a cell overflows, it gets neatly clipped.

Development Chaos Theory

An on-going conversation about stuff I find interesting