메아리 저널

다음 질문을 잘 읽고 답해 주십시오.

1. C에서 널 문자('\0')로 끝나는 문자열의 길이를 알아 내는 함수, strlen을 짜십시오. strlen은 문자열의 시작을 가리키는 char 포인터를 받으며, 길이를 반환해야 합니다. 시작점에서 출발해서 '\0'가 나올 수 없는 경우에는 아무 짓이나 해도 좋습니다. (세그폴트를 내거나 음수를 반환하거나 등등…)
2. 이제 1번에서 답한 코드에서 버그를 최대한 많이 수정하십시오.
3. 이제 2번에서 답한 코드를 최대한 최적화하십시오.

사실 이 문제는 IRC에서 몇몇 채널에 내 본 것을 다듬은 것입니다. 그러니 이미 질문에 답했더라도 한 번 더 보면 유익할 지도 모릅니다. (응?) strlen을 쓰는 것 자체가 잘못된 코드라는 주장에는 약간 동감하지만 그냥 예시로 봐 주시죠.

1번에 대한 답변

가장 쉽게 답할 수 있는 코드는 다음과 같겠지요.

int strlen(char *s)
{
    int len = 0;
    while (*s++) ++len;
    return len;
}

2번에 대한 답변

사실 위의 코드는 제가 원래 "정답"이라 할 만한 코드가 아닙니다. 몇 가지 문제점이 있는데,

• strlen 함수는 들어 오는 인자의 값을 바꾸지 않습니다. 따라서 형식은 const char *이어야 합니다.
• 재수 없으면 s의 길이가 오버플로우 될 수 있습니다. 왜냐하면 int의 크기가 포인터의 크기와 비교해서 더 크거나 같다는 보장도 없을 뿐만 아니라 (64비트 환경을 생각해 보세요) 같다고 쳐도 int는 부호가 있기 때문에 잘못된 값을 반환할 수도 있습니다. 따라서 반환값은 size_t여야 합니다.

두 번째 주장에 대해서 저는 흥미로운 반론을 들었습니다. 포인터의 차이를 담을 수 있는 형식인 ptrdiff_t를 쓰면 되지 않느냐? (당사자는 윈도 API를 많이 써서 INT_PTR 얘기를 했지만 뭐 같은 뜻입니다.) 뭐 아주 틀린 말은 아니지만 여기에 대한 답변은 이렇습니다.

• ISO C에서는 size_t도 ptrdiff_t만한 크기를 가지는 것이 보장됩니다. 왜냐하면 size_t는 sizeof 식의 반환값을 담을 수 있는 크기여야 하니까요.
• ptrdiff_t는 부호가 존재합니다. 따라서 재수 없으면 문자열 길이가 오버플로우 될 수 있다는 얘기는 여기서도 성립합니다.

고로 수정된 코드는 다음과 같습니다.

size_t strlen(const char *s)
{
    size_t len = 0;
    while (*s++) ++len;
    return len;
}

덤으로 C++의 char_traits를 쓰면 다음과 같은 코드도 가능하겠습니다만, 여기서 하고자 하는 얘기는 아니니 덤으로 보시고 넘어 가세요. 좀 더 멀쩡한(?) 코드라면 length 메소드를 써야 겠죠.

template <class T>
size_t strlen(const T *s)
{
    size_t len = 0;
    while (std::char_traits<T>::eq(*s++, T())) ++len;
    return len;
}

3번에 대한 답변

먼저 glibc의 코드는 위와 같지 아니하다는 점을 지적하겠습니다. 당연해 보이는 코드 같지만 더 최적화할 여지가 있다는 얘기지요. 어떤 방법이 있을까요?

가장 쉽게 생각할 수 있는 방법은 루프를 풀어 헤치는 것입니다. IA-32(x86) 같이 현대의 마이크로프로세서 아키텍처들은 어떤 명령을 수행하기 한참 전에 미리 캐시에 읽어서 준비해 두곤 합니다. 그런데 이렇게 애써 읽어들인 캐시는 분기 명령을 수행하는 순간 쓸모가 없어지게 됩니다. 이런 문제를 해결하기 위해서 많은 프로세서가 분기가 성공할지 실패할지 예측하여 미리 캐시를 읽어 두려는 분기 예측을 수행하곤 합니다만, 사실 분기가 없는 게 가장 낫겠죠.

루프를 풀어 헤치는 방법은 불필요한 분기를 줄이는 데 도움이 됩니다. 위의 코드 같은 경우 분기 수 자체는 줄지 않습니다만 다른 이유로 성능 향상에 도움이 되는데, 그건 아래에서 보이겠습니다. 하여간 이렇게 해서 나온 코드는 다음과 같아집니다.

/* unsigned는 4바이트라 치고 리틀 엔디언 환경이라 가정합시다. 아니면 알아서… */
size_t strlen(const char *s)
{
    size_t len = 0;
    const unsigned *p = (const unsigned *)s;
    while (1) {
        unsigned v = *p;
        if ((v & 0xff) == 0) return len;
        if ((v & 0xff00) == 0) return len + 1;
        if ((v & 0xff0000) == 0) return len + 2;
        if ((v & 0xff000000) == 0) return len + 3;
        len += 4; ++p;
    }
}

위의 코드에서 주목할 것은 루프를 풀지 않은 것에 비하여 각 비교 사이에 수행하는 연산이 최소화되었다는 것입니다. 컴파일러가 알아서 모든 변수를 레지스터로 올려 주면 뭐 딱히 문제는 없겠습니다만, 안타깝게도 이 루프는 풀어 냈음에도 불구하고 명령 캐시에 꽉 찰 정도로 작은 데다가 컴파일러가 항상 이런 변수를 레지스터로 올려 줄 수 없는 경우도 있습니다. 따라서 최대한 루프 안에 들어 가는 연산을 줄이고, 특히 원래는 서로 분리되어 있던 연산을 하나로 합치는 작업을 통해서 최적화를 꾀하는 게 좋겠지요. (이 코드의 경우 len += 4;가 그런 예)

루프를 풀 때 가장 주의해야 할 점은 명령 캐시입니다. 루프가 명령 캐시에 들어 가지 못 할 정도로 많이 풀어 버리면 루프를 풀어서 얻는 이득보다 캐시가 루프를 돌 때마다 초기화되는 문제가 더 커질 수 있습니다. GCC의 -funroll-loops 같은 옵션은 이를 고려해서 자동으로 루프를 풀어 줍니다. (아마도…)

조금 더 머리를 쓰면 이런 코드도 가능하겠습니다.

#define HAS_NULL_BYTE(x) (((x) - 0x01010101u) & ~(x) & 0x80808080u)

size_t strlen(const char *s)
{
    size_t len = 0;
    const unsigned *p = (const unsigned *)s;
    unsigned v;
    while (1) {
        v = *p;
        if (HAS_NULL_BYTE(v)) break;
        len += 4; ++p;
    }
    if ((v & 0xff) == 0) return len;
    if ((v & 0xff00) == 0) return len + 1;
    if ((v & 0xff0000) == 0) return len + 2;
    return len + 3;
}

HAS_NULL_BYTE 매크로는 v를 바이트 단위로 나타냈을 때 널 바이트가 들어 있는지 확인하는 함수입니다. 이 매크로는 1980년대에 이미 알려져 있던 유명한 방법인데, 왜 동작하는지 궁금하다면 먼저 v가 8바이트 unsigned char일 때 (v - 1) & ~v &amp 0x80가 v == 0임을 확인해 보면 쉽게 이해할 수 있을 것입니다.

위의 코드는 짧은 문자열에 대해서 특히 빠르다고 알려져 있습니다. 그도 그럴 것이 매 루프 별로 네 번의 비교를 하던 것을 한 번으로 줄여 버렸으니까요. 좀 더 무리를 해서 HAS_NULL_BYTE를 네 번 해 본다거나 할 수도 있겠는데 실제로 이게 효과가 있다는 얘기는 못 들어 봤습니다.

위에서 제시한 코드는 실제로 glibc에서 비슷한 방법으로 사용하고 있습니다. 하지만 만약 긴 문자열이 많이 나온다면, 일반 레지스터를 사용한 방법보다는 MMX 레지스터를 쓰는 것이 더 빠릅니다. (MMX는 병렬 수행에 더 최적화되어 있습니다. 다만 상태 초기화를 위해서 드는 부하가 크기 때문에 짧은 문자열에서는 불리하죠.) 여기에 대해서는 코드 짜기 귀찮으니 생략합니다.

보너스 문제

위의 코드는 (제가 그냥 심심해서) 간단한 코드도 얼마나 다양하게 최적화될 수 있는지 전형적인 예를 들어 본 것입니다. 하지만 IRC에서 위 문제를 들어 보신 분이시라면 다음 문제도 들어 보셨을 겁니다.

4. 이제 3번에서 답한 코드의 제약 사항과 문제점을 지적하십시오.

눈썰미 좋으신 분이라거나, 이식성을 위해 많은 고민을 해 보셨다면 위 코드의 문제점을 쉽게 눈치채실 수 있을 것이라 믿습니다. 여기서 답을 주기는 귀찮으니 생략하고, 힌트를 드리자면 모든 아키텍처에서 문제가 발생할 수 있습니다. :p