3 ms·
on a non-optimizing compiler you are hitting the string every time in the loop because of the strlen In practice, what assumptions one should make here about
by nkurz 16y ago
on a non-optimizing compiler you are hitting the string every time in the loop because of the strlen
In practice, what assumptions one should make here about optimizing compilers?
It seems like it would take a lot of compiler intelligence to figure out that even though we are modifying the string in place, we are never terminating the string, and thus strlen() remains constant. Thus my instinct would be to never use it in a loop like this.
But maybe current compilers are actually this smart? I just compiled with gcc -O3 and looked at the result with objump -S, but I'm not familiar enough with the assembly to figure out how it's handling things here.
By contrast, my instinct was to do this with in a single pass with two incrementing pointers. I'm not sure if the code is clearer (http://gist.github.com/416170 http://gist.github.com/416170), but at least the assembly turns out simple enough to read!
- jacquesm 16y ago> In practice, what assumptions one should make here about optimizing compilers? > It seems like it would take a lot of compiler intelligence to figure out that even though we are modifying the string in place, we are never terminating the string, and thus strlen() remains constant. Thus my instinct would be to never use it in a loop like this. You're completely right, I just tried it on several gcc settings and it is O(n^2) every time. I thought the 'n' is invariant across the execution of the loop but it might be changed because we're modifying the string and the compiler realizes that and re-runs strlen every time. > By contrast, my instinct was to do this with in a single pass with two incrementing pointers. I'm not sure if the code is clearer (http://gist.github.com/416170 http://gist.github.com/416170), but at least the assembly turns out simple enough to read! That's pretty much what I sent in as a solution, and I figure there will be a lot of them isomorphic with yours.