갑자기 궁금해져서 C strstr()이 어떤 알고리즘으로 구현되어 있나 조금 찾아봤는데, 난 순진하게 보이어-무어나 KMP를 썼겠거니 생각했다만, 여러 의미에서 아니다. 표준 라이브러리 함수들은 앞서 알려진 어떤 매칭 알고리즘과 비교해도 더 빠른데, 여러 strstr 구현을 직접 본 사람(몇 년 간 문자열 탐색 구현에 대해 광범위하게 작업했다고 한다)에 의하면 놀랍게도 나이브 탐색(...)으로 구현되어 있다고 한다. BM, KMP 등은 비교 수를 최소화 하는데 최적인 알고리즘이다. 그런데, 현대 프로세서에서는 그건 병목지점이 아니라고 한다. 2003년 이래 모든 x86에서 SSE2가 지원되었는데 glibc strlen()을 디스어셈블 해 보면 한번에 16바이트 null terminator를 찾는 SSE2 PCMPEQB, MOVMASK 를 볼 수 있고, 이것은 매우 효율적이어서 명백히 루프를 능가 한다고 한다. 아무튼 결론은 고도로 최적화된 표준 라이브러리는 매칭 알고리즘 같은 거 없이 그냥 찾는다. 그게 더 빠르다. C 표준 라이브러리가 여전히 최고인 이유를 다시 한번 인식하게 된다.
그렇지 않습니다... 물론 하드웨어 가속 쓰는거 중요하지만요, 직접 보시죠: git.musl-libc.org/cgit/musl/tree…. Two-way 라는 알고리즘을 쓰는 것이 보통입니다.
#include <string.h> #include <stdint.h> static char *twobyte_strstr(const unsigned char *h, const unsigned char *n) { uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1]; for (h++; *h && hw != nw; hw = hw<<8 | *++h); return *h ? (char *)h-1 : 0; } static char *threebyte_strstr(const unsigned char *h, const unsigned char *n) { uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8; uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8; for (h+=2; *h && hw != nw; hw = (hw|*++h)<<8); return *h ? (char *)h-2 : 0; } static char *fourbyte_strstr(const unsigned char *h, const unsigned char *n) { uint32_t nw = (uint32_t)n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3]; uint32_t hw = (uint32_t)h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3]; for (h+=3; *h && hw != nw; hw = hw<<8 | *++h); return *h ? (char *)h-3 : 0; } #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define BITOP(a,b,op) \ ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) static char *twoway_strstr(const unsigned char *h, const unsigned char *n) { const unsigned char *z; size_t l, ip, jp, k, p, ms, p0, mem, mem0; size_t byteset[32 / sizeof(size_t)] = { 0 }; size_t shift[256]; /* Computing length of needle and fill shift table */ for (l=0; n[l] && h[l]; l++) BITOP(byteset, n[l], |=), shift[n[l]] = l+1; if (n[l]) return 0; /* hit the end of h */ /* Compute maximal suffix */ ip = -1; jp = 0; k = p = 1; while (jp+k<l) { if (n[ip+k] == n[jp+k]) { if (k == p) { jp += p; k = 1; } else k++; } else if (n[ip+k] > n[jp+k]) { jp += k; k = 1; p = jp - ip; } else { ip = jp++; k = p = 1; } } ms = ip; p0 = p; /* And with the opposite comparison */ ip = -1; jp = 0; k = p = 1; while (jp+k<l) { if (n[ip+k] == n[jp+k]) { if (k == p) { jp += p; k = 1; } else k++; } else if (n[ip+k] < n[jp+k]) { jp += k; k = 1; p = jp - ip; } else { ip = jp++; k = p = 1; } } if (ip+1 > ms+1) ms = ip; else p = p0; /* Periodic needle? */ if (memcmp(n, n+p, ms+1)) { mem0 = 0; p = MAX(ms, l-ms-1) + 1; } else mem0 = l-p; mem = 0; /* Initialize incremental end-of-haystack pointer */ z = h; /* Search loop */ for (;;) { /* Update incremental end-of-haystack pointer */ if (z-h < l) { /* Fast estimate for MAX(l,63) */ size_t grow = l | 63; const unsigned char *z2 = memchr(z, 0, grow); if (z2) { z = z2; if (z-h < l) return 0; } else z += grow; } /* Check last byte first; advance by shift on mismatch */ if (BITOP(byteset, h[l-1], &)) { k = l-shift[h[l-1]]; if (k) { if (k < mem) k = mem; h += k; mem = 0; continue; } } else { h += l; mem = 0; continue; } /* Compare right half */ for (k=MAX(ms+1,mem); n[k] && n[k] == h[k]; k++); if (n[k]) { h += k-ms; mem = 0; continue; } /* Compare left half */ for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--); if (k <= mem) return (char *)h; h += p; mem = mem0; } } char *strstr(const char *h, const char *n) { /* Return immediately on empty needle */ if (!n[0]) return (char *)h; /* Use faster algorithms for short needles */ h = strchr(h, *n); if (!h || !n[1]) return (char *)h; if (!h[1]) return 0; if (!n[2]) return twobyte_strstr((void *)h, (void *)n); if (!h[2]) return 0; if (!n[3]) return threebyte_strstr((void *)h, (void *)n); if (!h[3]) return 0; if (!n[4]) return fourbyte_strstr((void *)h, (void *)n); return twoway_strstr((void *)h, (void *)n); }