4 ms·
Generally, you cannot scan the loop body to find redefinitions of `chr`. This is known as the halting problem. Consider, for example, a redefinition of `chr` i
by lysium 16y ago
Generally, you cannot scan the loop body to find redefinitions of `chr`. This is known as the halting problem.
Consider, for example, a redefinition of `chr` in an `if`-clause: you would have to actually run the program to know if the `if`-clause is taken or not.
Further, in Python, the redefinition of `chr` does not even have to be in the form of `chr = ...`, but could be an assignment into a global hash, maybe even using a variable as an index.
- derefr 16y agoI'm not suggesting that you have to know specifically that chr is being redefined; to cancel the optimization, you simply have to know that "this loop body is not limited to the subset of operations which are known to not redefine chr" (i.e. basically the same sort of analysis Google NaCl does.) This leaves a large number of optimizations on the table (i.e. any loop body that modifies a global hash will cancel the optimization), but is better than no optimization at all.
- lysium 16y agoI wonder how large (or small) that restricted subset is and how easily it is 'violated', turning off the optimization although it would have been possible (For example, the global hash could be referred to via a local variable which might carry the result of a function call). Do you have any insights on that? Until then, using a 'dirty flag' on the `chr` definition that turns off the optimization at run time as mentioned elsewhere in this thread, seems to be the appropriate approach for me.
- deleted 16y ago[deleted]
- edanm 16y agoGood points. What about multi-threading? Isn't it possible that another thread entirely reassigns "chr" to something different, while the for loop is running? Obviously this would only happen in a pathological program written purely for perpetrating evil on unsuspecting programmers :) But seriously, it's possible, and it's the kind of thing optimizing compilers have to take into consideration.