# Choosing algorithms and/or data structures at runtime based on input characteristics

I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in Self-Optimization: how to write programs that are able to choose the best algorithm/data structure in response to changes in the input profile. In the lower end, simple heuristics are used to apply specific algorithms in special cases, eg. Tim/Quick/MergeSort using Insertion Sort (which is $$O(n^2)$$) when the partition size is below a certain threshold. On the other extreme we have JIT compilers that optimize/deoptimize the code at runtime according to certain metrics.

However, I haven't found so far any examples of "high-level" decisions, like automatically choosing between two distinct implementations of an algorithm or a data structure at runtime. For example, think about a AdaptiveList object with the usual operations (add,remove...) and a array-backed storage. If the program keeps inserting elements in the middle of the list (which requires moving a lot of data to free space for the new element), the AdaptiveList may choose to move the data out of the array into a linked list. If the usage pattern changes again, the AdaptiveList may decide to go back to the array storage.

The closest thing I've been able to find (other than JIT compilers, of course) are projects like ATLAS and FFTW where the code generation/algorithm selection is done a priori and never revisited. Maybe I'm the first one to entertain such fantasies, but I doubt it. Are you aware of other papers/projects that have investigated this idea?

Thanks for reading!

• Query optimizers for relational databases do something like this all the time. – Derek Elkins Jun 10 at 0:40
• One example may be MongoDB, which, as far as I have heard, dynamically creates indexes when it considers them useful. Myself, I have done this on a smaller scale for my PH-Tree project, a multi-dimensional index. During index creation, it chooses between 3 different implementations, depending on the dimensionality. Internally it has some (in-hindsight-not-to-be-proud-of-)micro-optimisations: It uses linear search instead of binary search if an array has less than 10 elements. It also uses for-loops instead of System.arrayCopy if it copies less than 7 elements. – TilmannZ Jun 10 at 13:02
• I just remembered liboil (Library for Optimized Inner Loops) for C/C++. If I remember correctly, when linked, it runs are very short benchmark at startup to determine which types of loops (for-loops etc) run fastest on the current CPU. Actual loops in your program then use the fastest implementation when a (accordingly marked) loop is executed. Someone told me this is now standard in GCC, but I could find no reference to support this. This is a bit like JIT. – TilmannZ Jun 10 at 13:07
• There is also a large research body on adaptive databases, which may be interesting. – TilmannZ Jun 10 at 13:13