Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

概要

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

Kogia_sima
Rustはじめました
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away