In what areas of programming is algorithm run time actually an important issue?

Question

Sometimes I hear people say that because of the speed of processors and the amount of memory available, algorithm efficiency and runtime aren't, in practice, of major concern.

But I imagine there are still areas where such considerations do remain of paramount importance. Two that come to mind are in algorithmic trading, where thousands of transactions must be conducted in fractions of a second, and embedded systems programming, where memory and power are often scarce. Am I right about these examples ? and what other areas would also be examples?

Answer 1

Speed is always in demand. I guess you are correct. Here are some examples were neat algorithms are in demand:

1. Cryptography

2. Searching large databases

3. Sorting and merging

4. Text searching (non-indexed), including wildcards

5. Math problems with intensive calculations

6. Simulation

7. Data Mining Applications

8. Animation

9. AI

10. Computer vision

Answer 2

There are some cases where algorithm run-time might not be a big deal, because we've gotten to the point that you can simply punch through a longer-running algorithm with more powerful hardware. But there are definitely some places where speed-ups are essential.

Generally speaking, anything using huge datasets will be a problem. When you have something that scales poorly with n, and then you make n a really huge number, you have a problem. I suspect if you went over to the Computational Science beta site and poked around a bit, you could find plenty of problems in need of better, faster algorithms. Some areas that I've run into:

• Particularly complex statistical analysis. A combination of inefficient algorithms and large data sets can mean massive slowdowns. For some studies, this might not matter, but what if you're trying to do something with fast turn around? "It will come off the server in a month" is probably a bad thing when you're running a chemical/nuclear/biological threat surveillance system.
• Data mining on large data sets.
• Simulations involving many variables.

Generally speaking, scientific computing generally seems to be an area where the complexity of what's being programmed generates opportunities for serious slowdowns if your algorithm is sluggish (many of them suffering from very large n's). And, as you mentioned, there's financial applications. When milliseconds can determine whether you make or lose money on a trade, "good enough" algorithms aren't going to cut it if there's something better that can be done.

Answer 3

Sometimes I hear people say that because of the speed of processors and the amount of memory available, algorithm efficiency and runtime aren't, in practice, of major concern.

Take it with a grain of salt. More computing power basically just means that your n can become much larger before it significantly slows down. For most everyday problems, this n is now large enough that you don't need to care. However, you should still know the complexities of your algorithms.

With more available resources, it may need to crunch more data later. Today you need to analyze a 10MB log file with 100,000 lines. In a year you may have a 100GB log file with 1,000,000,000 lines. If the amount of data grows faster than the resource powers, you run into problems later.

With more available resources, more layers are stacked upon each other. OS, OS framework, 3rd party framework, language interpreter, and finally on top your own tool. All unnecessary inefficiencies in all the different layers multiply up. Tomorrow your tool may run on a new OS with more bells and whistles, that itself eats more cycles and more memory, leaving less for you.

So to answer your question, you still need to care where more and more data needs to be crunched (enough examples given in the other answers), and where you do not provide the final tool, but another abstraction layer for other tools.

Answer 4

A few years ago I had to write an algorithm that sorted test tubes arranged on n racks into two distinct partitions: i.e. one subset of the tubes were 'chosen' and the rest were 'not-chosen' and the end result would be that no rack would have both a 'chosen' and 'not-chosen' tube on it (there were some extra requirements such as compression). Each rack contained a maximum of 100 tubes.

The algorithm was to be used to drive a tube sorting robot in a pharmaceutical laboratory.

When the original specification was given to me I was allocated in the region of 1 minute of calculation time to sort around 2000 tubes as we thought that usability wise that was not too painful. There was a requirement that number of moves was to be minimal over all possible combinations as the robot itself was slow.

The implicit assumption was that the complexity would be exponential with the number of tubes. However, whilst working on the algorithm design I discovered that there is a fast O(n) algorithm where n is the number of racks that performed an optimal partitioning of the tubes. The result of that was that the algorithm sort time was instant so the sorting display would be updated in real time as the user configured their sort operation.

For me the difference between the user sitting for a minute after every change and having an instantly responsive GUI was the difference between a piece of software that was functionally sufficient and a piece of software that was a pleasure to use.

Answer 5

Other areas include many kinds of real-time signal processing, feedback control systems, oil exploration deconvolution, video compression, ray tracing and movie frame rendering, virtual reality systems, games where high frame rate might be a significant competitive advantage, and smartphones and other mobile device apps, where large numbers of CPU cycles will consume the users battery life faster.

I'm quite surprised this question would even be asked, since for any Top-500 supercomputer ever built, there is likely a waiting list of researchers who can max it out and wish for magnitudes more compute power or magnitudes better algorithms to solve some problem (fold some protein to decipher cancer, etc.) before they retire.

Answer 6

I think search engines like Google and Bing are one of the biggest areas where complex algorithms are used and they play a key role in speeding up results with relevance ( page ranking ) bringing more utility to the users.

Answer 7

Algorithm efficiency isn't a major concern nowadays because we're using efficient algorithms. If you used an O(n!) algorithm, it would be slow on any kind of hardware.

Answer 8

Algorithm complexity is becoming more and more important as the sheer amount of data increases. Fortunately, efficient generic solutions for common programming problems (searching and sorting, mainly) are included in pretty much every modern programming language's standard library, so normally, a programmer doesn't have to worry about these things much. The downside is that many programmers do not know at all what is going on under the hood and what the characteristics are of the algorithms they use.

This becomes especially problematic as many applications aren't properly stress-tested: People write code that works well for small test data sets, but when confronted with a few thousand times more data, the code grinds to a halt. Something that works well for ten records quickly explodes when the data set grows. Real-world example: a piece of code that was supposed to clean out items that weren't linked to any category anymore used a three-level nested loop, which is O(n^3). With just 10 records in the test database, this meant 1000 checks - perfectly doable, and doesn't introduce a noticable delay. However, the production database quickly filled with around 1000 rows, and suddenly the code does a billion checks each time.

So: No, you don't need to know the ins and outs of implementing all sorts of neat algorithms, and you don't need to be able to invent your own, but you do need some basic knowledge of common algorithms, what their strong and weak points are, when and when not to use them, and you need to be aware of the possible impact of algorithmic complexity, so that you can decide which level of complexity is acceptable.

Answer 9

It's not a question of what application domains are runtime-sensitive. Any program, anywhere, has a minimum performance below which it is effectively worthless. The point of algorithm complexity is how it varies with increasing input size. In other words, the areas where speed particularly matters are those where you expect to have to scale beyond not just your current problem size, but the order of magnitude of your current problem size. If you process the tax applications of the citizens of a département of France, the task may be large, but it's not likely that either the population size or the complexity of processing one record will ever increase ten or hundred-fold, so whatever works for you now, will probably keep working. But if you try to create something that will take off at internet volumes, algorithm complexity is key: anything that depends more than linearly or log-linearly on the input size will become much more expensive very fast, and eventually processor speed just can't keep up with the growth.

Answer 10

In my field (VFX, which covers things like path tracing, computer animation, particle simulation, fluid dynamics, image processing, etc), algorithmic complexity is fundamental. There's no way anything operating in worse than linearithmic time can hope to complete in any reasonable time on inputs that commonly reach millions of vertices, polygons, voxels, particles, texels, especially when many of these things need to complete many times a second to provide real-time, interactive feedback.

With that said, there's not that strong of an emphasis on algorithmic complexity in discussion typically among colleagues, perhaps because it's somewhat taken for granted and rather "rudimentary". It's generally assumed if you're writing a path tracer that it's going to operate in logarithmic time or better, and that data structures like bounding volume hierarchies are familiar and relatively trivial to implement for the reader. I even had a skilled colleague who kept saying that multithreading and SIMD are more important than algorithms, and I don't think he meant that in the sense that you could expect to get much out of parallelizing a bubble sort. I think he said that because he took it for granted that we'd apply sensible algorithms, and the rest of the challenge is often parallelization and choosing and adapting algorithms and designing the data representation to operate in parallel.

Often a lot of the focus these days is on taking many of these familiar algorithms and making them better exploit the underlying characteristics of the hardware like the CPU cache, SIMD registers and instructions, GPUs, and multiple cores. For example, Intel came up with a novel way of taking the familiar old BVH and coming up with the concept of "ray packets", basically testing multiple coherent rays at a single time with a recursive sort of tree traversal (which might sound like it'd come with its share of complexity and overhead, except it's more than made up by the fact that those rays can now be tested simultaneously for ray/AABB and ray/triangle intersections through SIMD instructions and registers). Other cutting-edge path tracers have managed to implement such spatial indices and actually perform the ray intersections directly on GPU.

Similar thing with like catmull-clark subdivision, which is very rudimentary stuff in computer graphics. But nowadays what's competitive and hot and super efficient are GPU implementations which approximate CC subdivision using Gregory Patches, as popularized by Charles Loop and later adopted by Pixar. The more straightforward CPU implementation is now rather obsolete, not necessarily because it was superseded in terms of algorithmic complexity, but because it was superseded by something that plays well with the GPU.

And that's usually a lot of the challenge these days is not coming up with the best algorithm in a way that's relatively independent of the underlying characteristics of the hardware. I actually got my foot in the industry by coming up with a novel acceleration structure that significantly sped up collision detection for animating characters and other soft bodies in the 90s using a hierarchical segmentation approach as opposed to a spatial index, which got me a lot of job offers, but these days it's not so impressive anymore since I published it long before we had such impressive CPU caches and multiple cores and programmable GPUs and what not, and nowadays I use a completely different approach as a result of the significant changes to the underlying hardware. So the focus has actually shifted more towards what might be in the realm of "micro-optimizations" in my case over novel algorithmic concepts because now we've got multiple cores, AVX registers, GPU shaders, etc. It's a different ball game to me now where I can't just hope to compete by coming up with a cool algorithm unless it really plays well with the peculiar nature of today's hardware which especially requires a lot of attention and care these days to fully exploit.

Answer 11

I once ran into a problem where an algorithm usually ran in O (n), but in rare and extremely unlikely circumstances would need O (n^3) time - the "rare" circumstances were a directory containing files with names that were valid in one operating system but not in another.

Nobody ever ran into problems. Then one customer used a strategy to name files that would systematically run into the O (n^3) case, and with a few 100 files there system came to a virtual standstill. Result was that the algorithm had to be changed.

Answer 12

Three more that haven't been mentioned:

1) Many real time strategy games. Look at those which have units which can't share a position. Watch what happens to the pathfinding when a large group of units moves through restricted terrain. I have yet to encounter a game without some sort of substantial problem with this because there simply isn't enough CPU power available.

2) Many optimization problems. (Edit: Since I wrote this answer I've hit one. My objective was to prune redundant paths so as to leave all nodes connected with the minimum weight of the connecting paths. My original approach worked pretty well until I moved more of the pruning to that routine, then I realized it was 2^n. Now it's n^2 even though that can sometimes produce a slightly non-optimal result.)

3) Things which must operate on large amounts of data in realtime. Consider a DVD: You usually get 2 hours of video in 4.7gb. Consider a typical video file at the same resolution: Those 2 hours of video will generally come in under 1gb. The reason for this is when the DVD spec was laid down you couldn't make a reasonably-priced DVD player that could decode the more modern formats fast enough.

Answer 13

Well, any application that's typically run on a supercomputer (list of the biggest machines) qualifies. These are diverse, but a big subclass of them is physics simulations:

• Physics simulations:
  • Weather forecast
  • Climate simulations
  • Simulations of exploding stars etc.
  • Simulations of exploding nukes
  • Aerodynamic simulations of cars/planes/trains etc.
  • ...
• Computing images from radio telescope data
• Biological applications:
  • Stuff with DNA sequences (I'm not really into those)
  • Biochemical stuff like protein folding
  • Simulations of how nerve cells work together to process information
  • Simulations of other complex interactions like ecosystems
  • ...
• ...

These are just the top of my head topics, but just read the list of the different supercomputers and realize that each and every one of these is built to enable some kind(s) of computations that would not be possible without such gigantic machines.

And, once you see that we actually need these machines, realize how much costs can be saved, just by speeding these application up by 10%. Any optimization of these codes directly increases the amount of results that we are able to get out of these machines.