String & SSO

프로그래밍에서 문자열을 다루는 일은 굉장히 잦지만,

문자열이 어떻게 구현되었는지 생각해 본 적 있으신가요?

 

물론 단순히 문자(character)의 배열(array)이라는 답도 근본적으로는 틀리지 않지만요 :3

낮익은 천장이다...

 

... 저번에는 유니코드 인코딩 방식을 위주로 설명했다면, 이번에는 문자열 구현체의 설계를 소개해보고자 해요.

이번 글은 다양한 개념들을 한꺼번에 다루기에, 만약 기억이 안 나신다면 이전 글들을 확인해 보는 걸 추천드릴게요!

---

문자열의 크기는 컴파일 시간(compile-time)에 알 수 없는 경우가 있어요.

 

크기를 알 수 없다면, 문자열의 내용을 stack 메모리에 저장할 수 없고,

따라서 필연적으로 실행 시간(runtime)에 heap 메모리를 할당해야 해요.

그리고 heap 메모리를 할당하는 작업은 성능적으로 많은 악영향을 끼쳐요...

가변 길이 배열 - VLA(Variable Length Array) - 은 다음에 다뤄볼게요!

 

추가로, C/C++에서 배열은 포인터로 변경(decay)되는 과정에서 배열의 길이 정보를 손실하는 문제가 있어요.

그리고 동적으로 할당된 메모리는 직접 해제하지 않으면 메모리 누수(leak)가 발생하기에 주의를 요해요.

소유권(ownership)을 갖고 자동으로 메모리를 해제하는 smart pointer는 다음에 다뤄볼게요!

---

아래는 heap 메모리 할당을 최소화하기 위해서, 만약 길이가 n인 문자열을 변형시켜서 n'으로 길이가 줄어들어도

null terminator에 의존하지 않고 할당된 heap 메모리 크기를 알 수 있도록 필드 capacity(용량)를 포함한 구조체예요.

size_t 및 포인터의 크기는 1 word와 같지만, 이 글에서는 64bit OS를 기준으로 설명할게요!

#include <cstddef>

struct string
{
	char* data;
	size_t size;
	size_t capacity;
};

 

정말이지 완벽하네요... 그럼 20000 ( ◡̀_◡́)ᕤ

---

... 헤어지기 전에 마지막으로 구조체의 크기를 계산해 볼까요?

#include <cstddef>
#include <iostream>

struct string
{
	char* data; // 8 byte
	size_t size; // 8 byte
	size_t capacity; // 8 byte
};

int main()
{
	std::cout << sizeof(string) << std::endl; // 24
	std::cout << alignof(string) << std::endl; // 8
}

struct string

data

size

capacity

alignment

alignment

alignment

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

 

구조체 패딩 없이 24 byte를 사용하는 것을 볼 수 있어요.

다만 딱 한 가지 아쉬운 점은 항상 heap 메모리를 사용한다는 ㄱ...

만약 size ≤ sizeof(data) + sizeof(capacity)의 경우에는 공용체를 사용하면요?

#include <cstddef>
#include <iostream>

struct string
{
	union
	{
		struct
		{
			char* data;  // 8 byte
			size_t capacity; // 8 byte
		}
		large;
		// for SSO
		char small[sizeof(large)]; // 16 byte
	};
	size_t size; // 8 byte
};

int main()
{
	std::cout << sizeof(string) << std::endl; // 24
	std::cout << alignof(string) << std::endl; // 8
}

struct string

small

size

data

capacity

alignment

alignment

alignment

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

ℬ

 

대박대박ㅋ 공용체를 사용함으로써 size ≤ 16 byte의 문자열은 stack 메모리를 사용해서 저장할 수 있게 됐어요!

이처럼 문자열의 크기가 작은 경우 stack 메모리에 저장하는 최적화를 SSO(Short String Optimization)라고 해요.

FBString

내가 어릴 때는 분명 회사명이 페이스북이었는데...

meta(구 facebook)사에서는 직접 folly라는 C++라이브러리를 만들어서 사용하고 있어요.

해당 라이브러리는 문자열 구현체(FBString)를 제공하는데, 과연 어떻게 구현되어 있을까요?

---

만약 24 byte의 공간을 전부 사용해서 c-style 문자열을 표현한다면 다음과 같은 구조가 될 거예요.

c-style string literal

h

e

l

l

o

w

o

r

l

d

.

i

l

o

v

e

c

+

+

.

0

 

이 경우 24 byte 전부를 문자열의 내용에 할당했기 때문에 길이를 알기 위해서는 순회가 필요해요.

그리고 24 byte 전부를 사용하더라도 null terminator가 요구되기에 문자열의 가용량은 최대 23 byte에요.

---

1 byte(8 bit)를 전부 사용하면 부호가 있을 경우 -128에서 127까지, 부호가 없을 경우 0~255까지 표현 가능해요.

1 byte
1 bit	1 bit	1 bit	1 bit	1 bit	1 bit	1 bit	1 bit
2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0

---

지금까지의 내용을 정리해 보자면 다음과 같아요.

1. 가용량 = N -1 byte
2. sizeof(string) = 24
3. uint8_t 범위 = 0 ~ 255
4. null terminator = '\0' = 0

따라서 RMB(Right Most Byte)에 23 - sizeof(T) 를 저장하면, 나머지 용량과 널 종료 문자를 동시에 표현 가능해요.

FBString

data

size

capacity

small

alignment

alignment

alignment

0

23

h

0

22

h

e

0

21

h

e

l

0

20

h

e

l

l

0

19

h

e

l

l

o

0

18

h

e

l

l

o

0

17

h

e

l

l

o

w

0

16

h

e

l

l

o

w

o

0

15

h

e

l

l

o

w

o

r

0

14

h

e

l

l

o

w

o

r

l

0

13

h

e

l

l

o

w

o

r

l

d

0

12

h

e

l

l

o

w

o

r

l

d

.

0

11

h

e

l

l

o

w

o

r

l

d

.

i

0

10

h

e

l

l

o

w

o

r

l

d

.

i

0

9

h

e

l

l

o

w

o

r

l

d

.

i

l

0

8

h

e

l

l

o

w

o

r

l

d

.

i

l

o

0

7

h

e

l

l

o

w

o

r

l

d

.

i

l

o

v

0

6

h

e

l

l

o

w

o

r

l

d

.

i

l

o

v

e

0

5

h

e

l

l

o

w

o

r

l

d

.

i

l

o

v

e

0

4

h

e

l

l

o

w

o

r

l

d

.

i

l

o

v

e

c

0

3

h

e

l

l

o

w

o

r

l

d

.

i

l

o

v

e

c

+

0

2

h

e

l

l

o

w

o

r

l

d

.

i

l

o

v

e

c

+

+

0

1

h

e

l

l

o

w

o

r

l

d

.

i

l

o

v

e

c

+

+

.

0

 

사실 2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 31 > 23 이기에 마지막 1 byte의 5 bit만 사용해도 전혀 문제가 없어요.

그러면 나머지 3 bit는 flag로 사용해서 stack 메모리를 사용하는지 heap 메모리를 사용하는지 판별할 수 있어요.

---

그렇다면 의문점이 한 가지 떠오를 수 있어요...

 

SSO의 경우 공용체의 마지막 1 byte를 이용해서 null terminator와 나머지(spare) 용량을 저장하는 것은 알겠지만,

SSO를 적용하지 않는 경우 capacity 필드의 마지막 1 byte가 flag의 이진부호와 겹칠 수 있는데 어떻게 구별할까요?

---

이런 불상사를 방지하기 위해서 FBString은 마지막 2 bit를 항상 보존(reserve)해요.

small, medium, large 3가지를 표현하기 위한 flag는 최소 2 bit를 요구하기 때문이에요

그리고 bit-wise 연산자를 사용해서 마지막 2 bit를 제외한 나머지 부분을 포함한 정수값을 읽어요.

따라서 필드 capacity의 가용량은 1 word - 2 bit, 실질적 표현 범위는 2^(1 word - 2) - 1 = 2^62 - 1 에요.

capacity
1 byte	1 byte	1 byte	1 byte	1 byte	1 byte	1 byte	last byte

last byte
for capacity						for flag
1 bit	1 bit	1 bit	1 bit	1 bit	1 bit	1 bit	1 bit

 

그런데 굳이 복잡한 bit-wise 연산자를 사용하는 대신 bit-field를 사용하면 보다 코드가 명료하지 않을까요?

どうして ..?

#include <cstddef>

struct size_and_flag
{
	size_t size: sizeof(size_t) * 8 - 2;
	size_t flag: 2;
};

FBString

data

size

size_and_flag

small

alignment

alignment

alignment

size_and_flag
Compiler A from vendor ??
1 byte			1 byte	1 byte	1 byte	1 byte	1 byte	1 byte	6		2
Compiler B from vendor ??
2	6		1 byte	1 byte	1 byte	1 byte	1 byte	1 byte	1 byte

 

c style 문자열에서 널 종료 문자는 항상 끝에 배치되어야 하는데

bit-field를 사용하면 필드의 순서를 보장할 수 없어서 이런 문제가 생겨요...

글에는 담지 않았지만 FBString은 엔디안(endianess) 또한 고려해서 설계가 더욱 정교해요!

Credits

Meaning of acronym SSO in the context of std::string

jank's new persistent string is fast

If you're thinking about fbstring, here's how it's setup: First thing member methods of fbstring need to do is to figure out if it's small string or heap allocated string (there's also a "medium" string). The only part of structure not mangled by the actual small string data is the last byte of data, that is, the last byte of capacity in case of heap data string (not highest/lowest byte of capacity, this depends of endianness). If you look at the Github code of fbstring, you will see this code: constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3; enum class Category : category_type { isSmall = 0, isMedium = kIsLittleEndian ? 0x80 : 0x2, isLarge = kIsLittleEndian ? 0x40 : 0x1, }; Category category() const { // works for both big-endian and little-endian return static_cast<Category>(bytes_[lastChar] & categoryExtractMask); } So if it's little-endian system (Intel x86) the information is in the highest two bits of last byte and in the lowest two bits in case of big-endian. After that size/capacity is retrieved in this way: - For small string the remaining 6 bits of last byte are size, giving 2^6=63 max capacity which is OK because it can be at most 23. - For heap allocated string data flags will occupy highest two bits of capacity field in case of little-endian and the lowest two bits otherwise. In little-endian case highest two bits are ignored (zeroed) when retrieving the value. In big-endian case the capacity field is shifted 2 bits to the right. This limits the maximum fbstring length to 2^62. "isMedium" type is being allocated in the same way as "isLarge", differences are not related to this story.

In the normal string, the data pointer, size, and capacity are all 64 bits. In the small string, the last 64 bits are 56 bits of string data followed by eight bits of size. This means the small string "spare capacity" and the normal string capacity representations share that last byte. Flags stored in that byte need to be stripped out. Another commenter said the implementation has two flags, so I'll explain that more restrictive case. For little endian, the bit numbers in capacity go from 0, 1, ... 62, 63. You can reserve bits 62 & 63, which are in the last byte, and mask those out after reading capacity. (capacity & 0x3fffffffffffffff) For big endian, the bits go 63, 62, ... 1, 0. You can reserve bits 0 & 1 in the last byte, and right-shift capacity twice after reading it. So the flag bits are in the same byte either way but have different places values on different endian architectures. The implementation needs to ensure that valid states of the string don't alias those bits. In the small string, the "spare capacity" field can range from 0b00010111 (23) to 0, so the upper two bits don't interfere. In the normal string the capacity can be no more than 2^62-1, freeing up two bits at the beginning/end of the number.'