레이블이 최적화인 게시물을 표시합니다. 모든 게시물 표시
레이블이 최적화인 게시물을 표시합니다. 모든 게시물 표시

2020년 7월 7일 화요일

C++ 최적화 책, 7장 문장 최적화

C++ 최적화 책을 보게 되었고 읽으며 기억해야 할 내용을 간략히 정리 함.
C++ 언어를 사용하시거나 더 자세한 내용을 보시려면 아래 책을 꼭 읽어보세요. 오랜만에 읽는 유익한 C++ 책이네요.

C++ 최적화 최고 성능을 구현하는 10가지 검증된 기법
커트 건서로스 저/옥찬호 역/박수현 감수 | 한빛미디어

C++ 최적화 책, 4장 문자열 최적화
http://charlie0301.blogspot.com/2020/05/c-4.html

C++ 최적화 책, 6장 동적 할당 변수 최적화


반복문에서 코드 제거하기


- 반복문에서 종료값을 캐싱하라

char s[] = "This string is toooooooo long ";

for(size_t i=0; i< strlens(s);++i)
    if(s[i] == ' ')
        s[i] = '*';

위의 경우 문자열을 탐색하며 개수를 세는 strlen() 때문에 O(n) - O(n^2)의 비용이다.
이런 경우 값을 저장해 두고 사용하면 된다.

for(size_t i=0, len=strlen(s); i< len;++i)
    if(s[i] == ' ')
        s[i] = '*';

- 효율적인 반복문을 사용하라. 
다른 책에서도 do while()을 사용하는 것을 추천하던데 이유가 제대로 설명되어 있지 않았는데 이 책에서는 아래와 같이 설명

for(초기화 표현식; 조건식; 증감문) 반복해서 실행할 코드
는 다음과 같이 컴파일 된다고 함
        초기화 표현식;
L1: if (!조건식) goto L2;
        반복해서 실행할 코드;
        증감문;
        goto L1;
L2:

for 문은  조건식 결과가 false일 경우 두번 점프해야 함.
그에 반해 do while문은 다음과 같다.

do 반복해서 실행할 코드 while (조건식);
은 다음과 같이 컴파일 된다.
L1: 반복해서 실행할 코드
       if(조건식) goto L1;


- 반복문에서 불변 코드를 제거하라.
 : 반복문 진행 중에 변경되지 않는 코드는 컴파일러가 자동으로 반복문 바깥으로 옮기지만 함수가 복잡하거나 함수의 본문이 다른 컴파일 단위에 있다면 컴파일러가 자동으로 처리할 수 없으니 직접 확인 해서 반복문 바깥으로 옮겨라.


- 반복문에서 불필요한 함수 호출을 제거하라.
 : 반복문내의 제공하는 값이 항상 동일하거나 반복문과 상관 없는 함수는 제거하거나 외부로 옮기는 것이 맞다.


 순수함수(pure function)

아래 wikipedia를 보면 간단하게 말하면 함수에서 local static 변수, non-local 변수, parameter를 변경하거나 I/O 기기의 값을 참조하지 않아 같은 입력에 대해서 같은 출력을 제공하는 함수를 말한다. 

In computer programming, a pure function is a function that has the following properties:[1][2]

  1. Its return value is the same for the same arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams from I/O devices).
  2. Its evaluation has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or I/O streams).


아래 글을 참고하면 pure function의 경우 컴파일러가 최적화 대상으로 인식하여 최적화 하게 된다.





- 반복문에서 숨겨진 함수 호출을 제거하세요.
 : 일반적으로 함수의 이름을 쓰고 괄호로 인수를 적어 호출하는 함수 외 클래스 타입 변수를 취급할 경우 다음 함수들이 호출 될 수 있다.
  . 클래스 인스턴스의 선언 (생성자를 호출)
  . 클래스 인스턴스의 초기화 (생성자를 호출)
  . 클래스 인스턴스의 대입 (대입 연산자를 호출)
  . 클래스 인스턴스를 포함하는 산술 표현식 (연산자 멤버 함수를 호출)
  . 범위를 빠져나갈 때 (범위에서 선언된 클래스 인스턴스의 소멸자를 호출)
  . 함수 인수 (각 인수 표현식은 형식 인수로 복사 생성됨)
  . 클래스 인스턴스의 함수 반환 (아마도 복사 생성자를 두 번 호출)
  . 표준 라이브러리 컨테이너에 항목을 삽입 (항목이 이동 또는 복사 생성됨)
  . 벡터에 항목을 삽입 (벡터가 재할당될 경우 모든 항목이 이동 또는 복사 생성됨)
 : 클래스의 불필요한 생성자, 연산자를 제거하거나 반복문 내에서 클래스 인스턴스 생성, 삭제, 복사를 최소한으로 하는 것이 방법

- 반복문을 함수 안에 넣어 호출 오버헤드를 줄이세요.
 : 문자열, 배열, 다른 자료구조를 반복하며 함수를 호출한다면 반복문 뒤집기(loop inversion) 기법을 사용하여 함수 호출 횟수를 줄여 성능 향상이 가능하다.



loop inversion

이것이 저자가 말하는 기법인지 모르겠으나 설명에 의하면 
while loop을 do..while loop을 가지는 if문으로 변경하는 방법으로
적절히 사용되면 cpu instruction pipelining에 의해 성능을 향상할 수 있다고 함.

위 링크의 어셈블리를 예를 확인하면  while loop 보다 if do..while loop이 불필요한 실행이 감소된 것을 확인할 수 있다.

https://en.m.wikipedia.org/wiki/Loop_optimization 에서도 하나의 기법으로 소개하고 있음.


* 책의 저자는 여러 저수준 최적화 기법이 있지만 생각만큼 효과가 없을 수 있다고 말하며 오히려 이미 C++ 컴파일러가 훌륭히 처리하고 있다고 함.


함수에서 코드 제거하기

함수가 호출 되면
컴퓨터는 현재 실행 중인 코드의 위치를 저장하고,
함수 본문으로 실행 흐름을 바꾼 다음,
함수 호출이 끝나고 이전에 실행하던 명령어의 다음 위치로 복귀하는 방법으로
실행 흐름에 함수 본문을 효율적으로 집어 넣음.

1. 실행 코드는 함수의 인수와 지역 변수를 저장하기 위해 호출 스택에 새 프레임을 삽입
2. 각 인수 표현식을 계산한 뒤 스택 프레임에 복사
3. 현재 실행 주소를 복사해서 스택 프레임에 반환 주소로 넣음.
4. 실행 코드는 실행 주소를 (함수를 호출한 후의 다음 문장 대신) 함수 본문의 첫 번째 문장으로 갱신
5. 함수 본문에 있는 명령어들을 실행
6. 스택 프레임에 저장되어 있는 반환 주소를 명령어 주소에 복사. 그리고 함수를 호출한 후의 문장으로 제어권을 넘김
7. 호출 스택에서 스택 프레임을 삭제

함수 호출의 기본 비용
- 함수 인수
 : 인수 표현식을 계산하는 비용, 인수값을 메모리 스택에 복사하는 비용 필요
 : 인수 몇개는 레지스터를 통해 전달 가능하지만 많으면 스택으로 전달함.

- 멤버 함수 호출(vs 함수 호출)
 : 멤버 함수를 호출하는 모든 코드에는 자신을 가리키는 this 포인터가 숨겨져 있다.

가상함수의 비용
 - 가상 멤버 함수가 있는 클래스의 각 인스턴스는 vtable이라는 테이블을 가리키는 이름 없는 포인터를 포함
 : vtable은 가상 함수들의 시그니처와 연관된 본문을 가리킴
 : vtable 포인터는 역참조 비용을 줄이기 위해 클래스 인스턴스의 첫번째 필드로 만듬.
 : 가상 함수를 호출하는 코드는 vtable을 가리키는 포인터를 얻고자 클래스 인스턴스를 가리키는 포인터를 역참조함. 즉 호출 시 비 순차적인 메모리를 추가로 두번 불러와야 함.

파생 클래스에서의 멤버 함수 호출의 비용도 상당하다.

함수를 가리키는 포인터의 비용
- 함수 포인터 (함수와 정적 멤버 함수를 가리키는 포인터)
 : 코드는 함수의 실행 주소를 얻기 위해 포인터를 역참조함. 컴파일러는 인라인할 수 없음.
- 멤버 함수 포인터
 : 함수 시그니처와 클래스를 모두 식별해야 하며 최악의 경우에 해당하는 성능을 갖는다고 가정해도 무리는 아님

- 인수가 없는 C 스타일의 void 함수는 호출 비용이 적음.
 : 함수를 인라인할 수 있다면 비용이 들지 않고 메모리 접근과 실행 비용이 전부
- 가상 다중 상속 클래스를 포함하지만 가상 함수가 없는 기본 클래스에서 파생된 클래스의 가상 함수를 호출하는 것이 최악의 경우
 : 코드는 클래스 인스턴스 포인터에 더할 오프셋을 결정하기 위해 클래스 인스턴스 테이블을 역참조
 : 가상 다중 상속된 함수의 인스턴스 포인터를 형성하고 vtable을 얻기 위해 인스턴스를 역참조한 뒤 함수의 실행 주소를 얻기 위해 vtable을 인덱싱

- 간단한 함수는 인라인으로 선언
- 함수를 처음 사용하기 전에 정의
 : 정의가 호출 전에 있다면 컴파일러가 함수를 호출하는 코드를 최적화 가능
- 사용하지 않는 다형성을 제거
 : 런타임 다형성을 구현하기 위해 가상 멤버 함수를 자주 사용함.

- 사용하지 않는 인터페이스를 버려라
- 템플릿으로 컴파일 타임에 구현을 선택하라
- PIMPL 관용구를 사용하는 코드를 제거하라
- 멤버 함수 대신 정적 멤버 함수를 사용하라
- 가상 소멸자를 기본 클래스로 옮겨라



표현식 최적화

- 표현식을 단순하게 만들어라
y = a*x*x*x + b*x*x +c*x + d;
=> y = (((a*x + b)*x) + c)*x + d;
로 바꿔 단순화 할 수 있다.

- 상수를 함께 모아라.
seconds = 24 * 60 * 60 * days;
seconds = days * (24 * 60 * 60);
이런 문장을 컴파일러에서는
seconds = 86400 * days;
바꿀 수 있지만 
seconds = 24 * days * 60 * 60;
인 경우 컴파일러는 곱셈을 런타임에 계산해야 한다고 함.

- 비용이 적은 연산자를 사용하라.
- 부동 소수점 연산 대신 정수 연산을 사용하라.
- double이 float보다 빠를 수 있다.
- 반복 계산을 닫힌 형태라 바꿔라


제어 흐름 최적화

- if-elseif-else 대신 switch를 사용하라.
 : if-else if-else 문은 선형 제어 흐름이고 O(n)번 비교함.
 : switch문은 색인 작업을 한 번 수행하고 테이블에 있는 주소로 점프함.
  . 비교하는데 O(1)이지만 색인에 사용되는 상수의 간격이 크다면 컴파일러는 상수를 정렬하여 이진 검색을 수행하는 코드를 생성함. 그래도 O(log2n)이다.

- swtich나 if 대신 가상 함수를 사용하라.
- 비용이 들지 않는 예외 처리를 사용하라.
  : 예외 사양을 사용하지 마라.
  : 예외 사양에는 개발자가 호출한 함수 라이브러리의 함수에서 어떤 예외를 던질 수 있는지 알아내기가 어렵다.
  : 예외 사양은 성능에 부정적인 영향을 미친다.
  : C++11에서는 더이상 예외 사양이 사용되지 않고 noexcept라는 새로운 예외 사양이 도입됨.
   . 함수를 noexcept로 선언하면 함수가 예외를 던질 수 없다고 알려주는 것임.
   . 컴파일러가 이동 문법을 구현하기 위해 특정 이동 생성자와 이동 대입 연산자를 noexcept로 선언해야 한다고 요구함. 이는 예외 안정성 보장 보다 이동 문법이 중요하다는 선언과 같음.


 
noexcept 및 C++에서의 예외처리 기본 지침

C++11부터 정의된 keyword로 함수에서 예외를 throw 할 수 있는지를 지정할 때 사용됨.


noexcept(true)의 별칭인 throw()를 제외하고는 C++17에서 모두 제거됨.
각각은 아래와 같은 의미를 가짐 

예외 사양의미
noexcept
noexcept(true)
throw()		이 함수는 예외를 throw하지 않습니다. /Std: c + + 14 모드 (기본값)에서는 noexcept 및 noexcept(true)가 동일 합니다. noexcept 또는 noexcept(true)선언 된 함수에서 예외가 throw 되는 경우 std:: terminate 가 호출 됩니다. /Std: c + + 14 모드에서 throw()로 선언 된 함수에서 예외가 throw 되는 경우 결과는 정의 되지 않은 동작입니다. 특정 함수가 호출 되지 않습니다. 이는 컴파일러에서 std::를 호출 하는 데 필요한 c + + 14 표준과의 차이입니다.
Visual Studio 2017 버전 15.5 이상: /std: c + + 17 모드에서 noexcept, noexcept(true)및 throw() 모두 동일 합니다. /Std: c + + 17 모드에서 throw()는 noexcept(true)에 대 한 별칭입니다. /Std: c + + 17 모드에서 이러한 사양 중 하나를 사용 하 여 선언 된 함수에서 예외가 throw 되는 경우 std:: Terminate 는 c + + 17 표준에 필요한 대로 호출 됩니다.
noexcept(false)
throw(...)
사양 없음		함수는 모든 형식의 예외를 throw 할 수 있습니다.
throw(type)(C + + 14 및 이전) 함수는 type형식의 예외를 throw 할 수 있습니다. 컴파일러는 구문을 허용 하지만 noexcept(false)로 해석 합니다. /Std: c + + 17 모드에서 컴파일러는 경고 될 때 c5043를 발생 시킵니다.



기본 지침

강력한 오류 처리는 모든 프로그래밍 언어에서 어렵습니다. 예외가 좋은 오류 처리를 지원하는 여러 기능을 제공하기는 하지만 사용자를 대신해 모든 작업을 수행할 수는 없습니다. 예외 메커니즘의 혜택을 누리려면 코드를 디자인할 때 예뢰를 염두에 둡니다.

  • 절대 발생하지 않아야 하는 오류를 확인하려면 어설션을 사용합니다. 예외를 사용하여 발생할 수 있는 오류, 예를 들어 공용 함수의 매개 변수에 대한 입력 유효성 검증 오류를 점검하세요. 자세한 내용은 예외 및 어설션이라는 섹션을 참조 하십시오.

  • 오류를 처리하는 코드가 하나 이상의 개입 함수 호출로 오류를 감지하는 코드와 분리될 수 있는 경우 예외를 사용합니다. 오류를 처리하는 코드가 오류를 감지하는 코드에 밀접하게 연결되어 있으면 성능이 중요한 루프에서 오류 코드를 대신 사용할지 고려합니다.

  • 예외를 throw 하거나 전파 하는 모든 함수에 대해, 강력한 보장, 기본 보장 또는 nothrow (noexcept) 보장의 세 가지 예외 보장 중 하나를 제공 합니다. 자세한 내용은 방법: 예외 안전성을 위한 디자인을 참조 하세요.

  • 값에 따라 예외를 발생(throw)시키고 참조로 포착(catch)합니다. 처리할 수 없는 것은 포착(catch)하지 않도록 주의합니다.

  • C++11에서 더이상 사용되지 않는 예외 사양을 사용하지 마세요. 자세한 내용은 예외 사양 및 noexcept섹션을 참조 하세요.

  • 가능하다면 표준 라이브러리 예외 형식을 사용합니다. 예외 클래스 계층 구조에서 사용자 지정 예외 형식을 파생 시킵니다.

  • 소멸자 또는 메모리 할당 해제 함수에서 예외가 빠져나오는 것을 허용하지 마세요.






시간: 댓글 없음:
라벨: ,

2020년 6월 10일 수요일

C++ 최적화 책, 6장 동적 할당 변수 최적화

C++ 최적화 책을 보게 되었고 읽으며 기억해야 할 내용을 간략히 정리 함.
C++ 언어를 사용하시거나 더 자세한 내용을 보시려면 아래 책을 꼭 읽어보세요. 오랜만에 읽는 유익한 C++ 책이네요.

C++ 최적화 최고 성능을 구현하는 10가지 검증된 기법
커트 건서로스 저/옥찬호 역/박수현 감수 | 한빛미디어

C++ 최적화 책, 4장 문자열 최적화
http://charlie0301.blogspot.com/2020/05/c-4.html


C++ 변수

- C++ 변수는 고정된 레이아웃을 가지고 컴파일 타임에 크기가 결정됨
- 변수는 저장 기간(수명)을 가짐
- 정적 저장 기간
 . 컴파일러가 예약해둔 메모리에 상주
 . 메모리 주소는 컴파일 타임에 결정
 . 전역 정적 변수는 main()함수 진입 전에 생성, main()함수를 떠난뒤 파괴
 . 함수에서 선언한 정적 변수는 함수에 처음 진입하기 전에 생성
 
- 스레드 지역 저장 기간
 . C++ 11 이후 thread-local storage(TLS) 변수를 선언 가능
 . 스레드 진입 시 생성, 스레드가 끝나면 파괴
 . thread_local 키워드로 선언된 변수는 스레드 지역 저장 기간을 가짐

- 자동 저장 기간
 . 함수 호출 스텍에서 컴파일러가 예약해둔 메모리 상주
 . 컴파일 타임에 메모리 크기 결정
 . 함수 호출 스택 포인터에서 고정된 오프셋 위치를 가짐
 . 코드 블록 {} 안에 존재하므로 {} 진입 시 생성, 빠져나오면 파괴

- 동적 저장 기간
 . 실행 중인 프로그램에서 요청한 메모리에 상주
 . 프로그램에서 new로 명시적으로 저장 공간을 요청하고 delete로 파괴
 . 메모리 관리자가 메모리 관리
 . 자동 변수와 마찬가지로 주소는 런타임에 결정


- 변수의 소유권( 변수의 생성, 파괴를 결정하는 주체를 설명하기 위한 개념인듯)
 : 전역 소유권
  . 프로그램이 가지며 main()함수 진입 전 생성되고 main()함수를 떠난 뒤 파괴 됨.
 : 유효 범위가 지정된 소유권 
  . 중괄호로 둘러 싸인 코드블록의 유효 범위가 소유권을 가짐. 
  . main() 함수의 {} 도 해당 되며 main()함수에서 선언된 자동 변수는 정적 변수와 동일한 수명을 가짐
 : 멤버 소유권 
  . 클래스 인스턴스가 가짐. 
  . 클래스 인스턴스가 생성될 때 생성되며 인스턴스가 파괴될 때 파괴됨.
 : 동적변수의 소유권 
  . 정해져 있지 않고 프로그램에서 명시적으로 관리해야 함. 
  . new로 만들어진 포인터를 프로그램이 관리하고 더이상 사용하지 않는 경우 delete로 제거해야 함. (포인터 날로 쓰는게 가장 싫었음. 가능하면 동적 변수는 스마트 포인터로 관리하는게 맞는 방법임.)


- C++11의 nullptr이라는 특정한 값은 유효한 메모리를 가지키지 않는다. 
  : 0을 nullptr로 변환할 수 있지만 0 != nullptr 이다.



POCO(Plain Old C++ 개체)에 대한 포인터를 캡슐화하는 데 가장 먼저 스마트 포인터를 사용합니다.

  • unique_ptr
    기본 포인터로 한 명의 소유자만 허용합니다. shared_ptr이 필요하다는 점을 확실히 알 경우 POCO의 기본 선택으로 사용합니다. 새 소유자로 이동할 수 있지만 복사하거나 공유할 수 없습니다. 사용하지 않는 auto_ptr을 대체합니다.boost::scoped_ptr과 비교합니다. unique_ptr작고 효율적입니다. 크기는 하나의 포인터이며 C++ 표준 라이브러리 컬렉션에서 빠른 삽입 및 검색을 위한 rvalue 참조를 지원합니다. 헤더 파일: <memory>. 자세한 내용은 unique_ptr 인스턴스 및 unique_ptr 클래스를 만드는 방법( 사용 방법)을 참조하십시오.

  • shared_ptr
    참조 횟수가 계산되는 스마트 포인터입니다. 원시 포인터 하나를 여러 소유자에게 할당하려고 할 경우 사용합니다(예: 컨테이너에서 포인터 복사본을 반환할 때 원본을 유지하고 싶을 경우). 원시 포인터는 모든 shared_ptr 소유자가 범위를 벗어나거나 소유권을 포기할 때까지 삭제되지 않습니다. 크기는 2개의 포인터입니다. 하나는 개체용이고, 다른 하나는 참조 횟수가 포함된 공유 제어 블록용입니다.헤더 파일: <memory>. 자세한 내용은 인스턴스 및 shared_ptr 클래스를shared_ptr 만드는 방법: 인스턴스 만들기 및 사용 방법을 참조하십시오.

  • weak_ptr
    shared_ptr과 함께 사용할 수 있는 특별한 경우의 스마트 포인터입니다.weak_ptr은 하나 이상의 shared_ptr 인스턴스가 소유하는 개체에 대한 액세스를 제공하지만, 참조 수 계산에 참가하지 않습니다. 개체를 관찰하는 동시에 해당 개체를 활성 상태로 유지하지 않으려는 경우 사용합니다. shared_ptr 인스턴스 사이의 순환 참조를 차단하기 위해 필요한 경우도 있습니다. 헤더 파일: <memory>. 자세한 내용은 weak_ptr 인스턴스 및 weak_ptr 클래스를 만드는 방법: 인스턴스 만들기 및 사용 방법을 참조하십시오.



스마트 포인터의 삭제 조건
- break, continue를 만났을 때, 함수에서 값을 리턴할 때, 예외가 발생하는 등 선언문을 둘러싸고 이쓴 범위를 빠져 나갈 때 소유한 동적 변수 삭제
- 클래스 멤버로 선언된 스마트 포인터는 클래스 인스턴스가 파괴될 때 소유한 동적 변수를 삭제함.
- 스레드 지역 저장 기간으로 선언된 스마트 포인터 인스턴스는 스레드가 정상 종료될 때 소유한 동적 변수를 삭제
 : 운영체제가 스레드를 종료시킨 경우 일반적으로 삭제되지 않는 다고 함.
- 정적 저장 기간으로 선언된 스마트 포인터의 인스턴스는 프로그램이 종료될 때 소유한 동적 변수 삭제

- 동적 변수를 한 소유자가 관리하는 경우 
 : std::unique_ptr 사용 추천. 비용 패널티도 거의 없음.

스마트 포인터는 메모리 및 성능 관점에서 최대한 효율적으로 사용할 수 있도록 설계되었습니다. 예를 들어, unique_ptr의 유일한 데이터 멤버는 캡슐화된 포인터입니다. 즉, unique_ptr은 해당 포인터와 정확히 동일한 크기(4바이트 또는 8바이트)입니다. 오버로드된 스마트 포인터 * 및 -> 연산자(s)를 사용하여 캡슐화된 포인터에 액세스하는 것은 원시 포인터에 직접 액세스하는 것보다 훨씬 느리지 않습니다.


- 동적 변수를 여려명이 공유하는 경우, 두개 이상의 포인터가 동적변수를 관리하는 경우 접근 시 유효성을 확인하기 어렵고 삭제 같은 관리가 어려움. 
 : std::shared_ptr를 사용하는 것을 추천
 : 단 shared_ptr에 대입할 때 new 표현식에서 리턴되는 것을 바로 넣고 std::make_shared를 사용하는 것을 추천

- 동적 변수는 런타임 비용이 있음.
- 동적 변수의 메모리를 할당하기 위해서는 수천번의 메모리 접근이 필요할 때도 있음.
 : 동적 변수 생성을 위해 메모리 할당 함수는 빈 메모리 블럭을 찾음.
  . 빈 메모리 블록을 찾으면 블록을 제거한 뒤 제공
  . 필요한 것보다 큰 블록을 찾으면 분할한 뒤 일부를 반환
 : 이용 가능한 메모리 블록이 없다면 할당 함수는 큰 메모리 블럭을 추가로 얻기 위해 가용 메모리 시스템 풀에서 운영체제 커널을 고비용으로 호출
  . 커널에서 사용하는 메모리는 RAM에 캐시되어 있을 수도 없을 수도 있음. 캐시되어 있지 않다면 지연 될 수 있음
 : 빈 메모리 블록의 컬렉션은 프로그램의 모든 스레드가 공유하는 자원이며 메모리 블록 변경 사항은 스레드 세이프(thread-safe) 함
  . 할당, 해제 함수를 자주 호출하면 하나 외 다른 스레드들이 대기하게 됨
 : 동적 변수의 할당된 메모리를 해제할 때 반환된 블럭을 빈 메모리 컬렉션에 넣게 되지만 복잡함.
  . 할당, 해제로 블록들의 크기가 작아지는 것을 방지하기 위해 해제된 메모리 블록을 인접한 메모리 블록과 합치려고 시도함. 


동적 변수 사용 줄이기

- 클래스 인스턴스를 정적으로 만들어라
  ex) YourClass yourInstance("hahaha",111);

- 클래스 멤버 변수를 정적으로 만들어라
 : 클래스 멤버변수가 클래스 인스턴스라면 클래스 생성 시 멤버변수도 정적으로 생성되어 할당하는 비용을 줄일 수 있음.
 : 클래스 생성 시 멤버 변수를 생성하기 위한 자원이 없어 동적으로 생성해야 하는 경우 두 단계초기화(two-part initialization)을 사용하라.

- 배열의 크기가 정해져 있다면 std::vector 대신 std::array를 사용하라.
 : std::array는 복사 생성할 수 있고 operator[]로 임의 접근 반복자와 첨자 지정을 제공함.

- 저장공간이 커지면서 발생하는 재할당 비용을 줄이기 위해 스택에 큰 버퍼를 만들어라

- 정적으로 초기화된 데이터가 연결 자료 구조라면 정적으로 구성하라.

- 이진트리를 배열로 만들어라

- std::deque 대신 원형 버퍼(http://bit.ly/b-buffer)를 사용하라.

- 변수 할당 비용을 줄이기 위해 new 대신 std::make_shared를 사용하라.
  ex) std::shared_ptr p = std::make_shared("hahah",111);
        auto p = std::make_shared("hahah",111);

- 동적 변수를 사용한다면 std::unique_ptr, std::shared_ptr을 사용하라.


동적 변수의 재할당 줄이기

- 동적 변수를 미리 할당하여 재할당을 방지하라.
 : 메모리할당 비용을 줄이기 위해 std::string, std::vector의 reserve(size_t n) 같은 함수로 적당히 공간을 확보하라.
- 반복문 바깥에서 동적 변수를 만들어라
 : 반복문내의 변수는 할당/해제를 반복하므로 외부에 두고 clear()같은 함수를 사용하여 초기화 후 사용하라.


불필요한 복사 제거하기

- 클래스의 대입 시(ClassA = ClassB)의 대입 연산자(Assignment operator)가 호출 됨. 이 때 클래스 멤버에 따라서 대입하는 비용이 상당히 커질 수 있음.
- 선언과 동시에 초기화 하는 문장(Foo a = b)의 경우 Foo가 클래스라면 복사생성자(Copy constructor)가 호출 됨. 
 : 대입 연산자와 복사 생성자는 하는일이 거의 동일하고 비용이 클 수 있어 최적화 시 다음상황에서 발생가능한지 확인해야 함.

- 초기화 (생성자 호출)
- 대입 (대입 연산자 호출)
- 함수 인수 (함수의 인자/형식 인수로 전달되면서 이동 생성이나 복사 생성됨)
- 함수 반환 (이동 생성자나 복사 생성자를 호출)
- 표준 라이브러리 컨테이너에 항목을 삽입 (항목은 이동 생성이나 복사 생성됨)
- 벡터에 항목을 삽입 (벡터가 재할당 될 경우 모든 항목은 이동 생성이나 복사 생성됨)

- 클래스 정의에서 원치 않는 복사 방지하기
 : 클래스 인스턴스를 복사하는 비용이 많거나 복사를 원하지 않는다면 복사를 금지할 수 있음.
 : 단 아래와 같이 복사를 금지한다면 표준 라이브러리 컨테이너 클래스 값으로 사용하지 못함.

// C++ 11 이전 방법
class BigClass {
private :
   BigClass(BigClass const&);
   BigClass& operator=(BigClass const&);
public : 
...
};

// C++11 이후
class BigClass {
public 
   BigClass(BigClass const&) = delete;
   BigClass& operator=(BigClass const&) = delete;
   ...
};


- 함수 호출에서 복사 제거하기, 
 : 함수 인자로 넘겨지는 클래스 인스턴스의 경우 레퍼런스로 받아라. 
 : 내부에서 수정이 필요 없으면 const &, 수정이 필요하면 &
 : 하지만 함수 내에서 레퍼런스값을 여러번 참조한다면 역참조(dereferencing)로 인한 비용이 더 커질 수 있음.

포인터나 레퍼런스에서 값을 확인할 때를 역참조라 표현


- 함수 반환에서 복사 제거하기
 : 함수에서 클래스 인스턴스를 리턴 시 반환값으로 복사 생성됨.
 : 하지만 C++ 컴파일러에서는 복사 생략(copy elision), 반환값 최적화(return value optimization, RVO) 방법을 사용하지만 구체적인 조건에서만 가능함.
   . 함수는 내부에서 생성된 객체를 반환해야 함.
   . 함수에서 선언했던 반환 타입과 똑같은 타입이어야 함.
   . 함수가 간단하고 제어 경로가 하나뿐이라면 컴파일러는 RVO를 수행할 가능성이 높음
 : 그 외 방법으로는 출력용 매개변수(out parameter)를 사용하여 값을 반환하는 것도 방법임.
  ex) vector scalar_product(std::vector const& v, int c) 
        =>  void scalar_product(std::vector const& v, int c, vector& result)
 

RVO(Return Value Optimization)
 Output (note that -fno-elide-constructors disables RVO in clang):
$ clang++ -std=c++11 main.cpp && ./a.out
c'tor
d'tor

$ clang++ -std=c++11 -fno-elide-constructors main.cpp && ./a.out
c'tor
move c'tor
d'tor
move c'tor
d'tor
d'tor
RVO 적용과 미적용의 차이를 확실히 알 수 있다.


- COW(Copy On Write) 구현하기
 : COW의 개념은 원본 객체와 복사한 객체 중 하나가 수정되기 전까지 객체가 동일하다는 것
    즉 초기에는 얕은 복사(shallow copy)를 하고 객체가 수정될 때까지 깊은 복사(deep copy)를 지연 시키는 것


COW(Copy On Write)
예시를 보여주고 있지만 주의점도 함께 설명하고 있다.

n a multi-threaded environemnt (which is most of them nowadays) CoW is frequently a huge performance hit rather than a gain. And with careful use of const references, it's not much of a performance gain even in a single threaded environment. 
Additionally, as other people have pointed out, CoW strings are really tricky to implement, and it's easy to make mistakes. That coupled with their poor performance in threading situations makes me really question their usefulness in general. This becomes even more true once you start using C++11 move construction and move assignment. 
답변의 내용이 생각보다 부정적인 반응임. 구현하기 까다롭고 성능 개선도 크지 않을 수 있다고 함.


이동 문법 구현하기
책의 내용을 참고하자. 어렵지만 이 책(https://www.oreilly.com/library/view/effective-modern-c/9781491908419/)도 참고하면 좋다.


평평한(flat) 자료구조
- 자료 구조 요소들이 인접한 저장 공간에 저장되었다면 자료구조가 평평하다고 표현함.
- 평평한 자료구조는 생성 시 포인터로 연결된 자료구조보다 메모리 관리자를 호출하는 횟수가 적음
- list, deque, map, unordered_map 자료구조는 동적 객체를 많이 만드는 반면 vector는 이보다 적게 만듬. 같은 big O 성능을 갖는다고 하더라도 평평한 자료구조가 가지는 장점이 많음.
- std::array, std::vector와 같은 평평한 자료구조는 list, map, unordered_map과 같은 노드 기반의 자료구조보다 메모리를 적게 차지함.
- 평평한 자료구조를 사용하면 스마트 포인터와 스마트 포인터가 가리키는 객체를 할당하는 런타임 비용을 없앨 수 있음.

시간: 댓글 없음:
라벨:

2020년 5월 28일 목요일

C++ 최적화 책, 4장 문자열 최적화


C++ 최적화 : 최고 성능을 구현하는 10가지 검증된 기법 
커트 건서로스 저/옥찬호 역/박수현 감수 | 한빛미디어

책을 보고 간략히 정리하려고 함.
오랜만에 보는 괜찮은 c++ 언어 서적이다.
"Effective Modern C++" 을 보다가 내용과 번역에 질려버리고 
"모던 C++ 입문" 을 봤었는데 그 책의 저자가 이 책을 번역하였음.

책의 전반적인 내용은 최적화라는 관점에서 가능한 모든 방법을 소개하는 것 같다.
최적화의 방법이 정도가 없어 일반적인 내용, 저자의 경험과 테스트를 통해서 알게 된 내용들을 소개하고 있다. 
C++ 문법, skill을 가르치는 것은 아니고 효율적인 코드를 작성하기 위해 알아야 하는 내용과 방법을 제시한다.



1장 최적화란

다음 권고 사항들로 정리할 수 있어 보인다.
- 더 좋은 컴파일러를 사용하고 최적화 설정을 사용하세요.
- 최적의 알고리즘을 사용하세요.
- 더 좋은 라이브러리를 더 잘 사용하세요.
- 메모리 할당을 줄이세요.
- 복사를 줄이세요.
- 계산을 제거하세요.
- 최적의 자료구조를 사용하세요.
- 동시성을 증가시키세요.
- 메모리 관리를 최적화하세요.

책의 목차를 보면 알겠지만 위 내용을 책에서 나눠 설명하고 있고
각 내용을 간략히 정리하는 챕터이다. c++ 언어 특성과 관련이 있는 팁도 있지만, 프로그래밍 시 일반적으로 알아야 하고 적용할 수 있는 조언이 대부분이라 유익하다.



4장 문자열 최적화

(오라일리에서 제공하는 online book 페이지입니다.
아래 내용, 코드는 모드 아래 출처에서 발췌하였다.)

std::string은 저장소를 동적으로 할당합니다.
문자열이 추가되면서 문자열보다 저장소가 훨씬 크게 할당할 수 있어 메모리가 낭비될 수 있다고 합니다.
문자열은 값처럼 동작하여 문자열 사용 시 복사가 많이 일어날 수밖에 없다고 합니다. 

책에서는 아래 함수를 예시로 최적화를 진행합니다.

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; 
} 

그냥 봐도 수정할 것이 많아 보임...

(임시 문자열 객체 생성 제거) 
result = result + s[i]  에서 
s[i]를 더한 새로운 result를 저장하기 위해 
생성된 임시 문자열을 
  result += s[i];
로 변경하여 임시 문자열이 생성되지 않게 하여 성능을 개선합니다.

(문자열 저장 공간 예약)
result에 저장하는 문자열은 최대 s의 크기이므로
result.reserve(s.length())를 호출하여
미리 저장 공간을 예약하여 
result 값이 증가함에 따라 저장 공간 확보 시도를 줄여 성능을 개선합니다. 

(함수 인자 복사를 제거)
std::string s로 넘겨지는 인자의 복사(pass by value)를 제거하기 위해
std::string const& s
로 변경하여 인자를 레퍼런스(pass by reference)로 받아
불필요한 임시객체 생성&복사를 방지하여 성능을 개선하려고 하였지만
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[i] 를 
iterator로 사용하여 성능을 개선할 수 있었습니다.
함께 loop을 반복할 때 마다 종료 조건에서의 간접 참조 비용을 줄이기 위해 
it != s.end() 대신 s.end()를 캐싱하여 it != end로 변경하여 성능을 개선합니다. 
  
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; 
} 


(반환된 문자열 값의 복사 제거하기)
반환되는 std::string이 복사되게 되어
이를 생략하기 위해 함수의 참조 인자(std::string& result)로 변경하여 성능을 개선합니다.

마지막으로 속도가 중요한 경우에 사용할 수 있는
C 스타일 문자열을 사용하여 성능을 개선합니다. 

책에서는 성능 요약을 표로 정리했는데 릴리즈 빌드로 24.8 마이크로 걸리던 코드를 1.02 마이크로초로 줄이고 c 스타일 문자열을 사용하여 0.15 마이크로초까지 성능을 개선했다.

그 외 성능 개선을 위한 다른 방법들을 설명하고 있고  
다음의 방법으로 개선을 시도할 수 있다고 말하고 있음. 
- 더 좋은 알고리즘 사용
- 저 좋은 컴파일러 사용
- 더 좋은 문자열 라이브러리 사용
- 더 좋은 할당자 사용


시간: 댓글 없음:
라벨: ,
피드 구독하기: 글 (Atom)