What computer output is supposed to look like


Image of conv net learning to classify images of chess pieces
Conv net attempting to classify chess pieces

This month is the 41st anniversary of me coming face-to-face with a “micro-computer” for the first time – in WH Smith’s in Brent Cross. I am not truly sure how I knew what I was looking at (beyond I suppose the shop’s own signage) – because at that time not even “The Mighty Micro” – ITV’s groundbreaking (and exceptionally far-sighted) TV series had yet been broadcast, but I was instantly smitten.

If you remember the time, then you’ll recall computers were very basic and only ran BASIC (but you could still do a lot with that). Black and white (or green and white) graphics were the standard (unless you were a rich kid and owned an Apple II).

But that didn’t stop us – my brother and I got a Sinclair ZX80 in 1980 (even if you ordered early the wait was long) and started writing code straight away (there wasn’t much choice if you wanted to get some use from the device).

The best code was mathematical and computationally intensive (as far as 1KB of RAM on a board with an 8 bit 3.25MHz CPU would allow that is) yet managed to combine that with rapid screen updates – something that was difficult on a ZX80 because computation blanked the screen (a ROM update and an interrupt driver – we copied the machine code bytes into every program – later fixed that.)

So 41 years later the code I am now running – shown above – perfectly fits the bill for “proper computing”. It is a computationally intensive – essentially multiple matrix multiplications – convolutional neural network that is attempting to classify images of chess pieces of the sort commonly seen with published chess puzzles. But what I love most of all is the fast flickering digits (the nine classes) and small images (the output of the first two layers of the 50 filters that are at the heart of the network).

This is the second time I’ve had a go at this personal project and I’ve made some progress – but it’s been hard going. Most conv net users seem to have long moved on from C++ (which I am using) to Python libraries like Tensor Flow – so it’s not even that I feel I am part of a strong community here.

Lots of subtle (that’s my story and I’m sticking to it) programming traps – like the fact that the STL Maps class reorders the objects added to reflect the order of the key (sounds obvious when you say it like that – why would it not have such a lexical order?) – I had simply assuming that the entries kept the order they were added in. (This was today’s discovery).

But if it was easy to write these things then it would be no fun.

Sometimes, admitting defeat is the very best thing you can do


English: Screenshot of GDB, the debugger of th...
English: Screenshot of GDB, the debugger of the GNU Project. . (Photo credit: Wikipedia)

I have spent the last month and half or so writing a particular computer program to model how some code would run on a 16 core “network-on-chip” device.

There were a lot of problems to get over – for although I had already written a Groovy/Java program to do the same thing, that code just was not up to handling the additional level of complexity I wanted for this iteration, so the whole thing had to be redone in C/C++.

About three weeks ago I got to the point where the code compiled and it should have been doing what I wanted, but it was crashing with memory bugs, a lot.

Debugging multi-threaded Posix Threads code is not meant to be easy but I was able – after teaching myself the basics of the GNU debugger (GDB) – to make a lot of progress (having realised that the old programmer’s saw of “if God had wanted us to use debuggers, she wouldn’t have given us printf” does not raise many laughs when you are dealing with multi-threaded code).

I discovered that the bugs were in my four year old red-black tree code. I had used it before in many situations and never had a problem, but also realised that where I used it before (and where I am still using it now), I was continually adding nodes to the tree and not deleting them. The deletion code was wrong.

Most people write their red-black tree code having read Introduction to Algorithms – but here, at least, I was not like most people. I had written the code myself more or less from scratch, piecing together the various things I needed to do from a lot of different online sources. And I was very proud of that too.

But that also meant that, when I tried to fix the code by looking at the canonical description in “Introduction…” the match was poor and my model was, at a quite fundamental level, different (I used null pointers for the leaves, not the “guard node” approach advocated in the book.)

I thought I could get around the issue by not doing any rebalancing after a deletion – after all I was still inserting nodes even as I was deleting them and my insertion code seems (and still seems) quite robust.

But while that allowed by code to run quite a lot longer before falling over, it still fell over. I had to face the facts and use the Standard Template Library (STL) classes – map and set.

I started work on that on Friday on a long train journey. I thought it would be weeks of further chopping and changing. In fact it took little more than 48 hours and I am wondering why I put myself through such misery when robust and well-tested solutions were always to hand (I kept my code for one tree I used where I am only doing insertions – as converting that would have taken a further day, but that was the margin I was operating in – having contemplated weeks, I now worried it would take more than a few hours).

The new code seems pretty robust, but I am struggling to get it on the university’s compute server as that is now under such heavy load, and so I am thinking of adding an nCurses interface while I wait.

Admitting defeat was the quickest way, it seems, to victory. Something worth remembering, perhaps, when your software project is in trouble.

Enhanced by Zemanta

Red-black trees


Example red-black tree
Image via Wikipedia

Binary trees are seen and used frequently in computing science and computing. They are a good abstraction for many naturally occurring relationships (most of our mathematics is based on binary operations, for instance) and have O(log n) complexity (ie if you went from searching a tree of 1000 elements to a tree of 100,000 elements then the search should not take 100 times longer but about 10.)

Of course that log n goodness requires the tree to be “balanced” ie for any given node there should be roughly equal numbers to the left and the right. One way of doing this is through a “red black tree” – here nodes in the tree are assigned a colour: the root is always black. The rule is that any traversal from the root to the leaves should always go through an equal number of black nodes and to ensure this is possible red nodes may be inserted in the tree, but no red node may have another red node as an immediate descendant. (A full explanation is in Introduction to Algorithms though one can also work off various explanations on the internet, though they tend to be less than complete.)

The Linux kernel natively implements a red black tree (in C) and the first bit of work I started on my MSc project was to write my own, userland, implementation so I could see processes in the same way the kernel did.

As I had got a less than glorious mark (still a pass, so that’s what counts) in the C++ exam last year I also decided that I would write this in C++ using templates. A few days after I started I discovered that actually the writers of the STL had got there before me, but as this was an academic exercise I ploughed on with my own implementation.

Essentially this is what I did on my two week summer holiday in Scotland last year! When I was there I also started (though completed when I got home) a couple of helper applications to position the tree according to Reingold and Tilford’s algorithm (which I had to translate from PASCAL) for “better drawing of trees” and a Qt application to display it all.

In fact I had a nagging problem with the Reingold-Tilford algorithm which I finally got around to fixing last night.


LaTeX to PNG representation of processes

(Interestingly the code also allows you to use the Turing-complete capabilities of LaTeX by specifying a TeX output that uses LaTeX’s own positioning algorithm – something I picked up from The LATEX Graphics Companion – that is what the example shown above uses, though unfortunately for even moderately loaded systems the LaTeX processor objects to the width of the output).

Fancy trying it? I could do with someone giving it a bash on a BSD system – not needed for my course but interesting none the less.

The code is all at GitHubhttp://github.com/mcmenaminadrian: memball gives the basic GraphML or TeX or plaintext output, treedraw will convert the GraphML to an SVG or serialiszed stream using Reingold and Tilford’s algorithm and treeqt will use Qt to display the tree using the serialized class. You may have to download various libraries to get it to work (certainly the libproc-dev package on Ubuntu/Debian) – I couldn’t get memball to work on a Windows machine using Cygwin but maybe even that is fixable.

There is a script in the treeqt repo to make it easier: download the sources form all three repos, build them and then run:

./setup | ./treeqt --r 1