Edited at

[C++] C++ proposalとして提案中のfunction_refを実装してみた


概要

ISO C++のproposalとして提出されているstd::function_refに関する解説と実装


なぜfunction_refが必要なのか

C++11から導入されたstd::functionは、関数を統一的に扱うことを可能にする一方、実装が複雑すぎることによる弊害があります。


  • 与えられた関数オブジェクトが左辺値であれば、そのオブジェクトをコピーする。

  • オブジェクトがコピーされる度に、中身の関数オブジェクトもコピーする。

  • 関数オブジェクトのサイズが大きい場合、operator newを使用してメモリを動的に確保する。

  • 通常はSmall-Size Optimizationを用いて実装されるため、右辺値代入を行う際にもコピーが発生する場合がある。

  • ほとんどの場合std::functionのメンバ関数はインライン化されず、呼び出し動作も遅くなる場合がある。

  • 関数同士の等号比較が出来ない

しかしながら、関数を統一的に扱う場合であっても、これらの動作が不要な場合があります。


例: TCP再送機能の実装

例として、TCPにおける再送機能を実装する場合を考えます。

struct payload { /* ... */ };

// action関数を最大でtimes回呼び出す。
// ただし、action関数の返り値の型はstd::optional<payload>であり、
// 返り値が有効な場合は即座にreturnする。
std::optional<payload> retry(std::size_t times, /* ????? */ action);


従来の実装方法


関数ポインタを使用した実装

std::optional<payload> retry(std::size_t times,

std::optional<payload>(*action)())
{
/* ... */
}



  • メリット


    • テンプレートを使用していないので、宣言と実装を分けるのが容易。

    • ラッパークラスを使用していないため、外部依存がない。余計なincludeも不要。

    • ポインタ渡ししているため、余計なコピーが発生しない。




  • デメリット


    • キャプチャ付きのラムダ式やメンバ関数、その他の関数オブジェクトを渡すことが出来ない。




templateを使用した実装

template <typename F>

auto retry(std::size_t times, F&& action)
-> std::enable_if_t<std::is_invocable_r_v<std::optional<payload>, F&&>,
std::optional<payload>>
{
/* ... */
}



  • メリット


    • 呼び出し可能なオブジェクトならどんな型でも渡すことが出来る。

    • 参照渡ししているため、余計なコピーが発生しない。

    • 関数オブジェクトを直接呼び出すため、呼び出し動作が非常に高速




  • デメリット


    • 記述が冗長で可読性の低下やバグを引き起こす。

    • retry関数をヘッダーファイルに実装しなければならない

    • ラムダ式が頻繁に渡されると、その度にテンプレートが実体化され、コンパイル時間の増大やバイナリの肥大化を引き起こす




std::functionを用いた実装

std::optional<payload> retry(std::size_t times,

std::function<std::optional<payload>()> action)
{
/* ... */
}



  • メリット


    • 呼び出し可能なオブジェクトならどんな型でも渡すことが出来る。

    • 記述がシンプルで分かりやすい。

    • テンプレートを使用していないので、宣言と実装を分けるのが容易。




  • デメリット


    • actionを左辺値で初期化した場合に余計なコピーが発生する。

    • 関数オブジェクトのサイズが大きい場合、メモリの動的確保が発生する。

    • 動的確保で予期せぬ例外が発生する可能性がある

    • 変数actionが独立したリソースを保有しているとは限らない(std::reference_wrapperを用いて初期化した場合など)




代替法

考えてみれば、action変数はretry関数内でのみ使用され、retry関数の中でリソースが他のオブジェクトにムーブされることもありません。

したがって、関数オブジェクトをコピーするのではなく、もとのオブジェクトを参照するだけで十分です。

function_refは、あらゆる関数オブジェクトへの参照を保持する機能を持ちます。

インスタンス生成時に動的確保やオブジェクトのコピーを行わないため、std::functionよりも高速に動作します。

std::optional<payload> retry(std::size_t times,

function_ref<std::optional<payload>()> action)
{
/* ... */
}

このように定義した場合、action変数はもとの関数オブジェクトへのポインタしか保有していませんが、retry関数の中ではstd::functionと同様に扱うことが出来ます。


  • メリット


    • 呼び出し可能なオブジェクトならどんな型でも渡すことが出来る。

    • 記述がシンプルで分かりやすい。

    • テンプレートを使用していないので、宣言と実装を分けるのが容易。

    • オーバーヘッドが比較的小さく、また最適化によって呼び出し処理がinline化されるので、テンプレートと同程度の性能を発揮する。




簡易版function_refを実装する

実装するなんて言ってますが、facebookが開発しているfollyというライブラリですでに簡単な実装がなされているので、今回はそのコードを参考に実装しています。


function_ref.hpp

#include <type_traits>

#include <functional>

template <typename FunctionType>
class function_ref;

template <typename ReturnType, typename... Args>
class function_ref<ReturnType(Args...)> final {
using Call = ReturnType (*)(void*, Args&&...);

static ReturnType uninitCall(void*, Args&&...) {
throw std::bad_function_call();
}

/// operator()によって実際に呼び出すラッパー関数
template <typename Fun>
static ReturnType call(void* object, Args&&... args) noexcept(
noexcept(std::declval<Fun>()(std::forward<Args>(args)...))) {
using Pointer = std::add_pointer_t<Fun>;
return (*static_cast<Pointer>(object))(std::forward<Args>(args)...);
}

/// 関数オブジェクトへのポインタ
void* object_ = nullptr;

/// object_を呼び出すためのラッパー関数へのポインタ
Call call_ = &function_ref::uninitCall;

public:
constexpr function_ref() noexcept = default;

constexpr function_ref(std::nullptr_t) noexcept {}

constexpr function_ref(const function_ref& other) noexcept = default;

template <typename Fun,
typename std::enable_if_t<
std::is_invocable_r_v<ReturnType, Fun, Args...>, int> = 0>
constexpr function_ref(Fun&& fun) noexcept {
// funのアドレスを取得しobject_に格納
// operator&がオーバーロードされている場合も考えて回りくどい方法を用いている
object_ = reinterpret_cast<void*>(
&const_cast<char&>(reinterpret_cast<const volatile char&>(fun)));

// ラッパー関数を実体化して格納
call_ = &function_ref::call<Fun>;
}

/// コピーコンストラクタ
constexpr function_ref& operator=(const function_ref& other) noexcept =
default;

constexpr function_ref& operator=(std::nullptr_t) noexcept {
object_ = nullptr;
call_ = &function_ref::uninitCall;
}

template <typename Fun>
constexpr function_ref& operator=(Fun&& fun) noexcept {
static_assert(std::is_invocable_r_v<ReturnType, Fun, Args...>,
"argument is not invocable with specified signature.");

object_ = reinterpret_cast<void*>(
&const_cast<char&>(reinterpret_cast<const volatile char&>(fun)));
call_ = &function_ref::call<Fun>;
}

constexpr void swap(function_ref& other) noexcept {
std::swap(object_, other.object_);
std::swap(call_, other.call_);
}

constexpr explicit operator bool() const noexcept { return object_; }

/// 同じ関数オブジェクトを指しているかどうかの比較
constexpr bool operator==(const function_ref& other) const noexcept {
return (object_ == other.object_);
}

/// ラッパー関数を呼び出す
ReturnType operator()(Args&&... args) const {
return call_(object_, std::forward<Args>(args)...);
}
};


関数オブジェクトのnoexceptやcv修飾子を一切考えていないというのもありますが、全体として実装は非常にシンプルです。

関数が呼び出し可能かどうかをチェックし、その関数のアドレスとラッパー関数へのポインタを保持するだけ。

メンバ関数のcv修飾子とか関数のnoexceptとか本気で考え出すと長くなるので今回は実装しませんが、それらを実装したとしてもstd::functionに比べればかなり短く済むのではないかと思います。

というか、std::functionだってnoexceptのこと考慮してないよね。


実験

ほとんどのメンバ関数にconstexprがついているので実験するまでもないと思いますが、一応呼び出しコストがゼロになることを示す実験です。

#include <iostream>

#include <array>
#include "function_ref.hpp"

__attribute__((visibility("hidden")))
inline void apply(std::array<int, 8>& arr, function_ref<void(int&)> func) {
for (auto&& elem : arr) {
func(elem);
// ++elem;
}
}

__attribute__((noinline))
void print_array(const std::array<int, 8>& arr) {
for (auto&& elem : arr) {
std::cout << elem << std::endl;
}
}

int main() {
std::array<int, 8> arr = {10, 11, 12, 13, 14, 15, 16, 17};
::apply(arr, [](int& v) { ++v; });
print_array(arr);

return 0;
}

最適化オプション(-O3)をつけてアセンブラ出力(必要な部分のみ抜粋)。

// ...


main:
sub rsp, 56
movdqa xmm0, XMMWORD PTR .LC0[rip]
mov rdi, rsp
mov rax, QWORD PTR fs:40
mov QWORD PTR 40[rsp], rax
xor eax, eax
movaps XMMWORD PTR [rsp], xmm0
movdqa xmm0, XMMWORD PTR .LC1[rip]
movaps XMMWORD PTR 16[rsp], xmm0
call _Z11print_arrayRKSt5arrayIiLm8EE
mov rdx, QWORD PTR 40[rsp]
xor rdx, QWORD PTR fs:40
jne .L17
xor eax, eax
add rsp, 56
ret
.L17:
call __stack_chk_fail@PLT

// ...

.LC0:
.long 11
.long 12
.long 13
.long 14
.LC1:
.long 15
.long 16
.long 17
.long 18

コンパイル時にもう計算処理が終了しているようですね。

計算後の値を読み込んでprint_array関数に渡しているだけのようです。

ちなみに、ソースコード中のfunc(elem)を呼び出す部分を++elemに変えても同様の出力が得られました。

今度は、function_refの部分をstd::functionに変えたらどうなるか、実験してみます。

_ZNSt17_Function_handlerIFvRiEZ4mainEUlS0_E_E9_M_invokeERKSt9_Any_dataS0_:

add DWORD PTR [rsi], 1
ret

_ZNSt14_Function_base13_Base_managerIZ4mainEUlRiE_E10_M_managerERSt9_Any_dataRKS4_St18_Manager_operation:
test edx, edx
je .L6
cmp edx, 1
jne .L5
mov QWORD PTR [rdi], rsi
.L5:
xor eax, eax
ret
.L6:
lea rax, _ZTIZ4mainEUlRiE_[rip]
mov QWORD PTR [rdi], rax
xor eax, eax
ret

main:
push r13
push r12
lea rcx, _ZNSt14_Function_base13_Base_managerIZ4mainEUlRiE_E10_M_managerERSt9_Any_dataRKS4_St18_Manager_operation[rip]
push rbp
push rbx
sub rsp, 104
movdqa xmm0, XMMWORD PTR .LC0[rip]
lea r13, 16[rsp]
lea rbp, 48[rsp]
mov rax, QWORD PTR fs:40
mov QWORD PTR 88[rsp], rax
xor eax, eax
movaps XMMWORD PTR 16[rsp], xmm0
lea rax, _ZNSt17_Function_handlerIFvRiEZ4mainEUlS0_E_E9_M_invokeERKSt9_Any_dataS0_[rip]
mov QWORD PTR 8[rsp], rcx
mov rbx, r13
lea r12, 32[r13]
movdqa xmm0, XMMWORD PTR .LC1[rip]
movaps XMMWORD PTR 32[rsp], xmm0
movq xmm0, QWORD PTR 8[rsp]
mov QWORD PTR 8[rsp], rax
movhps xmm0, QWORD PTR 8[rsp]
movaps XMMWORD PTR 64[rsp], xmm0
jmp .L20
.L22:
test rax, rax
je .L36
mov rax, QWORD PTR 72[rsp]
.L20:
mov rsi, rbx
mov rdi, rbp
call rax
add rbx, 4
mov rax, QWORD PTR 64[rsp]
cmp rbx, r12
jne .L22
test rax, rax
je .L23
mov edx, 3
mov rsi, rbp
mov rdi, rbp
call rax
.L23:
mov rdi, r13
call _Z11print_arrayRKSt5arrayIiLm8EE
xor eax, eax
mov rdx, QWORD PTR 88[rsp]
xor rdx, QWORD PTR fs:40
jne .L37
add rsp, 104
pop rbx
pop rbp
pop r12
pop r13
ret
.L36:
call _ZSt25__throw_bad_function_callv@PLT
.L27:
mov rbx, rax
mov rax, QWORD PTR 64[rsp]
test rax, rax
je .L25
mov edx, 3
mov rsi, rbp
mov rdi, rbp
call rax
.L25:
mov rdi, rbx
call _Unwind_Resume@PLT
.L37:
call __stack_chk_fail@PLT

.LC0:
.long 10
.long 11
.long 12
.long 13
.align 16
.LC1:
.long 14
.long 15
.long 16
.long 17

はい、これだけ処理が冗長になります。

一応解説しておくと、最初の

_ZNSt17_Function_handlerIFvRiEZ4mainEUlS0_E_E9_M_invokeERKSt9_Any_dataS0_:

add DWORD PTR [rsi], 1
ret

というセクションで実際にラムダ式の処理(引数をインクリメント)を行っています。

このセクションはインライン化されておらず、従って毎回この処理を行うためだけにジャンプ命令が呼び出されることになります。

また、ジャンプ命令を呼ぶ側では、

    mov rax, QWORD PTR 64[rsp]

call rax

といったように、一度メモリから該当するセクションのアドレスを読み込み、callするという所謂「間接参照」を行っていることも分かります。

さらに、

.L22:

test rax, rax
je .L36
mov rax, QWORD PTR 72[rsp]
.L20:
mov rsi, rbx
mov rdi, rbp
call rax
add rbx, 4
mov rax, QWORD PTR 64[rsp]
cmp rbx, r12
jne .L22

この部分はループ処理を行っています。

std::arrayの要素の最初のポインタから、4バイト(1要素)ずつ移動、最後の要素に到達するまでループ。

この程度のループなら普通はコンパイラが自動で展開してくれるはずなのですが、funcの呼び出しが影響してなのか、ループがそのまま残ってしまっています。さらにそのせいで、Simdによる並列化も行われていません。


まとめ

function_refはオブジェクトをコピーせずに関数オブジェクトを統合的に扱うインターフェースを提供し、また最適化によってインライン化されるため呼び出しコストもゼロになります。


追記(2018/11/13)

Intel C++ Compiler(19.0.1.1444)ではfunction_refを用いた場合もinline化されませんでした。gccもclangもインライン化出来たのに何故だー!

詳しい人がいたらご教示ください。。。


追記2(2018/11/13)

Intel C++ Compilerでは、関数内で関数ポインタの変数を初期化するとインライン化されないようです。

また、上記の実装の場合、gccにおいてfunction_refのコンストラクタにラムダ式以外のオブジェクトを与えるとインライン化されませんでした。


追記3(2018/11/14)

GCCで関数ポインタを与えた時にインライン化されない問題は、ラムダ式でラップすることにより解決。

Intel C++ Compilerの問題は未だに解決せず。