3 ms·
It should be possible to create constant-time C code, if the code avoids branching (if, case, goto), and all loops have a constant number of operations. Expres
by nine_k 6y ago
It should be possible to create constant-time C code, if the code avoids branching (if, case, goto), and all loops have a constant number of operations.
Expressing most algorithms this way is not impossible, but does nor feel natural for many.
- lmm 6y ago> It should be possible to create constant-time C code, if the code avoids branching (if, case, goto), and all loops have a constant number of operations. It fundamentally isn't, because there is no way (in standard C) to prevent the compiler from introducing performance differences. Even if you avoid control flow constructions, what if the compiler e.g. generates a separate codepath for when one particular variable is 0 (perhaps as part of arithmetic optimizations)? There's just no (standard) way to stop that happening, no matter how cleverly you write your code.
- nine_k 6y agoSad! It's as if we might need some kind of simple portable assembly, one which straightforwardly translates simple constructs and formulas to the target machine code. Like, well, C used to be in 1975. Jokes aside, I wonder if some kind of -Ox option could be standardized to switch off all optimizations, like -O0, and also guarantee no code rewriting for whatever other purposes. Hand-crafting constant-time algorithms in assembly is even more error-prone.
- lmm 6y agoIn fairness assembly isn't what it was in 1975 either - with superscalar architectures and the dominance of caches these days even assembly is not as constant-time as you might expect.