範囲の概念、パート 3/4:Iterable の紹介

過去 2 回のブログ投稿では、次世代の範囲ライブラリを構築する際に遭遇した課題について説明しています。この投稿では、私が提案する解決策をスケッチします。パフォーマンスや表現力を失うことなく、区切り記号付き、無限、およびペアの反復子スタイルの範囲を概念階層内に快適に収めることができる範囲概念の改良と、安全性を高めます。 すべてを包含し、拡張するこれらの概念の周りに範囲ライブラリを構築しました C++98 STL アルゴリズムのおよび Boost.Range アダプターを使用しているため、これらの概念が有用で一貫性のある一般的な範囲ライブラリーにつながると自信を持って言えます。

まとめ

前回の投稿の最後で、ペア オブ イテレータ (PoI) スタイルの範囲の問題を次のようにまとめました。

  • 区切られた範囲と無限の範囲が不適切なコードを生成する
  • これらの範囲タイプは、そうでない場合よりも弱い概念をモデル化することを余儀なくされることがあります
  • 一部のアルゴリズムでの無限範囲の使用は安全ではありません
  • 区切られた範囲と無限の範囲は、必要以上に実装が困難です
  • おそらく無限の範囲は、00 をオーバーフローする可能性があります

創刊号は特に飲み込むのが難しいので、この投稿ではそこに力を注ぎます。

レンジのコンセプト

先に進む前に、「範囲」が何を意味するかについてもう少し正式に説明しましょう。 C++ 標準では、「範囲」という言葉を正式に定義せずにいたるところで使用しています。しかし、セクション [iterator.range] から、範囲は 15 を呼び出すことができるものであると推測できます。 そして 20 begin から end に到達できるイテレータのペアを取得します。現在の「Concepts Lite」提案の言語では、Range の概念を次のように形式化できます。

using std::begin;
using std::end;

template<typename T>
using Iterator_type =
    decltype(begin(std::declval<T>()));

template<typename T>
concept bool Range =
    requires(T range) {
        { begin(range) } -> Iterator_type<T>;
        { end(range) }  -> Iterator_type<T>;
        requires Iterator<Iterator_type<T>>;
    };

これは基本的に、 32 を呼び出すことができることを示しています と 45 範囲で、イテレータを返すこと。 51 の改良点があります 65 と呼ばれる概念 (表示されていません) 、 72 など、より多くのイテレータを必要とするだけです。絞り込み階層を以下に示します。それはかなり簡単です。 (上記の構文は、Concepts Lite 提案の著者である Andrew Sutton によって、2014 年 2 月の標準化委員会の会議の直後に提供されたものであり、新しいことが保証されています。彼は、構文が将来変更される可能性があることを警告しています。)

範囲概念階層

これらの概念は、Boost.Range ライブラリの基礎です。

問題 1:コード生成が不十分

思い出してください、区切り範囲と無限範囲をイテレーターのペアとして実装するには、終了イテレーターはある種の番兵イテレーターでなければなりません。センチネルは概念を表します 物理的なものではなく、位置。最後のプラス 1 の位置と考えることができますが、唯一の違いは、到達するまで物理的な位置がわからないことです。番兵は反復子と同じ型を持っているため、指定された反復子が番兵であるかどうかを判断するには実行時テストが必要です。これにより、反復子の比較が遅くなり、範囲の実装がぎこちなくなります。

反復可能なコンセプト

イテレータで行うことを考えてみてください。それらをインクリメントし、逆参照し、それらが等しいかどうかを比較しますよね?センチネル イテレータを使用して何ができますか?あまりない。物理的な位置ではなく、概念的な位置を表しているため、位置を変更することはできません。それらは常に最後のプラス 1 の位置を表すため、逆参照できません。これは逆参照できません。しかし、あなたはできます イテレータと比較してください。言い換えれば、センチネルはとても 弱いイテレータ

区切られた範囲と無限の範囲の問題は、センチネル イテレータを通常のイテレータにしようとすることに起因します。それはただ一つではなく、そのようにすることは問題を引き起こします.だから、そのままにしておいてください。つまり:

範囲センチネルがその範囲の反復子とは異なる型を持つようにします。

範囲の概念では、開始イテレータと終了イテレータが同じ型である必要があります。タイプの違いを許容する場合、Range よりも弱いものについて話していることになります:Iterable 概念。 Iterable は、begin と end の型が異なることを除けば、Range と同じです。 Iterable の概念は次のとおりです。

template<typename T>
using Sentinel_type =
    decltype(end(std::declval<T>()));

template<typename T>
concept bool Iterable =
    requires(T range) {
        { begin(range) } -> Iterator_type<T>;
        { end(range) }  -> Sentinel_type<T>;
        requires Iterator<Iterator_type<T>>;
        requires EqualityComparable<
            Iterator_type<T>, Sentinel_type<T>>;
    };

template<typename T>
concept bool Range =
    Iteratable<T> &&
    Same<Iterator_type<T>, Sentinel_type<T>>;

すべての Range は自明な Iterables です。つまり、Range の概念は、1 つの追加の制約を追加することによって Iterable を改良します。つまり、begin と end は同じ型を持つということです。実際、Iterable の概念階層は、Range 階層とよく似ています。

反復可能な概念階層

これは、Range、Iterable、および Iterator を検討したときに階層がどのように見えるかですが、コードでこれらの概念を実際に定義する方法であるとは限りません。 「範囲性」、つまり、begin と end が同じ型であるかどうかは、begin イテレータの強度と直交することに注意してください。型モデル RandomAccessRange を要求したい場合、83 と言えます。 他の範囲の概念を完全に廃止します。

たとえば、BidirectionalIterable と ForwardIterable の違いは、Iterable の begin イテレータによってモデル化された概念にあります。 98 の場合 105 の制約 コンセプトはあなたに一時停止を与え、読み進めます。以下にその理由を説明します。

イテラブルと STL アルゴリズム

「でも待って」とあなたは言います。 「いいえ STL アルゴリズムは、begin と end が同じ型を持つことを想定しているため、Iterables で機能します!」それは悲しいことに本当です。だから私はすべてを経験した STL アルゴリズムを使用して、どちらがより弱い概念の観点から再実装できるかを確認します。 115を取る 例:

template<class InputIterator, class Value>
InputIterator
find(InputIterator first, InputIterator last,
     Value const & value)
{
    for (; first != last; ++first)
        if (*first == value)
            break;
    return first;
}

今日、124 範囲が必要です。しかし、このアルゴリズムが終了反復子の位置を決して変更しようとしないことに注目してください。 137 アルゴリズムは、Ranges の代わりに Iterables で動作するように非常に簡単に変更できます:

template<class InputIterator, class Sentinel, class Value>
InputIterator
find(InputIterator first, Sentinel last,
     Value const & value)
{
    for (; first != last; ++first)
        if (*first == value)
            break;
    return first;
}

それでおしまい。変更は非常に小さいため、見つけるのに苦労するかもしれません!

では、どの C++98 アルゴリズムを Range の代わりに Iterable で動作させることができるのでしょうか?それらのほぼすべてが判明しました。実際、そうでないものをリストする方が簡単です イテラブルで動作します。それらは:

  • 147
  • ヒープ アルゴリズム (151165170181 )
  • 190
  • 203
  • 213226
  • 230241
  • 252
  • 264273
  • 289292
  • 305

50 人ほどの他の人にとって、Iterables で動作させるには、ほとんどがソース コードを機械的に変換する必要があります。 Range がそれを改良するように Iterable の概念を定義することにより、Iterable に関して実装されたアルゴリズムは自動的に Ranges と連携し、コードを再利用できるようになります。そして、それは非常に重要です。イテレータ用に書かれたコードが多すぎて、互換性のない抽象化を選択することを考えることができません。

証明はPerfにあります

しかし、私たちは何を得ますか?古い友人である C スタイルのヌル終了文字列をもう一度見てみましょう。以前の投稿で、 319 を定義しました クラスを調べたところ、文字を反復すると非常に悪いコードが生成されることがわかりました。今度は 323 を使ってもう一度試してみましょう Range の代わりに Iterable を構築するヘルパー。コードは次のようになります:

using namespace ranges;
struct c_string_iterable
  : range_facade<c_string_iterable>
{
private:
    friend range_core_access;
    char const *sz_;
    char const & current() const { return *sz_; }
    void next() { ++sz_; }
    bool done() const { return *sz_ == 0; }
    bool equal(c_string_iterable const &that) const
    { return sz_ == that.sz_; }
public:
    c_string_iterable(char const *sz)
        : sz_(sz) {}
};

最初に気付くのは、このコードがロットであるということです 古い 332 よりもシンプル クラス。 340 ヘルパーはここですべての面倒な作業を行います。イテレータとセンチネルはすべて、示されているプリミティブに関して実装されています。厄介で複雑な等価比較はなくなりました。しかし、それはどのように機能しますか?それをテストするために、次の 2 つの関数用に最適化されたアセンブリを生成しました。 クラス、および新しい 368 を使用するクラス :

// Range-based
int range_strlen(
    c_string_range::iterator begin,
    c_string_range::iterator end)
{
    int i = 0;
    for(; begin != end; ++begin)
        ++i;
    return i;
}

// Iterable-based
int iterable_strlen(
    range_iterator_t<c_string_iterable> begin,
    range_sentinel_t<c_string_iterable> end)
{
    int i = 0;
    for(; begin != end; ++begin)
        ++i;
    return i;
}

アセンブリ コードについてあまり知らなくても、次のことを理解する必要があります。

378 388
    pushl    %ebp
    movl    %esp, %ebp
    pushl    %esi
    leal    8(%ebp), %ecx
    movl    12(%ebp), %esi
    xorl    %eax, %eax
    testl    %esi, %esi
    movl    8(%ebp), %edx
    jne    LBB2_4
    jmp    LBB2_1
    .align    16, 0x90
LBB2_8:
    incl    %eax
    incl    %edx
    movl    %edx, (%ecx)
LBB2_4:
    testl    %edx, %edx
    jne    LBB2_5
    cmpb    $0, (%esi)
    jne    LBB2_8
    jmp    LBB2_6
    .align    16, 0x90
LBB2_5:
    cmpl    %edx, %esi
    jne    LBB2_8
    jmp    LBB2_6
    .align    16, 0x90
LBB2_3:
    leal    1(%edx,%eax), %esi
    incl    %eax
    movl    %esi, (%ecx)
LBB2_1:
    movl    %edx, %esi
    addl    %eax, %esi
    je    LBB2_6
    cmpb    $0, (%esi)
    jne    LBB2_3
LBB2_6:
    popl    %esi
    popl    %ebp
    ret
        
    pushl    %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    xorl    %eax, %eax
    cmpb    $0, (%ecx)
    je    LBB1_4
    leal    8(%ebp), %edx
    .align    16, 0x90
LBB1_2:
    cmpb    $0, 1(%ecx,%eax)
    leal    1(%eax), %eax
    jne    LBB1_2
    addl    %eax, %ecx
    movl    %ecx, (%edx)
LBB1_4:
    popl    %ebp
    ret
        

Iterable アルゴリズムから生成されたコードは far です イテレータのペアから生成されたものよりも優れています。実際、生の C スタイル反復のアセンブリと照合すると、ほとんど同じであることがわかります。

イテレータ、センチネル、等価性

しかし、それは意味 異なるタイプの 2 つのオブジェクトが等しいかどうかを比較するには?または、より正式な用語で言えば、Iterable のイテレーターとセンチネルがクロスタイプの EqualityComparable の概念を満たすという要件を満たすことができるでしょうか?答えはイエスだと思います。

初心者向けの背景:N3351 は 正確 を定義しています クロスタイプの等価比較がいつ、どのように意味を持つか。構文「x==y」が有効で 399 を生成するだけでは不十分です . 406 の場合 と 414 異なるタイプがあり、両方のタイプ 426432 それ自体が EqualityComparable である必要があり、共通の型が存在する必要があります どちらにも変換でき、その型も EqualityComparable である必要があります。 444 を比較することを考えてください 454 で . 467 両方の理由で機能します と 478 は EqualityComparable であり、両方とも 488 に変換できるため これは EqualityComparable でもあります。

イテレータは比較可能であり、センチネルは自明に比較可能です (それらは常に同等に比較されます)。トリッキーな部分は、一般的な型の要件です。論理的には、すべてのイテレータとセンチネルには、次のように構築できる共通の型があります:新しいイテレータ型 497 が存在すると仮定します。 これは、イテレータまたはセンチネルのいずれかを含むタグ付き共用体です。イテレータをセンチネルと比較すると、イテレータとセンチネルの両方が最初に 501 型の 2 つのオブジェクトに変換されたかのように意味的に動作します。 — それらを 514 と呼びます および 523 — 次に、次の真理値表に従って比較します:

530 546 557
561 576 587
590 602 616
628 636 643
659 663 673

このシリーズをフォローしている場合、上記の真理値表はベルを鳴らすはずです。 688 の等価演算子は動作するはずであり、それは偶然ではありません。これは、このより一般的な構造の特殊なケースでした。この構造は、私が書いた 2 つのクラス 694 を見た後の直感を検証します。 と 708 . 1 つは反復子のペアで、もう 1 つは反復子とセンチネルのペアですが、同等性を計算するための同等の手順を実装しています。 知っている それらは同じであり、すべてから同等の範囲を構築できると直感的に感じています。 パフォーマンスをいくらか犠牲にしても構わないと思っているなら、反復可能です。そして今、それが真実であることがわかりました。

反復子とセンチネルを直接比較できるようにすることで、C++ 型システムを使用して、等値比較演算子から分岐を排除することで、反復の大規模なカテゴリを最適化できます。

反論

開始イテレータと終了イテレータに異なる型を持たせるという考えは新しいものではなく、私のものでもありません。 (実際、ここまたは reddit.com の最初の 2 つの投稿にコメントした多くの人が、まさにこの提案をしています。) 私は何年も前に Dave Abrahams からこのことを初めて聞きました。最近では、Dietmar Kuehl が同様のアイデアを Ranges メーリング リストに投稿しました。 Sean Parent はフォローアップ メッセージで次の異議を唱えました:

私が Sean を正しく理解していれば、彼は 3 つの並列範囲概念階層 (IteratorRange、CountedRange、SentinelRange) を主張しています。これらの階層には、それらの間に洗練された関係はありません。 715 アルゴリズムには、概念階層ごとに 1 つずつ、3 つの基本的な実装があります。このように 3 重化する必要がある奇妙なアルゴリズムが 50 あります。これは多くのコード重複です。

実際、一部のアルゴリズムはより洗練された概念を利用するように特化されているため、それよりも悪いことです。たとえば、libc++ では 726 アルゴリズムは、前方、双方向、またはランダムアクセス反復子のいずれを渡すかに応じて、3 つの実装のいずれかにディスパッチします。 Iterator、Counted、および SentinelRanges に対応するには、合計で 9 731 が必要です。 アルゴリズムの実装!ショーン・ペアレントには敬意しかありませんが、それは狂気です。 Iterable の概念により、Sean の 3 つの個別の階層は、パフォーマンス特性を維持しながら一般的なアルゴリズムを記述できる単一の構文に統合されます。つまり、Iterables では、746 の 3 つの実装

(ちなみに、Iterable の概念は、カウントされた範囲にきちんと対応できます。イテレータとカウントを Iterable に変換したい場合は、イテレータとカウントを一緒に新しいイテレータ型にまとめて、イテレータがインクリメントされるたびにカウントをデクリメントすることができます。イテレータをセンチネルと比較するときは、カウントがゼロかどうかをチェックするだけです。)

まとめ、とりあえず…

この投稿の冒頭で、pair-o'-iterator の範囲に関するいくつかの問題をまとめました。新しい概念である Iterable がパフォーマンスの問題にどのように対処するかを示し、範囲の実装の複雑さの問題に少し触れました。 Iterable の概念が無限の範囲でどのように役立つか、または無限の範囲を処理できないアルゴリズムに無限の範囲を渡すことの安全性の問題に対処する方法については、まだ説明していません。この投稿は少し長くなったので、ここで中断し、最後の 4 回目の記事で他の問題に対処します。願わくば、それまでに考えるべきことがいくつかあったことを願っています。

コードをダウンロードして試してみたい場合は、github の range-v3 リポジトリで見つけることができます。提案やバグ報告は喜んで受け付けますが、このコードを実際の目的で使用しないでください。テストされておらず、まだ進化しています。

謝辞

Concept Lite 構文を支援し、クロスタイプ EqualityComparable コンセプトの要件を説明し、ここで提示されたアイデアの多くを一般的に改善および形式化してくれた Andrew Sutton に感謝します。彼の多くの貢献により、この記事は計り知れないほど優れています。

x
x