20

I recently finished a course on advanced algorithms, and another on complexity & computability theory, and in the past few days my mind has been somewhat preoccupied by this question.

Why don't we just use a different algorithm based on the size of the input?

I'm asking this question because I've never seen this done in practice or heard of it, and I'm also simply curious about the answer. I also tried looking it up on StackExchange and Google with various queries but couldn't come up with anything remotely related to my question.

I'll take the example of sorting algorithms, as they're quite common and there are so many, with different properties and runtime complexities.

Say I have three algorithms, SortA, SortB and SortC. SortA is incredibly efficient on inputs of size <= 100 but becomes very slow on inputs that are any bigger; SortB is more efficient on inputs of length > 100 than SortA but falls off quickly after a size of 1000. Finally, SortC isn't very fast on inputs of size < 1000, but is faster than SortA and SortB on very large inputs.

Why shouldn't/couldn't I make a function like this (written in pseudo-C#-ish code for simplicity)? Or why isn't it done in practice?

int[] Sort(int[] numbers) {
    if (numbers.Length <= 100) {
        return SortA(numbers);
    } 
    else if (numbers.Length <= 1000) {
        return SortB(numbers);
    } 
    else {
        return SortC(numbers);
    }
}

I'm assuming some of the potential reasons are that

  1. it's more code to write,
  2. more potential bugs since there's more code,
  3. it's not necessarily easy to find the exact breakpoints at which some algorithm becomes faster than another, or it might take a lot of time to do so (i.e. running performance tests on various input sizes for every algorithm),
  4. the breakpoints could only be on small or medium-sized input, meaning there won't be a significant performance increase that is worth doing the additional implementation work,
  5. it just isn't worth it in general, and is only used in applications where performance is crucial (similar to how some numerical algorithms use a different method to solve a problem based on the properties of a matrix, like symmetry, tridiagonality,...),
  6. input size isn't the only factor on an algorithm's performance.

I'm familiar with Landau/Big O notation, so feel free to use it in your answers.

8
  • 66
    This is completely normal and done all the time, so it is kind of hard to answer the question "Why isn't this done". Any real-world quick sort will switch to insertion sort for smaller inputs. Aug 27, 2020 at 15:41
  • 1
    The majority of libraries implementing quicksort will automatically switch to insertion sort for small arrays. If I'm not mistaken this is what glibc does so all code compiled by the GNU toolchain does exactly what you are suggesting. I suspect llvm also does this so all code written for Mac OS and iOS do this automatically (XCode uses llvm internally which is why Apple is funding and supporting development of llvm). Not sure about Windows though because I don't write Windows code too often
    – slebetman
    Aug 28, 2020 at 11:25
  • 1
    To add, we sometimes launch multiple attempts at solving the same problem in parallel using different algorithms/parameters when it's hard to predict which might work best.
    – Nat
    Aug 28, 2020 at 12:12
  • 1
    glibc is not tied to GCC nor is GCC tied to Glibc, I have compiled MSVCRT code wihh GCC and Glibc code with Clang
    – Jasen
    Aug 28, 2020 at 12:37
  • 3
    You don’t need the exact point where algorithm A becomes faster than B. In most cases, there will be a reasonably large range where they have very similar speed.
    – gnasher729
    Aug 29, 2020 at 11:05

6 Answers 6

72

Why don't we just use a different algorithm based on the size of the input?

We do. Hybrid algorithms are used all the time.

Why shouldn't/couldn't I make a function like this (written in pseudo-C#-ish code for simplicity)? Or why isn't it done in practice?

That is quite literally how most real-world implementations of sorting algorithms look like.

E.g. quick sort has quite a high overhead, so every real-world quick sort implementation switches to insertion sort for the simple cases at the lower levels of the recursion tree. Instead of switching algorithms at the leaves of the recursion, you can also simply stop sorting altogether at some pre-defined partition size, and then run insertion sort once on the "almost-sorted" result of the "aborted quick sort". This may be more efficient, because instead of having many tiny insertion sorts, you have one longer one, so you don't constantly switch between quick sort and insertion sort in the instruction cache.

Merge sort is also often combined with insertion sort. For example, for cache efficiency, you might want to switch to an in-place insertion sort as soon as the partitions are small enough to fully fit into the cache.

One of the most-widely used sorting algorithms is Timsort, which was implemented for CPython in 2002 by Tim Peters, and has since been adopted by (among others) Oracle JRE (and many others, e.g. IBM J9) as Arrays.sort for reference types, Android, V8, Swift, and GNU Octave. It is a hybrid insertion sort and merge sort, It tries to find "runs" of already sorted elements and merges those; if it can't find any runs, it will create them by partially sorting the list with insertion sort.

Considering that it is used in some of the most widely-used implementations of some of the most widely-used languages, i.e. in Android and Swift (in other words, on pretty much every smartphone and tablet) and also in Java (in other words on pretty much every desktop and a large number of servers) and V8 (i.e. in Chrome and Node.js) and CPython, we can quite confidently say that there is probably not a single person on the planet who has not used it in some form. I don't know about you, but I wouldn't call that "not done in practice", in fact, it doesn't get any more practical than running on almost every computer in the world.

it's not necessarily easy to find the exact breakpoints at which some algorithm becomes faster than another, or it might take a lot of time to do so (i.e. running performance tests on various input sizes for every algorithm)

Introsort solves this by being, as the name implies, introspective. It starts off as a quick sort, but it watches itself while it executes, and when the recursion exceeds a certain depth, it switches to heap sort. Regardless of whether it switches to heap sort in between or stays at quick sort, for very small arrays, it then switches to insertion sort.

Introsort is used in several C and C++ standard library implementations, in .NET, and with Shellsort instead of insertion sort as the final algorithm in Go.

As we have seen above, Timsort has a really clever take on this problem: if the input data doesn't fit its assumptions, it simply makes it fit by partially sorting it first!

8
  • 5
    Thank you. Hybrid algorithm is exactly the word I was looking for and couldn't find anywhere. I guess I haven't had enough real world experience to see these actually applied.
    – cliesens
    Aug 27, 2020 at 18:59
  • 3
    "The data mangling will continue until performance improves" is the amusing thought that pops into my mind upon reading that last sentence. (Yes, I'm aware that Timsort doesn't actually mangle data in the traditional sense of data-mangling.)
    – 8bittree
    Aug 27, 2020 at 22:07
  • 9
    Re: "we can quite confidently say that there is probably not a single person on the planet who has not used it in some form": I believe there are millions of people who've never used a computer (even a smartphone), not even counting babies. And to take an extreme case, I think we can confidently say that none of the Sentinelese have used Timsort!
    – ruakh
    Aug 28, 2020 at 0:32
  • 1
    @8bittree: You are actually correct, and the amazing thing is that it actually works, in that using a simple and slow algorithm to create conditions required for a specialized fast algorithm is actually competitive with a more general sophisticated algorithm! Timsort is essentially competitive with quick sort in the best and average case, is much better in the worst case, and is stable to boot! Aug 28, 2020 at 8:22
  • 2
    RE: "literally how most real-world implementations" Real-world is even better than OP's pseudocode. It can use SortA then switch to SortB. OP's merely chooses once at the start. Aug 28, 2020 at 18:39
8

I'm coming at this from an engineering rather than an academic answer.

Two algorithms mean twice as much code to write, test, and maintain. It's also twice as much code which could potentially break. With current computers it's often better to write your software as clearly as possible and then optimize if it's required, otherwise you end up creating illegible code for no benefit (I it's possible to write legible efficient code but lets assume for the sake of argument there's a correlation and if both was an easy option then there would be no question to ask).

Next, let's assume that Algorithm A operates best on <1000 items and Algorithm B works best on anything over 1000. In reality how long is Algorithm A really going to take? A fraction of a second? If it's any more than that you could probably step through one at a time and be more efficient. So, if the less efficient algorithm takes less than a second would it really be that inefficient to use the less optimized one?

The largest cost in software is more often than not the development and the bugs. From a practical point of view often the simplest solution really is the best one - why create twice as much code to maintain to save a fraction of a second in operation which humans probably wouldn't notice anyway?

Obviously the question changes if you're processing <1000 items a million times a day but if that's the case just batch them per second!

4
  • 19
    The standard library sorting algorithm executes trillions of times a day. If you save one microsecond, that is an entire tonne of coal per day.
    – user253751
    Aug 28, 2020 at 10:59
  • 4
    @user253751: and as you allude to, library and compiler authors, the people implementing sorts, have different goals and purposes than application developers. Aug 28, 2020 at 17:27
  • 5
    @user253751 Oooh, dangerous terrain. If I only think about the tons of coal wasted by interpreting and just-in-time compiling java byte-code or ECMA-script, not to speak of the overheads of garbage collection... I think, we programmers should be very quiet when it comes to being efficient. Don't get me wrong, I'm all for optimizing. But worrying about a single ton of coal a day when we foster so many inefficiencies feels like an SUV pilot bragging about the fuel savings they get from overinflating their tires... Aug 29, 2020 at 18:20
  • Good point @user! I’ll try and update my answer when I get the chance
    – Liath
    Aug 30, 2020 at 3:41
3

The answers so far has concentrated on practical aspects. A more academic answer follows.

In Algorithm Analysis we look at what happens when size grows towards infinity. And that is all we do.

So, what happens in your example when size grows? The program will call SortC and ignore the other alternatives. So, all we have to do is analyse SortC and we are done.

To make easy for the students we will only give them the code for SortC. No need to confuse things with unimportant details.

An interesting wrinkle happens when the algorithm is recursive. The top level call and the first levels uses SortC, but the recursive calls can use the other parts. However, it turns out that this will only change the result by a constant factor. And as we know, constant factors are not important... to academics.

A good course in Algorithm Analysis will explain all this, but not all courses are good.

2

Why don't we just use a different algorithm based on the size of the input?

I'll look at this question from a very different perspective, which is human spaceflight safety. It has been near dogma since the start of human spaceflight that highly critical segments of spaceflight must have a backup flight system. The rationale is a what if game: What if the algorithms used in / the sensors used by the primary flight software are flawed?

The backup flight system typically uses a different and possibly reduced set of sensors and maybe even different effectors than those used by the primary flight system. (Sensors are devices that passively measure aspects of a vehicle's state while effectors are devices that actively change aspects of a vehicle's state.) The backup flight system is driven by backup flight software, which is written by a completely separate group of people than those who write the software for the primary flight system.

The primary argument in favor of a backup flight system is that the reduced scope and reduced sensor set makes the backup flight system and the resulting backup flight software less complex. That the backup flight system was developed by an independent team supposedly makes the system more reliable overall.

The primary arguments against a backup flight system are that the scope is not significantly reduced (those critical sections of flight are inherently complex), that the reduced sensor set does not reduce and may even increase software complexity, that the redundant sensors unnecessarily add weight, that the backup flight system inherently increases cost, and perhaps most importantly, that the people who write the backup flight software / create the backup sensors went to the same schools as did the people who write the primary flight software / create the primary sensors.

As far as I can tell, SpaceX does not ascribe to the concept of a backup flight system. There are others who agree with the SpaceX perspective. From this anti-BFS perspective, it would be far better to spend a fraction of the money needed to develop a backup flight system toward improving the primary (and only) flight system so as to develop better and more reliable behavior by this system.

While this might mean more primary sensors, more inspection into the primary flight system, and greater testing of the primary flight software, the claim is that the end result of ditching the concept of a backup flight system results in a better and cheaper system overall.

3
  • Airline safety works similar. E.g. the Airbus A380 only needs one flight computer to fly, but it has 3 primaries and 2 secondaries. And each of those 5 computers has 2 channels, a command channel and a monitoring channel. So, every flight-relevant decision is actually computed 10 times. The three primaries use a majority voting system. If one of them disagrees, it is kicked out. If now the other two disagree, the secondaries take over. Also, within each computer, the monitoring channel computes the same things as the control channel, but is written by a different team in a different … Aug 28, 2020 at 19:46
  • … language. The primaries and secondaries are based on different hardware, different CPU architecture, different OS, and different languages as well, and developed by different teams. Aug 28, 2020 at 19:47
  • SpaceX have a very different philosophy for a lot of things. E.g. if you compare SLS vs. Starship/Superheavy, NASA and co. spent years, if not decades designing SLS, verifying, re-verifying re-re-verifying every single aspect of it, and now they have finally managed to build one. In one tenth of the time, SpaceX has built, blown up, analyzed, evolved, built again, blown up again, etc. 5 Starships. And they will probably blow up a whole lot more of them. With F9, they benefit from something no other company has: historical data from the vehicle. B1049 has now flown 6 times. Aug 28, 2020 at 19:53
0

It depends on the situation.

Take this example, streaming video. When there is ample bandwidth and CPU available then higher quality video can be encoded. When there is less resources then less quality video can be encoded. Now, is this a change in algorithm, maybe, or maybe it's a change in parameters for a Encode() method.

It does represent a behavioral difference, altered by the environment the software runs in.

Let's assume it's a change in algorithm. It might be just an additional step after the encoding step, say a compression step, or it might actually use a different encoder a different video format, one where sound is encoded as MP3 and not FLAC.

In this case the additional code, the duplicate approach, might allow over 1 million more people to watch, generating a revenue stream of 8 million dollars with maintenance costs of 2 million.

With 6 million profit, now it's worth it.

Another example, and this is used in real time systems for redundancy, is each similar algorithm runs at the same time and produces different answers, then the best solution is derived for the current situation is then used. This is a good way to deal with fault tolerance. If 3 of the 4 algorithms are within 0.01% margin of error then there is consensus and the action should be taken. Think safety systems of nuclear power plants.

So the idea of using similar but different algorithms under different circumstances should absolutely be considered; if it makes sense, and by that we need to consider the side effects that have been mentioned; cost, maintenance, testing, and benefits.

3
  • 3
    While the examples are nice, I don't think it addresses the actual question - namely, does the choice of algorithm depend on the size of the input? In your encoding example, would your program select mp3 coding for an hour-long concert but FLAC for a 3 minute song? Will the results be the same (to the untrained ear, probably, but to an audiophile, probably not)?
    – mmathis
    Aug 27, 2020 at 17:58
  • I guess we interpreted the question differently based on our perspectives. You may have taken input to mean data parameters, while I took input to also include the environment (the compute and network resources) that the system needs to operate within; which from my perspective is just as important as data parameters. In the example anything can happen, as it is only an example.
    – null
    Aug 27, 2020 at 19:37
  • I think this answer is indirectly valid, the example chosen may not exactly fit, but it's the same case that choosing or not to compress data depending on the size
    – Kaddath
    Aug 28, 2020 at 7:49
0

Many times you’ll have a simple algorithm that is fast for small n, But not as n grows, and another algorithm that is more complex and faster for large n. And for small n, the simple algorithm may be faster.

When would you write a hybrid algorithm that picks a simple or a complex algorithm depending on size?

One case where you definitely do it is when the complex algorithm has problems with small n. Are you sure that your favourite Quicksort implementation works with n=0 or n=1? So you handle small sizes separately.

Otherwise you ask yourself: Does anyone care? If I sort 1,000 arrays of size 1, and the complex algorithm is needlessly slow, it still takes no measurable time. But there may be problems that you need to solve gazillions of times for small n, and it makes a difference. And if you build a framework or library, a million apps could use the faster code, so it adds up. So in a situation where someone is willing to pay money for handling small n faster, that’s where you implement a hybrid strategy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.