libc ++에서 짧은 문자열 최적화의 메커니즘은 무엇입니까? 짧은 문자열과

이 답변 은 짧은 문자열 최적화 (SSO)에 대한 멋진 고급 개요를 제공합니다. 그러나 실제로 libc ++ 구현에서 어떻게 작동하는지 더 자세히 알고 싶습니다.

  • SSO 자격을 얻으려면 문자열이 얼마나 짧아야합니까? 이것은 대상 아키텍처에 따라 달라 집니까?

  • 구현시 문자열 데이터에 액세스 할 때 짧은 문자열과 긴 문자열을 어떻게 구분합니까? m_size <= 16다른 멤버 변수의 일부인 플래그 만큼 간단 합니까? ( m_size또는 그 일부가 문자열 데이터를 저장하는 데 사용될 수도 있다고 생각합니다 ).

SSO를 사용한다는 것을 알고 있기 때문에 libc ++에 대해 특별히이 질문을했습니다. 이것은 libc ++ 홈페이지 에 언급되어 있습니다.

출처를 살펴본 후 몇 가지 관찰 사항은 다음과 같습니다. .

libc ++는 문자열 클래스에 대해 약간 다른 두 가지 메모리 레이아웃으로 컴파일 할 수 있습니다 _LIBCPP_ALTERNATE_STRING_LAYOUT. 이것은 플래그 에 의해 관리됩니다 . 두 레이아웃 모두 리틀 엔디안 머신과 빅 엔디안 머신을 구분하므로 총 4 가지 변형이 있습니다. 나는 다음에서 “일반적인”레이아웃과 리틀 엔디안을 가정 할 것이다.

추가 size_type로 4 바이트이고 value_type1 바이트 라고 가정하면 다음은 문자열의 처음 4 바이트가 메모리에서 보이는 것과 같습니다.

// short string: (s)ize and 3 bytes of char (d)ata
sssssss0;dddddddd;dddddddd;dddddddd
       ^- is_long = 0

// long string: (c)apacity
ccccccc1;cccccccc;cccccccc;cccccccc
       ^- is_long = 1

짧은 문자열의 크기는 상위 7 비트에 있으므로 액세스 할 때 이동해야합니다.

size_type __get_short_size() const {
    return __r_.first().__s.__size_ >> 1;
}

마찬가지로, 긴 문자열의 용량에 대한 getter 및 setter __long_maskis_long비트 를 처리 하는 데 사용 합니다 .

나는 여전히 내 첫 번째 질문에 대한 답을 찾고 있습니다. __min_cap , 짧은 문자열의 용량이 다른 아키텍처에 대해 까요?

기타 표준 라이브러리 구현

이 답변std::string다른 표준 라이브러리 구현 의 메모리 레이아웃에 대한 멋진 개요를 제공합니다 .



답변

libc ++ basic_stringsizeof모든 아키텍처에서 3 단어 를 갖도록 설계되었습니다 sizeof(word) == sizeof(void*). long / short 플래그와 짧은 형식의 size 필드를 올바르게 분석했습니다.

짧은 문자열의 용량 인 __min_cap은 다른 아키텍처에 대해 어떤 값을 사용합니까?

짧은 형식으로 작업 할 3 개의 단어가 있습니다.

  • 1 비트는 long / short 플래그로 이동합니다.
  • 크기는 7 비트입니다.
  • char1 바이트가 후행 널로 이동 한다고 가정하면 libc ++는 항상 데이터 뒤에 후행 널을 저장합니다.

이것은 짧은 문자열을 저장하기 위해 3 단어에서 2 바이트를 뺀다 capacity().

32 비트 컴퓨터에서는 10 개의 문자가 짧은 문자열에 맞습니다. sizeof (문자열)는 12입니다.

64 비트 시스템에서는 짧은 문자열에 22 개의 문자가 들어갑니다. sizeof (문자열)는 24입니다.

주요 설계 목표는 sizeof(string)내부 버퍼를 최대한 크게 만드는 동시에을 최소화하는 것이 었습니다 . 그 이유는 이동 구성 및 이동 할당을 가속화하는 것입니다. 클수록sizeof 이동 구성 또는 이동 할당 중에 더 많은 단어를 이동해야합니다.

긴 형식은 데이터 포인터, 크기 및 용량을 저장하기 위해 최소 3 단어가 필요합니다. 따라서 짧은 형식을 동일한 3 단어로 제한했습니다. 4 단어 크기가 더 나은 성능을 가질 수 있다고 제안되었습니다. 나는 그 디자인 선택을 테스트하지 않았습니다.

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT

_LIBCPP_ABI_ALTERNATE_STRING_LAYOUT“긴 레이아웃”이 다음에서 변경되도록 데이터 멤버를 재정렬하는 라는 구성 플래그 가 있습니다.

struct __long
{
    size_type __cap_;
    size_type __size_;
    pointer   __data_;
};

에:

struct __long
{
    pointer   __data_;
    size_type __size_;
    size_type __cap_;
};

이러한 변화의 동기는 __data_ 우선 이 더 나은 정렬로 인해 성능상의 이점이 . 성능상의 이점을 측정하려고 시도했지만 측정하기가 어려웠습니다. 성능이 나빠지지는 않으며 약간 더 나아질 수 있습니다.

플래그는주의해서 사용해야합니다. 다른 ABI이며 실수로 std::string다른 설정으로 컴파일 된 libc ++와 혼합되면 _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT런타임 오류가 발생합니다.

이 플래그는 libc ++ 공급 업체에서만 변경하는 것이 좋습니다.


답변

의 libc ++ 구현은 조금 복잡하다, 나는 그것의 대체 설계를 무시하고 리틀 엔디안 컴퓨터를 가정합니다 :

template <...>
class basic_string {
/* many many things */

    struct __long
    {
        size_type __cap_;
        size_type __size_;
        pointer   __data_;
    };

    enum {__short_mask = 0x01};
    enum {__long_mask  = 0x1ul};

    enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
                      (sizeof(__long) - 1)/sizeof(value_type) : 2};

    struct __short
    {
        union
        {
            unsigned char __size_;
            value_type __lx;
        };
        value_type __data_[__min_cap];
    };

    union __ulx{__long __lx; __short __lxx;};

    enum {__n_words = sizeof(__ulx) / sizeof(size_type)};

    struct __raw
    {
        size_type __words[__n_words];
    };

    struct __rep
    {
        union
        {
            __long  __l;
            __short __s;
            __raw   __r;
        };
    };

    __compressed_pair<__rep, allocator_type> __r_;
}; // basic_string

참고 : __compressed_pair기본적으로에 최적화 한 쌍의 빈 자료 최적화 일명 template <T1, T2> struct __compressed_pair: T1, T2 {};; 모든 의도와 목적을 위해 일반 쌍으로 간주 할 수 있습니다. 그 중요성 std::allocator은 무국적이므로 비어 있기 때문에 나타납니다 .

좋아, 이건 좀 날것 이니까 역학을 확인 해보자! 내부적으로 많은 함수는 문자열이 또는 표현을 사용하고 있는지 확인하기 위해 __get_pointer()자체적으로 호출하는 함수를 호출 __is_long합니다 .__long__short

bool __is_long() const _NOEXCEPT
    { return bool(__r_.first().__s.__size_ & __short_mask); }

// __r_.first() -> __rep const&
//     .__s     -> __short const&
//     .__size_ -> unsigned char

솔직히 말해서 이것이 표준 C ++인지 너무 확신하지 못합니다 (초기 하위 시퀀스 프로비저닝을 union알고 있지만 익명 공용체 및 별칭이 함께 던져지는 방법을 모릅니다), 표준 라이브러리는 정의 된 구현을 활용할 수 있습니다. 어쨌든 행동.


답변