5 ms·

It's not unreasonable to assume the compiler will optimize it to a single call. Though I guess people who are capable of making that judgement won't need to lo

It's not unreasonable to assume the compiler will optimize it to a single call. Though I guess people who are capable of making that judgement won't need to look this idiom up on the internet.

sokoloff 5y ago
Is there something in the C spec that allows optimizing to a single strlen call?
- foxfluff 5y ago
  Absolutely. The gist of it: "In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object)."
  - sokoloff 5y ago
    As I understand it, the strlen implementation ("calling a function") is typically going to come from another object file (at link time), so it’s not clear that when compiling this file that “calling strlen has no side effects” is information available to the compiler.
    - foxfluff 5y ago
      strlen is a standard function (in a hosted environment). So it must do exactly what the standard says it does, and the standard doesn't say it has side-effects. The compiler could very well use a built-in implementation of strlen, or even omit the call entirely if it had another way to deduce its would-be return value. Object files are an implementation detail not known by the C standard.
      - sokoloff 5y ago
        > the standard doesn't say it has side-effects The relevant question is "does the standard say that it does not have side-effects?" (is a pure function). @skissane's sibling comment to yours provides the explanation of how the compiler can deduce that it's a pure function.
        foxfluff 5y ago
        The compiler can deduce that it is a pure function using the same logic by which it can deduce it is free to replace the call with a builtin: the function is defined in the standard. Everything @skissane said is implementation details and not particularly relevant (the compiler can do the optimization without the attribute they mentioned). I think the standard would fall apart if you read it under the assumption that anything not explicitly forbidden can happen. Instead, you should read and find out what the side effects are (and same for undefined behavior, unspecified behavior, implementation defined behavior, etcetra). "Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment." (There are more details if you care to dig in) Of course nothing stops you or me from making extensions to the standard, but analysing things from the perspective that some implementation might extend strlen to have visible side effects goes too far into whataboutism for my taste, unless there are real world examples to make it a relevant point.
    - skissane 5y ago
      > so it’s not clear that when compiling this file that “calling strlen has no side effects” is information available to the compiler. It is because strlen is a #define to __builtin_strlen And __builtin_strlen is declared (internally) as __attribute__((pure)). The fact that it is a compiler builtin isn't that important; the compiler will perform the exact same loop optimisation on a non-builtin function if you declare it as __attribute__((pure)). So, in practice, it is not the object file which tells the compiler it can do this, it is the function declaration in the header file. __attribute__((pure)) is of course a GCC extension, not standard C or C++ – but Clang supports it and so do many proprietary compilers, MSVC appears to be the main exception. This isn't part of the standard but is a compatible extension. C++11 standardises attributes (with a different syntax) and C202x is going to do the same. Neither is yet including "pure" among the standardised attributes but a future standard revision could always add it. There is a proposal to add pure to the C++ standard [0]. If it successfully makes it into C++, don't be surprised if it makes it into the C standard as well at some point. It is the kind of C++ feature which the C standard is likely to borrow, and is already widely implemented (just under different syntax) anyway. [0] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0078r0.pdf http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p007...
      - Someone 5y ago
        Nitpick: I don’t think the compiler needs that __attribute__((pure)) annotation to move strlen around. __builtin_strlen is a reserved name, so if the compiler sees it, it may assume it came from an #include <string.h> and that it does what the standard says strlen does. That is what allows compilers to do much more than move that function call out of the loop. Because they know what it does (or rather: what the programmer promises it will do, once the program get linked) they can inline its code or even, if the length of the string is known up front, replace the function call by a constant.
        foxfluff 5y ago
        It doesn't even need to see __builtin_strlen (try modify your string.h or use musl, which has neither the attribute nor __builtin_strlen). It just needs to see strlen in a hosted environment (with the right header included?). If you want gcc to treat it otherwise, you also need -fno-builtin-strlen.
- ratww 5y ago
  Don't know about the C spec, but this is a very popular optimisation. It's called Loop-invariant code motion.
Stratoscope 5y ago
We don't write code only for compilers, but for human readers as well. Why write code that makes a smart human wonder "Is that going to be quadratic? I'd better make sure the compiler optimizes it out!"
- foxfluff 5y ago
  Smart human for you, someone obsessed with micro-optimization but lacking knowledge of compiler optimizations for me.. Writing it for human readers can be used to argue for the original implementation if you think of for(i=0;i<expr;i++) as the C idiom for "iterate expr times" and here you want expr to equal the length of the string, which is what the (obviously pure) function yields. No unnecessary variables and assignments -- no clutter. It perfectly describes the intent.
  - Stratoscope 5y ago
    This conversation started when another developer was alarmed that the strlen() call in the for loop looked like it could be quadratic. I think we owe that dev the respect to not dismiss their concern as being "obsessed with micro-optimization but lacking knowledge of compiler optimizations". I try to write code that is as plain and simple as possible, and make it obvious what it does and that it has no gotchas. I want my code to be understandable both for new developers, and for my future self, who will surely be less smart than I think I am today. Here is the original code, with the loop body elided: for( int i = 0; i < strlen(s); i++ ) { } It is trivial to rewrite this as: for( int i = 0, n = strlen(s); i < n; i++ ) { } This is a very common idiom, and now it is perfectly clear what the code actually does. Obviously, it only calls strlen() once. Of course, as I pointed out in another comment, if you're writing a loop that iterates over a C string, you never have to call strlen() at all! You can just use the canonical C string loop: for( int i = 0; s[i] != '\0'; i++ ) { } Or if you like brevity (which I like too): for( int i = 0; s[i]; i++ ) { }
    - deleted 5y ago
      [deleted]
andrepd 5y ago
But still, it will be two passes through the string when it could be only one.
agent327 5y ago
It's still asking for trouble though. Look at this minor variation: https://godbolt.org/z/ncjEejsxe https://godbolt.org/z/ncjEejsxe It shows what happens if you take away the compilers' ability to reason about 's': it could be a global variable, and 'foo' could be modifying it, so now the compiler has to call strlen on every iteration. So even though 'strlen' gets optimized out in the original version, it's quite a maintenance hazard since any minor change could inadvertently change the complexity from linear to quadratic. It also doesn't get optimized in debug builds, making those far slower than necessary.

It's not unreasonable to assume the compiler will optimize it to a single call. Though I guess people who are capable of making that judgement won't need to look this idiom up on the internet.

sokoloff 5y ago

Is there something in the C spec that allows optimizing to a single strlen call?

foxfluff 5y ago
Absolutely. The gist of it: "In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object)."
- sokoloff 5y ago
  As I understand it, the strlen implementation ("calling a function") is typically going to come from another object file (at link time), so it’s not clear that when compiling this file that “calling strlen has no side effects” is information available to the compiler.
  - foxfluff 5y ago
    strlen is a standard function (in a hosted environment). So it must do exactly what the standard says it does, and the standard doesn't say it has side-effects. The compiler could very well use a built-in implementation of strlen, or even omit the call entirely if it had another way to deduce its would-be return value. Object files are an implementation detail not known by the C standard.
    - sokoloff 5y ago
      > the standard doesn't say it has side-effects The relevant question is "does the standard say that it does not have side-effects?" (is a pure function). @skissane's sibling comment to yours provides the explanation of how the compiler can deduce that it's a pure function.
      - foxfluff 5y ago
        The compiler can deduce that it is a pure function using the same logic by which it can deduce it is free to replace the call with a builtin: the function is defined in the standard. Everything @skissane said is implementation details and not particularly relevant (the compiler can do the optimization without the attribute they mentioned). I think the standard would fall apart if you read it under the assumption that anything not explicitly forbidden can happen. Instead, you should read and find out what the side effects are (and same for undefined behavior, unspecified behavior, implementation defined behavior, etcetra). "Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment." (There are more details if you care to dig in) Of course nothing stops you or me from making extensions to the standard, but analysing things from the perspective that some implementation might extend strlen to have visible side effects goes too far into whataboutism for my taste, unless there are real world examples to make it a relevant point.
  - skissane 5y ago
    > so it’s not clear that when compiling this file that “calling strlen has no side effects” is information available to the compiler. It is because strlen is a #define to __builtin_strlen And __builtin_strlen is declared (internally) as __attribute__((pure)). The fact that it is a compiler builtin isn't that important; the compiler will perform the exact same loop optimisation on a non-builtin function if you declare it as __attribute__((pure)). So, in practice, it is not the object file which tells the compiler it can do this, it is the function declaration in the header file. __attribute__((pure)) is of course a GCC extension, not standard C or C++ – but Clang supports it and so do many proprietary compilers, MSVC appears to be the main exception. This isn't part of the standard but is a compatible extension. C++11 standardises attributes (with a different syntax) and C202x is going to do the same. Neither is yet including "pure" among the standardised attributes but a future standard revision could always add it. There is a proposal to add pure to the C++ standard [0]. If it successfully makes it into C++, don't be surprised if it makes it into the C standard as well at some point. It is the kind of C++ feature which the C standard is likely to borrow, and is already widely implemented (just under different syntax) anyway. [0] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0078r0.pdf http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p007...
    - Someone 5y ago
      Nitpick: I don’t think the compiler needs that __attribute__((pure)) annotation to move strlen around. __builtin_strlen is a reserved name, so if the compiler sees it, it may assume it came from an #include <string.h> and that it does what the standard says strlen does. That is what allows compilers to do much more than move that function call out of the loop. Because they know what it does (or rather: what the programmer promises it will do, once the program get linked) they can inline its code or even, if the length of the string is known up front, replace the function call by a constant.
      - foxfluff 5y ago
        It doesn't even need to see __builtin_strlen (try modify your string.h or use musl, which has neither the attribute nor __builtin_strlen). It just needs to see strlen in a hosted environment (with the right header included?). If you want gcc to treat it otherwise, you also need -fno-builtin-strlen.
ratww 5y ago
Don't know about the C spec, but this is a very popular optimisation. It's called Loop-invariant code motion.

Stratoscope 5y ago

We don't write code only for compilers, but for human readers as well. Why write code that makes a smart human wonder "Is that going to be quadratic? I'd better make sure the compiler optimizes it out!"

foxfluff 5y ago
Smart human for you, someone obsessed with micro-optimization but lacking knowledge of compiler optimizations for me.. Writing it for human readers can be used to argue for the original implementation if you think of for(i=0;i<expr;i++) as the C idiom for "iterate expr times" and here you want expr to equal the length of the string, which is what the (obviously pure) function yields. No unnecessary variables and assignments -- no clutter. It perfectly describes the intent.
- Stratoscope 5y ago
  This conversation started when another developer was alarmed that the strlen() call in the for loop looked like it could be quadratic. I think we owe that dev the respect to not dismiss their concern as being "obsessed with micro-optimization but lacking knowledge of compiler optimizations". I try to write code that is as plain and simple as possible, and make it obvious what it does and that it has no gotchas. I want my code to be understandable both for new developers, and for my future self, who will surely be less smart than I think I am today. Here is the original code, with the loop body elided: for( int i = 0; i < strlen(s); i++ ) { } It is trivial to rewrite this as: for( int i = 0, n = strlen(s); i < n; i++ ) { } This is a very common idiom, and now it is perfectly clear what the code actually does. Obviously, it only calls strlen() once. Of course, as I pointed out in another comment, if you're writing a loop that iterates over a C string, you never have to call strlen() at all! You can just use the canonical C string loop: for( int i = 0; s[i] != '\0'; i++ ) { } Or if you like brevity (which I like too): for( int i = 0; s[i]; i++ ) { }
  - deleted 5y ago
    [deleted]

andrepd 5y ago

But still, it will be two passes through the string when it could be only one.

agent327 5y ago

It's still asking for trouble though. Look at this minor variation: https://godbolt.org/z/ncjEejsxe https://godbolt.org/z/ncjEejsxe It shows what happens if you take away the compilers' ability to reason about 's': it could be a global variable, and 'foo' could be modifying it, so now the compiler has to call strlen on every iteration. So even though 'strlen' gets optimized out in the original version, it's quite a maintenance hazard since any minor change could inadvertently change the complexity from linear to quadratic. It also doesn't get optimized in debug builds, making those far slower than necessary.