컴파일러 도와주기 (feat. loop unrolling)

dusunim·2023년 2월 19일

compiler optimization disassemble if constexpr loop unrolling std::index_sequence std::integer_sequence template recursion

아래처럼 다양한 형식의 2차원 백터에 대해 덧셈 연산을 하기 위한 아래 함수들이 준비되어 있었는데, 매번 자료형에 맞춰서 함수명을 바꿔가며 코드를 적는게 뭐랄까... 덜 세련되어 보여 vectormath::add()라는 함수 하나로 오버로딩하려 마음먹은 적이 최근 있었다.
이 과정에서 있었던 동료와의 논의가 나름 재미있어서 옮겨보려 한다.

namespace vectormath
{
	template <typename uv1, typename uv2>
	constexpr auto uvAdd(const uv1& vec1, const uv2& vec2) noexcept
	{
		return uv1(vec1.u + vec2.u, vec1.v + vec2.v);
	}

	template <typename xy1, typename xy2>
	constexpr auto xyAdd(const xy1& vec1, const xy2& vec2) noexcept
	{
		return xy1(vec1.x + vec2.x, vec1.y + vec2.y);
	}

	template <typename XY1, typename XY2>
	constexpr auto XYAdd(const XY1& vec1, const XY2& vec2) noexcept
	{
		return XY1(vec1.X + vec2.X, vec1.Y + vec2.Y);
	}

	template <typename Component>
	constexpr auto vec2Add(const Component vec0[2], const Component vec1[2], Component vec2[2]) noexcept
	{
		vec2[0] = vec0[0] + vec1[0];
		vec2[1] = vec0[1] + vec1[1];
	}
}

1. 함수명 하나로 Overloading하기

1.1 SFINAE (with `concept`)

처음엔 SFINAE를 사용하면 어찌어찌 되지 않을까... 라는 생각을 가졌다. 멤버 함수에 대해서만이라면 아래처럼 적용하면 되니까.

template <typename xy> requires std::is_fundamental_v<decltype(xy::x)>
xy add(const xy& p0, const xy& p1) noexcept
{
	return xy(p0.x + p1.x, p0.y + p1.y);
}

template <typename XY> requires std::is_fundamental_v<decltype(XY::X)>
XY add(const XY& p0, const XY& p1) noexcept
{
	return xy(p0.X + p1.X, p0.Y + p1.Y);
}

template <typename uv> requires std::is_fundamental_v<decltype(uv::u)>
uv add(const uv& p0, const uv& p1) noexcept
{
	return uv(p0.u + p1.u, p0.v + p1.v);
}

1.2 컴파일 타임 시퀀스 - `std::index_sequence`

여기까진 쉬웠고, 배열 형태의 데이터에 대해 어떻게 하면 쉽게 확장할까... 하고 있던 차에 동료가 PR 커멘트로 std::index_sequence를 사용하는 방법을 제안해주었다.

https://en.cppreference.com/w/cpp/utility/integer_sequence

template <size_t Dimension, typename Component, size_t... AxesIndices>
void vecAdd_impl(const Component vec0[Dimension], const Component vec1[Dimension],
	Component vec2[Dimension], std::index_sequence<AxesIndices...>) noexcept
{
	for (size_t axisIndex : { AxesIndices... })
	{
		vec2[axisIndex] = vec0[axisIndex] + vec1[axisIndex];
	}
}

template <size_t Dimension, typename Component>
void add(const Component vec0[Dimension], const Component vec1[Dimension],
	Component vec2[Dimension]) noexcept
{
	vecAdd_impl<Dimension>(vec0, vec1, vec2, std::make_index_sequence<Dimension>());
}

int main()
{
	double vec2[3][2] = { 
		{ 1, 1 },
		{ 2, 2 },
		{ 0, 0 } };

	double vec3[3][3] = {
		{ 1, 1, 1 },
		{ 2, 2, 2 },
		{ 0, 0, 0 } };

	add<2>(vec2[0], vec2[1], vec2[2]);
	add<3>(vec3[0], vec3[1], vec3[2]);

	return 0;
}

1.3 Template Recursion

모르던 초식이라 신박하긴 한데... 왠지 초 간단한 함수에 range-based for loop를, 그것도 braced-init-list 까지 사용하면 왠지 unroll되지 않을 것도 같다는 염려에 아래처럼 (소싯적에 안드레이 알렉산드레스쿠 형님이 Modern C++ Design에서 날 피토하게 하셨던) template recursion을 적용해보면 어떻게냐고 했고...

template <size_t Dimension, typename Component>
struct addImpl
{
	addImpl(const Component* vec0, const Component* vec1, Component* vec2) noexcept
	{
		vec2[Dimension] = vec0[Dimension] + vec1[Dimension];
		addImpl<Dimension - 1, Component>(vec0, vec1, vec2);
	}
};

template <typename Component>
struct addImpl<0, Component>
{
	addImpl(const Component* vec0, const Component* vec1, Component* vec2) noexcept
	{
		vec2[0] = vec0[0] + vec1[0];
	}
};

template <size_t Dimension, typename Component>
void add(const Component* vec0, const Component* vec1, Component* vec2) noexcept
{
	addImpl<Dimension - 1, Component>(vec0, vec1, vec2);
}

비록 컴파일 타임이지만 재귀호출이 마음에 안들어 이쯤 되면 그냥 아래처럼 풀어서 하는 건 어떠냐고 재차 제안했었다.

template <size_t Dimension, typename Component>
struct addImpl {};

template <typename Component>
struct addImpl<3, Component>
{
	addImpl(const Component* vec0, const Component* vec1, Component* vec2) noexcept
	{
		vec2[0] = vec0[0] + vec1[0];
		vec2[1] = vec0[1] + vec1[1];
		vec2[2] = vec0[2] + vec1[2];
	}
};

template <typename Component>
struct addImpl<2, Component>
{
	addImpl(const Component* vec0, const Component* vec1, Component* vec2) noexcept
	{
		vec2[0] = vec0[0] + vec1[0];
		vec2[1] = vec0[1] + vec1[1];
	}
};

1.4 컴파일 타임 상수표현식 - `if constexpr`

그 동료분이 다시 제안한 마지막 방법이 가장 나이스하더라... 이것 역시 신박하게도 if constexpr을 사용하는 방법. 요즘 나오는 책 좀 사서 문법 공부를 다시해야겠다는 생각이 든다...ㅎㅎ

https://en.cppreference.com/w/cpp/language/if

template <size_t Dimension, typename Component>
void add(const Component* vec0, const Component* vec1, Component* vec2) noexcept
{
	if constexpr (Dimension == 0)
	{
		vec2[0] = vec0[0] + vec1[0];
	}
	else
	{
		vec2[Dimension - 1] = vec0[Dimension - 1] + vec1[Dimension - 1];
		add<Dimension - 1, Component>(vec0, vec1, vec2);
	}
}

결과적으로 SFINAE로 구현한 세 함수와, 마지만 if constexpr 버전을 모아 아래처럼 add함수 하나로 오버로딩이 가능해졌다. (마지막 네 줄)

template <typename Component>
struct Point2
{
	Coordinate x;
	Coordinate y;
};

template <typename Component>
struct POINT2
{
	Coordinate X;
	Coordinate X;
};

template <typename Component>
struct TexCoord2
{
	Coordinate u;
	Coordinate v;
};

void myfunc()
{
	Point2<float> p0(1, 2), p1(3, 4);
	POINT2<int64_t> P0(1, 2), P1(3, 4);
	TexCoord2<double> uv0(0.1, 0.2), uv1(0.3, 0.4);
	int vec0[2] = { 1, 2 }, vec1[2] = { 3, 4 }, vec[2];

	auto p = vectormath::add(p0, p1);
	auto P = vectormath::add(P0, P1);
	auto uv = vectormath::add(uv0, uv1);
	vectormath::add<2>(vec0, vec1, vec);
}

2. Disassemble해서 확인하기

마지막으로 위에 나열했던 함수들이 정말 loop unroll이 되는지를 확인해봤다. 아래 예제처럼 동일한 목적을 수행하는 add0, add1, add2, add3 네 개의 함수를 작성해서 disassembled code를 살펴보는 방식으로...
(참고로... 어셈블리엔 까막눈입니다...)

template <typename Component>
void add0(size_t n, const Component* vec0, const Component* vec1, Component* vec2) noexcept
{
	for (size_t i = 0; i != n; ++i)
	{
		vec2[i] = vec0[i] + vec1[i];
	}
}

template <size_t dimension, typename Component, size_t... axesIndices>
void add1_impl(const Component vec0[dimension], const Component vec1[dimension], Component vec2[dimension], std::index_sequence<axesIndices...>) noexcept
{
	for (size_t axisIndex : { axesIndices... })
	{
		vec2[axisIndex] = vec0[axisIndex] + vec1[axisIndex];
	}
}

template <size_t dimension, typename Component>
void add1(const Component vec0[dimension], const Component vec1[dimension], Component vec2[dimension]) noexcept
{
	add1_impl<dimension>(vec0, vec1, vec2, std::make_index_sequence<dimension>());
}

template <size_t Dimension, typename Component>
void add2(const Component* vec0, const Component* vec1, Component* vec2) noexcept
{
	if constexpr (Dimension == 1)
	{
		vec2[0] = vec0[0] + vec1[0];
	}
	else
	{
		vec2[Dimension - 1] = vec0[Dimension - 1] + vec1[Dimension - 1];
		add2<Dimension - 1, Component>(vec0, vec1, vec2);
	}
}

template <size_t Dimension, typename Component>
void add3(const Component vec0[3], const Component vec1[3], Component vec2[3]) noexcept
{
	vec2[0] = vec0[0] + vec1[0];
	vec2[1] = vec0[1] + vec1[1];
	vec2[2] = vec0[2] + vec1[2];
}

아래는 add0(). 의도적으로 unroll 되지 않는 케이스를 만들어본 것이다. inlining을 억제하려 n을 int n; sscanf("3", "%d", &n);와 같은 방식으로 초기화한 것인데 했더니 코드가 많이 지저분하더라. (호출부로 돌아가는 것 포함 conditional jump가 두 개...)

	add0(n, vec[0], vec[1], vec0);
00007FF62E935780  movups      xmm1,xmmword ptr [rbp+rax*8+108h]  
00007FF62E935788  movups      xmm0,xmmword ptr [rbp+rax*8+0F0h]  
00007FF62E935790  addpd       xmm1,xmm0  
00007FF62E935794  movups      xmmword ptr [rbp+rax*8+0D8h],xmm1  
00007FF62E93579C  movups      xmm2,xmmword ptr [rbp+rax*8+118h]  
00007FF62E9357A4  movups      xmm0,xmmword ptr [rbp+rax*8+100h]  
00007FF62E9357AC  addpd       xmm2,xmm0  
00007FF62E9357B0  movups      xmmword ptr [rbp+rax*8+0E8h],xmm2  
00007FF62E9357B8  movups      xmm1,xmmword ptr [rbp+rax*8+128h]  
00007FF62E9357C0  movups      xmm0,xmmword ptr [rbp+rax*8+110h]  
00007FF62E9357C8  addpd       xmm1,xmm0  
00007FF62E9357CC  movups      xmmword ptr [rbp+rax*8+0F8h],xmm1  
00007FF62E9357D4  movups      xmm2,xmmword ptr [rbp+rax*8+120h]  
00007FF62E9357DC  movups      xmm0,xmmword ptr [rbp+rax*8+138h]  
00007FF62E9357E4  addpd       xmm2,xmm0  
00007FF62E9357E8  movups      xmmword ptr [rbp+rax*8+108h],xmm2  
00007FF62E9357F0  add         rax,8  
00007FF62E9357F4  cmp         rax,rdx  
00007FF62E9357F7  jne         TestBody+100h (07FF62E935780h)  
00007FF62E9357F9  cmp         rax,rcx  
00007FF62E9357FC  je          TestBody+1A3h (07FF62E935823h)

참고로, add0()에서 sscanf()를 사용하지 않고 int n = 3;으로 주면 아래처럼 루프가 unroll된다.

	int n = 3;
	add0(n, vec[0], vec[1], vec0);
00007FF7F6B45729  movsd       xmm6,mmword ptr [__real@4022000000000000 (07FF7F6F52F90h)]  
00007FF7F6B45731  movaps      xmm3,xmm6  
00007FF7F6B45734  movq        r9,xmm6  
00007FF7F6B45739  movsd       xmm7,mmword ptr [__real@401c000000000000 (07FF7F6F52F70h)]  
00007FF7F6B45741  movaps      xmm2,xmm7  
00007FF7F6B45744  movq        r8,xmm7  
00007FF7F6B45749  movsd       xmm8,mmword ptr [__real@4014000000000000 (07FF7F6F52F50h)]  
00007FF7F6B45752  movaps      xmm1,xmm8  
00007FF7F6B45756  movq        rdx,xmm1  
00007FF7F6B4575B  lea         rcx,[__xmm@00000000000000003fe0000000000000+898h (07FF7F7029B98h)]

다음은 std::index_sequence를 사용한 add1()이다. add0()에 비해 코드는 간소화되었지만 완전히 unroll되지는 않아서 conditional jump가 존재한다.

	add1<3>(vec[0], vec[1], vec1);
00007FF62E935856  mov         qword ptr [rbp+0D8h],r14  
00007FF62E93585D  mov         qword ptr [rbp+0E0h],1  
00007FF62E935868  mov         qword ptr [rbp+0E8h],2  
00007FF62E935873  lea         rcx,[rbp+0D8h]  
00007FF62E93587A  nop         word ptr [rax+rax]  
00007FF62E935880  mov         rax,qword ptr [rcx]  
00007FF62E935883  movsd       xmm0,mmword ptr [rbp+rax*8+108h]  
00007FF62E93588C  addsd       xmm0,mmword ptr [rbp+rax*8+0F0h]  
00007FF62E935895  movsd       mmword ptr [rbp+rax*8+1E0h],xmm0  
00007FF62E93589E  add         rcx,8  
00007FF62E9358A2  lea         rax,[rbp+0F0h]  
00007FF62E9358A9  cmp         rcx,rax  
00007FF62E9358AC  jne         TestBody+200h (07FF62E935880h)

if constexpr을 사용한 add2()와 직접 루프를 풀어서 적은 add3()는 사실상 동일한 코드를 생성한다. 재미있는 것은 add2()의 경우 recursion 과정에서 생성되는 코드와 disassembled code가 역순이라는 것이다. 컴파일러가 최적화 과정에서 memory ordering (instruction reordering)을 적용했는가보다...

	add2<3>(vec[0], vec[1], vec2);
00007FF62E9358E1  movsd       xmm3,mmword ptr [__real@4022000000000000 (07FF62ED42F90h)]  
00007FF62E9358E9  movq        r9,xmm3  
00007FF62E9358EE  movsd       xmm2,mmword ptr [__real@401c000000000000 (07FF62ED42F70h)]  
00007FF62E9358F6  movq        r8,xmm2  
00007FF62E9358FB  movsd       xmm1,mmword ptr [__real@4014000000000000 (07FF62ED42F50h)]  
00007FF62E935903  movq        rdx,xmm1  
00007FF62E935908  lea         rcx,[__xmm@00000000000000003fe0000000000000+910h (07FF62EE19C10h)]  

	add3<3>(vec[0], vec[1], vec3);
00007FF62E935914  movsd       xmm3,mmword ptr [__real@4022000000000000 (07FF62ED42F90h)]  
00007FF62E93591C  movq        r9,xmm3  
00007FF62E935921  movsd       xmm2,mmword ptr [__real@401c000000000000 (07FF62ED42F70h)]  
00007FF62E935929  movq        r8,xmm2  
00007FF62E93592E  movsd       xmm1,mmword ptr [__real@4014000000000000 (07FF62ED42F50h)]  
00007FF62E935936  movq        rdx,xmm1  
00007FF62E93593B  lea         rcx,[__xmm@00000000000000003fe0000000000000+928h (07FF62EE19C28h)]

결론, 최적화 수준과 사용성 면에서 if constexpr을 사용한 add2가 가장 낫더라...

template <size_t Dimension, typename Component>
void add2(const Component* vec0, const Component* vec1, Component* vec2)
{
	if constexpr (Dimension == 1)
	{
		vec2[0] = vec0[0] + vec1[0];
	}
	else
	{
		vec2[Dimension - 1] = vec0[Dimension - 1] + vec1[Dimension - 1];
		add2<Dimension - 1, Component>(vec0, vec1, vec2);
	}
}

dusunim

C++로 기하 알고리즘과 애플리케이션 아키텍처 위주로 작업해온 시니어 개발자였습니다만, 요즘은 React.js, Node.js, Kubernetes 등등... 프론트와 백엔드 이것저것을 배워가는 중입니다.

컴파일러 도와주기 (feat. loop unrolling)

1. 함수명 하나로 Overloading하기

1.1 SFINAE (with `concept`)

1.2 컴파일 타임 시퀀스 - `std::index_sequence`

1.3 Template Recursion

1.4 컴파일 타임 상수표현식 - `if constexpr`

2. Disassemble해서 확인하기

비지터 패턴과 함수형 프로그래밍

Polygon Mesh - 에지 검색 테이블

0개의 댓글

컴파일러 도와주기 (feat. loop unrolling)

1. 함수명 하나로 Overloading하기

1.1 SFINAE (with concept)

1.2 컴파일 타임 시퀀스 - std::index_sequence

1.3 Template Recursion

1.4 컴파일 타임 상수표현식 - if constexpr

2. Disassemble해서 확인하기

비지터 패턴과 함수형 프로그래밍

Polygon Mesh - 에지 검색 테이블

0개의 댓글

1.1 SFINAE (with `concept`)

1.2 컴파일 타임 시퀀스 - `std::index_sequence`

1.4 컴파일 타임 상수표현식 - `if constexpr`