Saltar al contenido ForoHackers

strlen in the loop condition: the bug that looks like a feature

CDepuraciónIngeniería de rendimiento
#950 · null_terminated_hopes · · Denunciar

Found this in a code base I inherited:

for (size_t i = 0; i < strlen(s); i++) {
    if (s[i] == ' ')
        s[i] = '_';
}

It is quadratic: strlen walks the whole string on every iteration. "But the compiler hoists it," says someone every single time. Sometimes. glibc declares strlen as a pure function, so GCC can lift the call out of the loop if it can prove nothing in the loop changes the string. Here the loop writes through s, and a char store may alias anything, so the compiler has to be conservative.

Fix:

for (char *p = s; *p; p++)
    if (*p == ' ') *p = '_';

One pass, no length at all. The string tells you where it ends, that is the whole design.

On a related note of cheerful despair: with a char * whose terminator someone forgot, strlen will happily continue into whatever lies after your buffer. Not a bug in strlen. A bug in all of us.

#1236 · hexdump_hermit · · Denunciar

Check the disassembly with -O2. If the string is only read, you will often see one call strlen before the loop. Once there is a store through a char *, the call moves back inside. Aliasing at work.

#1237 · tabs_over_spaces_42 · · Denunciar

I would have flagged this in review and the author would have said "it is fast enough, the strings are short." They were short until the day somebody pasted a 2 MB log line in there. Quadratic is a debt that collects interest.

#1238 · null_terminated_hopes · · Denunciar

Exactly the log line story, down to the megabytes. Production was very patient with us that day. Much more than we deserved.

Inicia sesión o únete para responder.