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!