References
- Optimized C++
Contents
- 문자열(std::string) 최적화 방법
C++의 std::string은 C++ 표준 라이브러리에서 많이 사용하는 기능 중 하나이며, 구글의 크로미움 개발자 포럼에 의하여 std::string은 크로미움의 메모리 관리자를 호출하는 모든 코드 중 절반이나 차지한다고 합니다. 문자열을 조작하는 코드는 자주 실행되기 때문에 최적화한다면 최고의 효과를 낼 수 있습니다.
Why Strings Are a Problem
문자열은 개념적으로는 단순하지만, 효율적으로 구현하기에는 약간 미묘한 부분이 있습니다. std::string의 기능 중 몇 가지 잘못 조합하면 비효율적인 방법으로 동작합니다. 아마 최신의 컴파일러에서는 이러한 부분들이 많이 개선된 것으로 보입니다.
또한 std::string은 C++ 표준에서 변경된 부분들을 반영하기 위해 수년동안 변경되어 왔습니다. C++98을 준수하는 컴파일러에서 std::string을 구현한 방법과 C++11 이후 표준을 준수하는 컴파일러에서 std::string을 구현한 방법은 서로 다를 수 있습니다. 즉, 기존에 동작하던 코드가 새로운 표준에서는 동작하지 않을 수 있습니다.
그리고 문자열에는 구현과 관계없이 사용하기에 비용이 너무 큰 함수들이 있습니다. 이 함수들은 메모리를 동적으로 할당하고, 표현식에서 값처럼 동작하여 내부에서 많은 복사를 수행합니다.
Strings Are Dynamically Allocated
문자열은 그 내용을 보관하기 위해 필요한 만큼 자동으로 크기를 키우기 때문에 편리합니다. 반면, C 라이브러리 함수(strcat(), strcpy() 등)는 고정 크기를 갖는 문자 배열을 사용합니다. 이러한 유연성을 구현하기 위해서 문자열은 동적으로 메모리를 할당합니다. 동적 할당은 대부분의 다른 C++ 기능보다 cost가 커서, 문자열은 최적화할 여지가 많습니다.
문자열을 저장하는 내부 버퍼는 고정된 크기를 갖습니다. 따라서 기존 문자열에 새 문자나 문자열을 추가하면 문자열의 길이가 길어져 내부 버퍼의 크기를 초과할 수 있습니다. 만약 내부 버퍼의 크기를 초과하면 메모리 관리자에서 새로운 버퍼를 가져오고, 문자열을 새로운 버퍼에 복사합니다.
std::string은 문자열이 길어졌을 때 내부 버퍼를 다시 할당하는 비용을 절약하기 위해 트릭을 사용합니다. 실제 필요한 만큼의 메모리 공간이 아니라 문자열 길이보다 더 큰 공간을 할당합니다. 이때 얼마나 더 큰 공간을 할당할 것인지는 구현에 따라 다릅니다. 예를 들어, 필요한 문자열의 길이보다 큰 2의 거듭제곱의 값으로 공간을 할당합니다. 즉, 필요한 문자열의 길이가 5라면 8이라는 크기의 공간을 할당하게 됩니다. 따라서 이후에 문자열의 길이를 늘려야 하는 경우가 발생하더라도 내부 버퍼에 충분한 공간이 있으면 새로운 버퍼를 할당하지 않아도 됩니다. 이 트릭의 장점은 문자열이 길어질수록 문자를 추가하는 비용은 점진적으로 상수에 가까워진다는 것입니다. 단점은 문자열이 사용하지 않는 공간을 차지한다는 것입니다.
Strings Are Values
문자열은 대입문(assignments)과 표현식(expressions)에서 값(values)처럼 동작합니다. 변수에 새로운 값을 대입할 수 있지만, 변수를 변경한다고 해서 원래 변수의 값이 변하지는 않습니다.
int i, j;
i = 3; // i has the value 3
j = i; // j also has the value 3
i = 5; // i now has the value 5, j still has the value 3하지만 문자열을 다른 문자열로 대입하는 경우도 동일한 방식으로 동작합니다. 마치 문자열 변수마다 각각의 복사본을 가진 것처럼 동작합니다.
std::string s1, s2;
s1 = "hot"; // s1 is "hot"
s2 = s1; // s2 is "hot"
s1[0] = 'n'; // s2 is still "hot", s1 is "not"문자열이 값이기 때문에 문자열 표현식의 결과도 값입니다. s1 = s2 + s3 + s4; 처럼 문자열을 연결하게 되면, s2+s3의 결과는 새로 할당된 임시 문자열 값이 됩니다. 이 임시 문자열에 s4를 연결하면 또 다른 임시 문자열 값이 됩니다. 그리고 이 값은 s1의 이전 값을 대체합니다. 그후에 첫 번째 임시 문자열과 s1의 이전 값에 동적으로 할당된 공간이 해제됩니다. 따라서 이는 메모리 관리자를 너무 많이 호출하게 됩니다.
Strings Do a Lot of Copying
문자열은 값처럼 동작하므로 한 문자열을 수정하더라도 다른 문자열은 수정되지 않습니다. 그러나 문자열에는 문자열의 내용을 변경하는 함수들도 있습니다. 이러한 함수들 때문에 각 문자열 변수는 해당 문자열의 개인 복사본이 있는 것처럼 동작해야 합니다. 이 동작을 구현하는 가장 간단한 방법은 문자열을 생성하거나, 대입하거나, 함수에 인수로 전달할 때 문자열을 복사하는 것입니다. 이 방법으로 문자열을 구현하면 대입하거나 인수로 전달하는 비용은 크지만, 함수와 const가 아닌 참조를 변형하는 비용은 크지 않습니다.
값처럼 동작하지만, 복사하는 비용이 큰 것을 설명하는 프로그래밍 용어가 있는데, 이를 "Copy on Write"라고 합니다. C++ 문서에서는 이를 축약해 COW라고 표기합니다. COW 문자열에서는 동적으로 할당된 공간을 문자열끼리 서로 공유할 수 있습니다. 공유하는 저장 공간을 사용하는지 알고 싶다면, 참조 카운트(reference count)를 통해서 알 수 있습니다. 한 문자열을 다른 문자열에 대입하면 값이 아닌 포인터를 복사하고 참조 카운트를 증가시킵니다. 문자열을 수정하는 함수는 우선 해당 저장 공간을 가리키는 포인터가 하나만 있는지 확인하며, 만약 여러 문자열이 저장 공간을 가리키고 있다면 문자열을 변경하기 전에 먼저 새로운 저장 공간을 할당하고 문자열의 복사본을 만듭니다.
COWstring s1, s2;
s1 = "hot"; // s1 is "hot"
s2 = s1; // s2 is "hot" (s1 and s2 point to the same storage)
s1[0] = 'n'; // s1 makes a new copy of its storage before
// changing anything
// s2 is still "hot", s1 is "not"std::string이 COW 방식으로 구현되었다고 생각할 수 있지만, C++11 표준에서는 문제가 발생할 수 있기 때문에 허용되지 않습니다.
문자열이 COW 방법으로 구현된 경우, 대입이나 인수로 전달하는 비용은 크지 않습니다. 하지만 문자열을 const가 아닌 레퍼런스의 내용을 수정하면 할당 및 복사 연산을 위한 추가 비용이 발생합니다.
또한 동시성 코드에서도 비용이 큽니다. COW의 문자열을 수정하는 모든 함수와 const가 아닌 레퍼런스는 참조 카운트가 저장된 메모리에 접근합니다. 여러 스레드에서 참조 카운트에 접근할 때, 각 스레드는 메인 메모리에서 참조 카운트의 복사본을 가져오기 위해 특수한 명령(atomic 연산)을 사용해 중간에 다른 스레드가 이 값을 변경하지 않도록 합니다.
C++11 표준 이후에는 우측값 참조와 이동의미론(move semantics) 덕분에 복사 비용이 많이 감소하였습니다. 함수의 인수가 우측값에 대한 참조일 때, 문자열이 실제로 우측값 표현식이라면 내용이 아닌 포인터를 복사하기 때문에 비용이 낮고 복사본을 만들지 않습니다.
문자열 최적화 첫 번째
큰 프로그램을 프로파일링한다고 가정해봅시다. 그리고 그 과정에서 아래의 remove_ctrl() 함수가 프로그램에서 많은 시간을 소모한다는 사실을 알게 되었습니다. 이 함수는 ASCII 문자로 구성된 문자열에서 control 문자를 제거합니다.
std::string remove_ctrl(std::string s)
{
std::string result;
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result = result + s[i];
}
return result;
}겉으로 보기에는 아무런 문제가 없어 보이지만, 여러 이유로 성능이 좋지 않습니다.
remove_ctrl()은 반복문에서 인수로 전달된 문자열 s의 각 문자를 처리하는데, 이 부분이 바로 최적화해야 할 곳입니다. if문은 문자열에서 하나의 문자를 가져와 리터럴 상수와 비교하는데, 이 부분은 문제가 없습니다. 하지만, if문의 결과가 true일 때 실행되는 문장(line 6)은 이야기가 다릅니다.
문자열의 연결 연산자(concatenation operator)는 비용이 큽니다. 그렇다면 문자열 연결 연산자는 어떤 방법으로 동작할까요?
문자열 연결 연산자는 먼저 메모리 관리자를 호출해 연결된 문자열을 저장하는 임시 문자열 객체를 할당합니다. remove_ctrl()의 인수가 출력 가능한 문자열이라면, s에 있는 거의 모든 문자마다 임시 문자열 객체를 생성합니다. 예를 들어, 문자열이 100개의 문자로 이루어져 있다면 임시 문자열을 위한 저장 공간을 만들기 위해 메모리 관리자를 100번 호출하고 저장 공간을 해제하기 위해 또 100번 호출하게 됩니다.
문자열을 연결한 결과를 저장하기 위해 임시 문자열을 할당할 뿐만 아니라 문자열 표현식을 result에 대입할 때, 문자열을 어떻게 구현했느냐에 따라 문자열을 추가로 할당할 수 있습니다.
- COW 방식을 사용한다면, 대입 연산자는 포인터를 복사하고 참조 카운트를 증가시킴
- 문자열을 공유하지 않는 버퍼로 구현했다면, 대입 연산자는 임시 문자열의 내용을 복사함. 단순하거나 result의 버퍼가 충분한 공간을 가지지 않는 경우, 대입 연산자는 새 버퍼를 할당해 복사. 결국 복사 연산과 할당이 100번씩 호출됨
- 문자열을 C++11 스타일의 우측값 참조 및 이동의미론으로 구현했다면, 컴파일러는 result의 이동 대입 연산자를 호출할 수 있음. 이는 연결 표현식의 결과가 우측값이기 때문이다. 결과적으로 프로그램을 효율적으로 포인터를 복사하게 된다.
또한 연결 연산이 실행될 때마다 이전에 처리했던 모든 문자를 임시 문자열에 복사합니다. 따라서 문자열이 n개의 문자로 이루어져 있다면 remove_ctrl()은 O(\(n^2\))개의 문자들을 복사합니다.
아래에서 최적화된 코드들을 살펴보면서, 얼마나 성능이 개선되었는지 측정하기 위해 간단한 테스트 함수와 시간을 측정하기 위한 Stopwatch를 구현했습니다. 전체 코드는 포스팅의 마지막 하단에 첨부해두도록 하겠습니다.
테스트를 위한 문자열은 다음과 같습니다.
std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07");
std::string test("Now is the time for all good men to come to the aid of their country. ");
std::string result;
s = s + s + s;
test = test + test + test;s는 인수로 전달할 문자열이며, result는 함수를 수행한 결과를 저장하는 문자열입니다. 그리고 test는 함수의 결과와 비교할 결과를 저장하고 있는 문자열입니다. 모든 테스트는 릴리즈 모드로 실행하였으며, 각 함수를 1000번 반복 수행할 때의 시간을 측정하였습니다.
먼저 remove_ctrl()를 한 번 호출하는데 평균 15.517us가 걸렸습니다. 이를 기준으로 성능이 얼마나 개선되었는지 비교해보도록 하겠습니다.
Use Mutating String Operations to Eliminate Temporaries
먼저 할당 및 복사 연산을 제거하여 remove_ctrl()을 최적화해보도록 하겠습니다. 아래 함수는 개선된 remove_ctrl() 함수를 보여주는데, 임시 문자열 객체를 생성하는 기존 연산자 대신 문자열의 내용을 변경하는 연결 연산자 '+='를 사용합니다(line 6).
std::string remove_ctrl_mutating(std::string s)
{
std::string result;
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
return result;
}연산자를 하나만 바꾸었을 뿐인데 성능에는 큰 영향을 미치는 것을 확인할 수 있습니다. 위 코드로 시간을 측정한 결과 평균 1.159us가 걸렸습니다(약 13배 개선). 연결 표현식의 결과를 저장하려고 임시 문자열 객체를 할당하는 코드와 임시 문자열 객체와 연관된 복사 및 삭제 연산을 모두 제거하여 성능이 개선되었습니다. 문자열의 구현 방법에 따라 대입할 때 발생하는 할당 및 복사 연산 또한 같이 제거되었습니다.
Reduce Reallocation by Reserving Storage
remove_ctrl_mutating() 함수는 여전히 result에 문자열을 더하면서 점점 길어지도록 합니다. 이는 내부 버퍼의 크기를 초과하면 메모리 관리자를 통해 새로운 버퍼를 할당하고 result를 새로운 버퍼에 복사한다는 것을 의미합니다. 이때, 새 버퍼의 크기를 기존 버퍼 크기의 2배로 늘리도록 구현되어 있을 수 있는데, 만약 그렇다면 100개의 문자로된 문자열을 저장하기 위해 재할당을 최대 8번 수행해야 합니다.
문자열이 대부분 출력 가능하고 일부만 제거될 control 문자라면, 인수로 전달된 문자열 s의 길이를 result 문자열의 최종 길이로 추정할 수 있습니다. 아래의 함수는 std::string의 reserve() 멤버 함수를 통해 추정한 저장 공간을 미리 할당하여 remove_ctrl_mutating()의 성능을 개선합니다. reserve()를 사용하면 문자열 버퍼를 재할당하는 연산을 제거할 수 있을 뿐만 아니라 함수에서 접근하는 데이터의 캐시 지역성(cache locality)도 향상됩니다.
std::string remove_ctrl_reserve(std::string s) {
std::string result;
result.reserve(s.length());
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
return result;
}이렇게 수정하면 성능이 또한 크게 개선됩니다. remove_ctrl_reserve() 함수를 한 번 호출하는데 측정된 시간은 평균 0.6037us입니다. remove_ctrl_mutating()보다 약 2배 더 빨라졌습니다.
Eliminate Copying of String Arguments
지금까지는 메모리 관리자를 잠재적으로 호출하는 코드를 제거하여 remove_ctrl() 함수를 최적화하였습니다. 이것 말고 또 제거할 수 있는 코드가 있는지 계속 찾아봅시다.
문자열 표현식을 함수로 전달하면 형식 인수(formal arguments, 여기서 s)를 복사 생성합니다. 이는 문자열의 구현 방법에 따라 달라질 수 있습니다.
아래 함수 remove_ctrl_ref_args()는 호출 시 s를 절대로 복사하지 않도록 개선한 함수입니다.
std::string remove_ctrl_ref_args(std::string const& s)
{
std::string result;
result.reserve(s.length());
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
return result;
}이 함수는 s를 수정하지 않기 때문에 따로 복사할 필요가 없습니다. 대신 const 레퍼런스를 사용하는데, 이는 할당 비용을 절약합니다. 할당은 비용이 크기 때문에, 비록 하나이더라도 제거할만한 가치가 있습니다.
테스트 결과, 이 함수를 호출하는데 평균 0.6425us가 걸렸습니다. 의외의 결과가 나왔는데, 큰 차이는 없지만 방금 위에서 살펴본 remove_ctrl_reserve()보다 조금 느려졌습니다(VS 2019기준: 사실 테스트를 수행할 때마다 더 빨리 나오는 경우도 있었습니다).
함수 호출 시 문자열의 복사를 제거하여 할당 비용을 절약한 것은 분명합니다. 그렇다면 s를 문자열 참조로 바꿔서 절약한 비용을 다른 곳에서 소비한다는 것을 의미합니다.
여기서 레퍼런스 변수는 포인터로 구현됩니다. remove_ctrl_reserve()에서는 s를 역참조(dereference)할 필요가 없었지만, remove_ctrl_ref_rgs()에서는 s가 레퍼런스이기 때문에 포인터를 역참조해야 합니다. 결국 포인터를 역참조하는 비용이 추가되어서 이러한 결과가 나오게 된 것입니다.
Eliminate Pointer Dereference Using Iterators
위에서 발생한 문제는 문자열에 이터레이터를 사용하면 해결할 수 있습니다. 문자열 이터레이터는 문자 버퍼를 가리키는 포인터인데, 포인터를 역참조하는 데 드는 비용을 절약할 수 있습니다.
std::string remove_ctrl_ref_args_it(std::string const& s)
{
std::string result;
result.reserve(s.length());
for (auto it = s.begin(), end = s.end(); it != end; ++it) {
if (*it >= 0x20)
result += *it;
}
return result;
}위 함수로 테스트한 결과, 한 번 호출하는데 0.3918us가 걸렸습니다. 즉, 이터레이터를 사용하지 않은 버전보다 확실히 성능이 개선되었습니다.
그렇다면, s를 레퍼런스로 바꾸었던 작업은 성능이 개선되었을까요?
이를 확인하기 위해 remove_ctrl_reserve()의 이터레이터 버전(remove_ctrl_reserve_it())을 작성하여 테스트해봤습니다.
std::string remove_ctrl_reserve_it(std::string s) {
std::string result;
result.reserve(s.length());
for (auto it = s.begin(), end = s.end(); it != end; ++it) {
if (*it >= 0x20)
result += *it;
}
return result;
}위 함수를 테스트한 결과, 한 번 호출하는데 평균 0.5019us가 걸렸습니다. 즉, 인수를 레퍼런스로 변경하여 성능이 개선된 것을 확인할 수 있습니다.
이터레이터 버전을 작성하면서 또 다른 최적화 작업이 사실 숨어 있습니다. 바로 for문을 제어하는데 사용하는 s.end() 값을 반복문의 초기화 부분에서 캐싱하였습니다.
Eliminate Copying of Returned String Values
remove_ctrl() 함수는 결과를 값으로 리턴합니다. C++은 결과를 복사 생성해서 반환하지만, 컴파일러는 가능한 경우 복사 생성을 생략할 수 있습니다. 복사가 발생하지 않도록 하는 몇 가지 방법이 있는데, 모든 C++ 버전 및 문자열 구현에서 동작하는 한 가지 방법은 문자열을 out 파라미터로 반환하는 것입니다. 이 방법은 컴파일러가 복사 생성을 생략할 때 실제로 수행하는 방법입니다.
void remove_ctrl_ref_result_it(std::string& result, std::string const& s)
{
result.clear();
result.reserve(s.length());
for (auto it = s.begin(), end = s.end(); it != end; ++it) {
if (*it >= 0x20)
result += *it;
}
}프로그램이 remove_ctrl_ref_result_it() 함수를 호출하면 문자열 변수를 가리키는 레퍼런스를 형식 인수인 result로 전달합니다.
위 함수로 테스트한 결과, 한 번 호출하는데 평균 0.2901us가 걸렸습니다. 이전 결과보다 약 1.35배 빨라졌습니다.
이 함수는 매우 효율적이지만, 인터페이스가 remove_ctrl() 함수와 다르므로 잘못 호출할 가능성이 있습니다.
Use Character Arrays Instead of Strings
프로그램의 성능을 극한으로 끌어올려야 한다면, 아래 함수처럼 C++ 표준 라이브러리 대신 C 스타일의 문자열 함수를 사용할 수 있습니다. C 스타일의 문자열 함수는 std::string보다 사용하기 더 어렵지만, 개선된 성능은 놀랍습니다. C 스타일의 문자열 함수를 사용하려면 문자 버퍼를 수동으로 할당하고 해제하거나 크기에 딱 맞는 정적 배열을 사용해야 합니다. 메모리가 제한된 경우 정적 배열을 선언하는 것은 문제가 됩니다. 그러나 일반적으로 로컬 저장소(stack)에 큰 임시 버퍼를 정적으로 선언할 공간이 있습니다. 이 버퍼를 사용하면 함수가 종료될 때 무시할 수 있는 정도의 수준으로 바꿔줍니다. 극도로 제한된 임베디드 환경이 아니라면 스택에 1000개나 10000개의 문자를 저장하는 버퍼를 선언해도 아무런 문제가 없습니다.
void remove_ctrl_cstrings(char* destp, char const* srcp, size_t size)
{
for (size_t i = 0; i < size; ++i) {
if (srcp[i] >= 0x20)
*destp++ = srcp[i];
}
*destp = 0;
}위 함수를 테스트한 결과, 한 번 호출하는데 평균 0.0001us가 걸렸습니다. 성능이 놀라울 정도로 개선되었는데, 그 이유는 여러 함수 호출을 없애고 캐시 지역성(cache locality)를 향상했기 때문입니다.
그러나 캐시 지역성이 우수하면 성능 측정에서 오해의 소지가 발생할 수 있습니다. 일반적으로 remove_ctrl_cstrings() 함수 호출 사이에 다른 작업이나 연산이 있다면 캐시를 비우게 됩니다. 하지만 다른 연산없이 반복문에서 remove_ctrl_cstrings()만 호출하면 명령과 데이터가 캐시에 유지됩니다.
또 다른 영향은 기존의 인터페이스와 많이 다르다는 점입니다. 만약 여러 곳에서 이 함수를 호출한다면, 코드를 모두 바꾸기 위한 노력이 필요합니다. 따라서 이 함수는 개발자가 함수를 전부 다시 코딩하고 인터페이스를 바꾸는 노력 대비 얻을 수 있는 성능이 얼마나 되는지 보여주는 예시가 됩니다.
아래의 결과는 실제 함수들을 릴리즈 모드에서 테스트한 결과입니다(각 함수를 1000번 호출하여 수행된 시간).
메모리 할당 및 관려 복사 연산을 제거하여 꽤 놀라운 성능 개선을 이루었습니다.
시간 측정에 영향을 주는 인자로는 프로세스, 기본 클럭 속도, 메모리 버스 주파수, 컴파일러, 최적화 설정 등이 있습니다.
문자열 최적화 두 번째
성능을 개선할 수 있는 방법은 더 있습니다. 아래에서는 고려할 만한 몇 가지 옵션을 더 살펴보겠습니다.
Use a Better Algorithm
한 가지 옵션은 알고리즘을 개선하는 것입니다. 원래의 함수인 remove_ctrl()은 한 번에 하나의 문자를 결과 문자열로 복사하는 간단한 알고리즘을 사용합니다. 하지만 이 알고리즘은 매우 비효율적입니다. 아래의 개선 코드는 부분 문자열 전체를 결과 문자열로 이동해 알고리즘을 개선하였습니다.
std::string remove_ctrl_block(std::string s)
{
std::string result;
for (size_t b = 0, i = b, e = s.length(); b < e; b = i + 1) {
for (i = b; i < e; ++i) {
if (s[i] < 0x20) break;
}
result = result + s.substr(b, i - b);
}
return result;
}이 알고리즘을 사용하면 할당 및 복사의 연산 횟수가 줄어드는 효과가 있습니다. 또한 remove_ctrl_block()에는 외부 for문의 반복문 종료를 처리하는 인수 문자열의 길이를 캐싱하는 최적화 방법도 사용되었습니다.
위의 함수로 테스트한 결과, 한 번 호출하는데 평균 1.9386us가 걸렸으며 약 7~8배 정도 빠릅니다.
이 함수를 기반으로 연결 연산자를 '+=' 연산자로 바꾼 remove_ctrl_block_mutate() 함수는 한 번 호출하는데 평균 01.4487us가 걸리며 성능이 약간 개선되었습니다. 하지만 substr() 함수는 여전히 임시 문자열을 생성합니다.
이는 append() 함수를 사용하여 임시 문자열을 만들지 않고, 부분 문자열을 복사할 수 있습니다. 이러한 개선이 적용된 remove_ctrl_block_append() 함수로 테스트한 결과, 한 번 호출하는데 평균 0.4205us가 걸렸습니다.
std::string remove_ctrl_block_mutate(std::string s)
{
std::string result;
result.reserve(s.length());
for (size_t b = 0, i = b, e = s.length(); b < e; b = i + 1) {
for (i = b; i < e; ++i) {
if (s[i] < 0x20) break;
}
result += s.substr(b, i - b);
}
return result;
}
std::string remove_ctrl_block_append(std::string s)
{
std::string result;
result.reserve(s.length());
for (size_t b = 0, i = b; b < s.length(); b = i + 1) {
for (i = b; i < s.length(); ++i) {
if (s[i] < 0x20) break;
}
result.append(s, b, i - b);
}
return result;
}이처럼 좋은 알고리즘을 사용하면 성능을 많이 향상시킬 수 있습니다.
위 함수들을 기반으로 result의 메모리 공간을 예약하고 인수의 복사를 제거한 remove_ctrl_block_args() 함수는 한 번 호출하는데 평균 0.3099us가 걸렸고, 반환값의 복사본을 제거한 remove_ctrl_block_ret() 함수는 한 번 호출하는데 0.2639us가 걸렸습니다.
마지막으로 remove_ctrl_block_ret() 함수에 이터레이터를 사용한 버전인 remove_ctrl_block_ret_it()를 사용했는데, 이를 테스트한 결과 평균 0.2205us가 걸려 성능이 개선되었습니다.
std::string의 erase() 멤버 함수를 사용해 인수 문자열의 control 문자를 제거하는 방법으로 성능을 개선할 수도 있습니다.
std::string remove_ctrl_erase(std::string s)
{
for (size_t i = 0; i < s.length(); )
if (s[i] < 0x20)
s.erase(i, 1);
else ++i;
return s;
}이 알고리즘의 장점은 s의 길이가 짧아지기 때문에 반환값을 제외하고는 재할당할 일이 절대로 없다는 것입니다. 이 함수의 성능은 뛰어난 편이며 한 번 호출하는데 평균 0.5021us가 걸리며, remove_ctrl() 보다 약 30배 가량 빠릅니다.
Use a Better Compiler
저는 비주얼 스튜디오 2019 컴파일러를 사용해 테스트를 수행했는데, 다른 버전의 컴파일러마다 아마 성능이 다르게 나올 것입니다. 무조건 최신 컴파일러라고 더 빠른건 아니며, 테스트가 필요합니다.
Use a Better String Library
std::string은 원래 사용하는 사람이 자유롭게 구현할 수 있도록 애매하게 정의되어 있습니다. C++ 표준은 효율성과 예측 가능성이라는 이유로 std::string과 관련된 새로운 구현을 대부분 제외합니다. std::string에 정의된 동작은 많은 사람들이 오랜 기간 동안 설계하면서 발전시킨 결과입니다.
- std::string은 다른 표준 라이브러리 컨테이너와 마찬가지로 문자열의 각 문자에 접근할 수 있는 이터레이터를 제공한다.
- std::string은 C 문자열과 마찬가지로 operator[]를 사용해 요소에 접근하는 배열식 인덱스 표기법을 제공하며, 또한 NULL로 끝나는 C 스타일의 문자 배열을 가리키는 포인터를 얻는 메커니즘도 제공한다.
- std::string은 BASIC 문자열과 유사하게 만든 값 의미론(value semantics)으로 구현한 연결 연산자와 값을 반환하는 함수가 있다.
- std::string은 제한된 연산 집합을 제공한다.
C++ 표준은 std::string을 C 스타일의 char 배열만큼 효율적으로 만들고 싶었고, 그래서 연속적인 메모리에 문자열을 저장하는 방법으로 구현했습니다. C++ 표준에서는 이터레이터가 임의 위치로 접근할 수 있어야 하며, COW 방법을 금지합니다.
또한 상업용 C++ 컴파일러에 포함된 std::string은 모든 상황에서 표준을 준수하며 효율성을 보장해야 합니다. 컴파일러 공급업체가 실수하면 고치기 어렵기 때문에 std::string을 최대한 단순하게 구현합니다.
표준에 정의된 std::string의 동작 때문에 몇 가지 약점이 존재합니다. 100만 개의 문자를 가진 문자열에 하나의 문자를 삽입하면, 문자열의 접미사 전체가 복사되고 재할당될 수 있습니다. 마찬가지로 값을 반환하는 모든 부분 문자열의 동작은 결과를 할당하고 복사해야 합니다. 일부 개발자들은 제한(이터레이터, 인덱스, C 문자열 접근, 값 의미론, 간결함)을 풀어 최적화할 기회를 찾기도 합니다.
Adopt a richer library for std::string
때때로 더 많은 문자열 기능을 제공하는 라이브러리르 사용하는 것이 좋습니다. std::string과 호환되는 라이브러리 중 일부는 다음과 같습니다.
- Boost string library: 토큰화, formatting, std::string을 조작할 수 있는 함수를 제공합니다. 표준 라이브러리의 <algorithm>을 자주 사용하는 사람들을 위한 라이브러리입니다.
- C++ String Toolkit Library: 이 라이브러리(StrTk)은 특히 문자열 파싱 및 토큰화에 적합하며 std::string과 호환됩니다.
Use std::stringstream to avoid value semantics
C++에는 템플릿화되어 있으며 이터레이터로 접근하고 가변 길이를 갖는 std::string, 이터레이터 기반의 std::vector<char>, 고정 크기를 갖고 배열로 NULL 문자로 끝나는 C 스타일의 문자열 등 여러 문자열 타입이 구현되어 있습니다.
C 스타일의 문자열은 사용하기 어렵지만, 위의 실험을 통해 std::string을 대체해 성능을 크게 개선할 수 있음을 확인했습니다. 그렇지만 모든 상황에 완벽하게 동작하는 문자열은 없습니다.
C++에는 또 다른 문자열이 구현되어 있는데, 바로 std::stringstream입니다. 이것은 std::ostream이 출력 파일에 수행하는 작업과 똑같은 작업을 문자열에 대해 수행합니다. std::stringstream 클래스는 데이터를 추가할 수 있는 엔티티(entity)처럼 다른 방식으로 동적으로 크기를 변경할 수 있는 버퍼(일반적으로 std::string)를 캡슐화합니다. std::stringstream은 비슷한 구현에 다른 API를 사용해 조금 더 효율적으로 코딩할 수 있게 해준다는 점을 보여줍니다.
std::stringstream의 사용법은 다음과 같습니다.
std::stringstream s;
for (int i = 0; i < 10; ++i) {
s.clear();
s << "The square of " << i << " is " << i * i << std::endl;
log(s.str());
}위 예제는 여러 최적화 기법을 사용합니다. s를 엔티티로 수정했기 때문에 삽입 표현식은 임시 변수를 생성하지 않습니다. 임시 변수를 생성하지 않으므로 할당 및 복사 연산도 수행하지 않습니다. 또한 s를 반복문 외부에서 선언하므로, 이를 통해 s의 내부 버퍼를 재사용하게 됩니다. 처음에는 반복문에서 문자를 추가하며 버퍼를 여러 번 재할당해야 했지만, 다음 반복문에서는 버퍼를 재할당할 가능성이 낮습니다.
std::string을 사용해 std::stringstream이 구현되는 경우, std::string보다 성능이 월등히 뛰어날 수 있습니다.
Use a Better Allocator
std::string 내부에는 동적으로 할당된 char 배열이 있습니다. 다음 코드는 std::string이 클래스 템플릿을 특수화한 타입이라는 것을 보여줍니다.
세 번째 템플릿 매개변수인 Alloc은 C++ 메모리 관리자를 특수화한 인터페이스인 할당자 allocator를 정의합니다. Alloc은 기본값으로 전역 C++ 메모리 할당자 함수인 ::operator new()와 ::operator delete()를 호출하는 std::allocator를 사용합니다.
new()와 delete()의 동작은 약간 복잡한데, 지금은 new()와 delete()가 매우 복잡하고 어려운 작업을 수행하고 모든 종류의 동적 변수에 대한 저장 공간을 할당하는 역할을 한다고 생각하면 됩니다. 두 연산자는 크고 작은 개체(objects), 싱글스레드와 멀티스레드 프로그램에서 동작해야 되기 때문에 모든 경우를 고려하여 설계되었습니다. 하지만 어떤 경우에는 특수화된 할당자가 더 나은 작업을 수행할 수도 있습니다. Alloc은 std::string에 특수화된 할당자를 제공하기 위해 기본값이 아닌 다른 값으로 지정할 수도 있습니다.
적당한 할당자를 사용하면 성능을 개선할 여지가 있습니다.
Eliminate String Conversion
C++에서 가장 복잡한 부분 중 하나는 문자열의 종류가 여러 가지라는 것입니다. 일반적으로 문자열 함수는 같은 종류의 문자열만 비교/대입할 수 있습니다. 또한 같은 종류의 문자열만 피연산자나 인수로 사용할 수 있습니다. 따라서 프로그래머는 다른 문자열을 사용해야 할 경우 변환을 수행해야 합니다. 문자열을 복사하거나 동적 메모리를 할당하는 변환 연산은 성능을 개선할 수 있는 부분이라고 볼 수 있습니다.
라이브러리의 변환 함수 자체를 개선할 수도 있습니다. 하지만 중요한 것은 대규모 프로그램에서 설계를 통해 변환 연산을 제한할 수 있다는 것입니다.
Conversion from C String to std::string
컴퓨터 사이클이 낭비되는 원인 중 하나는 NULL로 끝나는 문자열에서 std::string으로의 불필요한 변환 연산 때문입니다.
std::string MyClass::Name() const {
return "MyClass";
}이 함수는 문자열 상수 MyClass를 std::string으로 변환하는 과정에서 저장 공간을 할당해 문자들을 std::string에 복사합니다. std::string에는 char* 인수를 받는 생성자가 있으므로 C++에서는 자동으로 변환됩니다.
위 코드는 std::string으로 변환할 필요가 없습니다. std::string에는 char* 인수를 받는 생성자가 있으므로 Name()에서 반환된 값이 문자열에 할당되거나 문자열 인수를 사용하는 함수에 전달되면 변환이 자동으로 발생합니다. 따라서 함수를 다음과 같이 변경할 수 있습니다.
char const* MyClass::Name() const {
return "MyClass";
}이렇게 바꾸면 반환된 값을 변환하는 동작을 함수가 실제로 사용되는 지점까지 미룰 수 있습니다.
한편, 변환이 필요없는 경우도 있습니다.
char const* p = myInstance->Name(); // no conversion
std::string s = myInstance->Name(); // conversion to std::string
std::cout << myInstance->Name(); // no conversion대규모 소프트웨어 시스템에 여러 계층이 존재한다면, 문자열 변환 연산은 큰 문제가 될 수 있습니다. 예를 들어 어떤 계층이 std::string을 사용하는데, 그 아래 계층이 char*을 사용할 경우 std::string으로 변환한 결과를 다시 반대로 변환하는 코드가 있을 수 있습니다.
void HighLevelFunc(std::string s)
{
LowLevelFunc(s.c_str());
}
Converting Between Character Encodings
프로그램에서 리터럴 C 문자열(ASCII)와 UTF-8 문자열을 비교하거나 UTF-16 워드 스트림을 생성하는 XML 파서로부터 출력된 문자열을 UTF-8로 변환할 수 있습니다. 따라서 프로그램에 따라 조합할 수 있는 경우의 수가 엄청나게 많습니다.
변환 연산을 제거하는 가장 좋은 방법은 하나의 포맷을 선택해 모든 문자열을 선택한 포맷으로 저장하는 것입니다.
아래 코드는 위에서 테스트에 사용한 코드입니다.
#include <iostream>
#include <string>
#include "Timer.h"
std::string remove_ctrl(std::string s)
{
std::string result;
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result = result + s[i];
}
return result;
}
std::string remove_ctrl_mutating(std::string s)
{
std::string result;
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
return result;
}
std::string remove_ctrl_reserve(std::string s) {
std::string result;
result.reserve(s.length());
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
return result;
}
std::string remove_ctrl_reserve_it(std::string s) {
std::string result;
result.reserve(s.length());
for (auto it = s.begin(), end = s.end(); it != end; ++it) {
if (*it >= 0x20)
result += *it;
}
return result;
}
std::string remove_ctrl_ref_args(std::string const& s)
{
std::string result;
result.reserve(s.length());
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
return result;
}
std::string remove_ctrl_ref_args_it(std::string const& s)
{
std::string result;
result.reserve(s.length());
for (auto it = s.begin(), end = s.end(); it != end; ++it) {
if (*it >= 0x20)
result += *it;
}
return result;
}
void remove_ctrl_ref_result(std::string& result, std::string const& s)
{
result.clear();
result.reserve(s.length());
for (int i = 0; i < s.length(); ++i) {
if (s[i] >= 0x20)
result += s[i];
}
}
void remove_ctrl_ref_result_it(std::string& result, std::string const& s)
{
result.clear();
result.reserve(s.length());
for (auto it = s.begin(), end = s.end(); it != end; ++it) {
if (*it >= 0x20)
result += *it;
}
}
void remove_ctrl_cstrings(char* destp, char const* srcp, size_t size)
{
for (size_t i = 0; i < size; ++i) {
if (srcp[i] >= 0x20)
*destp++ = srcp[i];
}
*destp = 0;
}
std::string remove_ctrl_block(std::string s)
{
std::string result;
for (size_t b = 0, i = b, e = s.length(); b < e; b = i + 1) {
for (i = b; i < e; ++i) {
if (s[i] < 0x20) break;
}
result = result + s.substr(b, i - b);
}
return result;
}
std::string remove_ctrl_block_mutate(std::string s)
{
std::string result;
result.reserve(s.length());
for (size_t b = 0, i = b, e = s.length(); b < e; b = i + 1) {
for (i = b; i < e; ++i) {
if (s[i] < 0x20) break;
}
result += s.substr(b, i - b);
}
return result;
}
std::string remove_ctrl_block_append(std::string s)
{
std::string result;
result.reserve(s.length());
for (size_t b = 0, i = b; b < s.length(); b = i + 1) {
for (i = b; i < s.length(); ++i) {
if (s[i] < 0x20) break;
}
result.append(s, b, i - b);
}
return result;
}
std::string remove_ctrl_block_args(std::string const& s)
{
std::string result;
result.reserve(s.length());
for (size_t b = 0, i = b, e = s.length(); b < e; b = i + 1) {
for (i = b; i < e; ++i) {
if (s[i] < 0x20) break;
}
result.append(s, b, i - b);
}
return result;
}
void remove_ctrl_block_ret(std::string& result, std::string const& s)
{
result.clear();
result.reserve(s.length());
for (size_t b = 0, i = b, e = s.length(); b < e; b = i + 1) {
for (i = b; i < e; ++i) {
if (s[i] < 0x20) break;
}
result.append(s, b, i - b);
}
}
void remove_ctrl_block_ret_it(std::string& result, std::string const& s)
{
result.clear();
result.reserve(s.length());
for (auto b = s.begin(), i = b, e = s.end(); b != e; b = i + 1) {
for (i = b; i != e; ++i) {
if (*i < 0x20) break;
}
result.append(b, i);
}
}
std::string remove_ctrl_erase(std::string s)
{
for (size_t i = 0; i < s.length(); )
if (s[i] < 0x20)
s.erase(i, 1);
else ++i;
return s;
}
std::string remove_ctrl_erase_it(std::string s)
{
for (auto i = s.begin(); i != s.end(); )
if (*i < 0x20)
s.erase(i);
else ++i;
return s;
}
int test_strings(int test_no, unsigned int iterations = 1000)
{
typedef unsigned int counter_t;
std::string s("\07Now is the time\07 for all good men\r\n to come to the aid of their country. \07");
std::string test("Now is the time for all good men to come to the aid of their country. ");
std::string result;
s = s + s + s;
test = test + test + test;
switch (test_no) {
default:
return -1;
case 0:
return 9;
case 1:
{
Stopwatch sw("remove_ctrl()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl(s);
}
break;
case 2:
{
Stopwatch sw("remove_ctrl_mutating()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_mutating(s);
}
break;
case 3:
{
Stopwatch sw("remove_ctrl_reserve()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_reserve(s);
}
{
Stopwatch sw("remove_ctrl_reserve_it()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_reserve_it(s);
}
break;
case 4:
{
Stopwatch sw("remove_ctrl_ref_args()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_ref_args(s);
}
{
Stopwatch sw("remove_ctrl_ref_args_it()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_ref_args_it(s);
}
break;
case 5:
{
Stopwatch sw("remove_ctrl_ref_result_it()");
for (counter_t i = 0; i < iterations; ++i)
remove_ctrl_ref_result_it(result, s);
}
break;
case 6:
{
Stopwatch sw("remove_ctrl_cstrings()");
for (counter_t i = 0; i < iterations; ++i) {
char a[1000];
remove_ctrl_cstrings(a, s.data(), s.length());
}
}
break;
case 7:
{
Stopwatch sw("remove_ctrl_block()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_block(s);
}
break;
case 8:
{
Stopwatch sw("remove_ctrl_block_mutate()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_block_mutate(s);
}
{
Stopwatch sw("remove_ctrl_block_append()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_block_append(s);
}
{
Stopwatch sw("remove_ctrl_block_args()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_block_args(s);
}
{
Stopwatch sw("remove_ctrl_block_ret()");
for (counter_t i = 0; i < iterations; ++i)
remove_ctrl_block_ret(result, s);
}
{
Stopwatch sw("remove_ctrl_block_ret_it()");
for (counter_t i = 0; i < iterations; ++i)
remove_ctrl_block_ret_it(result, s);
}
break;
case 9:
{
Stopwatch sw("remove_ctrl_erase()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_erase(s);
}
{
Stopwatch sw("remove_ctrl_erase_it()");
for (counter_t i = 0; i < iterations; ++i)
result = remove_ctrl_erase_it(s);
}
break;
}
return 0;
}
int main(int argc, char* argv[])
{
int total_test = test_strings(0);
for (int i = 1; i <= total_test; i++) {
test_strings(i);
}
}
/* Timer.h */
#pragma once
#include <chrono>
using namespace std::chrono;
class TimerBaseChrono {
public:
typedef double tick_t;
TimerBaseChrono() : m_start(system_clock::time_point::min()) {}
void clear() {
m_start = system_clock::time_point::min();
}
bool is_started() const {
return (m_start != system_clock::time_point::min());
}
void start() {
m_start = system_clock::now();
}
double get_ms() {
if (is_started()) {
system_clock::duration diff;
diff = system_clock::now() - m_start;
return static_cast<double>(duration_cast<nanoseconds>(diff).count()) / 1000000.f;
}
return 0;
}
private:
system_clock::time_point m_start;
};
#include "Stopwatch.h"
typedef basic_stopwatch<TimerBaseChrono> Stopwatch;
/* Stopwatch.h */
#pragma once
#include <iostream>
template<typename T>
class basic_stopwatch : public T
{
public:
typedef typename T BaseTimer;
typedef typename T::tick_t tick_t;
// create, optionally start timeing an activity
explicit basic_stopwatch(bool start);
explicit basic_stopwatch(char const* activity = "stopwatch", bool start = true);
basic_stopwatch(std::ostream& log, char const* activity = "stopwatch", bool start = true);
// stop and destroy a stopwatch
~basic_stopwatch();
// get last lap time
tick_t get_lap() const;
// predicate: return true if the stopwatch is running
bool is_started() const;
// show accumulated time, keep running, set/return lap
tick_t show(char const* event = "show");
// (re)start a stopwatch, set/return lap time
tick_t start(char const* event_name = "start");
// stop a running stopwatch, set/return lap time
tick_t stop(char const* event_name = "stop");
private:
char const* m_activity; // "activity" string
tick_t m_lap; // lap time (time of last stop or 0)
std::ostream& m_log; // stream on which to log events
};
// performs a start() if start_now == true
template<typename T>
inline basic_stopwatch<T>::basic_stopwatch(bool start_now)
: m_activity("Stopwatch")
, m_lap(0)
, m_log(std::cout)
{
if (start_now)
start();
}
template<typename T>
inline basic_stopwatch<T>::basic_stopwatch(char const* activity, bool start_now)
: m_activity(activity && activity[0] ? activity : nullptr)
, m_lap(0)
, m_log(std::cout)
{
if (start_now) {
if (m_activity)
start();
else
start(nullptr);
}
}
template<typename T>
inline basic_stopwatch<T>::basic_stopwatch(std::ostream& log, char const* activity, bool start_now)
: m_activity(activity&& activity[0] ? activity : nullptr)
, m_lap(0)
, m_log(std::cout)
{
if (start_now) {
if (m_activity)
start();
else
start(nullptr);
}
}
template<typename T>
inline basic_stopwatch<T>::~basic_stopwatch()
{
if (is_started()) {
if (m_activity)
stop();
else
stop(nullptr);
}
}
template<typename T>
inline bool basic_stopwatch<T>::is_started() const
{
return BaseTimer::is_started();
}
template<typename T>
inline basic_stopwatch<T>::tick_t basic_stopwatch<T>::get_lap() const
{
return m_lap;
}
template<typename T>
inline basic_stopwatch<T>::tick_t basic_stopwatch<T>::show(char const* event_name)
{
if (is_started()) {
m_lap = BaseTimer::get_ms();
if (event_name && event_name[0]) {
if (m_activity)
m_log << m_activity << ": ";
m_log << event_name << " at " << m_lap << " ms" << std::endl << std::flush;
}
}
else {
if (m_activity)
m_log << m_activity << ": not started" << std::endl << std::flush;
}
return m_lap;
}
template<typename T>
inline basic_stopwatch<T>::tick_t basic_stopwatch<T>::start(char const* event_name)
{
if (is_started()) {
stop(event_name);
}
else {
if (event_name && event_name[0]) {
if (m_activity)
m_log << m_activity << ": ";
m_log << event_name << std::endl << std::flush;
}
}
BaseTimer::start();
return m_lap;
}
template<typename T>
inline basic_stopwatch<T>::tick_t basic_stopwatch<T>::stop(char const* event_name)
{
if (is_started()) {
m_lap = BaseTimer::get_ms();
if (event_name && event_name[0]) {
if (m_activity)
m_log << m_activity << ": ";
m_log << event_name << " " << m_lap << " ms" << std::endl << std::flush;
}
}
BaseTimer::clear();
return m_lap;
}'프로그래밍 > C & C++' 카테고리의 다른 글
| [C/C++] Program Execution (0) | 2022.11.04 |
|---|---|
| [C/C++] 간단한 프로그램 컴파일/링크 과정 (1) | 2022.11.03 |
| [C++] Error Handling (2) (0) | 2022.03.06 |
| [C++] Error Handling (1) (0) | 2022.03.06 |
| [C++] 멀티스레딩 프로그래밍 (2) (0) | 2022.03.03 |
댓글