[Python-Dev] talking about performance...

[Tim Peters]

[posted & mailed]

[Fredrik Lundh]
> how about this one:
>
>     if (dir > 0) {
>         char *p, *e;
>         if (n == 0 && i <= last)
>             return (long)i;
>         e = s + last - n + 1;
>         for (;;) {
>             p = memchr(s, sub[0], e - s);
>             if (p == NULL)
>                 break;
>             if (n == 1 || memcmp(p, sub, n) == 0)
>                 return (long) (p - s);
>             s = p + 1;
>         }
>     }
>
> new record time: 1.6 seconds (down from 2.2)

I expect that whether this is faster or slower depends on both the compiler
you're using and the exact strings you're using to time it.

In any case, it appears to be incorrect:  p & s both change inside the
infinite loop, and the innermost return computes their difference.  Surely
it should be returning the difference between p and the value s had *before*
the loop was entered.  If this passed your tests, then, it suggests you had
no "false hits" (i.e., that the inner loop returned on its first iteration,
else the return value would have been wrong), which are probably the cases
in which using memchr rather than the current code is least likely to slow
things down.

It's bad that the original code never bothered to document what it's
supposed to return, but that's no excuse to return probabilistically-correct
gibberish <wink>.