www.algorithmic-consultants.com

Your Concerns | Partners & Consultants | Algorithmics | Services | Contact

Algorithmics for performance.

Algorithms are `blueprints´ of computer code. Algorithms relate to the actual code similarly as an architect´s drawing to the building described, containing the basic structural and conceptual information but not all the details required to actually construct the building. They are usually written up in so called pseudo-code, which an application programmer can use as the basis for writing actual code for your specific system.

Algorithmics is the art of analysing algorithms and creating efficient new ones from a vast `toolbox´ of techniques and ideas your specific problem may be tackled with. We shall not dwell on the subtle distinction that Algorithmics in the strict sense is primarily concerned with computational aspects of discrete, combinatorial problems as opposed to problems arising from `continuous´ Mathematics, traditionally addressed by Numerical Analysis. Algorithmic Consultants can contribute on either field.

We shall give a short introduction to the benefits of using efficient algorithms employing advanced data structures. Efficiency is the same as performance, essentially. Our major point is to demonstrate that inefficient pieces of code can act as bottlenecks, severely impairing the overall performance of your application, or even bringing everything to a grinding halt when growing demand (`load´) is placed upon the software.

Scaling and constants. Getting the priorities right.

The last mentioned phenomenon is due to the fact that running times tend to scale in a super-linear way as a function of the `load´ placed upon the software. This is an issue when handling large and growing amounts of data which is likely to occur in an expanding business.

Usually, nobody cares too much for an improvement of running times by, say, 20%, possibly achieved by removing `overhead´ in the code thereby rendering everything unreadable. And nobody will be impressed by 1000-fold improved performance, when merely the running time of a routine called once in the initialisation process is reduced from a millisecond to a microsecond.

Algorithmics is about understanding and as much as possible eliminating the relevant bottlenecks, with an eye on growing `load´. Contrary to prevailing opinion, it is in most cases impossible to cure the non-linear explosion of running times by simply buying faster hardware. You may gain a factor of 2, possibly up to 10 this way, but this can be far too little. See our example below.

Algorithmics and software development process.

Efficient algorithms scale better than inefficient ones, using algorithmic knowledge can have more benefits than merely tuning constants at a given `load´. Algorithmics is more than pedantic performance-tuning. We do agree that code should be readable, maintainable and the like, and we have no objections at all to using state of the art OO-technology.

Frequently it will suffice to consider performance issues after the software-design process, namely when performance bottlenecks are confined to within certain methods or sub-modules. Yet in some cases algorithmic considerations may even suggest a different class structure, reflecting cleverly chosen data structures.

An example: sorting. The drastic effects of scaling.

As an example consider the fairly well known problem of sorting a number of n items. A (sorting-)algorithm will be a top-level description of what a computer should do with an unsorted array of n items, in order to return the array sorted.

As a naive, inefficient algorithm consider bubble_sort. It has a running time of (some constant times) n² steps in the worst case, and even in the average case. The familiar quick_sort runs in (some other constant times) n log(n) steps in the average case, but in the worst case it has still quadratic running time. An efficient algorithm as merge_sort will take n log(n) steps in the worst case, i.e. whatever the order of the initial array may have been.

Admittedly the numerical values of the constants will be relevant in practice. They will strongly depend on the specific hardware, the platform chosen as well as implementation details. It is realistic and safe to assume that these constants do not differ by more than a factor of, say, 10 amongst the various algorithms. Let´s further simplify matters and assume that the aforementioned constants all happen to be exactly 1 nanosecond per step - just to get our main argument across.

We will focus on the effect of scaling when the number n of items to be sorted grows.

When n =100, merge_sort beats the quadratic algorithms by a factor or roughly 15. Nothing exciting really: under the aforementioned simplifying assumptions, the quadratic algorithm takes 10 milliseconds, whereas the efficient merge_sort will take 0.7 milliseconds. They differ by more than a factor of 10, but they are both pretty fast. [In reality, due to the recursive nature of merge_sort the constant for this algorithm may well be larger than the one for bubble_sort, contrary to our simplifying assumption. So don´t count on this factor of 10 - these constants are best determined experimentally.]
When n =10000000, things look different. The efficient merge_sort algorithm is roughly 430000 times faster, and takes roughly 0.23 seconds. The inefficient bubble_sort will take more than a day. Even giving away a factor of 10 it will take hours as opposed to fractions of a second.

Note that this collapse of performance occurred with the identical software that performed reasonably well for small values of n. These effects will become even more drastic when n further increases, or when the scaling of the algorithms involved is even worse than quadratic.

Particularly for Optimisation one will easily devise straightforward but highly inefficient algorithms with exponential running times. For moderate values of n we could easily face running times longer than the age of the universe. No joke, no exaggeration here. Such algorithms are practically worthless. And there is definitely no easy way out such as buying a faster computer.

What algorithms are there and which apply to my problem? Modelling your problem.

Your Concerns | Partners & Consultants | Algorithmics | Services | Contact