3 ms·
How can this paper be taken seriously when the paper doesn't even show the compilation flags?
by halayli 6y ago
How can this paper be taken seriously when the paper doesn't even show the compilation flags?
- coldtea 6y agoPerhaps because the paper is not about the specifics of the incident (which is menial work to figure out, left as an exercize to the header) but the fact that it can happen and a general explanation of the circumstances?
- flohofwoe 6y agoOnce you go accidentally quadratic, any clever combination of optimization flags or compiler magic becomes quite irrelevant though.
- josalhor 6y agoTo be fair, certain compilation flags can change the time complexity of some algorithms if the mistake is trivial enough to figure out.
- Lvl999Noob 6y agoReally? Can you give some examples? I know compilers are amazing but this seems too much.
- mehrdadn 6y agoAt least GCC was (and by now Clang and probably others are) known for occasionally optimizing out certain uses of functions like strlen(), which can change the time complexity in some trivial cases. For instance, if you consider strcmp(x, y, strlen(y)) where x is of fixed length, then the whole function would be constant-time if strlen(y) is optimized out, whereas it would take linear time (linear in strlen(y)) otherwise. GCC et al. can optimize out strlen() in some such cases. In practice you wouldn't want to rely on this, both because compilers aren't anywhere near smart enough to figure out complicated cases and also because these wouldn't happen in debug mode either, but it's not impossible for time complexity to change through optimization.
- maple3142 6y agoSummation from 1 to n: https://godbolt.org/z/673hTr https://godbolt.org/z/673hTr clang seems to optimize it to (n-1)(n-2)/2+2n-1, which is O(1).
- mehrdadn 6y agoEven more trivial: sum from 1 to n, then never use the result. It should get optimized out entirely!