Using Algorithmic Complexity with Care

Using Algorithmic Complexity with Care

Although algorithmic complexity is a very good guide to where time could be spent, several issues need to be considered.

It may be tempting to select the most efficient algorithms for every aspect of the code. Compare the lines of code necessary to implement the quicksort with those required for the bubble sort as well as how easy it is to read those lines of code and understand how the algorithm works. Algorithms with lower algorithmic complexity are usually more difficult to implement and more difficult to understand. Both of these fac-tors will lead to more developer time needed for the implementation, and the code may potentially need a more experienced developer to maintain it. The point is that using more complex algorithms can have an impact on developer time and cost. A simpler algorithm might be easier to implement and result in lower development costs. It may also be possible that the code does not need a more complex algorithm for typical workloads.

A second point to consider is that algorithmic complexity is concerned with the operation count. It does not consider the cost of those instructions. It may weigh the cost of an add operation the same as a multiply yet be possible to have algorithms that perform the same task with very different numbers of add and multiply operations. At another level, the algorithms don’t consider implementation details such as caches. One algorithm might be very cache friendly, whereas another could incur many cache misses. In any code, stall time because of cache misses can easily dominate the performance. Therefore, it is necessary to both look at the algorithmic complexity and evaluate the actual implementation of the algorithm to determine whether the implementation is likely to achieve good performance.

It is possible to look at an algorithm in the context of the number of loads that it will take and how likely each load is to miss cache. This would give an estimate of the amount of time spent waiting for data to arrive from memory. Of course, changing the algorithm will impact both the complexity and the probability of events. In the example of load misses, one algorithm might have higher miss rates but a lower-order complexity versus another algorithm.

One final consideration in the selection of algorithms may be whether the algorithms scale to multiple processors. If the algorithm has low algorithmic complexity but does not scale beyond a single thread, it could be slower than an algorithm of higher com-plexity that can be parallelized to run over multiple threads.