4 ms·

Obligatory Dan Bernstein presentation: https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf

Obligatory Dan Bernstein presentation: https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf (note: portrait slides!)

sandermvanvliet 7y ago
Thanks for sharing this
MaxBarraclough 7y ago
> Wikipedia: “An optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program.” > So the algorithm designer (viewed as a machine) is an optimizing compiler? > Nonsense. Compiler designers have narrower focus. Example: “A compiler will not change an implementation of bubble sort to use mergesort.” — Why not? (No answer is given.) An optimising compiler is permitted to replace your bubble-sort by a merge-sort, provided apparent program-behaviour is unchanged. The only reason real compilers aren't likely to do this, is that the transformation is too sophisticated/too specific, for current compiler technology. > compiler designers take responsibility only for “machine-specific optimization”. Outside this bailiwick they freely blame algorithm designers This is wrong. It's wrong in the shallow sense: in a typical modern compiler, most optimisations are performed at the level of an IR, not at the level of the particular target machine language. Common subexpression elimination, for instance. It's also wrong in a deeper sense: compilers may apply optimisations which improve time complexity. That is to say, they may transform the algorithm itself. The target machine has no bearing there. Consider the following unoptimised loop: int found = 0; for (size_t i = 0; i != n; ++i) { if (arr[i]) { found = 1; // break; } } An optimising compiler may be capable of essentially uncommenting the commented-out 'break'. This changes the time-complexity of the scan in an obvious way. This optimisation could even be applied by a source-to-source optimiser, with no awareness of the the target machine. (We can nitpick about possible tradeoffs regarding branch-prediction when adding the 'break', but I think my point is clear.)

Obligatory Dan Bernstein presentation: https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf (note: portrait slides!)

sandermvanvliet 7y ago

Thanks for sharing this

MaxBarraclough 7y ago

> Wikipedia: “An optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program.” > So the algorithm designer (viewed as a machine) is an optimizing compiler? > Nonsense. Compiler designers have narrower focus. Example: “A compiler will not change an implementation of bubble sort to use mergesort.” — Why not? (No answer is given.) An optimising compiler is permitted to replace your bubble-sort by a merge-sort, provided apparent program-behaviour is unchanged. The only reason real compilers aren't likely to do this, is that the transformation is too sophisticated/too specific, for current compiler technology. > compiler designers take responsibility only for “machine-specific optimization”. Outside this bailiwick they freely blame algorithm designers This is wrong. It's wrong in the shallow sense: in a typical modern compiler, most optimisations are performed at the level of an IR, not at the level of the particular target machine language. Common subexpression elimination, for instance. It's also wrong in a deeper sense: compilers may apply optimisations which improve time complexity. That is to say, they may transform the algorithm itself. The target machine has no bearing there. Consider the following unoptimised loop: int found = 0; for (size_t i = 0; i != n; ++i) { if (arr[i]) { found = 1; // break; } } An optimising compiler may be capable of essentially uncommenting the commented-out 'break'. This changes the time-complexity of the scan in an obvious way. This optimisation could even be applied by a source-to-source optimiser, with no awareness of the the target machine. (We can nitpick about possible tradeoffs regarding branch-prediction when adding the 'break', but I think my point is clear.)