Optimized C++ : 4 ~ 8장

C++공부/그 외의 C++

Optimized C++ : 4 ~ 8장

아헿헿헿 2022. 7. 7. 03:09

Chapter 4. 문자열 최적화

std::string은 C++ 표준 라이브러리에서 많이 사용되는 기능 중 하나로 문자열 조작하는 코드는 자주 실행되며 최적화한다면 좋은 결과를 낼 수 있습니다

4.1 문자열이 왜 문제인가요

문자열에는 구현과 관계없이 메모리를 동적으로 할당하지만 표현식에서는 값처럼 작동하여 복사하기에 비용이 높은 함수가 많습니다.
먼저, 문자열은 메모리를 동적으로 할당합니다.
하지만 문자열은 대입문과 표현식에서 값처럼 작동하여, 임시 문자열의 값도 할당되어야 하기때문에, 메모리 관리자를 많이 호출합니다.
값처럼 작동하지만 복사 비용이 큰 것을 COW(copy-on-write)라고 하는데, 값을 공유하다가 변경할 때만 복사하여 사용하는 것인데 표준 라이브러리에서는 제공하지 않습니다.
C++11 표준에서 우측값 참조와 이동 문법이 생기며 복사하기 보다는 이동시켜 비용이 낮게 작업이 수행 가능합니다.

4.2 문자열 최적화 첫번째 시도

먼저 문자열에 무언가를 더 더할 때 operator=를 사용하기 보다는 operator+=를 사용한다면 임시 객체가 사라지기에 효과적이게 됩니다.
만약 문자열의 길이를 사전에 어느 정도 예측이 가능하다면 reserve()로 할당하고 연산을 진행하는 것이 좋습니다.
변경하지 않는다면 인자로 받는 std::string은 const std::string&와 같이 참조자 형태로 받는 것이 좋습니다. 하지만 참조자라는 것은 컴파일러에서 포인터로서 해석이 되고, 이를 역참조한 포인터에 접근하는 것이기 때문에 성능이 저하될 수도 있습니다.
따라서 위와 같은 경우에는 포인터를 역참조하게 하는 것이 아닌, iterator를 소환하여 해결할 수 있습니다.
만약 결과값도 std::string의 형태라면, 지역 변수를 return 하기 보다는 밖에서 참조 형태의 인자를 받아 이에 할당하는 것도 괜찮지만, 잘 못 사용하게 되는 경우도 존재합니다.
성능을 최대한으로 하고 싶다면 C 스타일의 문자열 함수를 사용할 수 있습니다. 이는 여러 함수 호출과 캐시 지역성을 향상하기에 성능이 높아집니다.

4.3 문자열 최적화 두번째 시도

자체적으로 더 나은 알고리즘을 사용하는 것이 가장 좋은 방법으로 작동할 때도 있습니다.
더 좋은 컴파일러를 사용하면 더 좋은 결과를 낼 수도 있습니다.
더 좋은 문자열 라이브러리를 사용하면 더 많은 기능을 가져 선택의 폭도 넓어지고 성능이 좋아질 수 있습니다.
std::stringstream은 데이터를 추가할 수 있는 엔티티처럼 크기를 동적으로 바꿀 수 있는 버퍼를 다른 방법으로 캡슐화하여 조금 더 효율적으로 코딩이 가능합니다.
std::string_view, folly_fbstring과 같은 다른 다양한 라이브러리로 std::string을 대체하는 것도 하나의 방법입니다.
좀 더 좋은 할당자를 이용한다면, 효율이 올라갑니다.

4.4 문자열 변환 연산 제거하기

c 문자열에서 std::string으로의 불필요한 변환 연산을 막는 것이 좋습니다.
리터럴 c 문자열과 UTF-8 문자열을 비교 하는 경우와 같이, 문자 인코딩 사이의 변환을 하나의 형식을 택해 모든 문자열을 선택한 형식으로 바꾸어 저장하는 것으로 막을 수 있습니다.

Chapter 5. 알고리즘 최적화

5.1 알고리즘의 시간 비용

시간 비용은 함수의 입력값에 따라 알고리즘의 비용이 얼마나 증가하는 지를 추상적으로 나타낸 수학 함수입니다.
성능을 고려하는 데에 있어, 순서에 따라 성능이 바뀐다면, 최악을 고려해야합니다.
상환 시간 비용은 입력값이 클 때 전체 시간 비용을 입력값으로 나눈 평균 시간 비용을 의미합니다.

5.2 검색과 정렬을 최적화하는 툴킷

평균적으로 시간이 적은 알고리즘을 선택하고, 데이터의 특징에 따라 더 빠른 특정한 알고리즘을 선택합니다.

5.3 효율적인 검색 알고리즘

선형 검색 - O(n)으로 가장 일반적이며 정렬되지 않은 테이블에서 사용가능합니다.
이진 검색 - O(logn)으로 성능은 뛰어나지만 가장 빠르진 않습니다. 입력 데이터가 키를 기준으로 정렬되어 있어야만 합니다.
보간 검색 - O(loglogn)으로 키의 부가적 정보를 사용하여 키가 균일하게 분포되어 있으면 성능이 매우 뛰어납니다.
해싱 검색 - O(1)으로 키를 해시 테이블의 배열 색인으로 변환하여 빠르게 찾습니다. 최악의 경우는 O(n)으로 검색할 레코드 보다 해시 테이블 항목이 많은 경우도 존재합니다.

5.4 효율적인 정렬 알고리즘

퀵 정렬이 항상 빠르지는 않고 최악에는 O(n^2)의 성능을 보이기에 입력 데이터에 대해서 알고나서 정렬을 선택하는 것이 좋습니다.

5.5 최적화 패턴

사전 계산 - 자주 사용하는 코드를 미리 계산하여 실행 횟수가 많은 부분의 계산량을 줄이는 최적화 기법입니다. 이는 컴파일 타임에 특정 인수를 갖는 템플릿 함수 호출도 계산이 가능합니다.
지연 계산 - 계산 코드를 실제로 필요한 부분과 최대한 가까운 곳으로 미뤄서 계산하는 방법으로, 모든 실행 경로에서 계산할 필요가 없다면 필요한 곳에서만 계산하도록 만듭니다. 예로 COW가 존재합니다.
배칭 - 여러 작업을 함께 처리하는 것으로, 반복된 함수 호출 코드와 한 번에 하나씩 처리할 떄 발생하는 계산 코드를 제거할 수 있습니다.
캐싱 - 필요할 때마다 결과를 다시 계산하지 않고 저장한 뒤 재사용해 계산량을 줄이는 최적화 기법입니다.
특수화 - 어떤 특정 상황에서 필요하지 않은 고비용 계산을 제거하는 방법입니다. std::swap을 특수화하는 것과 같습니다.
더 큰 조각 선택하기 - 반복 과정에서 생기는 오버헤드를 줄이고 반복 횟수를 줄이는 방법입니다. 예를 들어 커널로 보내는 함수의 호출 횟수를 줄이는 것입니다.
힌팅 - 힌트를 사용해 연산 비용과 계산량을 줄이는 최적화 기법입니다.
예상 경로 최적화 - if문을 무작위 순서로 배치했다면, 더 확률이 높은 구문을 앞으로 내보내는 방법입니다.
해싱 - 입력값이 큰 자료구조나 길이가 긴 문자열을 해시로 정수로 변환하여 사용하는 방법입니다.
이중 검사 - 비용이 크지 않은 검사로 몇몇 경우를 배제하고 필요하다면 비용이 큰 후속 검사로 다른 모든 경우를 배제하는 최적화 기법입니다.

Chapter 6. 동적 할당 변수 최적화

메모리 관리자의 호출 횟수를 줄여 최적화하는 방법입니다.

6.1 C++ 변수

모든 C++ 변수는 메모리에 고정된 레이아웃을 가지며, 그 크기는 컴파일 타임에 결정됩니다.
프로그램이 변수의 크기를 바이트 단위로 얻고 변수에 대한 포인터를 선언하는 것은 허용하지만 비트 단위는 불가합니다.
개발자는 구조체에서 변수의 순서와 레이아웃을 추론할 수 있는데 이는 C++의 공용체 타입을 사용 가능토록 합니다.
변수는 저장 기간을 가지며, 정적 변수는 해당 함수에 진입할 때 생성되며 고정 메모리 주소에서 고정 크기를 차지합니다. 정전 변수를 위한 저장 공간 생성에는 런타임 비용이 들지 않습니다.
C++11부터 스레드 지역 저장(TLS) 기간을 갖는 변수를 선언할 수 있습니다. 스레드 지역 변수는 스레드에 진입할 때 생성되어 스레드가 끝날 때 파괴됩니다. 스레드 지역 변수는 환경에 따라 다르지만 정적 변수보다 접근 비용이 비쌉니다.
자동 저장 기간을 갖는 변수는 함수 호출 스택에서 컴파일러가 예약해둔 메모리에 상주하며 컴파일 타임에 크기가 결정되어 각 함수 호출 스택 포인터에서 고정된 오프셋 위치를 가지게 됩니다.
동적 저장 기간을 갖는 변수는 실행 중인 프로그램에서 요청한 메모리에 상주하며, 메모리 풀을 관리하는 자료구조로 구성된 메모리 관리자를 호출하여 프로그램이 저장 공간을 명시적으로 요청하여 변수를 동적 생성하며, 명시적으로 파괴할 수 있습니다.
값을 통해 의미를 갖는 변수는 값 객체, 프로그램에서의 역할에 따라 의미를 얻는 변수는 엔티티라고 합니다.
엔티티는 유일하며, 변경될 수는 있지만 복사될 수는 없고 비교할 수도 없습니다. ex) mutex, symbol table
값은 교환, 비교 및 복사는 가능하지만, 변경할 수는 없습니다.

6.2 C++ 동적 변수 API

스마트 포인터는 동적 변수의 소유권을 자동화합니다.
동적 변수의 소유권을 shared_ptr로 공유하면 비용이 더 커집니다.
동적 변수는 런타임 비용이 존재합니다.

6.3 동적 변수 사용 줄이기

클래스 인스턴스를 정적으로 만드는 것이 좋습니다.
클래스 멤버 변수를 정적으로 만드는 것이 좋습니다.
std::vector이나 std::string 대신 std::array와 같은 정적 자료구조를 사용하는 것도 한 방법입니다.
또는 스택에 큰 버퍼를 만들거나, 연결 자료구조를 정적으로 만드는 방법도 존재합니다.
new 대신 std::make_shared를 사용하면 할당을 한번에 할 수 있습니다.
소유권을 불필요하게 공유하지 않고 포인터를 내보내는 것이 좋습니다.
동적 변수를 소유하기 위한 스마트 포인터를 사용하는 것이 좋습니다.

6.4 동적 변수의 재할당 줄이기

reserve와 같이 동적 변수를 미리 할당해 재할당을 방지하는 것이 좋습니다.
반복문 바깥에서 동적 변수를 만드는 것이 좋습니다.

6.5 불필요한 복사 제거하기

클래스 정의에서 원치 않는 복사 방지시켜야 합니다.
함수 호출에서 복사를 제거할 수도 있습니다.
함수 반환에서 반환값 최적화(RVO) 혹은 출력용 매개변수를 사용하여 복사 제거할 수 있습니다.
참조를 사용하여 라이브러리를 왔다갔다 거리는 복사 없는 라이브러리를 활용하는 방법도 존재합니다.
COW를 구현하여 평소에는 얕은 복사를 수행하다 필요할 때만 깊은 복사를 수행토록 합니다.

6.6 이동 문법 구현하기

우측값을 이용하여 이동 문법을 구현하도록 합니다.
복사 생성자와 메모리 관리 함수에 시간 낭비가 많다면 이는 이동 문법을 통해 효율이 좋아집니다.
우측 값으로 반환하려고하면 RVO와 충돌하여 오히려 효율이 떨어지게 됩니다.

6.7 평평한 자료구조

자료구조의 요소들이 인접한 저장 공간에 함께 저장되었다면 자료구조가 평평하다고 합니다.
평평한 자료구조는 포인터로 연결된 자료구조 보다 메모리 관리자 호출이 적습니다.
노드 기반 자료구조에 비해 평평한 자료구조는 메모리를 적게 차지합니다.

Chapter 7. 문장 최적화

문장 수준에서 이뤄지는 최적화는 실행할 때 불필요한 명령어를 제거하는 과정으로 비유됩니다.
문장에서 이뤄지는 최적화의 문제점은 컴파일러에 따라 최적화의 효율성이 달라질 수 있다는 점입니다.

7.1 반복문에서 코드 제거하기

반복문의 종료값을 캐싱하십시오.
값을 증가하는 대신 감소하게 하여, 종료 조건에서의 비용을 줄이는게 좋습니다.
반복문에서 불변의 값들은 밖으로 옮기는 것이 좋습니다.
반복문에서 불필요한 함수 호출을 제거하는 것이 좋습니다.
반복문에 숨겨진 함수 호출을 제거하는게 좋습니다. 이는 클래스 타입 변수에서 많이 발생합니다.
반복문에서 비용이 크고 변화가 느린 호출을 제거하는게 좋습니다.
반복문을 함수 안에 넣어 호출 오버헤드를 줄이는게 좋습니다.
특정 행동을 하는 횟수를 줄이는 것이 좋습니다.

7.2 함수에서 코드 제거하기

함수 호출은 다음과 같이 이뤄집니다.
1. 함수의 인수와 지역 변수를 저장하기 위해 호출 스택에 새 프레임을 삽입
2. 각 인수 표현식을 계산하여 스택 프레임에 복사
3. 실행 주소를 복사하여 스택 프레임에 반환 주소로 대입
4. 실행 코드는 실행 주소를 함수 본문의 첫번째 문장으로 갱신
5. 함수 본문의 명령어 실행
6. 스택 프레임에 저장되어 있는 반환 주소를 명령어 주소에 복사
7. 호출 스택에서 스택 프레임을 삭제
가상 함수의 경우는 vtable을 통해 호출되기에 비순차적 메모리를 두번 불러와야해서, 캐시 미스와 실행 파이프라인 스톨의 가능성이 높아지며, 인라인화하기 어려워집니다.
간단한 함수는 인라인으로 선언하여 함수 호출 비용을 줄입니다
함수를 처음 사용하기 전에 정의를 하여 사용합니다.
사용하지 않는 다형성은 제거하는 것이 좋습니다.
사용하지 않는 인터페이스는 버려 인스턴스를 생성하지 않도록 합니다.
템플릿으로 컴파일 타임에 구현을 선택하는 것이 좋습니다.
PIMPL 관용구를 사용하는 코드를 제거하는 것이 좋습니다. 이는 예전에는 유의미한 컴파일 타임 감소를 가져왔지만, 현재는 컴파일이 빠르기에 사용하지 않아도 괜찮습니다.
DLL을 호출하는 코드를 제거하고, 라이브러리를 하나의 실행 파일로 만드는 방법으로 성능을 향상시킬 수 있습니다.
멤버 함수 대신 정적 멤버 함수를 사용하면, 비용이 큰 멤버 함수 포인터 대신 일반 함수 포인터를 참조할 수 있습니다.
가상 소멸자를 기본 클래스로 옮기는 것으로 vtable 포인터가 기본 클래스에 포함되게 하는 것이 좋습니다.

7.3 표현식 최적화

표현식을 단순하게 만드는 것이 좋습니다.
상수끼리 계산은 컴파일 타임에 이루어지기에 상수는 모아서 표현하는 것이 좋습니다.
비용이 적은 연산자를 사용하는 것이 좋습니다.(비트 연산)
부동 소수점 연산 대신 정수 연산이 빠르므로 사용하는 것이 좋습니다.
double이 float보다 빠를 수 있습니다.
반복 계산을 닫힌 형태로 바꾸는 것이 좋습니다.

7.4 제어 흐름 최적화

if-elseif-else 대신 switch를 사용하는 것이 O(1)로 접근할 수 있습니다.
switch나 if 대신 가상 함수를 사용하세요
비용이 들지 않는 예외 처리를 사용하세요

Chapter 8. 라이브러리 최적화

8.1 표준 라이브러리 최적화

C++은 범용성을 갖추고자 간결한 표준 라이브러리를 제공합니다. 이는 대부분은 매우 효율적인 코드를 생성하는 템플릿 클래스와 함수로 구성되어 있습니다.
이는 여러 운영체제에서 매우 광범위하게 재사용할 수 있습니다.
표준 라이브러리의 구현이 C++ 표준을 준수하지 않을 수 있습니다.
표준 라이브러리의 개발자에게 가장 중요한 것은 성능이 아니라 범용성입니다.
라이브러리의 구현이 최적화 시도를 좌절시킬 수도 있습니다.
C++ 표준 라이브러리의 모든 부분이 똑같이 유용하지는 않습니다. ex) vector<bool>
표준 라이브러리는 운영체제의 가장 좋은 네이티브 함수만큼 효율적이지 않습니다.

8.2 기존 라이브러리 최적화

가능한 한 적게 수정하는 것이 좋습니다.
기능을 변경하기 보다는 추가하는 것이 좋습니다.

8.3 최적화된 라이브러리 설계

급하게 설계한 라이브러리나 라이브러리 안에 독립적으로 작성된 함수 집합은 호출 및 규칙, 작동 및 효율성이 일치하지 않을 수도 있고, 라이브러리의 범용성을 해칠 수도 있습니다.
자원을 절약하도록 짜는 것도 중요합니다.
라이브러리 바깥에서 메모리 할당을 결정하는 것이 좋습니다.
확신이 서지 않는다면 속도를 위한 라이브러리 코드를 작성하는 것이 좋습니다.
함수가 프레임워크보다 최적화하기 쉽습니다.
상속 계층 구조를 평평하게 만드는 것이 좋고, 이는 대부분 3계층 이하인 것이 좋습니다.
호출 체인을 평평하게 만들어, 함수 호출의 중첩 횟수가 3회 이하로 만드는 것이 좋습니다.
계층화된 설계를 평평하게 만드는 것이 좋습니다.
동적 검색을 피하는 것이 좋습니다.