[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の問題は未だに解決せず。