两种strStr()实现的效率差异原因探究

Context #

I was working on LeetCode's strStr() problem, which asks for the following:

Implement the strStr() function. Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

My initial implementation passed all test cases but took 440ms to run:

int strStr(char* haystack, char* needle) { 
    char * hay = haystack; 
    char * haytmp ; 
    char * nd = needle; 
    if(!*nd) return 0; 
    while(*hay){ 
        haytmp = hay; 
        while(*haytmp==*nd && *haytmp && *nd){ 
            haytmp++; 
            nd++; 
        } 
        if(*nd){ 
            hay++; 
            nd = needle; 
        } else{ 
            return strlen(haystack) - strlen(hay); 
        } 
    } 
    return -1; 
}

I found an alternative implementation that only took 4ms—100x faster than mine:

int strStr(char* haystack, char* needle) { 
    char *hay = haystack; 
    char * nd = needle; 
    char * haytmp = hay; 
    if(!*needle) return 0; 
    while(*hay){ 
        if(*haytmp==*nd){ 
            haytmp++; 
            nd++; 
            if(*nd=='\0') return strlen(haystack)-strlen(hay); 
            if(*haytmp=='\0') return -1; 
        }else{ 
            hay++; 
            haytmp = hay; 
            nd=needle; 
        } 
    } 
    return -1; 
}

I notice my version uses an extra nested while loop, but I believe both have the same theoretical time complexity. Why is there such a huge gap in actual runtime efficiency?

Breakdown of the Performance Difference #

Great observation—you’re right that both are naive string matching implementations with a worst-case O(n*m) time complexity (where n = length of haystack, m = length of needle). The massive runtime gap comes down to how the code interacts with CPU hardware optimizations, branch prediction, and loop structure, not just theoretical complexity.

Let’s break down the key factors:

1. Branch Predictability

   • Your nested loop structure creates more complex branching logic. After the inner match loop exits, you have to check if *nd is non-null to decide whether to reset pointers. For cases with lots of partial matches (e.g., searching for "AAAAA" in a haystack of "AAAAAAAAAAAA"), this unpredictable branching confuses the CPU’s branch predictor. When the predictor guesses wrong, it causes pipeline stalls—wasting cycles while the CPU corrects itself.
   • The faster implementation uses a linear flow with a single outer loop and an if check inside. It incrementally checks matches and exits early, which is far more predictable for the branch predictor. This leads to far fewer stalls and smoother execution.

2. Early Termination

   • The faster code includes two critical early exit checks during the matching process:
     • As soon as *nd hits the null terminator (meaning the full needle is matched), it returns immediately—no extra loop iterations needed.
     • If haytmp hits the end of the haystack mid-match, it returns -1 right away instead of continuing to loop.
   • Your code only checks these conditions after the inner loop finishes, which means it may do unnecessary pointer increments or checks before exiting.

3. Loop Overhead & Cache Locality

   • While both implementations reset pointers after a failed match, the faster code’s linear structure lets the CPU optimize memory access better. The predictable access pattern allows the CPU to prefetch parts of the haystack and needle into L1/L2 cache, reducing slow memory lookups.
   • Your nested loop’s back-and-forth flow can disrupt cache prefetching, leading to more time waiting for data from main memory.

4. Minimal Iteration Overhead

   • The faster implementation avoids the extra inner loop’s setup and teardown costs. Every loop iteration has a small overhead, and removing that nested loop cuts down on repeated operations like pointer initialization and condition checks.

The takeaway here is that theoretical time complexity doesn’t always tell the whole story—practical performance depends heavily on how well your code aligns with the CPU’s capabilities. Small tweaks to loop structure and branching can lead to massive runtime gains, especially in tight, repeated operations like string matching.

内容的提问来源于stack exchange，提问作者shanshan wang