(Paper:Bansal S, Aiken A, Automatic generation of peephole superoptimizers)
This is the GRAIL. Infinity. The platonic ideal of optimization. Eu-optimization. One true optimization.
What we usually call optimization is nothing but improvement. Superoptimization is the real deal.
It's finding the one true optimal canonical fastest sequence of instructions to accomplish a task.
How could you tell if two instruction sequences are the same?
Q: How could you tell if two code sequences produce the same result? I see the phrase "Boolean tests"?
A: the entire state of the machine is represented as bits. Everything. Stack, memory, registers, stack counters, program counter, everything.
Paper: 1996 Lipasti S, Wilkinson C, Shen J, Value locality and Load Value Prediction)
N-way associative: each memory piece can only have N places to go in cache fully associative: each memory piece can be anywhere in the cache Tradeoff: more assocative = more search time looking for data, but also less likely to miss.
Extra, slightly slower cache to store most recently evicted item.