User:Realazthat/Projects wishlist/LLVM/Strategic optimizations: Difference between revisions
Content added Content deleted
(Created page with "Strategic optimizations are those that change the overall way a function does its duty; ie. it changes the algorithm entirely, changing control flow and complexity, both time and...") |
No edit summary |
||
Line 10: | Line 10: | ||
*** On a random combination, execute the algorithm for tiny inputs, most won't match |
*** On a random combination, execute the algorithm for tiny inputs, most won't match |
||
*** Choose the instructions as a graph of possible paths, make sure not to lose any bits of information that would be necessary for the output |
*** Choose the instructions as a graph of possible paths, make sure not to lose any bits of information that would be necessary for the output |
||
* Use a SMT solver to simulate a [[wp:Machine_that_always_halts|halting turing machine]] (decider) |
** Use a SMT solver to simulate a [[wp:Machine_that_always_halts|halting turing machine]] (decider) |
||
** Assert that there is no input to the decider that has the same output as the function (also translated to SMT for the decider) |
*** Assert that there is no input to the decider that has the same output as the function (also translated to SMT for the decider) |
||
** Ask for a counter example |
*** Ask for a counter example |
||
** Additionally, if complexity can be auto-computed (due to the loops being finite), assert that there is no algorithm with a lower complexity |
*** Additionally, if complexity can be auto-computed (due to the loops being finite), assert that there is no algorithm with a lower complexity |
||
** Additionally, when calculating the complexity, add weights to different instructions to be used as constants, and keep the constants and lower order nomials in the complexity calculation to determine a winning overall algorithm |
*** Additionally, when calculating the complexity, add weights to different instructions to be used as constants, and keep the constants and lower order nomials in the complexity calculation to determine a winning overall algorithm |
||
Revision as of 21:40, 18 October 2010
Strategic optimizations are those that change the overall way a function does its duty; ie. it changes the algorithm entirely, changing control flow and complexity, both time and/or memory.
The only way I know of currently that a strategic optimization can take place is either by:
- Dead code elimination
- wp:Superoptimization
- Combinations of instructions are tested for functional equivalence
- Takes forever
- Better way would be to find a way to iterator over set of all possible equivalent algorithms, in a decidable (subset) language, and test their complexity
- Some other pruning approaches
- On a random combination, execute the algorithm for tiny inputs, most won't match
- Choose the instructions as a graph of possible paths, make sure not to lose any bits of information that would be necessary for the output
- Use a SMT solver to simulate a halting turing machine (decider)
- Assert that there is no input to the decider that has the same output as the function (also translated to SMT for the decider)
- Ask for a counter example
- Additionally, if complexity can be auto-computed (due to the loops being finite), assert that there is no algorithm with a lower complexity
- Additionally, when calculating the complexity, add weights to different instructions to be used as constants, and keep the constants and lower order nomials in the complexity calculation to determine a winning overall algorithm
Other approaches:
- Recognize problems in their complexity class (eg. in P, or in NP), and use reductions to reduce the complexity to the easiest problem