Software Development

Normally in Java, if the main thread starts one or more non-daemon threads, the Java process will not terminate until the last non-daemon thread terminates.

Yet, I was surprised to find that a particular JUnit test completed normally, despite never calling shutdown() on a ThreadPoolExecutor it had started. No Java process was left behind. This was the case both when running the test from within IntelliJ and also from Maven (using the surefire plugin). Replicating the test code in a vanilla main() method led to the expected behaviour: a “hanging” process.

So what was going on? Surely something fascinating and enlightening, right? Running the JUnit test from my IDE revealed the underlying java invocation in the Console pane (abbreviated):

java -classpath "some-massive-classpath" com.intellij.rt.execution.junit.JUnitStarter -ideVersion5 MyTest,someMultiThreadedTest

So, the main method which launches the JUnit tests is in the class called JUnitStarter, which is an internal class within IntelliJ. A quick look at the code for JUnitStarter reveals the answer is very simple: an explicit call to System.exit() before main() returns. Maven Surefire’s ForkedBooter does the same thing.

As always, some strange behaviour turns out to be something entirely simple! But this is something to watch out for. Ideally, unit tests wouldn’t test multithreaded code (rather, they would test logic which is abstracted from the surrounding threaded environment). But if you must test multi-threaded production code, then be aware that your tests could give a misleading positive result in cases such as this.

It’s common to see “find the number of possibilities” problems in Computer Science. This kind of problem stems from Discrete Maths - an important pre-requisite for doing anything beyond the trivial, for example Cryptography or Graph Theory.

I found one of these problems on Project Euler.  Project Euler is a collection of mathematically-inclined programming problems - probably more than you could ever solve in a lifetime (some of them are still unsolved by anybody). The particular problem which drew my attention doesn’t actually require any programming to solve.  

The problem is based on the idea of finding routes between two points on a grid:

Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner. 
How many routes are there through a 20x20 grid?

This is pretty fundamental maths, but I find these kind of techniques are always worth re-visiting, as it seems to be a case of “use it or lose it”.

Following is my approach, so don’t read any further if you want to try it yourself first!

I started by drawing a tree structure for the 2x2 grid, where each node had two choices = ‘R’ or ‘D’ (for go Right, or Down).  This gave me a feel for things.  Towards the end of some paths, there was clearly some pruning - where the only option is to head for the goal (rather than back-tracking or going out of bounds).

It then became clear that any plan for getting to the goal simply involved two Rs and two Ds.  You clearly need to take two steps Right, and two steps Down to reach the goal, whatever your route.  So the problem can be re-stated as “how many ways are there of arranging two Rs and two Ds?”  Or more vividly: “If I have a bag containing two Kit-Kats and two Mars Bars, how many distinct ways can I eat them in sequence?”

Of course, the stated problem involves twenty each of Kit-Kats and Mars Bars.  So if I was really hungry, how many ways could I eat them all? Suitably motivated, it’s time for some fun with combinatorics.  

For the moment, let’s go back to the 2x2 grid, and ignore the repetition of Right and Down moves.  This means we must take four distinct steps to reach the goal.  So let’s assume that we have a bag of four chocolate bars - all different.  How many ways can we draw them in sequence?  Or more properly, how many permutations are there?

For the first choice, we have four options.  Once we’ve made this first selection, we have three left to choose from.  Then two, and finally there’s only one left.  This naturally leads us to the factorial function:

4! = 4 x 3 x 2 x 1 = 24

So there are 24 ways (permutations) to draw four tasty, chocolate treats. Now let’s amend our calculation, taking into account that two of the chocolate bars are identical.  Say, two Milky Ways, one Kit-Kat, and one Mars Bar. This is easy to work out - out of our 24 original permutations, we need to omit the repeated permutations of the two identical items.  There are 2! (2 x 1 = 2) ways to arrange two chocolate bars, so we adjust our answer for this.

4!/2! = 12 permutations

Now, it’s only one more step to re-discover the example solution, by taking into account that there are two classes of two identical ‘objects’ (Right moves and Down moves), and so we end up with:

4!/(2!*2!) = 6 permutations.

Now it’s really easy to solve the stated problem - I won’t give away the solution of course!

I was reminded of the power of automated testing by this talk by Rod Johnson, the original creator of the Spring framework. It is a little dated (2007), but what he says is still highly relevant.  The content mainly covers things we should already be practicing as developers, but it’s worth a reminder every now and then. Following are the main points I took away from the presentation.

First, there are several key concepts to bear in mind.  These came up again and again in the talk:

• Test Early, Test Often
• Test at Multiple Levels
• Automate Everything

Unit Testing

As developers, we know we should do lots of unit testing.  We do this by targeting classes in isolation, and mocking out collaborators.

To be clear, unit testing is looking at your class “in the lab”, not in the real world.  A unit test should not interact with Spring, or the database, or any infrastructure concerns.  Therefore, unit tests should run extremely fast: of the order of tens of thousands of tests per minute.  It shouldn’t be painful to run a suite of unit tests.

Do Test-Driven Development. Not only does this help you discover APIs organically, but it’s a way of relieving stress.  Once a defect is detected, you can write a failing test for it, then come back to fix it later on.  The failing test is a big red beacon reminding you to finish the job.

Use tools such as Clover to measure the code-coverage of your tests.  80% is a useful rule of thumb.  Any more than this, and the benefits are not worth the cost.  Any less than 70%, and the risk of defects becomes significant.

Integration Testing

We should also do integration testing - for example to ensure our application is wired up correctly, and SQL statements are correct.  

But how many of us are still clicking through flows in a browser?  Ad-hoc testing by deploying to an application server and clicking around is very time-consuming and error-prone.  If it’s not automated, chances are it won’t happen.  If it doesn’t happen or occurs late in the project cycle, defects will be expensive to fix.

So instead, maintain a suite of integration tests.  It should be possible to run hundreds or thousands of these per minute and again, they should be automated so they just happen.

Use Spring’s Integration Testing support.  Among other things, this provides superclasses which can perform each test in a transaction, and roll it back upon completion to avoid side-effects across tests.  This avoids the need to re-seed the database upon each test.

Another benefit of Spring Integration Testing is that the Spring context is cached between tests.  This means that the highly expensive construction of the Hibernate SessionFactory (if you use one) only happens once.  This context caching is usually impossible, because the test class is reconstructed by JUnit upon each test.

Remember to test behaviour in the database.  Stored procedures, triggers, views - regressions at the schema level should be caught early, in an automated fashion.

Integration tests should be deterministic - that is, they should not rely on the time of day, or random side-effects from previous tests.  This should be obvious, but when testing concerns such as scheduling, this can become difficult.  One strategy is to abstract out the concept of the current time of day.  This could be done by replacing a literal call to System.getCurrentTime() with a call to a private method.  This method would check for an override property set only during testing, the existence of which would cause a static Date to be returned to your application code.

Performance Testing

This should begin as early as possible.  Use scriptable frameworks such as The Grinder, so performance testing is cheap to execute early and often.  This means performance regressions will be caught immediately, for example if somebody drops an index.

Many performance problems are due to lack of understanding of ORM frameworks.  Learn to use your framework, for example relating to fetch strategies.  A common idiom is to eagerly fetch a collection of child entities up-front, rather than invoking the “N+1 Selects” problem by lazily loading each child record in a loop.  Additionally, consider evicting objects from the Session at appropriate points, to avoid memory overhead and to prevent the need for dirty-checking upon flushing of the Session.

One strategy to dive deeply into database performance concerns, is to enable SQL logging in your persistence framework.  A large number of SELECT statements per-use case will quickly become apparent.

Conclusion

Developers should Invest time into writing automated tests at multiple levels.  Even with a dedicated QA team in place, defects will only be caught early and fixed cheaply through an intelligent approach to automation. Along with adoption of best practices such as Dependency Injection and separation of concerns, the industry has many tools on offer to make comprehensive testing cheap and easy.

References / Further Reading

• JUnit: http://www.junit.org/
• Spring Testing: http://static.springsource.org/spring/docs/2.5.x/reference/testing.html
• The Grinder: http://grinder.sourceforge.net/ TDD (essay):  http://www.agiledata.org/essays/tdd.html
• Clover (test coverage): http://www.atlassian.com/software/clover/
• JWebUnit: http://jwebunit.sourceforge.net/

I was wondering: if I change class Foo, how do I determine 100% which use-cases to include in my regression tests? It would be useful to know with 100% certainty that I must consider the Acme login process, as well as the WidgetCo webservice authentication.  And nothing else. Can my IDE help me with this? 

Well, in some cases it’s straightforward to analyse for backward dependencies.  If I change class Foo, then static analysis tells me that webservice WSFoo, and controller Bar are the only upstream entry points to your application affected by this change.  So you test those flows, and that’s about it.

It seems I’m obsessed with finding new applications for GPS data.  The latest is an idea called Smart Trax: a hypothetical social application for discovering and sharing cycle routes. Imagine if you could upload a route (recorded via GPS), and find “similar” routes.  These similar routes can then be compared to your own.  It turns out there are a number of applications for this. Operation Duck Pond It’s the weekend, you’re a keen cyclist, and your bike is getting lonely.  You draw back the curtains, and see only blue sky and sunshine.  Ignoring the washing up, you fill up a water bottle and jump onto the saddle. But where to go?  Well, there was that circular route on quiet roads around the Thames Valley, published in Cycling Plus a few months back.  You feel fairly confident you can remember the route, and are too impatient to dig out the magazine. Never mind, it’ll be OK.  Just one last thing: you grab your iPhone, fire up a GPS app and press Record.  Stick it in your pocket and off you go. As you pass the pretty duck pond in Barnes though, it all goes wrong.  Taking a wrong turning, you find yourself on a hectic A Road, dodging juggernauts and choking on exhaust fumes.  Eventually, tapping into ancient wisdom, you sniff the air and somehow find your way back onto the planned route. When you arrive home, invigorated and exhausted, you wonder how you got so lost.  So you upload your route data from your iPhone to the “Smart Trax” website.  The website searches through its history of routes uploaded by other users, and finds the closest matches.  Fortunately for you, there will be many matches because the route is a well-known one (published in a major magazine). You see a map of your route appear on the screen.  A red dot appears at the start position (that’s you).  Other dots of different colours appear alongside yours (that’s the others who took the same route).  You then “play back” the route, watching the different dots progress in their different ways.  As your red dot approaches the duck pond in Barnes, it makes the fatal decision of going straight ahead, while all the other dots turn left.  That’s where you went wrong. Racing Dots As well as the described scenario, Smart Trax has competitive, ‘gaming’ applications, for example racing against other cyclists over the same route at different times.  For example, many competitive cyclists compare lap times of Richmond Park.  It would be interesting to overlay a number of cyclists on the same map, and watch them race side-by-side at a later time, even though they showed up on different days. Commuters could find value in Smart Trax, too.  If you cycle from Hammersmith to Baker Street, you might think you have to slog through Oxford Street traffic.  No matter, there are many others on Smart Trax who took routes with similar start and end points, but were more prudent by cutting through side-streets.  These will show up when you look for similar routes.  The alternative routes would appear as differently-coloured paths. Long-distance tourers and charity riders would benefit too.  Cyclists who are considering the “Lands End to John O’Groats” challenge might like to see real routes side-by-side, perhaps looking for the fastest, most scenic or shortest route.  Smart Trax would automatically detect LeJOG routes and group them together, because they’re all similar on a large scale. Challenges There are several technical challenges with this idea: - Algorithms to find closest matches.  It would be necessary to smooth the (sometimes erratic) GPS samples, and allow fuzzy-matching because relatively small deviations shouldn’t matter.  It should also be possible to scan for incomplete matches on routes.  For example, I might join a typical route half-way along, but I still want to know how my shorter route compared with others who did the whole hog. - Interface design.  The obvious choice would be to use public APIs and toolkits such as Google Maps.  But this might not provide the flexibility required for features such as “racing dots”.  So, a starting point would simply be paths traced over an opaque background, with pixels mapped to GPS co-ordinates.  A map or satellite background could be added later on. Personally, I might kick this idea off by comparing my daily commutes side-by-side.  It would be interesting to see one “dot” surge forward ahead of the others and wonder “what happened on that day?”  Perhaps the system would detect a particularly interesting “dot” and highlight it with annotations created at the time of upload, such as “mighty tailwind”, or “took the scooter for a change”.

I had an idea to create a road map for cyclists, colour-coded by the likelihood of congestion, using GPS data. Here’s some background.  I’ve been plotting a cycle commuting route from the West End to the Kingston area.  On the map, Fulham Road looked like the most direct route: a relatively straight diagonal to the SW. But when I jumped on the bike to try it out, I found that Fulham Road is narrow, and so there is no way to filter past heavy traffic.  The moral of the story is that the most direct route is not always the fastest. Now, I record all my routes via GPS, so I have data files containing time-stamped way-point data. In theory, if I looked back at the extract I would see that some roads were fast and others were slow, by working out the average speed between splits. I could then turn that GPS data into a nice colour-coded map: red roads for slow, and green roads for fast. Anybody who looked at that map would know to avoid Fulham Road at the time I hit it. Now what if thousands of cyclists did this, and the data was aggregated? You’d eventually have a road map of the British Isles, colour-coded by the likelihood of congestion given the time of day. Taking it further, you could ask for a suggestion of the route from A to B which is least likely to be a wall of steel and exhaust fumes. You could get even warnings or suggestions from your smartphone in real time. This does rely on having access to a large number of GPS recordings from cyclists, so there needs to be an incentive to participate. That’s where the route suggestions come in. I don’t know how practical this would be. There are certainly a number of snags with linking average speed to congestion … Time of day, hills, fitness levels, filtering abilities, “traffic light etiquette” and more. I get the impression that Tom Tom works in a similar way - collecting time-stamped GPS data from a large number of users. But Tom Tom is fairly closed, commercial and car-centric.  I want something tweak-able, for cyclists. Time-permitting, I’ll try this with my own data first as a proof-of-concept. EDIT: I’ve cooled down on this idea.  Once you aggregate large data sets, controlling for outside factors (hills, speed bumps, fitness levels and the like) would be far too complex.  The idea could be re-positioned as simply a “how fast do cyclists go” map for general interest.  I doubt this would get enough interest to justify the effort, though.

Good time management is a bit like computer programming, in some ways at least … How do you keep track of tasks which can’t be carried forward, until some outside event has taken place?  Perhaps you’re waiting for a response from a vendor, or a decision from your manager on which option to take. ‘Hanging’ tasks like this can compete for your attention: you can’t do anything for the time being, but you don’t want to forget about them.  Tasks like this aren’t really a “to do” item, there’s no action you can take.  Therefore on some level, your mind keeps telling you to check their progress over and over.  You just can’t let it lie and get on with something else. Polling and the Postman’s Knock To risk a slightly contrived analogy, imagine ordering a book from Amazon: a reference book you need before you can carry on with your project.  What do you do after you fire off the order?  There are only two basic options: keep checking your letterbox until it arrives, or get on with something else and wait for the postman to knock.  In computer parlance, the first approach is called polling, and the second is interrupt-based. Polling for an event is quite terrible as far as efficiency is concerned.  You just keep checking for the event to occur, over and over, without getting anything done in the meantime. You’d only want to do this in unusual situations: perhaps the postman won’t come right to your door, and leaves the parcel at the end of your drive instead.  In that case you would have to keep looking out the window for the parcel.  However, the upside is that since you’re continually checking for the arrival, it will be more obvious if it’s been delayed. The polling approach is fairly inept in general, assuming you have other things to do with your time.  It carries the cynical view that “I can’t trust anybody, I have to do everything myself!”  It takes an inaccurate view of responsibilities and feels like a generalised form of nagging (“Is it done yet? … Is it done yet? …”) Conversely the interrupt-based approach applies the inversion of control principle.  Rather than taking the burden yourself, this places responsibility where it is due.  The postman carries knowledge of your parcel’s arrival, so he can knock on your door when its time.  This allows you to forget about the order, depending purely on the ‘postman’s knock’ which acts as an interrupt.  At least in that case you could get on with something else in the meantime. However, there are several disadvantages to using interrupts.  First, you might forget you ordered the parcel, and it never arrives.  You had the luxury to get on with something else, but this distracted you from the pending task which never completed.  The second disadvantage is that when the postman finally knocks, you might be disturbed from what you were doing, allured by the shiny new tome in your haste to read it cover-to-cover. Ideally we want an approach to time management which gives us all the upsides, but controls for the risks.  “Give me a call when it’s ready, but I’ll keep one eye open in case that call never comes.” Fortunately, patterns to solve this problem exist, deep in the guts of your favourite multitasking operating system. Processes and I/O The polling approach may be seen in specialised single-process, real-time or embedded systems.  If only one special task is running, and that task is waiting for an event, then there is no harm in spinning in a loop. However, in typical multitasking systems, polling would be expensive and quite unnecessary.  Other more important tasks may be able to proceed while a task is waiting for its data. Therefore an interrupt-based ‘postman’s knock’ mechanism is favoured.  This design ensures that a multitasking operating system can maintain its guarantee that processes should be scheduled in priority order (in simple terms).  The interrupt-based approach is fair: I submit a request for the data, then I sleep while other things happen.  Subsequently I get a nudge once my data is ready. Let’s see how this happens in more detail.  When a process reads from disk, that request is sent to the disk controller, then the process is suspended (and placed onto a special Blocked queue).  Processes on the Blocked queue are waiting for some outside event to complete, and will never get any processing time until then. The hard disk (which can operate independently of the CPU itself) begins seeking the requested data in the background.  Meanwhile, the operating system switches to another process, say updating the screen or listening for mouse clicks.  It’s as though the pending “disk read” is out of mind, giving the luxury of a responsive system in the meantime. Later on, the hard disk finishes its work.  The hard disk controller is an actor in its own right, and gives the operating system a nudge (or interrupt): “Hey, someone requested some data - here it is”. How does the operating system respond to the interrupt?  Instead of immediately switching to the program that was waiting for the data (which might disturb a higher-priority task), the operating system moves the waiting process from the Blocked queue, to the Ready queue.  The Ready queue contains all the programs that can proceed with their work, often according to some priority order.  Once this is done, the operating system takes the opportunity to pick a new task from the Ready queue according to some priority order.  It may or may not be the task which requested the data. Once the waiting task gets its turn to run, it will proceed at the very next instruction after the call to read, with the pending data now in context.  This emerges as an elegant programming model - the application programmer does not have to explicitly do anything to deal with the complex mechanism under the hood. One issue is that a process may have to wait a very long time to receive its data, creating a ‘hang’.  What if some remedial action should be taken if a time limit is surpassed?  There’s no way the waiting process can implement this requirement - it’s in stasis on the Blocked queue and will never execute any code until the interrupt comes. To deal with this, a timeout value has to be passed to the operating system no later than when the call to read is invoked.  This suggests that the operating system must do some housekeeping on the Blocked queue; perhaps its items are ordered by a “time to live”.  This strategy appears to be utilised in the socket timeout parameter often available on calls to read data from a network. Maintaining your own Blocked and Ready Queues The scenarios described are similar to situations where a task on your to-do list is blocked on some outside event. Clearly we would want to take an interrupt-based approach in real life.  But how do we avoid the twin perils of (i) losing track of the time spent waiting, and (ii) becoming distracted by incoming ‘data’ as it arrives? The solution to both of these concerns is the “Waiting For” and “Next Actions” lists described in the Getting Things Done system.  The “Waiting For” list is your Blocked Queue - a list of items requiring a response from an outside party, each with an optional ’time to live’ before something has to be done to expedite it. Your “Waiting For” list is separate from your “Next Actions” (your very own Ready Queue).  It doesn’t pollute your everyday consciousness; you only have to review the “Waiting For” list as often as you really have to.  This ‘housekeeping’ prevents any items from sliding off the “Waiting For” list, and being forgotten. The second concern is easily solved.  When something you are waiting for becomes available, instead of becoming side-tracked by it, you simply move it from the “Waiting For” list to an appropriate addition to the “Next Actions” list.  Appropriately recorded, this frees your mind to focus on one task at a time.  You can then either continue what you were doing, or pick something from your “Next Items” (or Ready Queue) according to priority.

Good time management is a bit like computer programming, in some ways at least … How do you handle large tasks, without being overwhelmed by their size? Streams Computer programs generally read data from some location, process it, then output it somehow. For example, a video player will read data from the disk, decode it, then draw frames on the screen. Now, what is the best policy for this? How much data should be read from the disk, before it’s processed and flung out at the screen? In reality, it’s best to read a bite-sized chunk of data into a small buffer area, process it, output the result, clear the buffer, then proceed with the next chunk. If instead an entire video file was read in one go, on-board memory would be quickly exhausted or at least severely compromised. Streams provide this kind of functionality.  When you read from a stream, you just get the next chunk, without concern to how much input is yet to come. We often stream things from the net.  You can play an infinitely long audio stream (e.g. net radio), even with a relatively small amount of memory.   The audio player periodically engages in a buffering process - reading the next chunk of data from the network.  Therefore, an infinite audio stream should be just as “challenging” to process as a tiny sound file. It scales nicely.

I just pushed my most recent changes to NaturalNum - a python library for natural language representation of integer values.  E.g. usage:

$ python example.py 123456 en_GB [‘one’, ‘hundred’, ‘and’, ’twenty’, ’three’, ’thousand’, ‘four’, ‘hundred’,‘and’, ‘fifty’, ‘six’] $ python example.py 123456 fr_FR [‘cent’, ‘vingt’, ’trois’, ‘mille’, ‘quatre’, ‘cent’, ‘cinquante’, ‘six’]

Currently, only English and French are supported, for values up to hundreds of thousands. More languages will be added as inspiration strikes.  The library can be downloaded from github.  I stress that the implementation is a Proof of Concept, and is not a shining example of best practices. Really, it took far too much work to parse and validate the rules.  I didn’t want to write a full-blown DSL as I thought the requirements were fairly simple.  In future, I would not attempt this kind of thing with manually hand-crafted code.  There is heavy use of regexps for validation, and it is probably quite hard to understand what the code is doing.  Pyparsing could perhaps yield an alternative implementation. NaturalNum NaturalNum is a python module for easy conversion of numeric values to natural language, with full internationalization. E.g. “2100” can be mapped to “two thousand one hundred”, “deux mille cent”, “2.wav,1000.wav,1.wav,100.wav”, or any other representation, according to rules-based configuration. Quick Start The script example.py provides an example usage of the library, allowing command line evaluation of natural language. E.g.:

I’m trialling expert systems, in order to abstract away some tricky internationalization logic in an IVR application. Drools Expert might be what I need and will hopefully save time, compared with devil-in-the-details DSLs. The idea of a Rules Engine is that business rules are abstracted out of your application. Business rules are likely to change, so ideally they should not be in the source tree. Additionally, rules may be consulted or modified by business users, so ideally would be free from syntactic mess, and should be self-documenting. The idea in Drools is that a domain object (in this case an Applicant for a driving license) is injected into a rule. A rule is specified in a form which looks a bit like pseudo-code. The rule contains knowledge on what should happen to the Applicant depending on the values of its properties (for example if age is greater than 18). As conditions are satisfied, properties may be set on the object (e.g. setting valid to true or false). So when the Applicant has ‘passed through’ the rule, its state will reflect the outcome of the application. I wanted to get a quick example up and running, so I can gradually tweak it towards what I want. But I had some trouble with the Quick Start tutorial in the user guide. Here’s what I did to get a simple unit test passing in IntelliJ 9.