최근 알고리즘 관련 수업을 들으며, 3항 min, max를 구현할 일이 생겼다
물론 일반적인 사람이라면 그냥 parameter 3개 받아서 적당히 구현할 것이다
하지만 이런 식상한 방법은 지겹지 않은가
이 새낀 STL Vector를 쓰지말라고 하니까 Vector 구현체를 만들어 쓰는 놈이다
뭔가 parameter pack으로 해결할 수 있는 신박한 방법이 있지 않을까 싶었다
물론 제목에서 힌트를 얻을 수 있듯이, fold expression을 사용하면 된다
다만 한가지 걸리는 것이 fold expression을 사용하려면 c++17이 필요하다
그래서 찾아보던 중 c++11에서도 나름 비슷하게 구현이 가능하다고해서 시도해보았다
How STL solves the problem
사실 제일 먼저 시도해본 것은 STL에서 어떻게 처리했는가를 찾아본 것이다
https://en.cppreference.com/w/cpp/algorithm/min
그동안 알고리즘 쪽을 잘 안쳐다봐서 몰랐었는데 initializer_list로 구현해놓았다
그렇기에 아래와 같이 작성할 경우 쉽게 해결이 된다
#include <algorithm>
auto main() -> int {
return std::min({1, 2, 3, 5});
}물론 이 경우에는 당연하게도 반복문을 돌게 된다
일반적으로 std::min(std::initializer_list)는 std::min_element로 구현한다
그리고 이 std::min_element의 구현은 보통 다음과 같다
https://en.cppreference.com/w/cpp/algorithm/min_element
template<class ForwardIt>
ForwardIt min_element(ForwardIt first, ForwardIt last)
{
if (first == last)
return last;
ForwardIt smallest = first;
while (++first != last)
if (*first < *smallest)
smallest = first;
return smallest;
}물론 말그대로 possible implementation인 만큼, 컴파일러 자유긴하다
하지만 딱히 더 좋은 수가 안보이는 만큼 컴파일러들도 그냥 이런식으로 구현해놓았다
clang의 경우 동일하게 구현해놓은걸 확인할 수 있다
약간 다르긴 한데, 그냥 일반화를 좀 섞은걸로 보여서 무시했다
https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/min.h
https://github.com/llvm/llvm-project/blob/main/libcxx/include/__algorithm/min_element.h
물론 이렇게 만들어놓으면 최적화도 상당히 깔끔하다
값을 argv에서 받은건 그냥 귀찮아서다..절대 저렇게 코딩하진 말자..
clang x86-64 17.0.1 -O3
#include <algorithm>
auto main(int argc, char** argv) -> int {
auto v = reinterpret_cast<int*>(argv[0]);
return std::min({v[0], v[1], v[2], v[3]});
}main: # @main
mov rcx, qword ptr [rsi]
mov eax, dword ptr [rcx]
mov edx, dword ptr [rcx + 4]
mov esi, dword ptr [rcx + 8]
cmp edx, eax
cmovl eax, edx
mov ecx, dword ptr [rcx + 12]
cmp esi, eax
cmovl eax, esi
cmp ecx, eax
cmovl eax, ecx
ret예상했겠지만 개수가 compile time에 정해지고, 충분히 작다고 판단되면 반복문이고 뭐고 싹다 날린다
그냥 해당 숫자들을 register에 넣고 n-1번 반복하고 끝이다
이렇게 보면 끝..이라고 할수도 있겠지만, 저건 어떻게 봐도 Fold expression 같아 보이지 않는다
그리고 initializer_list이기 때문에 모든 argument의 type이 같아야한다
그래서 뭔가 엘레강스한 방법이 있지 않을까 고민하게 되었다
Just ask on StackOverflow
모르겠을땐 일단 stackoverflow에 검색해보라는 말이 있다
그리고 이 경우에도 스오플 형님들이 까리한 방법을 알려주신다
https://stackoverflow.com/questions/51005897/what-is-a-good-alternative-to-this-c17-fold-expression-in-c14
이제 정말 끝난걸까..?
아쉽게도 사소한 문제가 아직 남아있다
위 스오플 형님은 c++14를 기준으로 설명하였다
따라서 아직 deduced return type을 사용할 수 없다
즉, return type을 지정해주어야만 한다는 것이다
스오플 형님의 답안을 토대로 c++11에 돌아가도록 변경한다면 다음과 같다
#include <functional>
template <
typename Ret, typename Func, typename First, typename... Args
>
constexpr auto
__pack_operation_impl(Func &&func, First &&first, Args&&... args) -> Ret {
return func(std::forward<First>(first),
__pack_operation_impl<Ret>(func, std::forward<Args>(args)...));
}
template <typename T, typename Func>
constexpr auto
__pack_operation_impl(Func &&, T &&begin) -> T {
return std::forward<T>(begin);
}
template <
typename Ret, typename Func, typename... Args
>
constexpr auto
pack_operation(Func &&func, Args&&... args) -> Ret {
return __pack_operation_impl<Ret>(func, std::forward<Args>(args)...);
}
auto main() -> int {
return pack_operation<int>([](int const &_1, int const &_2) {
return _1 < _2 ? _1 : _2;
}, 1,2,3,4);
}코드가 좀 어지러운데 한쪽에 스오플 페이지를 켜놓고 비교해보면 동일한 동작임을 확인할 수 있다
한가지 다른점이라면 바로 template에 return type이 추가되었다는 것이다
즉, 우리가 직접 return type을 지정해줘야 하는 문제가 발생한다
이게 도대체 뭐가 문제냐고 할 수 있겠지만, 최종 목표를 다시 한번 더 상기시켜보자
'fold expression과 비슷한걸 c++11에서 구현한다'라는 목표와는 거리가 좀 있어보인다
최종목표를 위해서는 이제 저 return type을 deduce 할 수 있도록 바꿔줘야 한다
std::common_type
비교적 최근에 와서는 template을 적게 사용하기 위해 각종 feature가 추가되고 있다
하지만 이전에는 template meta programming이라는 이름아래 모든걸 template으로 해결했다
그 중 굉장히 유용하면서도 다소 쉬운 편에 속하는 std::common_type은 c++11에 추가된 function이다
이름에서 알 수 있듯, 여러가지 type 중 implicit convertion이 가능한 하나의 type을 뽑아주는 놈이다
바로 최종 목표를 위한 마지막 열쇠라 할 수 있다
이를 활용하여 수정할 경우 다음과 같다
#include <functional>
#include <type_traits>
template <
typename Func, typename First, typename... Args,
typename Ret = typename std::common_type<Args...>::type
>
constexpr auto
__pack_operation_impl(Func &&func, First &&first, Args&&... args) -> Ret {
return func(std::forward<First>(first),
__pack_operation_impl(func, std::forward<Args>(args)...));
}
template <typename Func, typename T>
constexpr auto
__pack_operation_impl(Func &&, T &&begin) -> T {
return std::forward<T>(begin);
}
template <
typename Func, typename... Args,
typename Ret = typename std::common_type<Args...>::type
>
constexpr auto
pack_operation(Func &&func, Args&&... args) -> Ret {
return __pack_operation_impl(func, std::forward<Args>(args)...);
}
auto main() -> int {
return pack_operation([](int const &_1, int const &_2) {
return _1 < _2 ? _1 : _2;
}, 1,2,3,4);
}기존에는 return type을 지정해줘야 했지만, 이제는 common type을 유추해서 사용한다
물론 이대로 끝내기엔 사용이 너무 어려우니 적당히 엘레강스하게 만들어주자
위에서 구현한 pack_operation을 사용하여 min, max를 구현한다면 다음과 같다
template <
typename... Args,
typename arg_type = typename std::common_type<Args...>::type
>
auto min(Args&&... args) -> arg_type {
return pack_operation([](arg_type const &_1, arg_type const &_2) {
return _1 < _2 ? _1 : _2;
}, args...);
}
template <
typename... Args,
typename arg_type = typename std::common_type<Args...>::type
>
auto max(Args&&... args) -> arg_type {
return pack_operation([](arg_type const &_1, arg_type const &_2) {
return _1 > _2 ? _1 : _2;
}, args...);
}
auto main() -> int {
std::cout << min(2.f, 3, 5, 2, 10, 1.5f, 0.75, -1.234) << std::endl;
}min, max를 구현하는 과정이 좀 어지러울 순 있지만, 한번 해놓고 나면 사용이 굉장히 간편해진다
이제 n항에 대한 min, max를 굉장히 직관적으로 사용할 수 있게 되었다
그리고 operator 자리에 원하는 operation을 넣어주면 나름 fold expression 비스무리한게 나오게 된다
Performance
구현이 끝났으니 성능 이야기를 안하고 넘어갈수가 없다
대충 보면 recursive하게 돌기에 굉장히 비효율적이라고 생각할수도 있을 것이다
물론 최적화가 들어가지 않은 Optimization 0에서는 맞는 말이다
Assembly가 너무 길어서 링크로 대체하는데 clang은 300줄, gcc는 500줄이 넘게 뱉어냈다
https://godbolt.org/z/s447E6df8
단순히 숫자 8개 비교하는게 왜 이렇게 힘드냐고 생각하겠지만, Optimization을 넣으면 이야기가 달라진다
clang x86-64 17.0.1 -O3
https://godbolt.org/z/xf1f4fPvs
.LCPI0_0:
.quad 0xbff3be76c8b43958 # double -1.234
main: # @main
...나머지를 다 자른 이유는 다 std::cout에 관련된 code이기 때문이다
잘 보면 이미 결과를 compile time에 계산해서 binary에 박아놓은걸 볼 수 있다
그렇다면 숫자가 동적으로 주어지는 경우에는 어떨까
죄짓는 기분이 들긴하지만 처음에 사용했던 예제를 그대로 들고와서 다시 사용해보자
처음에 사용했던 예제와의 비교를 위해서 cout을 빼고 parameter도 4개로 줄여서 넣어봤다
clang x86-64 17.0.1 -O3
https://godbolt.org/z/Yd7YcvxE7
main: # @main
mov rcx, qword ptr [rsi]
mov edx, dword ptr [rcx + 8]
mov eax, dword ptr [rcx + 12]
cmp edx, eax
cmovl eax, edx
mov edx, dword ptr [rcx]
mov ecx, dword ptr [rcx + 4]
cmp ecx, eax
cmovl eax, ecx
cmp edx, eax
cmovl eax, edx
ret연산 순서랑 사용하는 register가 좀 달라지긴 했지만, 그 외엔 완벽하게 동일한 결과가 나온다
개인적으로 언어의 관점에서 완벽한 결과가 아닐까 싶다
개인적으로 결과만 놓고보면 c++11에서 사용하기에 저것보다 깔끔한 방법은 없어보인다
다만, 뭔가 뻘짓한것 같아 좀 마음이 아프다..허구한날 하는게 뻘짓이긴 하다..
원래는 std::common_type도 다룰까하다가 귀찮아져서 그냥 포기했다
그리고 아직 template으로 적고 싶은게 한가득이라 그걸 먼저하는게 순서가 맞는거 같기도했다
이번 글은 번외편 느낌으로 가볍게 이런 뻘짓도 해봤다에 의의를 두는 글이다
