Coogle을 개발하며 발견한 C와 C++ 문자열의 설계, std::string의 템플릿 구조, SSO 및 std::string_view를 정리한 글입니다.
Coogle을 구현하던 중 C++ 문자열에 관한 기묘한 사실을 발견했습니다. 그래서 C++ 문자열에 대해 배운 내용을 정리하려고 이 노트를 작성했습니다.
Coogle은 제가 C++로 구현한 검색 엔진입니다. 대규모 코드베이스에서 함수 시그니처를 빠르고 효율적으로 찾도록 설계했습니다. 특히 제 사랑스러운 일상 업무처럼 C에서 마이그레이션되었고 C++11/14/17/20 기능이 뒤섞인 30년 된 C++ 코드베이스에 유용합니다.
저는 Haskell과 순수 함수를 좋아해서 Haskell 함수 검색 엔진인 Hoogle에 경의를 표하고 싶었습니다. C/C++에서 함수 시그니처를 검색하고 일치하는 함수 목록을 돌려받을 수 있다는 것이 아이디어입니다.
첫 단계는 int, char 같은 단순한 타입을 지원하는 것입니다. 좋아요, 그리 어렵지 않습니다.
// This is my test file
int add(int a, int b);
int std::string(std::string s);
"int(int, int)"를 검색하면 Coogle이 이 시그니처를 빠르게 찾아야 한다고 기대합니다. 그래서 구현했고, 잘 작동했습니다.
그런데 std::string을 받고 반환하는 함수 시그니처를 찾기 위해 "std::string(std::string)"을 검색했을 때, 테스트 코드베이스에 그런 함수가 많음에도 Coogle이 결과를 전혀 찾지 못한다는 것을 발견했습니다.
이건 저에게 정말 WTF의 순간이었습니다.
이유를 이해하지 못해 한동안 막혔고, 그러다 libclang으로 전체 AST 트리를 출력했습니다. 그때 혼란스러운 것을 보았습니다. std::string 대신 std::basic_string<char, std::char_traits<char>, std::allocator<char>>가 나타난 것입니다.
trait와 allocator는 대체 뭘까요? 저는 C++ 문자열을 전혀 이해하지 못하고 있었습니다. 그냥 std::string이어야 한다고 생각했으니까요!
음... 그래서 더 깊이 파고들어 C++ 문자열에 관해 더 읽었습니다.
처음에는 LLM에게 C++ 문자열과 설계를 물어볼 생각이었습니다. 하지만 저는 레거시 C 및 C++ 코드를 다루고, 최상의 성능을 뽑아내기 위한 제 알고리즘 상당수가 C로 구현되어 있으므로, 먼저 C 문자열과 문자 타입을 깊이 이해하기로 했습니다.
Jserv가 C Programming series에서 늘 말하듯이 말입니다.
"자신에게 솔직해지세요. 당신은 C를 모릅니다." --- Jserv Huang
그러니 std::string을 다루기 전에, 우리 자신에게 솔직해져서 char의 혼돈을 살펴봅시다. 아래 내용은 언어 표준과 글을 비롯한 다양한 자료를 사용해 조사한 내용을 바탕으로 합니다.
완전히 100% 정확하지 않을 수도 있지만, 배운 내용을 최선을 다해 요약했습니다. 실수가 있다면 부디 알려 주세요.
결론부터 시작하겠습니다.
C에서 char는 실제로 '문자'를 뜻하지 않습니다. 그저 메모리의 주소 지정 가능한 최소 단위(바이트)를 뜻합니다. ASCII나 다른 인코딩이 우연히 이 단위에 들어맞을 뿐입니다. --- The Cloudlet
아니면 VHDL의 관점으로 보면 더 명확할지도 모릅니다.
library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;
package C_Types is
-- Defined in <limits.h>
-- Most likely 8, but could be 16 or 32 on DSPs
constant CHAR_BIT : integer := 8;
-- "unsigned char" -> 0 to 255
subtype c_unsigned_char is unsigned(CHAR_BIT-1 downto 0);
-- "signed char" -> -128 to 127
subtype c_signed_char is signed(CHAR_BIT-1 downto 0);
-- Compiler defines "__CHAR_UNSIGNED__" on platforms like ARM.
-- Set by Arch (x86=false, ARM=true)
constant CHAR_IS_UNSIGNED : boolean := ???;
alias c_char is
case CHAR_IS_UNSIGNED generate
when false => c_signed_char; -- x86 (Default)
when true => c_unsigned_char; -- ARM
end generate;
end package C_Types;
여기서 VHDL을 특별히 선택한 이유는 엄격성 때문입니다. VHDL은 "Raw Bits"(std_logic_vector), "Unsigned Math"(unsigned), "Signed Math"(signed)의 차이를 보도록 강제합니다.
자세한 내용은 ISO C99 표준 §6.2.5를 참고하세요.
세 가지 타입 규칙: char, signed char, unsigned char는 서로 구별되는 세 타입입니다. 일반 char는 와일드카드로, x86에서는 signed처럼 동작하지만 ARM에서는 unsigned처럼 동작합니다.
사용 규칙:
char를 사용합니다.signed char를 사용합니다.unsigned char(또는 uint8_t)를 사용합니다.이것은 CS101 수준의 내용이라 너무 깊이 이야기할 필요는 없다고 생각합니다. 간단히 복습하고 C 문자열이 이렇게 설계된 이유를 보겠습니다.
핵심 메커니즘
\0은 널 종료자입니다.strlen, strcpy, strcmp 같은 연산은 선형 탐색 입니다.┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ H │ e │ l │ l │ o │ , │ │ W │ o │ r │ l │ d │ ! │ \0 │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ 72 │ 101 │ 108 │ 108 │ 111 │ 44 │ 32 │ 87 │ 111 │ 114 │ 108 │ 100 │ 33 │ 0 │
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│0x48 │0x65 │0x6C │0x6C │0x6F │0x2C │0x20 │0x57 │0x6F │0x72 │0x6C │0x64 │0x21 │0x00 │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]
^ ^
| |
str (pointer to first character) Null terminator ('\0')
널 종료 문자열의 이유
C 문자열이 왜 이렇게 설계되었는지 찾아보았습니다. 찾아낸 바로는 1970년 당시 메모리에서 문자열을 표현하는 전형적인 방식이 두 가지였습니다.
하지만 C가 길이 접두 문자열 대신 널 종료 문자열을 택한 확정적인 답은 찾지 못했습니다. 대신 C 문자열이 솔직히 말해 골칫거리라는 점을 지적하는 흥미로운 글들을 발견했습니다. Joel Spolsky의 고전 글 Back to Basics를 보세요. 그는 strcat의 성능 문제와 널 종료 문자열의 한계를 우회하기 위해 일부 개발자가 "F***ed-Up Strings"(C의 Pascal 스타일 문자열)에 의존한 방식을 설명합니다.
C에서는 문자열 처리를 위한 다양한 구현이 있습니다. 예를 들어 Linux 커널은 파일시스템 경로를 다룰 때 include/linux/dcache.h 아래에 qstr 구현을 둡니다. Google의 Abseil 라이브러리도 StringPiece를 도입했으며, 이것은 나중에 C++17의 string_view로 발전했습니다. 이러한 구현 전반에서 일반적으로 받아들여지는 접근법은 char 포인터와 함께 길이 필드를 보관하여 반복적인 strlen 호출을 피하는 것입니다.
그러므로 C++의 std::string만이 C 문자열 문제의 유일한 해법은 아닙니다. 하지만 그 설계를 이해하는 것은 컴파일러, 라이브러리, 시스템 프로그래머에게 도움이 될 수 있습니다.
업데이트: 커뮤니티 인사이트 (2025-11-26)
널 종료 문자열 설계에 관하여, Reddit의 친절한 댓글 몇 개는 다음과 같이 지적했습니다.
아주 오래전에는 1바이트 길이로 긴 문자열을 표현하기에 충분하지 않았지만, 길이 필드에 더 많은 바이트를 쓰는 것은 짧은 문자열에 비효율적이었습니다. 길이 접두사에 가변 길이 인코딩을 사용하는 복잡성을 아무도 원하지 않았던 것 같습니다. 그래서 오늘날 우리는 널 종료 문자열의 고통과 함께 살고 있습니다. --- u/Kered13
또한 더 깊이 있는 역사를 파고드는 데 훌륭한 자료를 알려 준 u/vip17에게도 감사합니다.
C의 널 종료 문자열 역사를 설명하는 곳은 많습니다:
효율성과 단순성 사이의 투쟁은 C의 태동부터 우리와 함께해 온 듯합니다.
업데이트: 메모리의 관점 (2025-11-27)
우리는 byte를 메모리의 주소 지정 가능한 최소 단위라고 말하지만, DRAM 칩에서 실제로 읽고 쓸 수 있는 최소 단위는 word(일반적으로 4 또는 8바이트)라는 사실을 알게 되었습니다. byte의 개념은 CPU 아키텍처 또는 ISA가 제공하는 논리적 추상화에 가깝습니다.
CPU가 메모리에 접근할 때는 word 단위로 읽고 씁니다. 이후 메모리 컨트롤러가 CPU가 처리할 수 있도록 이 word들을 바이트로 분할합니다. 즉, 코드에서는 바이트를 다루지만 내부적으로 메모리 시스템은 더 큰 단위로 동작합니다.
다음 참고 자료에는 캐시 라인, 메모리 계층 구조, 데이터가 DRAM에서 CPU 캐시로 가져와지는 방식 등 메모리 시스템 동작에 관한 자세한 설명이 있습니다.
참고 자료: 논문: 모든 프로그래머가 메모리에 대해 알아야 할 것
따라서 "C char는 왜 이렇게 설계되었을까?"라는 질문의 답은 프로그래머가 텍스트 데이터를 다룰 수 있는 단순한 추상화를 제공하면서 ISA/CPU 아키텍처에서의 기본 메모리 접근 단위에 맞추기 위해서입니다.
좋아요, 다시 Coogle의 버그로 돌아가 봅시다. 저는 AST에서 std::string(std::string)을 검색했지만 결과는 0개였습니다. 그러고 나서 libclang으로 AST에 저장된 전체 타입 이름을 출력했고, 거기에는 괴물 같은 타입 이름이 있었습니다.
std::basic_string<char, std::char_traits<char>, std::allocator<char>>
std::string은std::basic_string템플릿 클래스의 특정 인스턴스화에 대한 typedef(별칭)일 뿐입니다.
타입 시스템에 존재하지 않는 이름을 찾고 있었기 때문에 검색에 실패했습니다. std::string은 인간 프로그래머를 위한 문법적 설탕입니다. 컴파일러는 basic_string<char>와 기본 인수를 포함한 완전한 템플릿 인스턴스화만 봅니다.
basic_string은 실제로 세 매개변수를 가진 템플릿이며, 그중 두 개에는 기본값이 있습니다.
template<
class CharT, // Character type (char, wchar_t, etc.)
class Traits = char_traits<CharT>, // Character operations (comparison, copying)
class Allocator = allocator<CharT> // Memory management strategy
>
class basic_string;
이 별칭을 아는 것만으로도 제 문제를 해결하기에는 충분하지만, 각 매개변수를 이해하면 프로그래밍 실력 향상에 도움이 될 수 있습니다.
괴물 분해하기
CharT:
wchar_t, UTF-16용 char16_t 등입니다. 충분히 단순합니다.Traits:
char_traits 클래스는 주어진 문자 타입에 대한 기본 문자 및 문자열 연산을 추상화하는 traits 클래스 템플릿입니다. 정의된 연산 집합은 제네릭 알고리즘을 거의 항상 이를 기반으로 구현할 수 있도록 구성되어 있습니다.
비교, 복사, 길이 계산 같은 문자 연산의 사용자 정의 동작을 정의할 수 있다는 뜻입니다. 예를 들어 VHDL 파일은 대소문자를 구분하지 않으므로, 대소문자 차이를 무시하도록 비교 함수를 재정의하는 case_insensitive_char_traits를 정의할 수 있습니다.
멋집니다!
Allocator:
new~/~delete를 사용하지만, 특정 메모리 전략을 위한 사용자 정의 할당자를 연결할 수 있습니다. 예를 들면 아레나 할당, 풀 할당, 누수를 추적하는 디버깅 할당자 등이 있습니다. 이것이 C++17의 PMR(Polymorphic Memory Resources)이 기반으로 삼는 것이며, PART 3에서 다룹니다.
std::basic_string은 다양한 문자 타입, 동작, 메모리 전략에 적응할 수 있는 유연하고 재사용 가능한 문자열 클래스를 제공합니다.
간단한 요약 다이어그램:
Template Class (defined once)
┌────────────────────────────────────────────────────────────┐
│ template<class CharT, class Traits, class Allocator> │
│ class basic_string { │
│ CharT* data_; │
│ size_t size_; │
│ size_t capacity_; │
│ // ... methods ... │
│ }; │
└────────────────────────────────────────────────────────────┘
│
│ Template Instantiation
│
┌────────────────────────┼────────────────────────┐
│ │ │
▼ ▼ ▼
┌─────────────────┐ ┌─────────────────┐ ┌──────────────────────┐
│ std::string │ │ std::wstring │ │ std::pmr::u16string │
├─────────────────┤ ├─────────────────┤ ├──────────────────────┤
│ CharT: │ │ CharT: │ │ CharT: │
│ char │ │ wchar_t │ │ char16_t │
│ Traits: │ │ Traits: │ │ Traits: │
│ char_traits │ │ char_traits │ │ char_traits │
│ <char> │ │ <wchar_t> │ │ <char16_t> │
│ Allocator: │ │ Allocator: │ │ Allocator: │
│ allocator │ │ allocator │ │ polymorphic_alloc │
│ <char> │ │ <wchar_t> │ │ <char16_t> │
└─────────────────┘ └─────────────────┘ └──────────────────────┘
"Hello" L"Hello" u"Hello"
6 bytes 12/24 bytes 12 bytes
PMR runtime alloc!
All are typedefs of basic_string with different template arguments!
std::pmr::u16string -> DIFFERENT allocator = DIFFERENT type!
템플릿의 인수를 논의했으니, 이제 basic_string이 내부적으로 어떻게 구현되는지 보겠습니다.
이는 Linux 커널의 qstr과 정확히 같은 개념입니다. struct를 사용해 문자열 데이터의 포인터와 길이를 보관합니다. 용량 관리처럼 더 많은 기능도 있지만(앞서 Joel Spolsky의 글에서 언급한 strcat처럼), 핵심 아이디어는 같습니다.
코드는 자명하므로 여기에는 그대로 붙여 넣겠습니다.
template<class CharT, class Traits, class Allocator>
class basic_string {
private:
CharT* data_; // Pointer to character buffer
size_t size_; // Current length (excluding null terminator)
size_t capacity_; // Allocated capacity
Allocator alloc_; // Often zero-size due to EBO
// Many implementations use a union for SSO (Small String Optimization):
union {
struct {
CharT* ptr;
size_t size;
size_t capacity;
} heap; // For long strings
struct {
CharT buffer[16]; // Size varies by implementation
unsigned char size;
} stack; // For short strings (SSO)
} data_;
// Methods, iterators, etc.
};
짧은 문자열 최적화와 pmr/allocator 같은 자세한 내용은 PART 3을 참고하세요.
위의 basic_string 코드 조각을 보면 힙 할당 버퍼 또는 작은 스택 버퍼를 보관하는 union이 보입니다. 이것을 작은 문자열 최적화(SSO)라고 합니다.
SSO의 개념은 단순합니다! 스택 메모리 할당은 힙 할당보다 훨씬 빠릅니다. 따라서 문자열 객체 내부에 작은 버퍼를 미리 할당하면 작은 문자열이 new~/~delete를 자주 호출하지 않아도 됩니다.
간단히 말해 컴파일러나 어셈블리에서 스택 할당은 스택 포인터를 움직이는 것뿐이지만(프롤로그/에필로그 삽입), 힙 할당은 복잡한 장부 관리, 빈 블록 탐색, 메타데이터 갱신을 수반합니다.
조사해 보니 Linux 커널도 가상 파일시스템 경로에서 이 SSO 기법을 사용합니다. Linux 커널의 dentry 구조체는 shortname_store라는 union을 사용하여 구조체 안에 짧은 문자열을 직접 보관하거나 힙에 할당된 더 긴 문자열에 대한 포인터를 보관합니다. 이는 C++의 SSO와 정확히 같은 아이디어입니다. [출처: include/linux/dcache.h]
/*
* Try to keep struct dentry aligned on 64 byte cachelines (this will
* give reasonable cacheline footprint with larger lines without the
* large memory footprint increase).
*/
#ifdef CONFIG_64BIT
# define DNAME_INLINE_WORDS 5 /* 192 bytes */
#else
# ifdef CONFIG_SMP
# define DNAME_INLINE_WORDS 9 /* 128 bytes */
# else
# define DNAME_INLINE_WORDS 11 /* 128 bytes */
# endif
#endif
union shortname_store {
unsigned char string[DNAME_INLINE_LEN];
unsigned long words[DNAME_INLINE_WORDS];
};
#define DNAME_INLINE_LEN (DNAME_INLINE_WORDS*sizeof(unsigned long))
struct dentry {
/* RCU lookup touched fields */
unsigned int d_flags; /* protected by d_lock */
seqcount_spinlock_t d_seq; /* per dentry seqlock */
struct hlist_bl_node d_hash; /* lookup hash list */
struct dentry *d_parent; /* parent directory */
union {
struct qstr __d_name; /* for use ONLY in fs/dcache.c */
const struct qstr d_name;
};
struct inode *d_inode; /* Where the name belongs to - NULL is
negative */
union shortname_store d_shortname; //<-- SSO buffer for short names
// ...
};
Linux의 SSO가 뛰어난 이유
개념은 C++와 유사하지만, Linux는 성능을 위해 중요한 차이를 두고 구현합니다. 바로 분기 없는 접근입니다.
C++에서 std::string에 접근할 때는 데이터를 읽을 위치를 결정하기 전에 "이것은 짧은 문자열인가, 긴 문자열인가?"를 확인해야 하는 경우가 많습니다.
Linux는 이 확인을 완전히 피합니다. struct qstr 내부의 d_name.name 포인터는 생성 중 내부 d_shortname 버퍼 또는 외부 힙을 가리키도록 설정됩니다.
이는 시스템 프로그래머에게 메모리 레이아웃이 단순히 바이트를 아끼는 문제가 아니라 CPU 사이클을 아끼는 문제임을 보여 줍니다.
업데이트: 커뮤니티 인사이트 (2025-11-26)
Reddit의 질문:
분기를 피하는 대신 포인터 간접 참조를 얻는다면, 현대 CPU의 분기 예측 능력을 고려할 때 결국 얼마나 큰 이득이 있나요? u/Supadoplex
답변, 또는 답변하려는 시도:
정확한 답은 모르지만, 다음은 제가 조사한 내용입니다. 예측 가능성과 캐시 지역성에 달려 있습니다.
분기 예측 실패 비용:
포인터 간접 참조 비용: (agner.org의 수치)
그러므로...
분기가 예측 불가능하고(적중률 80% 미만) 포인터 데이터가 캐시에 상주한다면, 보통 간접 참조가 이깁니다. --- Cloudlet
SSO 버퍼 크기 사용자 정의
때로는 특정 사용 사례를 위해 SSO 버퍼의 크기를 사용자 정의해야 한다고 생각합니다. 예를 들어 저는 한때 상당히 길어질 수 있는 복잡한 Verilog/VHDL 혼합 언어 경로 이름을 다뤄야 했습니다. 따라서 다음에는 더 큰 SSO 버퍼를 지원하는 사용자 정의 문자열을 구현해 볼 수도 있습니다. 핵심은 스택 크기와 힙 할당 빈도 사이에서 적절한 균형을 찾는 것입니다. 이 글의 범위를 벗어나므로 다음 기회로 미루겠습니다.
GCC의 libstdc++에서 가져온 std::string_view의 내부 구조를 보세요. Linux 커널의 qstr과 놀라울 정도로 비슷합니다.
template<typename _CharT, typename _Traits = std::char_traits<_CharT>>
class basic_string_view
{
//...
private:
size_t _M_len;
const _CharT* _M_str;
}
포인터와 길이뿐입니다. allocator도, 힙도, 소유권도 없습니다. 소유권은 std::string(가장 일반적인 경우), char 배열 또는 ~mmap~된 파일이 가집니다.
물론 공짜 점심은 없습니다. std::string_view는 빌린 참조(Rust의 &str처럼)입니다. 원본 데이터(소유자)가 뷰보다 오래 살아남도록 반드시 보장해야 합니다.
std::string은 너무 많은 일을 하려 합니다. 소유권, 크기 조정, traits, 할당을 한 클래스에서 모두 처리합니다. 생산성이 우선인 일반 애플리케이션에는 훌륭한 스위스 아미 나이프입니다. (std::string과 RAII를 쓰는 느낌이 좋고 정말 머리를 편하게 해 준다는 점은 인정해야 합니다.)
하지만 Linux 커널이나 LLVM 컴파일러처럼 고성능 도구에는 과도하게 설계되었습니다.
Linux 커널의 struct qstr은 단순함의 우아함을 보여 줍니다. 포인터와 길이(그리고 해시)뿐입니다.
좋은 소식은 현대 C++(C++17)이 마침내 이를 std::string_view로 인정했다는 것입니다. allocator 마법과 메모리 소유권을 벗겨 내고, 타입 안전성과 함께 C 스타일 struct의 원초적 효율을 돌려줍니다.
따라서 고성능 도구를 작성한다면:
std::string을 std::vector 같은 무거운 컨테이너로 취급하세요.std::string_view를 주 인터페이스로 사용하세요.absl::Cord는 연속 메모리 문제를 어떻게 해결하는가?