에서 최적화 및 코드 스타일에 대한 C ++ 질문 몇 가지 답변의 사본을 최적화의 맥락에서 “SSO”라고 std::string. 그 맥락에서 SSO는 무엇을 의미합니까?
“단일 사인온”이 아닙니다. 아마도 “공유 문자열 최적화”입니까?
답변
배경 / 개요
자동 변수 ( malloc/에서 호출하지 않고 만드는 변수 인 “스택에서” new)에 대한 작업은 일반적으로 사용 가능한 저장소 ( “힙”,을 사용하여 만든 변수)와 관련된 작업보다 훨씬 빠릅니다 new. 그러나 자동 배열의 크기는 컴파일 타임에 고정되지만 무료 저장소의 배열 크기는 고정되지 않습니다. 또한 스택 크기는 제한적이며 (일반적으로 몇 MiB), 무료 저장소는 시스템 메모리에 의해서만 제한됩니다.
SSO는 Short / Small String Optimization입니다. A는 std::string일반적으로 통화에 것처럼 비슷한 성능 특성을 제공하는 무료 저장 ( “힙”)에 대한 포인터로 문자열을 저장합니다 new char [size]. 이렇게하면 매우 큰 문자열의 스택 오버플로가 방지되지만 특히 복사 작업의 경우 속도가 느려질 수 있습니다. 최적화로서, 많은 구현은 std::string다음과 같은 작은 자동 배열 을 만듭니다 char [20]. 문자열이 20 자 이하인 경우 (이 예제에서는 실제 크기가 다름) 해당 배열에 직접 저장합니다. 이렇게하면 전화 new를 전혀 하지 않아도되므로 속도가 약간 빨라집니다.
편집하다:
나는이 답변이 그렇게 인기가있을 것으로 기대하지는 않았지만, 실제로는 “실제로”SSO의 구현을 전혀 읽지 않았다는 경고와 함께보다 현실적인 구현을하겠습니다.
구현 세부 사항
최소한 std::string다음 정보를 저장해야합니다.
- 크기
- 용량
- 데이터의 위치
크기는 std::string::size_type또는 끝에 대한 포인터로 저장 될 수 있습니다 . 유일한 차이점은 사용자가 호출 할 때 두 개의 포인터를 빼야하는지 size또는 사용자가 호출 할 때 포인터 에 a size_type를 추가 해야하는지 end입니다. 용량은 어느 쪽이든 저장할 수 있습니다.
사용하지 않는 것에 대해서는 비용을 지불하지 않습니다.
먼저 위에서 설명한 내용을 기반으로 순진한 구현을 고려하십시오.
class string {
public:
// all 83 member functions
private:
std::unique_ptr<char[]> m_data;
size_type m_size;
size_type m_capacity;
std::array<char, 16> m_sso;
};64 비트 시스템의 경우 일반적으로 std::string문자열 당 24 바이트의 ‘오버 헤드’와 SSO 버퍼에 대한 16 바이트 (패딩 요구 사항으로 인해 20 대신 16이 선택됨)가 있음을 의미합니다. 간단한 예제 에서처럼이 세 가지 데이터 멤버와 로컬 문자 배열을 저장하는 것은 실제로 의미가 없습니다. 인 경우 m_size <= 16모든 데이터를에 넣을 m_sso것이므로 용량을 이미 알고 있으므로 데이터에 대한 포인터가 필요하지 않습니다. 인 경우 m_size > 16에는 필요하지 않습니다 m_sso. 내가 그들 모두를 필요로하는 곳은 겹치지 않습니다. 공간을 낭비하지 않는 똑똑한 솔루션은 다음과 같이 보일 것입니다 (예상되지 않은 예시 목적으로 만).
class string {
public:
// all 83 member functions
private:
size_type m_size;
union {
class {
// This is probably better designed as an array-like class
std::unique_ptr<char[]> m_data;
size_type m_capacity;
} m_large;
std::array<char, sizeof(m_large)> m_small;
};
};대부분의 구현은 다음과 같다고 가정합니다.
답변
SSO는 “작은 문자열 최적화”의 약어로, 작은 문자열이 별도로 할당 된 버퍼를 사용하는 대신 문자열 클래스의 본문에 포함되는 기술입니다.
답변
다른 답변에서 이미 설명했듯이 SSO는 Small / Short String Optimization을 의미 합니다. 이 최적화의 동기는 일반적으로 응용 프로그램이 긴 문자열보다 훨씬 짧은 문자열을 처리한다는 명백한 증거입니다.
데이비드 스톤 설명한 바와 같이 위의 그의 대답에서 의 std::string클래스는 주어진 길이로 저장 내용에 대한 내부 버퍼까지를 사용하고,이을 제거해은 할 필요 동적으로 메모리를 할당합니다. 이것은 코드를 보다 효율적 이고 빠르게 만듭니다.
이 다른 관련 답변 은 내부 버퍼의 크기가 std::string구현에 따라 다르며 플랫폼마다 다릅니다 (아래 벤치 마크 결과 참조).
벤치 마크
다음은 길이가 같은 많은 문자열의 복사 작업을 벤치마킹하는 작은 프로그램입니다. 길이가 1 인 천만 개의 문자열을 복사하는 시간을 인쇄하기 시작합니다. 그런 다음 길이가 2 인 문자열로 반복합니다. 길이가 50이 될 때까지 계속 진행합니다.
#include <string>
#include <iostream>
#include <vector>
#include <chrono>
static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
static const int ARRAY_SIZE = sizeof(CHARS) - 1;
static const int BENCHMARK_SIZE = 10000000;
static const int MAX_STRING_LENGTH = 50;
using time_point = std::chrono::high_resolution_clock::time_point;
void benchmark(std::vector<std::string>& list) {
std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
// force a copy of each string in the loop iteration
for (const auto s : list) {
std::cout << s;
}
std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
std::cerr << list[0].length() << ',' << duration << '\n';
}
void addRandomString(std::vector<std::string>& list, const int length) {
std::string s(length, 0);
for (int i = 0; i < length; ++i) {
s[i] = CHARS[rand() % ARRAY_SIZE];
}
list.push_back(s);
}
int main() {
std::cerr << "length,time\n";
for (int length = 1; length <= MAX_STRING_LENGTH; length++) {
std::vector<std::string> list;
for (int i = 0; i < BENCHMARK_SIZE; i++) {
addRandomString(list, length);
}
benchmark(list);
}
return 0;
}이 프로그램을 실행 ./a.out > /dev/null하려면 문자열을 인쇄하는 시간이 계산되지 않도록해야합니다. 중요한 번호가에 인쇄되어 stderr콘솔에 표시됩니다.
MacBook 및 Ubuntu 컴퓨터의 출력으로 차트를 만들었습니다. 길이가 주어진 지점에 도달하면 문자열을 복사하는 데 시간이 크게 걸립니다. 이제 문자열이 더 이상 내부 버퍼에 맞지 않고 메모리 할당을 사용해야하는 순간입니다.
리눅스 머신에서는 줄 길이가 16에 도달하면 점프가 일어난다는 것에 주목하라. 맥북에서는 길이가 23에 도달하면 점프가 발생한다. 이는 SSO가 플랫폼 구현에 의존한다는 것을 확인시켜 준다.
우분투
맥북 프로
