I’ve created my own version of the exercise used during my first agile job interview in order to compare it to the result of the pair programming session of the job interview. The exercise was quite simple: implement a stack, and store the values in an array. The implementation is pretty straightforward, the code is available on github. One can ask: why an array, why not using the collection framework? The answer is simple: just for fun, and just for the exercise

In order to store the necessary amount of values, the internal array needs to be enlarged from time to time. There is nothing wrong with this so far. But in order to avoid unnecessary memory loss, that internal array needs to be shrunk as well. The first version of my Stack implementation lacked this functionality. The user stories of the functionality request can be:

• As a developer, I don’t want to reserve more memory for my stack implementation than necessary
• As a customer, I don’t want to lose values after shrinking the internal container

The second user story is very straightforward, so let’s focus on the first one. User stories and previous test cases are available, so far so good, but how to test the user story? An even better question: how to write a test case first? I consider my Stack implementation as an end product, and as such, I believe that it should follow the encapsulation object oriented programming principle, and it shouldn’t be difficult to use. An obvious choice would be a reflection-based solution, but since I’m not a great fan of reflection, I started to test the code from different angles.

For better understanding, here comes the code being tested:

    private void shrinkContainerCapacity() {
        int[] extentedContainer = new int[container.length - 10];
        System.arraycopy(container, 0, extentedContainer, 0, container.length - 10);
        container = extentedContainer;
    }

The first user story suggests memory handling, so first let’s try out this angle. Memory usage can be checked with the following methods:

• Runtime.getRuntime().totalMemory()
• Runtime.getRuntime().freeMemory()
• Runtime.getRuntime().maxMemory()

Using those methods I wrote this test case sketch:

    @Test
    public void shouldUseLessMemoryAfterShrinkingInternalContainer() {
 
        for (int attempts = 0; attempts < 15; attempts++) {
            for (int i = 0; i < 10000; i++) {
                stack.push(i);
            }
 
            long availableMemoryBefore = getAvailableMemory();
            for (int i = 0; i < 10000; i++) {
                stack.pop();
            }
 
            long availableMemoryAfter = getAvailableMemory();
            assertTrue(availableMemoryBefore < availableMemoryAfter);
        }
    }
 
    private long getAvailableMemory() {
        System.gc();
        System.runFinalization();
        System.gc();
        System.runFinalization();
        long totalMemory = Runtime.getRuntime().totalMemory();
        long freeMemory = Runtime.getRuntime().freeMemory();
        return totalMemory - freeMemory;
    }

I’ve executed the test case several times and it never turned red. I was curious why, because it supposed to be work, isn’t it?

The javaDoc of System.gc() and System.runFinalization() states that: “…the Java Virtual Machine has made a best effort…“. Additionally Java Virtual Machine implementations may differ on operation system level: “…The aim is binary compatibility. Each particular host operating system needs its own implementation of the JVM and runtime. These JVMs interpret the bytecode semantically the same way, but the actual implementation may be different.” (source: Wikipedia).

Adding these statements up makes me nervous. The whole situation – using memory measurements for testing – starts looking black for me, so I did some measurements using the test code from above with different Java Virtual Machine implementations on different operating systems:

• Running with eclipse 1.6 jre on Ubuntu Linux
• Running with oracle’s 1.6 jre on Ubuntu Linux
• Running with jrockit 1.6 jre on Ubuntu Linux
• Running with oracle’s 1.6 jre on Windows XP

I’m interested how the assertTrue(availableMemoryBefore < availableMemoryAfter) will turn out in the different scenarios, so I’m measuring the availableMemoryBefore and availableMemoryAfter values, and calculate the SIGN of their difference: if the availableMemoryAfter is greater than availableMemoryBefore the SIGN will return 1, which is equal to a true test case and a green bar. In other words, after shrinking the array, the Stack uses less memory. Mission accomplished sort of say.

Before evaluating the results I have to note two things.  I’ve executed the test cases several times and I didn’t find any difference in their outputs, that’s the reason why I have only one measurement sheet for each case. Additionally I sometimes have the feeling that there is a slight difference when I’m running a java application/test case from eclipse and from command line using oracle’s jre, therefore I did the measurements with both of them separately. The detailed measurement values are available in this spreadsheet. Now the result:

Now my red bar is understandable. I’m using eclipse under Ubuntu Linux (and oracle’s jre), and according to the diagram above, there is less available memory after the first execution of the shrinking (again, I executed this particular measurement more than twenty times, and I always got the same result). If I had used jrockit, the problem above never would have turned out (the orange bars are always at 1, meaning that there is more available memory after shrinking in every case).

I would have stopped with the measurements here, unless my friend had asked me this: “Why did you have to call the System.gc() and System.runFinalization() twice?” It is a very good question. The more I call the System.gc() the more feasible is that the Java Virtual Machine will do garbage collection, which means that my application will use less memory, at least on paper.

Unfortunately experience shows otherwise. Have a look again at the javaDoc of System.gc(). In layman’s terms the System.gc() call is just a request to the Java Virtual Machine, and there is no guarantee that it will consider the call at all. According to my measurements below, the Java Virtual Machine considered it, but I had participated in a project several years ago, in which we had memory issues and no matter how often we called the System.gc() nothing really happened. The Java Virtual Machine felt that the time for garbage collection had not come yet, so it ignored our request.

So SIGN (before – after) looks this, when I’m calling the System.gc() and System.runFinalization() only once:

In this case I would still see a red bar with my setup, in several cases (7, 9, 11, 13 and 15) the SIGN is 0, meaning that the amount of available memory is the same before and after the shrinking. After having a close look there isn’t any option, which would make my bar green. I feel like I’m getting somewhere: checking memory usage as validation is not that promising as it was before I started measuring it. Let’s see the result without any System.gc() and System.runFinalization() calls in order to finish my measurements and provide more data for evaluation:

The result is not deterministic at all. Now I’m 100% sure that checking the memory is a dead end for me. I cannot garantee that my shouldUseLessMemoryAfterShrinkingInternalContainer() test case will produce the same output every time. Someone can use a different kind of machine for test case execution – for example Solaris, on which I didn’t do any measurement at all -, or can change my getAvailableMemory() helper method and execute less or more System.gc() calls. Unfortunately I need a different approach.

The next thing worth having a look at is injecting the array copy functionality. Unfortunately, the System.arraycopy() method is static, so I have to wrap it up, and inject the wrapper class into my Stack. The Stack is considered an end product, I cannot let the user take care of the dependency injection by herself, so I need a factory to do that:

public class StackFactory {
	public Stack create() {
		return new Stack(new ArrayCopyWrapper());
	}
}

// ...

public class ArrayCopyWrapper {
    public void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) {
        System.arraycopy(src, srcPos, dest, destPos, length);
    }
}

First let’s see the effect of this modification on the test code:

    @Test
    public void shouldShrinkInternalCapacity() {
        FakeArrayCopyWrapper arrayCopyWrapper = new FakeArrayCopyWrapper();
        stack = new Stack(arrayCopyWrapper);
 
        arrayCopyWrapper.setExpectations(0, 0, 10);
        for (int i = 0; i < 20; i++) {
             stack.push(i);
        } 
 
        // Had to cut the for() loop in half
        // In order to be able to set two expectations
        arrayCopyWrapper.setExpectations(0, 0, 20);
        stack.push(20);
 
        // The same reason here
        arrayCopyWrapper.setExpectations(20, 10, 1);
        stack.pop();
 
        arrayCopyWrapper.setExpectations(20, 10, 15);
        for (int i = 20; i >= 5; i--) {
           stack.pop();
        }
    }

I didn’t want to spend too much time on setting up and using mock libraries. I had the strange feeling that I didn’t have to put too much effort into this angle. A simple fake object will be just fine:

public class FakeArrayCopyWrapper extends ArrayCopyWrapper {
    private int srcPos;
    private int destPos;
    private int length;
 
    public void setExpectations(int srcPos, int destPos, int length) {
        this.srcPos = srcPos;
        this.destPos = destPos;
        this.length = length;
    }
 
    public void arraycopy(int srcPos, Object dest, int destPos, int length) {
        assertEquals(this.srcPos, srcPos);
        assertEquals(this.destPos, destPos);
        assertEquals(this.length, length);
    }
}

Although I wrote the shouldShrinkInternalCapacity() and FakeArrayCopyWrapper class, I don’t like them too much. The test case is complicated and the Fake is strange.

Additionally, when someone wants to instantiate my Stack she must do this:

Stack stack = new StackFactory().create()

But, this version seems to be more user friendly:

Stack stack = new Stack()

The first version is good for internal classes, but personally I don’t want my users to do complicated things like using wrapper factories for creating an object, when there is an easier way.

However there is one more thing. The ArrayCopyWrapper wraps only the System.arraycopy() call. If I executed a code coverage measurement using the shouldShrinkInternalCapacity() test case, the measurement would indicate that the shrinkContainerCapacity() method is 100% covered with shouldShrinkInternalCapacity() test case. This is not true. The current version of shouldShrinkInternalCapacity() does not test the command below, because it focuses only on the arraycopy:

    private void shrinkContainerCapacity() {
        //...
        //...
        container = extentedContainer;
    }

One can argue that the line above is indirectly tested by the other test cases.  This is true, but I would like to have focused test cases and correct coverage data.

This solution is not user friendly and I had to do things in testing which I don’t really like. This approach is another dead end for me, at least.

The last thing I can think of is checking the size of the internal container. I have the following options:

• make it protected
• create a protected method for getting its size
• use reflection

The first two options harm encapsulation, which I have no intention to do, so another dead end.

I had no other option but to do the testing with reflection. I don’t like the current state of the test cases, but I have no other ideas. So I’m going to leave this post open, feel free to submit other ideas on how this feature can be tested. The code is available on github, and any suggestions and comments are welcome.