Book Review: Design Patterns

Design Patterns or Design patterns : elements of reusable object-oriented software to give it, its full title is one of those books that anyone who is using an OO language should read. Although most of the example code is written in C++ it is easy to see how the patterns themselves could be translated to other OO languages such as Java and C#.

This is the original book on design patterns, often referred to as the GOF or gang of four book (refers to its authors) it offers a wealth of knowledge accumulated from years of experience in designing software.

The book is split into two main sections the second of which is broken down further into another three sections.

The first main section is an introduction to design patterns, what they are and how they can benefit the user. This section then walks the reader through a case study designing a document editor emphasising the use of design patterns throughout. This is where the real world meets the theory and as the case study progresses you can see how by using design patterns flexibility can be added to software. It also highlights ways of recognising when a design problem can be broken down into patterns and the way at which to go about it.

The second main section of the book acts as a reference to the patterns. It is broken down into three smaller sections dedicated to each type of pattern, be it creational, structural or behavioral.

Each pattern is explained fully, giving information about how the pattern would be applied as well as where and when it would be used. Consequences of using the pattern are explained and an example implementation written in C++ is provided, this is then wrapped up by stating software that is known to use the pattern as well as listing other patterns that would accompany the selected pattern well.

With this book you are really getting two books for the price of one. First you are getting a good quality tutorial introducing the use of design patterns in a real world example and secondly you are getting a reference that you can easily use to look for a specific type of pattern when it's needed.

Once again as in my Modern C++ Design book review I would highly recommend this book to any serious programmer, it's a must have on your book shelf even if you only ever use it as a reference, and even though all of the examples are in C++ the UML diagrams included should make it easy for any OO developer to use the patterns across languages.

Embedded: ARM development on the cheap. Part 1

Welcome to the first part of what will probably turn out to be a three part series all about using a combination of cheap and completely free tools to do embedded development on the ARM series of micro processors.

Embedded development for many years has been a bit of a black art as far as the hobbyist is concerned. Due to the large amount of money involved to buy specialist software development tools any type of embedded development has been restricted to companies making products or to those willing and able to fork out the money. Well that time has come to an end. Affordable hardware debuggers are now available and the open source community have brought us the relevant tools required to drive the hardware.

This series is aimed specifically at the Philips LPC2129 ARM7 based chip, as this is what I have been developing on myself. While the board I'm using was specially built by the hardware department in the company I work for, everything in this series will be transferable to other development boards based on ARM7 processors. Most of the time it will only require a small number of settings to be changed to get things up and working.

Tools that will be required.

• Development board
• JTAG
• Compiler tool chain (including debugger)
• IDE

Development board

As I stated above just about any ARM7 development board should work OK with this series. Just to make sure though it would be best to get something based on the Philips LPC2xxx series of CPUs. The development board will also require a JTAG header to be present.

JTAG

A JTAG is a piece of hardware that connects your PC to the development board. It can then be used to upload code into the memory or flash of the device and debug the applications running. It is this piece of equipment that originally used to make embedded development cost so much. Now however there are companies offering cheap JTAGs that can be used with open source software. The JTAG we will be using is from a company called olimex, and is a simple parallel port model. While they also do USB based models which are much faster at uploading code to the device they are relatively new and more expensive than the parallel port version.

Compiler tool chain (including debugger)

Thanks to the open source community all the tools required to build and debug the applications you want to make are available for free. I have been using GNUARM for building my applications, which also handily comes with a debugger. The only other piece of software used is OpenOCD. This is a debug server daemon that allows communication between the JTAG and the debugger being used. In true open source style both of these tools can be found for most operating systems available, so you don't have to be running Windows.

IDE

I decided to use a copy of Visual C++ 2005 that I use at work for Windows development to also do the embedded development. This can be done by using a make file project. You can use any IDE you like or no IDE at all it's up to you. All of the builds will be managed by make files so as long as you have something that can edit text with you'll be OK. I've used Visual C++ 2005 because I find it nice to work with, I can arrange my files etc into projects and it integrates nicely with our source control system. To keep with the theme of doing things for free, the Express edition of Visual C++ 2005 also supports make file projects so that can be used.

So that's basically it for this edition. In the next part of the series I will be going through setting up the compiler and getting it working with Visual C++ 2005.

Calculations with templates in C++

This is a quick post designed to show you how you can use templates for pre-calculations for optimisation or simply ease of use / design.

Let me give an example; imagine you have a class that has a buffer of size T, that stores information for use later, perhaps to return temporal statistics. The buffer size may rely on two parameters that define the size as X to the power of Y.

There doesn't exist a define to calculate powers at compile time, so normally you would have to have allocate the memory at run time. This can be useful but sometimes you want the memory to be allocated at compile time as it can make certain things easier and faster.

Firstly the power calculation isn't done at run time saving time there, it also means you know the exact size of the class before you create it, helping you keep tabs on your programs memory usage. It also means the memory is always there and you do not have to worry about checking pointer / memory validity. Now I know the time to calculate the power of a number is nominal however there will come a point where you need this solution. Trust me.

Right onto the code. You should have at least a basic understanding of templates to get the most out of this, so if you do not I suggest you look it up as there are lots of resources on Google.

This first template class is the guts of the system, it defines the power template that will do the calculation. It works iteratively.
template <int base, int N>

class MyPow
{
public:
enum { result = base * MyPow<base, N-1> ::result };
};

Next is the template specialisation for MyPow which defines result as 1 should the base reach 0.

template <int base>
class MyPow<base,0>
{
public:
enum { result = 1 };
};

And here is how you could use it within your class, m_MaxDataPoints is defined as T_Base to the power of T_Power.

template <int T_Base, int T_Power> class MyClass
{
...
const int m_MaxDataPoints = MyPow<T_Base, T_Power> ::result+1;
...
}

So in just 3 simple steps you can now perform power calculations at compile time. You can also extend these principals to create templates for different uses.

Tight loop optimization in C++

Duff's Device is a fairly well known technique used for optimizing small loops. It uses switch case statement fall through that [when compiled] mimicks loop unrolling but is generally much faster and cleaner to use than standard loop unrolling. This is a breif article on the usage and speed benefits of using Duff's Device for optimizing tight loops.

I first used Duff's Device whilst developing a cross platform graphics library from which the examples given are drawn from. They may not be perfect but definately indicate correct usage of the device.

Firstly here is the C++ implementation of Duffs Device, in the form of a #define. This #define takes care of all the operation of the device, all you need to do it use the right parameters with it.

#define DUFF_DEVICE_8(aCount, aAction) \
{ \
int count_ = (aCount); \
int times_ = (count_ + 7) >> 3; \
switch (count_ & 7){ \
case 0: do { aAction; \
case 7: aAction; \
case 6: aAction; \
case 5: aAction; \
case 4: aAction; \
case 3: aAction; \
case 2: aAction; \
case 1: aAction; \
} while (--times_ > 0); \
} \
}

Before I go on to discuss the device itself there are a few hidden optimizations in the code [which you could take not of and employ elsewhere in your code].

• Firstly you will notice that a shift has been done rather than a division, shifts are much faster than multiplications and divisions when dealing with powers of 2, so where possible you should use shifts.
• Secondly the while condition contains --times_ rather than times_--. Pre-decrement [and increment] is faster than post decrement / increment. This is because post operations require a copy of the variable to be made. Obviously this overhead is minimal, but if speed is of the essense small savings count.
• Also in the while condition you can see the comparison is against zero [counts down] rather than against aCount [counts up]. This is beacause a comparison against 0 is much faster than any other number.

N.b. many compilers will replace perform these optimisations on compile time so they are not always needed.

So how can you use Duff's Device in your code?

You simply use it like a normal define, taking care to finish each line with a semi colon.

void Bitmap::Blank(COLORREF colour)
{
unsigned long *blitPtr = m_BitmapData;
unsigned long *blitEnd = blitPtr + (m_Width*m_Height);
unsigned int index=0;

int numPixels = static_cast<int>(blitEnd-blitPtr);
if (numPixels > 0)
{
DUFF_DEVICE_8(numPixels, blitPtr[index++] = colour;);
}
}

This code is designed to simly fill my bitmap with a certain colour defines by COLORREF [simply a DWORD aka long which is 4 bytes on most machines].
The first operation I do is to get the pointer to the start of my array [i.e. the start of the bitmap] and then get the end of my array using some pointer arithmetic.

Onto the usage of the Duff Device itself; as you can see numPixels is passed as the count parameter and "blitPtr[index++] = colour;" is passed as the code to run in each iteration. Notice the trailing ; inside the statement which is required as it is text replacement and not a function.

Quite simply it iterates through each pixel [long] in our m_BitmapData array and assigns the colour to it.

In tests on my machine Duff's Device, in this instance, is faster than a memcpy. This is not to say that it will always be faster, but in this instance it was. The point is that no matter how efficient a certain algorithm or piece of code is, the generic algorithms / hardware accelerated variations will usually be faster for most instances.

So if you do have a very tight loop that requires speeding up then why not look to Duff's Device to see if it could improve the efficiency of the loop.

It is worth pointing out that more obvious optimisations should be made before looking to a novel solution such as this. i.e. remove allocations or any code that doesn't need to be in the loop - simple!

Book Review: Modern C++ Design

Weighing in at just over 300 pages, this book might not initially seem like it has much to offer. However this couldn't be more wrong. Andrei has packed a wealth of knowledge into every page of this book making it an invaluable tool.

When I first read this book I was in my first year at University and to be honest it meant nothing to me. If you had asked me then if I would have recommended it to anyone I would have said no. It's only since reading it again recently after writing real world C++ code, that it really starts to make sense.

This is really not a book for someone just learning C++. It tackles some of the more advance topics of C++, mostly revolving around templates and there use as a design tool. It does not teach templates themselves and assumes the reader has a good grasp of C++, so if you've been coding C++ for a couple of years at a reasonable level then this will be a good book for you.

The main focus of the book is taking common design patterns and creating generic implementations using templates that allow you to easily customise behaviour using different policies, which are provided in the form of small easily maintainable classes that implement very specific features in a generic fashion.

The start of the book introduces the concept of policy based class design along with techniques to allow you to recognise and extract policies from existing classes.

The book then moves on to explaining techniques to control the allocation of memory and typelists. Typelists are both elegant and breath taking, they really show the power of template meta programming to create code for you at compile time.

The above ideas and techniques are then used throughout the second section of the book, which takes commonly used design patterns and shows ways of extending there functionality easily using templates and policies, as well as introducing a high level of flexibility.

When dealing with the design patterns, Andrei first begins with pointing out the problems with the current pattern and then proceeds to set out a plan to improve it. This way instead of just being given a set of step by step operations to implement a certain design pattern, he points out the pitfalls of using the patterns and attempts to offer a solution to the problem, educating the reader rather than just holding their hand.

A lot of the code presented in this book is aimed at library writers. It attempts to create a flexible library of code that could be used along side the standard library to make common design tasks easier to implement. This however should not put you off if this is not your area of coding as there is still a lot to be learnt from this book even if you don't use it every day.

I would highly recommend this book to anyone who wants to be a serious C++ developer.