switching implementations dynamically according to execution time estimates

Question

I have a function that I can implement in two different ways. Each way has its own advantages, and performance depends on the arguments it will be given. Since each implementation has several short circuits, performance can be dramatically different compared to the other one, so I thought to wrap the two implementations in one that "magically" uses the faster one.

I normally wouldn't care about this kind of optimizations, but the function gets called a lot, and the short circuits are too tasty to not give this trick a try.

However, this is way harder than I thought it would be, and I realized I don't have enough knowledge to do this properly.

What I thought to have is something along the lines of:

var v1Time = v1.getExecTimeEstimate(arg1, arg2);
var v2Time = v2.getExecTimeEstimate(arg1, arg2);
var function = v1Time < v2Time ? v1 : v2;
return function.execute(arg1, arg2);

Where getExecTimeEstimate would return a float/double. This value shouldn't be an actual estimate of the execution time, but just something that allows me to compare it to the other value, relatively, not absolutely.

What I tried is counting the most basic operations and returning that value. For instance if the function would do 30 comparisons, 20 reads (from whatever data structure or memory) and 10 writes, I would return 60. This works, but I can already tell it is very imprecise (not acceptably-imprecise).

Another thing that (cosmetically) worries me, is that I will be inevitably forced to add some information about the performance also in arg1 and arg2's classes.

How would you implement this? Is this a good idea? Are there other approaches? Do you know of any software that makes use of this kind of tricks?

Thank you in advance for your answers, and please forgive my poor english.

Answer 1

The standard approach for, say, sorting a list is to use quicksort for lists greater than a threshold k and insertion sort otherwise. So partitioned lists using quicksort of a certain dimension are not handled using quicksort through and through because insertion sort actually beats quicksort for smaller arrays.

I would recommend you perform Monte Carlo simulations in order to find the "sweet spot" where both methods perform the same for the same input. Then your wrapper method simply checks for the number of items and calls the appropriate method that is more efficient for that input so you're guaranteed to be using the best method at all times.

To give you an example, supposing you perform Monte Carlo simulations and receive the following results:

n       method 1   method 2
10      0.013 s    0.001 s
100     0.130 s    0.130 s
1000    1.130 s    5.245 s
10000   11.30 s    109.313 s

As we can see from this, method 2 outperforms method 1, but only until you hit 100 items. Beyond 100 items, method 1 outperforms method 2.

So your optimization method would look like:

function bestMethod(array) 
    if(array.length < 100)
        method2(array)
    else 
        method1(array)

If you were to then run Monte Carlo simulations on the new method bestMethod, you'd get something similar to the following table:

n       best method  method 1   method 2
10      0.001 s      0.013 s    0.001 s
100     0.130 s      0.130 s    0.130 s
1000    1.130 s      1.130 s    5.245 s
10000   11.30 s      11.30 s    109.3 s

Of course the performance may actually change based on input, so I would encourage you to use input very similar to the type of input you'll be receiving in your program to perform the Monte Carlo simulations, and, should you suspect that the performance varies greatly by input, you should test with multiple inputs as it may have an impact on the threshold value.

The code itself would do no analysis, nor would it need to retain information regarding performance, only a quick check on the number of items or other metrics, so long as it is quick to check.

And in the worst case scenario in which performance wildly varies by input with no clear indication a priori, you're looking at something that might actually be better handled using machine learning algorithms, but I suspect that isn't your case.

Answer 2

This is an interesting idea but largely echoing Neil's answer, I think you need to investigate why one function is faster than the other and vice versa for certain types of inputs, ideally with a profiler in hand.

The idea of trying to make the code generate a time estimate on the fly of how quickly both functions might execute to determine which to use is neat but also quite indicative to me that you would benefit from better understanding why one surpasses the other in certain cases so that you can choose a simpler means of choosing among these two functions if you're going to keep and allow either to be used (like the size of the data to process as with Neil's example of using the list size for introsorting).

Personally according to my own sensibilities, I'd sit down for a while with the function that seems to be faster in more cases and profile and tune that for a good while, developing a greater understanding of the performance characteristics. You might even end up with a function that ends up being faster in all cases after addressing some hotspots. If not, you should at least end up with a superior understanding of why it performs better in certain cases and worse in certain cases than the other. Even if the bulk of the work is very algorithmic in nature, I often find that profiling even heightens my understanding of algorithms and where they're spending the most time and why.

In fact, when I'm developing a new data structure that's going to be used a whole lot in tight loops, I actually like to do "profiling-driven development", like the analogical equivalent of test-driven development, but fused with TDD since I'm profiling the tests I'm writing against the data structures as the data structure itself is being fleshed out. Often so many new ideas for improvements come about through that process, and the data structure and its data representation gets shaped and reshaped by the discoveries along the way until I can call her done and confidently feel like I have this badass data structure now that I can lean on with the combination of the unit test, benchmarks, and all the profiling I did to guide its development. It's the most fun thing in the world to me and I wish I could do it all day instead of working on GUIs and boring stuff like that. Anyway, I digress, but profiling your code might get you a step further.