Hugh Perkins's tech blog

Godel’s incompleteness theorem. I assume it is me that is stupid but I disagree with it….

You can find Godel’s incompleteness theorem expressed in very convoluted ways, but what it boils down to is this:

Godel’s incompleteness theorem, somewhat paraphrased: there are statements within a closed system that cannot be proved within that system

Wow! That sounds pretty interesting! It means that however many rules we find about the universe we cannot prove everything!

Sounds bizarre right?

And that’s because that’s not really what it’s saying, I feel.

What it really says are that one can create paradoxes within a system, and that one cannot use logic to show they are true or false, only common-sense.

To me, that shows a flaw in the expressivity of the system of logic, rather than a fundamental assertion that we cannot prove everything using logic.

Specifically, the paradox is the following:

Statement: it is impossible to prove that this statement is true.

It’s like that piece of paper “the statement on the other side is true”, “the statement on the other side is false”.

We don’t need ‘information from outside the system’ to solve it.

The way I see it, paradoxical statements have a state other than true or false, illustrated aptly by this cartoon true-false and quantum physics

Of course, I totally accept that there are probably counter-arguments to this. I am not a professional mathematician.

Nevertheless I feel the concept that godel’s incompleteness theorem meaning that there are what I will call “interesting” statements, non-paradoxical statements, that we will never be able to prove no matter how advanced our physics or maths is, seem to me to be a little misleading.

I’ve started writing my configuration files in standard java, using the fluent style.

I was originally using standard java, without fluent style, which was a mess, and unmaintainable.

I moved to xml, and was happy with the results initially. But I don’t need other people to be able to read/maintain my configuration files – it’s for a game, and I am the sole developer – and there is a fair amount of development overhead in handling serialization to and from xml, since you have to write both the configuration class, and an xml file.

So, I’ve been playing with using standard java, in the fluent style. I am very happy with the results!

It is possible to make such fluent language quite powerful. I’ve got a bit of configuration where the initial object is a formula, a function of x, or x and y, for example. Then, we can apply additional maths to this function, like say ‘minimum’. Now the bit I am really happy with is that I have made the parameter of the ‘minimum’ method to be itself a function. So, let’s start with the simple case, with the parameter being a constant:

Function function = somefunction.minimum(3);

somefunction is a function of lets say x. So we can do this, to evaluate somefunction for different values of x and display the results:

Function function = somefunction.minimum(3);
for( int x = 0; x < 10; x++  ){
   plot( x, function.evaluate(x) );
}

Now the cool thing is that the parameter to the ‘minimum’ method can itself by a Function. So we can do this:

Function function = somefunction.minimum(anotherfunction);

The result of evaluating function.evaluate(x) will be the minimum of somefunction.evalutate(x) and anotherfunction.evaluate(x), for any x.

This works, and it rocks. The configuration I have for certain formulae are now very readable and relatively intuitive 1 liners. Instead of a whole page of xml or non-fluent java before, for each formula.

I wrote an injector called EasyInjector a few weeks ago, and have been dog-fooding it in my own application recently. My application has 300 classes and 25000 lines, so it’s not huge, but it’s not so small either.

I use EasyInjector as follows:

class SomeClass {
    @InjectField final SomeOtherClassA someOtherClassA = null;
    @InjectField final SomeOtherClassB someOtherClassB = null;

    public void init(){
         // initialization code here
    }
}

I have an assembler class that looks like this:

EasyInjector injector = new EasyInjector();
injector.instanceOf(SomeClass.class).init();
injector.instanceOf(SomeOtherClassA.class).init();
injector.instanceOf(SomeOtherClassB.class).init();

injector.instanceOf(MainLoop.class).go();

EasyInjector instantiates each class instance, then injects them into each of the others. The init code in each one can assume that the final instances are fully instantiated, though perhaps the ‘init’ method on them hasn’t run yet. Typically in the init method, I’ll do things like subscribe to read events from other classes, and load resources.

For unit-testing, it is possible to use easyinjector.UnitTestingBuilder to construct objects without needing an injector, and using mocks, eg using Mockito.

It’s really easy to spawn threads in java using the executorservice implementations, and collect the results.

The easiest way to show how it works is just to write some code. Here’s how I do it:

	Future<String> future;
	ExecutorService executorService = Executors.newSingleThreadExecutor();

		future = executorService.submit(new Callable<String>(){
			public String call(){
				// put stuff you want done in child thread here;
                                // ...
                                return resultString;
			}
		});

I use a single threaded executor, so that I don’t need to deal with multiple threads accessing the same state too much. There are also thread pool executors available if you want.

The anonymous Callable can return any type you want.

When you want to fetch the result, you can do it like this:

if( future.isDone(){
    String result = future.get();
}

Easy!

I like to give my threads meaningful names. It makes debugging and profiling much easier. I add a couple of extra lines when I spawn the thread as follows:

	Future<String> future;
	ExecutorService executorService = Executors.newSingleThreadExecutor();

		final String threadname = this.getClass().getSimpleName();
		future = executorService.submit(new Callable<String>(){
			public String call(){
				Thread.currentThread().setName(threadname);
				// put stuff you want done in child thread here;
                                // ...
                                return resultString;
			}
		});

I think using the executorservice, along with the futures and callable interfaces, makes spawning threads in java very easy. I think it is arguably slightly easier than using the IAsyncResult paradigm in .Net 2.0. It’s certainly at least as good.

What didn’t used to exist in the IAsyncResult paradigm in .Net 2.0 was being able to easily choose between a single threaded executor service, or thread pools. Also, I seem to remember the thread pool was global, though I could be wrong. I imagine that .net 4.0 corrects these issues, but anyway, for now, I am quite happy with these in java!

The concurrent collections in Java are easy to use, and are essentially drop-in replacements for their non-concurrent counterparts.

They do not need locking or synchronization protection, and can be freely accessed and iterated from multiple threads.

The replacement for ArrayList is CopyOnWriteArrayList. A bit of a mouthful, but it is clear how it works.

The replacement for HashMap is ConcurrentHashMap. This is a drop in replacement. I believe the performance is very good. I use this as my primary means of offloading processing to other threads, by dividing the task into chunks that the helper threads can process on their own.

There is no drop-in replacement for HashSet. What I did was to write a wrapper around ConcurrentHashMap. I add a dummy object as the value in the ‘add’ method, since the ConcurrentHashMap requires the values to be non-null.

I’m really impressed by these concurrent java collections. Maybe they exist too now in C#, but they didn’t when I was really into C#, in the .Net 1.1/2.0 era.

Threading with Java today is quite a pleasure.

The Concurrent collections mean that it is possible to share state between threads with no additional locking or synchronization.

The ExecutorService along with the Callable interface make it easy to spawn helper threads, and to receive results from them.

I have had zero concurrent modification exceptions, or locking issues. Mostly because the concurrent collections make it possible to code without even using any locks. It’s easy and it works well.

Java has a nanosecond timer!

It works well too.

Quick test script:

We do empty loops of varying numbers of iterations, and use the nanotimer to test how long that takes:

		for( int its = 0; its < 100; its++ ) {
			long start = System.nanoTime();
			for( int i = 0; i < its; i++ ) {
			}
			long delta = System.nanoTime() - start;
			System.out.println("its " + its + ": " + delta );
		}

Results, using openjdk1.6 on ubuntu Lynx:

its 0: 2305
its 1: 2445
its 2: 2444
its 3: 2304
its 4: 2305
its 5: 2235
its 6: 2165
its 7: 2235
its 8: 2235
its 9: 2514
its 10: 2445
its 11: 2445
its 12: 2444
its 13: 2514
its 14: 2514
its 15: 2514
its 16: 2584
its 17: 2654
its 18: 2654
its 19: 2515
its 20: 2584
its 21: 2654
its 22: 3212
its 23: 2654
its 24: 2793
its 25: 2724
its 26: 2794
its 27: 2724
its 28: 2863
its 29: 2794
its 30: 2934
its 31: 2933
its 32: 2933
its 33: 2934
its 34: 2933
its 35: 2933
its 36: 3003
its 37: 3003
its 38: 3073
its 39: 3142
its 40: 3073
its 41: 3143
its 42: 3073
its 43: 3143
its 44: 3143
its 45: 3213
its 46: 3073
its 47: 3143
its 48: 3212
its 49: 3213
its 50: 3213
its 51: 3142
its 52: 3283
its 53: 3282
its 54: 3422
its 55: 3423
its 56: 1154546
its 57: 3422
its 58: 3422
its 59: 3423
its 60: 3422
its 61: 3562
its 62: 3562
its 63: 3492
its 64: 3561
its 65: 3631
its 66: 3632
its 67: 3631
its 68: 3702
its 69: 3632
its 70: 3632
its 71: 4051
its 72: 4400
its 73: 3702
its 74: 3771
its 75: 3701
its 76: 3771
its 77: 3771
its 78: 3911
its 79: 3841
its 80: 28286
its 81: 4540
its 82: 4470
its 83: 4679
its 84: 4539
its 85: 4610
its 86: 4609
its 87: 4539
its 88: 4679
its 89: 4680
its 90: 4679
its 91: 4819
its 92: 4680
its 93: 4819
its 94: 4819
its 95: 4889
its 96: 4750
its 97: 4819
its 98: 4959
its 99: 4889

So, the nanoseconds timer can measure reasonably accurately the difference in timing between an empty loop of n iterations and n+10 iterations. That’s impressive! And useful.

Interesting outliers at 56, and 80. gc?

Statistical profiling is easy to do in Java. It is easy, lets the program run at full speed, and gives meaningful results.

Before trying statistical profiling, I tried instrumenting profilers, the best of which I found for Java was NetBeans, at least, the best of the freely available ones. It did what it said on the box, but my program ran at somwhere around 1-10% of normal speed, which was horrible, and I imagine the timings for the tight inner loops were not very accurate. I also found it not very easy to configure or push to do what I wanted it to do.

Statistical profiling in java can actually be done with no external tools, not even an ide. This is how I did it:

• created a new thread, which polled the stack trace of the main thread ten times a second
• which thread wrote each sampled stack trace to a ConcurrentQueue
• the main thread read the concurrent queue once a second, processed the stack traces to my heart’s desire, and printed the results

I expected that this would be a far too naive implementation, not least with only ten samples a second. Surprisingly it turned out that 7 out of 10 samples of my application were for a tiny low down function that I would never have expected to be sampled more than 1% of the time. All it did was glDisable(GL_BLEND), and glPopMatrix(). Once I saw that, I could look at figuring out what was going on. Ultimately, I doubled my frame-rate.

Here is the basis of the statistical sampling. Nothing complicated. Very easy. Works well:

class Analyzer {
	ConcurrentLinkedQueue<StackTraceElement[]> stackTraces = new ConcurrentLinkedQueue<StackTraceElement[]>();

	class AnalyzerThreadObject implements Runnable {
		Thread mainThread;

		public AnalyzerThreadObject(Thread mainThread) {
			this.mainThread = mainThread;
		}

		@Override
		public void run(){
			while( true ) {
				long startTime = System.currentTimeMillis();
				while( System.currentTimeMillis() - startTime < 1000 ){
					StackTraceElement[] stackTrace = mainThread.getStackTrace();
					stackTraces.offer(stackTrace);
					Sleep.sleep(100);
				}
			}
		}
	}
}

That’s it. That’s all it takes. And a bit of code to filter the results appropriately. Not more than 5 minutes work for some basic filter, or as long as you like for something more advanced.

The most trivial output processor could be something like:

while( !stackTraces.isEmpty() ){
   StackTraceElement[] stackTrace = stackTraces.poll();
   System.out.println(stackTrace[1]);
}

stackTrace[1] is the lowest level call at the sampling time. You can walk upwards through the stack until you get to some higher level abstraction that you’re interested in. Or walk down from the other end.

Easy, and highly configurable.

So my current project is up to 282 .java files, 20000 lines, and scaling well.

I seem to be doing the following at the moment:
- unit tests for very specific mathematical things, like vector maths, matrix maths
– otherwise, I found that unit tests seemed to me to take more time than they saved me, at least for now
- using an injector with setter-based injection seems to save me time writing out code to pass objects between each other
- settled at the moment on a fairly flat package architecture, with many packages at the top level, one for each distinct ‘feature’, which is a fairly nebulous concept

What I’m finding is that if the code is spaghetti, writing unit tests doesn’t really save you. If the code is broken up into tiny tiny classes, each of which does something really simple, it seems that the code becomes fairly robust and bug-free, regardless of whether one unit tests or not.

I’m much happier with an injector that allows cyclic dependencies. Trying to remove cyclic dependencies from one’s code might be nice as an intellectual exercise but I found that the effort did horrible things to my productivity, and didn’t really improve the code’s readability too much.

I think that both of these contradict standard practice, so I might find myself changing my position at some point, but these are my feelings at this time.

Oh, I guess the other thing I’m trying to do is to make sure each package only has one or two classes that talk with other packages, a “facade” pattern type design. I’m not enforcing this rigorously but gently using this principle to guide oneself seems to make things cleaner.

I found an excellent tutorial to Opengl shader language that other day:

Joe’s Blog: An Intro to Modern OpenGL

It makes it seem pretty easy. Great fun!