We describe an automatic procedure for building a fast library
routine from a set of code fragments. These code fragments
solve the same problem (i.e., have identical inputs and outputs),
but we assume that each fragment has been performance-tuned for
different kinds of inputs. Suppose we are given a
sampling of possible inputs, and the execution times of each
algorithm on each sample input. Then, our procedure builds a
single library routine with static rules for quickly selecting a
code fragment. The rules are chosen to minimize overall execution
time on all inputs. We use a supervised learning approach to
classify regions of the input space by algorithm. Our
implementation works essentially by solving a non-linear optimization
problem.
