Performance and concurrency

Performance and concurrency

A technical post today, methinks. After having been assigned to my project supervisor for next year, it seems the thing we are most compatible on is exploring concurrency patterns in software. To that end, I have been researching some of the issues surrounding concurrency by analysing the design of some of my code at work. I am not at liberty to post real source code, so I have given the architectural overview below.

There is a lot to be said for concurrency and how it relates to software performance. It is easy to overlook the fact that a bad concurrency design can harm or completely destabilise the performance of even the simplest imperative algorithm. It is equally easy to dismiss that an inferior algorithm in a concurrent design may produce more scalable and thus faster results for larger problem sizes. A popular example of the last point can be found in matrix calculations (O(n^2.83) single threaded vs. O(n³) multi-threaded).

In my work at Tek, I have built a batch tool for extracting information from PDF files for evaluations purposes. The initial approach was to create one thread per document, per operation that the tool performs. In the early versions, this was a reasonably quick, if naïve, way to deal with concurrency in the application.

As I started to add more features to the codebase, like different types of information extraction, and particularly the creation of a new document containing only the images from the original, I ended up with several different methods with a fair amount of duplicate code, summarised as pseudo-code below:
foreach(PDFDoc doc in collection)
new Thread(doSomething, doc).start();

private void doSomething(PDFDoc doc)
foreach(Page p in doc)
foreach(Element e in p)
// extract the info

Now if you only have to call that once per file, the performance doesn’t suffer too much, but doing the same thing for multiple different kinds of information extraction (including casting and shared object update overhead) can become very slow, especially on a single-core CPU. My solution was to only browse the element tree of a document once, merging all the useful data extraction routines into a single method. This reduces the I/O overhead by about a third and reduces competition for shared objects while simultaneously making the code a lot easier to maintain, as there is now only one copy of all the thread set-up code, security initialisation, and element tree parsing logic.

The above example is greatly simplified (the element parser is a recursive method call, for example) but demonstrates the point well, I think. I got to the stage where my parallel code was slower than a single thread. A bit of optimisation later, and life is good again. I’m looking forward to cracking into the topic of concurrency more during the summer and when I return to university in October.

My internship is definitely paying off. I’ve managed to learn a lot about .NET, C# and Spanish so far.