식 템플릿

Expression templates

식 템플릿은 C++ 템플릿 메타프로그래밍 기술로 컴파일 시 계산을 나타내는 구조를 구축합니다.여기서 식은 [1]계산 전체에 대해 효율적인 코드를 생성하기 위해 필요한 경우에만 평가됩니다.따라서 표현식 템플릿을 사용하면 프로그래머는 C++ 언어의 정상적인 평가 순서를 생략하고 루프 퓨전 등의 최적화를 실현할 수 있습니다.

표현 템플릿은 Todd Veldhuizen과 David Vandevoorde에 [2][3]의해 독립적으로 발명되었습니다.그들에게 이름을 [3]붙인 것은 Veldhuizen이었습니다.그것들은 선형 대수 소프트웨어의 [1]구현을 위한 인기 있는 기술이다.

모티베이션

벡터 및 해당 벡터에 대한 연산을 나타내는 라이브러리를 고려합니다.하나의 일반적인 수학적 연산은 요소별로 두 개의 벡터 u와 v를 더하여 새로운 벡터를 생성하는 것입니다.이 작업의 명백한 C++ 구현은 과부하입니다. operator+: 새 벡터 개체를 반환합니다.

학급 벡 {     표준::벡터< >이중으로 하다> 소자;    일반의:     벡(size_t n) : 소자(n) {}      이중으로 하다 &교환입니다.[](size_t i)      { 돌아가다 소자[i]; }     이중으로 하다 교환입니다.[](size_t i) 컨스턴트 { 돌아가다 소자[i]; }     size_t 크기()               컨스턴트 { 돌아가다 소자.크기(); } };  벡 교환입니다.+(벡 컨스턴트 &u, 벡 컨스턴트 &v) {     주장하다(u.크기() == v.크기());     벡 합(u.크기());     위해서 (size_t i = 0; i < > u.크기(); i++) {          합[i] = u[i] + v[i];     }     돌아가다 합; }

이제 이 클래스의 사용자는 Vec x = a + b로 쓸 수 있습니다.여기서 a와 b는 모두 Vec의 인스턴스입니다.

이 접근법의 문제점은 Vec x = a + b + c와 같은 보다 복잡한 표현이 비효율적으로 구현된다는 것입니다.구현에서는 먼저 a + b를 유지하기 위한 임시 벡터를 생성한 다음 c 요소를 추가한 다른 벡터를 생성합니다.반환값 최적화를 사용하더라도 최소 2회 메모리를 할당하고 2개의 루프가 필요합니다.

지연된 평가는 이 문제를 해결하고 연산자+가 커스텀타입의 오브젝트(예: VecSum)를 반환하도록 함으로써 C++에서 구현할 수 있습니다.VecSum은 2개의 벡터의 미가변화 합계를 나타냅니다.그런 다음 식이 클수록 실제 Vec 변수에 할당되었을 때만 평가되는 식 트리가 효과적으로 구축됩니다.그러나 이를 위해서는 평가를 위해 이러한 트리를 건너야 하며,[4] 그 자체만으로도 비용이 많이 듭니다.

식 템플릿은 컴파일 시에만 존재하는 식 트리를 사용하여 지연된 평가를 구현합니다.Vec x = a + b + c와 같은 Vec에 대한 각 할당은 템플릿 인스턴스화를 통해 필요한 경우 새로운 Vec 생성자를 생성합니다.이 컨스트럭터는 3개의 Vec에서 동작하며 필요한 메모리를 할당하고 계산을 수행합니다.따라서 메모리 할당은 1개만 실행됩니다.

식 템플릿의 구현 예는 다음과 같습니다.기본 클래스 VecExpression은 모든 벡터 값 식을 나타냅니다.이상하게도 반복되는 템플릿 패턴에 따라 실장되는 실제 표현 유형E에 따라 템플릿화 됩니다.VecExpression과 같은 기본 클래스의 존재는 식 템플릿이 작동하기 위해 반드시 필요한 것은 아닙니다.이것은 단순히 다른 유형과 식을 구별하는 함수 인수 유형으로 기능합니다(아래 Vec 생성자 및 연산자+의 정의에 유의하십시오). 

템플릿 < >타이프네임 E> 학급 Vec Expression(벡 표현) {   일반의:     이중으로 하다 교환입니다.[](size_t i) 컨스턴트      {         // 실제 식 유형에 대한 위임입니다.이를 통해 동적 다형성(C++의 가상 함수라고도 함)이 방지됩니다.         돌아가다 static_cast< >E 컨스턴트&>(*이것.)[i];     }     size_t 크기() 컨스턴트 { 돌아가다 static_cast< >E 컨스턴트&>(*이것.).크기(); } };

Vec 클래스는 완전히 평가된 벡터 식의 좌표를 저장하고 VecExpression의 하위 클래스가 됩니다. 

학급 벡 : 일반의 Vec Expression(벡 표현)< >벡> {     표준::벡터< >이중으로 하다> 소자;    일반의:     이중으로 하다 교환입니다.[](size_t i) 컨스턴트 { 돌아가다 소자[i]; }     이중으로 하다 &교환입니다.[](size_t i)      { 돌아가다 소자[i]; }     size_t 크기() 컨스턴트               { 돌아가다 소자.크기(); }      벡(size_t n) : 소자(n) {}      // 이니셜라이저 목록을 사용하여 벡터 생성     벡(표준::이니셜라이저_리스트< >이중으로 하다> 초기화) : 소자(초기화) {}      // 모든 VecExpression에서 Vec을 구성할 수 있으므로 Vec을 강제로 평가할 수 있습니다.     템플릿 < >타이프네임 E>     벡(Vec Expression(벡 표현)< >E> 컨스턴트& expr) : 소자(expr.크기()) {         위해서 (size_t i = 0; i != expr.크기(); ++i) {             소자[i] = expr[i];         }     } };

두 벡터의 합은 새로운 유형인 VecSum에 의해 표현되며, VecSum은 임의의 벡터 표현 쌍에 적용될 수 있도록 합계의 왼쪽과 오른쪽의 유형에서 템플릿화됩니다.과부하 연산자+는 VecSum 생성자의 구문 설탕 역할을 합니다. 

템플릿 < >타이프네임 E1, 타이프네임 E2> 학급 벡섬 : 일반의 Vec Expression(벡 표현)< >벡섬< >E1, E2> > {     E1 컨스턴트& _u;     E2 컨스턴트& _v;  일반의:     벡섬(E1 컨스턴트& u, E2 컨스턴트& v) : _u(u), _v(v) {         주장하다(u.크기() == v.크기());     }      이중으로 하다 교환입니다.[](size_t i) 컨스턴트 { 돌아가다 _u[i] + _v[i]; }     size_t 크기()               컨스턴트 { 돌아가다 _v.크기(); } };    템플릿 < >타이프네임 E1, 타이프네임 E2> 벡섬< >E1, E2> 교환입니다.+(Vec Expression(벡 표현)< >E1> 컨스턴트& u, Vec Expression(벡 표현)< >E2> 컨스턴트& v) {    돌아가다 벡섬< >E1, E2>(*static_cast< >컨스턴트 E1*>(&u), *static_cast< >컨스턴트 E2*>(&v)); }

위의 정의에서는 a + b + c라는 식에 해당하는 타입입니다.

벡섬< >벡섬< >벡, 벡>, 벡>

따라서 Vec x = a + b + c는 이 유형을 E 템플릿 인수로 사용하여 템플릿된 Vec 생성자를 호출합니다.이 생성자 내에서 루프 본체는

소자[i] = expr[i];

(이 타입의 연산자+ 및 연산자[]의 재귀적 정의를 포함)로 효과적으로 확장됩니다.

소자[i] = a.소자[i] + b.소자[i] + c.소자[i];

임시 벡터는 필요 없고 각 메모리 블록을 하나만 통과합니다.

기본 사용법: 

인트 주된() {     벡 v0 = {23.4,12.5,144.56,90.56};     벡 v1 = {67.12,34.8,90.34,89.30};     벡 v2 = {34.90,111.9,45.12,90.5};          // 다음 할당은 Vec의 ctor를 호출하여 다음 유형을 받아들입니다.     // 'VecExpression <E> const &.다음으로 루프 본체를 확장합니다.     // a.elems[i] + b.elems[i] + c.elems[i]     벡 sum_of_vec_type = v0 + v1 + v2;       위해서 (size_t i=0; i< >sum_of_vec_type.크기(); ++i)         표준::외치다 << > sum_of_vec_type[i] << > 표준::끝;      // v0, v1, v2 이외의 추가 스토리지 생성 방지     // 다음 작업을 수행할 수 있습니다(GCC 5.3.0에서 C++11로 테스트 완료).     자동 합 = v0 + v1 + v2;     위해서 (size_t i=0; i< >합.크기(); ++i)         표준::외치다 << > 합[i] << > 표준::끝;     // 이 경우 typeid(sum)는 VecSum <VecSum <Vec, Vec>가 되는 것에 주의해 주세요.     // 이 동작의 체인은 계속 됩니다. }

적용들

표현식 템플릿은 선형 대수학을 위한 라이브러리, 즉 수의 벡터와 행렬을 다루는 데 특히 유용한 것으로 밝혀졌다.식 템플릿을 사용하는 라이브러리에는 Dlib,[5] Armadillo, Blaze,[6] Blitz++,[7] Boost uBLAS,[8] Igen,[9] POOMA,[10] Stan Math [11]Library 및 [12]xtensor가 있습니다.표현식 템플릿은 또한 Adapt 라이브러리에 설명된 대로 C++ 자동 차별화 [13]구현을 가속화할 수 있습니다.

벡터 연산 이외에 Spirit 파서 프레임워크는 식 템플릿을 사용하여 형식 문법을 표현하고 파서로 컴파일합니다.

레퍼런스

  1. ^ a b Matsuzaki, Kiminori; Emoto, Kento (2009). Implementing fusion-equipped parallel skeletons by expression templates. Proc. Int'l Symp. on Implementation and Application of Functional Languages. pp. 72–89.
  2. ^ Vandevoorde, David; Josuttis, Nicolai (2002). C++ Templates: The Complete Guide. Addison Wesley. ISBN 0-201-73484-2.
  3. ^ a b Veldhuizen, Todd (1995). "Expression Templates". C++ Report. 7 (5): 26–31. Archived from the original on 10 February 2005.
  4. ^ Abrahams, David; Gurtovoy, Aleksey (2004). C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond. Pearson Education. ISBN 9780321623911.
  5. ^ 근일 발매일
  6. ^ 비트버킷
  7. ^ "Blitz++ User's Guide" (PDF). Retrieved December 12, 2015.
  8. ^ "Boost Basic Linear Algebra Library". Retrieved October 25, 2015.
  9. ^ Guennebaud, Gaël (2013). Eigen: A C++ linear algebra library (PDF). Eurographics/CGLibs.
  10. ^ Veldhuizen, Todd (2000). Just when you thought your little language was safe: "Expression Templates" in Java. Int'l Symp. Generative and Component-Based Software Engineering. CiteSeerX 10.1.1.22.6984.
  11. ^ "Stan documentation". Retrieved April 27, 2016.
  12. ^ "Multi-dimensional arrays with broadcasting and lazy computing". Retrieved September 18, 2017.
  13. ^ Hogan, Robin J. (2014). "Fast reverse-mode automatic differentiation using expression templates in C++" (PDF). ACM Trans. Math. Softw. 40 (4): 26:1–26:16. doi:10.1145/2560359. S2CID 9047237.