Eigen의 aliasing 문제

TL;DR: 문제가 생긴 라인 우변에 .eval()을 추가하자

개요

Eigen 라이브러리를 이용하여 프로그래밍을 하다가 A = A.transpose() 꼴의 식을 사용했는데

/usr/include/eigen3/Eigen/src/Core/Transpose.h:376: static void Eigen::internal::checkTransposeAliasing_impl<Derived, OtherDerived, MightHaveTransposeAliasing>::run(const Derived&, const OtherDerived&) [with Derived = Eigen::Matrix<double, -1, -1>; OtherDerived = Eigen::Transpose<Eigen::Matrix<double, -1, -1> >; bool MightHaveTransposeAliasing = true]: Assertion `(!check_transpose_aliasing_run_time_selector <typename Derived::Scalar,blas_traits::IsTransposed,OtherDerived> ::run(extract_data(dst), other)) && "aliasing detected during transposition, use transposeInPlace() " "or evaluate the rhs into a temporary using .eval()"' failed.

라고 에러가 나왔다. Eigen이 친절하게 해결 방법도 같이 알려줬지만, 무슨 일이 일어난 건지 알아보자.

Aliasing

Aliasing은 “=” 심볼을 사용한 할당문에서 양변에 같은 행렬 또는 벡터가 등장하는 것을 말한다.

예)

A = 2 * A;
A = A.transpose();

이 때, 연산이 element-wise가 아니라면 문제가 될 수 있다. 즉, A가 matrix라고 했을 때, 위 식은 좌변의 $(i, j)$번째 element는 우변의 $(i, j)$번째 element에 2를 곱하면 얻을 수 있으니 문제가 없고, 아래 식은 좌변의 $(i,j)$번째 element가 우변의 $(j,i)$번째 element에 의존하므로 문제가 될 수 있다. 왜 그럴까?

Lazy evaluation

vec1 = vec2 + vec3;

고전적인 라이브러리는 위 표현식을 계산할 때, 먼저 하위 표현식(sub expression) vec2 + vec3을 계산해서 임시 변수 vec4에 저장하고, 다시 vec4의 값을 vec1로 복사한다. Eigen을 비롯한 표현식 템플릿(expression-template) 기반 라이브러리는 실제로 표현식이 matrix에 할당될 때 필요한 값들을 계산하기 시작하고, 그 전까지는 추상적인 정규식 트리만 구성해둔다고 한다. 이를 lazy evaluation이라고 하고, Eigen에서는 기본적으로 표현식은 lazy evaluation된다. 그런데 모두 lazy evaluation하는 것은 1) 성능을 위해 좋은 선택이 아닐 수 있고, 2) 사용해야 하는 값이 덮어씌어져서 잘못된 결과를 내놓을 수도 있다.

해결법

Eigen도 스스로 해결하려고 노력한다. 그래서 몇가지 경우에는 하위 표현식을 임시 변수에 저장하는데, (이 작업은 컴파일 타임이 아니라 런타임에 이루어진다.)

1. 할당문 a = b;에서 표현식 b가 evaluate-before-assigning flag를 가지고 있을 때

   대표적으로 matrix product가 이런 경우다.

   mat = mat * mat;

2. 중첩 표현식(nested expression) a+b에서 b가 evaluate-before-nesting flag를 가지고 있을 때

   대표적인 경우는

   mat1 = mat2 * mat3 + mat4 * mat5

   mat2 $\ast$ mat3, mat4 $\ast$ mat5가 각각 계산되어 임시 변수에 저장되었다가 mat1에 합쳐진다.

3. 비용 모델이 하위 표현식을 먼저 계산하는 것이 효율적이라 판단할 때

   mat1 = mat2 * (mat3 + mat4)

   Matrix의 크기가 $2\times 2$보다 클 때, mat3 + mat4의 성분들이 여러번 사용되야 하므로 매번 계산하는 것보다 임시 변수에 저장해두는 것이 낫다.

그런데 Eigen이 모든 경우를 다 잘 처리했다면 에러메시지도 나오지 않았을 것이다. (생각해보면 사실 이런 경우는 다행이다. 에러메시지가 나오지 않고 계산값이 예상과 다르게 나오는 경우가 최악이다.) 이런 경우에는 어떻게 해야할까?

우변의 표현식에 .eval()을 추가하면 완전히 평가한 다음 할당한다. transpose의 경우 transposeInPlace() 함수를 사용할 수도 있다.

참조

https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html

https://runebook.dev/ko/docs/eigen3/group__topicaliasing