News for hackers. Stuff that matters.
Re:Will it optimize? by viraptor on Friday July 23, 2010 @12:50PM (#1541694)
Question number 2 really surprised me. What if the layout of memory is:

    (s)(s+1)(s+2)...(result)
If `s` has no null bytes until `result`, then `strlen(s)` will terminate on `result`. However, if you change `result` while iterating over `s`, then `result` will be not null and the `strlen()` result will change. Or is there some rule in C standard that says local variables are not in the same memory range as external pointers?
Re:Will it optimize? by ramchip on Friday July 23, 2010 @01:25PM (#1541787)
Attempting to read s[i] when i is outside the bounds of the array is undefined behaviour, so the compiler is free to ignore this case. See example at http://en.wikipedia.org/wiki/Undefined_behavior#Examples_in_...

     Certain pointer operations may result in undefined behavior:
    int main()
    {
      int arr[4] = {0, 1, 2, 3};
      int * p = arr + 5; // undefined behavior
    }
In short, you can't assume that result will be placed after the array. What if result is optimized to a register? It actually sounds quite likely to me given the tight loop.
Re:Will it optimize? by afhof on Friday July 23, 2010 @03:05PM (#1542105)
With C comes the pedantry

    int main(int argc, char ** argv)
    {
      int arr[4] = {0, 1, 2, 3};
      int * p = arr + 5; // valid 
      *p; // undefined behavior
      return 0;
    }
Re:Will it optimize? by mian2zi3 on Friday July 23, 2010 @03:51PM (#1542225)
If you're going to be pedantic, it is best to be right. I don't have a copy of the C standard here, but I do have a copy of the C++ standard. From 5.7 Additive Operators (discussing an expression of the form P+N, where P has pointer type and N has integral type):

"If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined."

That is, if either P or P+N don't point to the same array object, or one past the end of the array object, the result is undefined. Thus,

  int arr[4] = {0, 1, 2, 3};
  ... arr + 4 ... // OK, points to one past the end of the array object
  ... arr + 5 ... // undefined
I'm sure the C standard is the same.
Re:Will it optimize? by nitrogen on Saturday July 24, 2010 @01:42AM (#1543180)
This is one instance where C++ and C are, indeed, the same. However, the languages do have their differences, so I would caution those developers who don't tend to read standards not to assume that C and C++ will behave identically when given valid C code. Obviously, having referenced the C++ standard yourself, you are aware of such caveats.

6.5.6.8 from ISO/IEC 9899:201x draft of March 1, 2009:

...If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined....

Re:Will it optimize? by notaddicted on Friday July 23, 2010 @01:24PM (#1541780)
Since "result" is on the stack it will only be allocated at the time of the function call. Also note that the stack grows downwards in memory. To get the memory layout you've shown you'd have to be summing up the bytes in the unallocated memory between the heap and the top of the stack. Probably this is explained somehow in the standard but I don't personally know.
Re:Will it optimize? by ramchip on Saturday July 24, 2010 @12:47AM (#1543119)
"result" is not necessarily on the stack, and stack growth direction is implementation-specific: http://stackoverflow.com/questions/664744/what-is-the-direct...
Re:Will it optimize? by InclinedPlane on Friday July 23, 2010 @02:56PM (#1542072)
If you've managed to embed an integer into your char array and you are using that integer as an accumulator, you're probably "doing it wrong", very wrong. More to the point, you've got bigger problems than gcc's optimization specifics.

As for this particular example, result is allocated on the stack and is guaranteed to not lie within s, so the gcc optimization is perfectly safe.

Re:Will it optimize? by viraptor on Friday July 23, 2010 @03:54PM (#1542236)
I'm not saying this is useful for anything - I'm just asking about correctness of such optimisation. You can set the pointer to any address, which includes future stack. Also, nothing can 'lie within a pointer' really... - it might be inside an array.

It might seem silly in this example, but as soon as I change the program to a very similar one:

    void sum2(const unsigned char *s, unsigned char *result) {
       *result = 0;
       for (size_t i=0; i < strlen(s); i++) {
          *result += s[i];
       }
    }
It cannot be optimised in the same way anymore (gcc won't) because you can't guarantee memory areas pointed at by arguments don't overlap.
Re:Will it optimize? by yuvi on Saturday July 24, 2010 @12:46AM (#1543117)
> You can set the pointer to any address, which includes future stack.

This is wrong. Attempting to use random pointers to outside of what your compiler and malloc allocated is undefined.

And indeed, aliasing issues like in your example will prevent gcc from optimizing out excess strlen; it can only do so if it can prove that both global memory and the buffer passed to strlen have not been modified. Local variables and return values cannot alias anything, and part of the guarantee of pure functions like strlen is that they have no side effects.