C++ の範囲:カウントされたイテラブルと効率

私は範囲ライブラリを具体化し、範囲サポートを標準に組み込むための提案を書くことに懸命に取り組んできました。その提案は、基本的な範囲の概念である Iterable を説明しています。 Iterable std::begin() に渡すことができるもの そして std::end() Iterator/Sentinel ペアを取得します。センチネルは、今年初めにここで説明したように、Iterable の概念が反復子ペア以外の他の種類の範囲を効率的に記述することを可能にします。

Iterable の概念で効率的にモデル化できるようにしたい 3 つのタイプの範囲は次のとおりです。

<オール>
  • 2 つの反復子
  • 反復子と述語
  • イテレータとカウント
  • Iterator/Sentinel の抽象化により、アルゴリズムはこれら 3 つのケースを統一された構文で処理できるようになります。ただし、Sean Parent がここで指摘したように、3 番目のオプションは、いくつかのアルゴリズムを最適に効率化しようとするときに課題を提示します。 2 月に Sean が批判を申し出たとき、私はそのデザインを正当化するブログ投稿でフォローアップすることを約束しました。これがその投稿です。

    注 1: 2 月の投稿以降、用語を変更しました。これらの投稿では、Iterable begin の範囲を表します と end さまざまなタイプがあり、Range それらが同じである Iterable です。私の現在の提案では、Iterable ほぼ以前と同じですが、範囲 要素を所有しない Iterable になりました。

    注 2: この投稿では、まだ採用されていない Concepts Lite の構文を使用しています。この投稿のすべては、ここで説明する Concepts Lite エミュレーション用のライブラリを使用して C++11 で実装できます。

    カウントされた範囲

    位置と要素の数を指定することによって形成されるカウントされた範囲には、反復子があります — すべての Iterable がそうであるように。カウントされた範囲の反復子は、範囲の範囲と、範囲に到達するまでの距離を認識している必要があります。したがって、カウントされた範囲のイテレータは、基になるシーケンスへのイテレータとカウント (最後までのカウントまたは先頭からのカウント) の両方を格納する必要があります。考えられるデザインの 1 つを次に示します。

    class counted_sentinel
    {};
    
    template<WeakIterator I>
    class counted_iterator
    {
        I it_;
        DistanceType<I> n_; // distance to end
    public:
        // ... constructors...
        using iterator_category =
            typename iterator_traits<I>::iterator_category;
        decltype(auto) operator*() const
        {
            return *it_;
        }
        counted_iterator & operator++()
        {
            ++it_;
            --n_;
            return *this;
        }
        friend bool operator==(counted_iterator const & it,
                               counted_sentinel)
        {
            return it.n_ == 0;
        }
        // ... other operators...
    };
    
    template<WeakIterator I>
    class counted_range
    {
        I begin_;
        DistanceType<I> count_;
    public:
        // ... constructors ...
        counted_iterator<I> begin() const
        {
            return {begin_, count_};
        }
        counted_sentinel end() const
        {
            return {};
        }
    };
    

    上記のコードには注目すべき点がいくつかあります。まず、counted_iterator イテレータとカウントをバンドルします。すぐに、カウントされたイテレータをコピーするとコストが高くなり、イテレータが頻繁にコピーされることがわかります。緩和要因は、センチネルが空であることです。 counted_iterator を渡す そして counted_sentinel イテレータとカウントを渡すのと同じ量のデータをアルゴリズムにコピーします。別々に渡された場合、コンパイラーはおそらくそれらをレジスターに適合させるのがより簡単になりますが、一部の最新のコンパイラーは構造体のメンバーをレジスターに渡すことができます。このコンパイラの最適化は、集計のスカラー置換と呼ばれることもあります 1、2 gcc と LLVM で実装されていることが知られています (たとえば、この最近の LLVM コミットを参照してください)。

    また、カウントされたイテレータをインクリメントするのはコストがかかります。基礎となるイテレータをインクリメントし、内部カウントをデクリメントする必要があります。これが潜在的にコストがかかる理由を理解するには、counted_iterator<list<int>::iterator> を渡す簡単なケースを考えてみてください。 advance へ .カウントされた反復子の型は双方向で、advance n インクリメントする必要があります 回:

    template<BidirectionalIterator I>
    void advance(I & i, DistanceType<I> n)
    {
        if(n >= 0)
            for(; n != 0; --n)
                ++i;
        else
            for(; n != 0; ++n)
                --i;
    }
    

    ++i ごとに または --i こちら、2 I のときに増分または減分が発生しています counted_iterator です .これは準最適です。 counted_iterator のより良い実装 です:

    template<BidirectionalIterator I>
    void advance(counted_iterator<I> & i, DistanceType<I> n)
    {
        i.n_ -= n;
        advance(i.it_, n);
    }
    

    これは、生成されたコードに顕著な影響を与えます。結局のところ、advance counted_iterator の特別な処理が行われている標準ライブラリの比較的数少ない場所の 1 つです。 有利です。アルゴリズムをいくつか調べて、その理由を見てみましょう。

    カウントされた反復子を使用したシングルパス アルゴリズム

    まず、for_each のような単純なアルゴリズムを見てみましょう 入力シーケンスを 1 回だけ通過する:

    template<InputIterator I, Regular S,
             Function<ValueType<I>> F>
        requires EqualityComparable<I, S>
    I for_each(I first, S last, F f)
    {
        for(; first != last; ++first)
            f(*first);
        return first;
    }
    

    カウントされた反復子が渡されると、ループの反復ごとに、インクリメント、デクリメント (基になるイテレータとカウント)、および比較が行われます。これを架空の for_each_n と比較してみましょう 基礎となる反復子とカウントを別々に取るアルゴリズム。次のようになります:

    template<InputIterator I, Function<ValueType<I>> F>
    I for_each_n(I first, DifferenceType<I> n, F f)
    {
        for(; n != 0; ++first, --n)
            f(*first);
        return first;
    }
    

    架空の for_each_n の場合 、各ループ反復で、インクリメント、デクリメント、および比較を行います。それはちょうど for_each と同じ数の操作です カウントされたイテレータが渡されたときに行います。別の for_each_n センチネルと counted_iterator がある場合、アルゴリズムはおそらく不要です 秒。これは、入力範囲を 1 回だけ通過するアルゴリズムに当てはまります。それは多くのアルゴリズムであることが判明しました.

    カウントされたイテレータを使用したマルチパス アルゴリズム

    入力シーケンスを複数回通過させるアルゴリズムは他にもあります。ただし、それらのほとんどは advance を使用します イテレータを複数のホップで移動する必要がある場合。 advance を特化したら counted_iterator の場合 、advance を使用するアルゴリズム 余分な作業なしで高速化。

    partition_point を検討してください .以下は、libc++ から取得され、Concepts Lite およびセンチネルに移植された 1 つの実装例です:

    template<ForwardIterator I, Regular S,
             Predicate<ValueType<I>> P>
        requires EqualityComparable<I, S>
    I partition_point(I first, S last, P pred)
    {
        DifferenceType<I> len = distance(first, last);
        while (len != 0)
        {
            DifferenceType<I> l2 = len / 2;
            I m = first;
            advance(m, l2);
            if (pred(*m))
            {
                first = ++m;
                len -= l2 + 1;
            }
            else
                len = l2;
        }
        return first;
    }
    

    I を想像してみてください フォワード counted_iterator です と S counted_sentinel です .ライブラリが advance に特化していない場合 、これは確かに非効率的です。毎回 advance と呼ばれ、無駄な作業が行われています。架空の partition_point_n と比較してください :

    template<ForwardIterator I, Predicate<ValueType<I>> P>
    I partition_point_n(I first, DifferenceType<I> len, P pred)
    {
        while (len != 0)
        {
            DifferenceType<I> l2 = len / 2;
            I m = first;
            advance(m, l2);
            if (pred(*m))
            {
                first = ++m;
                len -= l2 + 1;
            }
            else
                len = l2;
        }
        return first;
    }
    

    最初に気付くのは、partition_point_n です。 distance を呼び出す必要はありません !注意すべきより微妙なことは、 partition_point_n を呼び出すことです 生の反復子とカウントを使用すると、partition_point への同等の呼び出しよりも約 O(N) の整数デクリメントを節約できます counted_iterator で s … もちろん、advance を特殊化している場合を除きます 上記のアルゴリズム。取得したら、O(N) 整数減分を O(log N) 整数減算と交換します。これは大きな改善です。

    しかし、distance への O(N) 呼び出しはどうでしょうか。 ?実際、それは簡単です。それが SizedIteratorRange という概念を導入した理由です。 . counted_iterator 最後までの距離を保存します。 counted_iterator 間の距離は そして counted_sentinel (または 2 つの counted_iterators の間) ) は O(1) イテレータのカテゴリに関係なく . SizedIteratorRange の概念は、反復子 I かどうかをテストします そして歩哨 S 距離を得るために減算することができます。この概念は、その性質上、ランダムアクセス反復子によってモデル化されていますが、カウントされた反復子とそのセンチネルによってもモデル化されています。 distance アルゴリズムは SizedIteratorRange に特化しているため、カウントされたイテレータの場合は O(1) です。

    これらの変更により、partition_point が表示されます。 カウントされたイテレータを使用すると、仮想の partition_point_n とほぼ同じくらい効率的です 特別な配慮をする必要はありませんでした。 partition_point を作成できない理由 正確に partition_point_n と同じくらい効率的 ? partition_pointの場合 カウントされたイテレータで呼び出された場合、も返されます カウントされたイテレータ。カウントされた反復子には、位置と最後までの距離の 2 つのデータムが含まれます。しかし partition_point_n の場合 位置のみを返しますが、実際には計算して返す情報は少なくなります。ユーザーが追加情報を必要としない場合もあります。しかし、時々 partition_point_n を呼び出した後 、ユーザーは結果の反復子を別のアルゴリズムに渡したい場合があります。 もし アルゴリズムは distance を呼び出します (partition_point のように および他のアルゴリズムが行う)、O(N) になります。ただし、カウントされたイテレータでは O(1) です。 partition_point の場合 、カウントされた反復子により、アルゴリズムは O(log N) 余分な作業を行いますが、後で O(N) 作業を節約できる場合があります。

    例を見るには、些細な insertion_sort を想像してください アルゴリズム:

    template<ForwardIterator I, Regular S>
        requires EqualityComparable<I, S> &&
                 Sortable<I> // from N3351
    void insertion_sort(I begin, S end)
    {
        for(auto it = begin; it != end; ++it)
        {
            auto insertion = upper_bound(begin, it, *it);
            rotate(insertion, it, next(it));
        }
    }
    

    I を想像してみてください counted_iterator です .まず upper_bound distance を呼び出します . distance を作る counted_iterator の場合は O(1) ■ O(N) アルゴリズムの N 回の呼び出しを保存します。現在の STL で同等の手順で同等のパフォーマンスを得るには、ユーザーは別の insertion_sort_n を記述する必要があります。 upper_bound_n にディスパッチするアルゴリズム アルゴリズム — 彼らも自分で書く必要があります.

    カウント イテレータを使用したカウント アルゴリズム

    カウントされたイテレータを使用した通常のアルゴリズムは、専用のカウントされたアルゴリズムとほぼ同じくらい効率的であり、わずかなパフォーマンスの低下を補う以上の効果があることがわかりました。ただし、すべてがバラではありません。多くの カウント アルゴリズム があります 標準 (名前が _n で終わるアルゴリズム) )。 copy_n を検討してください :

    template<WeakInputIterator I,
             WeakOutputIterator<ValueType<I>> O>
    pair<I, O> copy_n(I in, DifferenceType<I> n, O out)
    {
        for(; n != 0; ++in, ++out, --n)
            *out = *in;
        return {in, out};
    }
    

    (copy_n の戻り値の型を変更しました 情報を失わないように。) If I ++in ごとに数えられる反復子です。 、インクリメントとデクリメントが発生しています。この場合、余分なデクリメントはまったく不要です。 すべての カウント (つまり、_n ) アルゴリズムでは、カウントされた反復子を渡したときにパフォーマンスが低下しないようにするために、何か特別なことを行う必要があります。

    ここでアルゴリズムの作成者には 2 つのオプションがあり、どちらも理想的ではありません。

    オプション 1:アルゴリズムをオーバーロードする

    以下は copy_n の最適化バージョンです カウントされた反復子:

    template<WeakInputIterator I,
             WeakOutputIterator<ValueType<I>> O>
    pair<I, O> copy_n(counted_iterator<I> in,
                      DifferenceType<I> n, O out)
    {
        for(auto m = in.n_ - n; in.n_ != m;
                ++in.i_, --in.n_, ++out)
            *out = *in;
        return {in, out};
    }
    

    明らかに、カウントされた反復子のオーバーロードを作成することは満足のいくものではありません。

    オプション 2:イテレータをカウントから分離する

    このオプションは、ライブラリの実装者が copy_n の 1 つのバージョンだけを作成する方法を示しています。 カウントされたイテレータ用に自動的に最適化されます。まず、カウントされたイテレータをアンパックおよびリパックするための 2 つのユーティリティ関数を提供する必要があります:

    template<WeakIterator I>
    I uncounted(I i)
    {
        return i;
    }
    
    template<WeakIterator I>
    I uncounted(counted_iterator<I> i)
    {
        return i.it_;
    }
    
    template<WeakIterator I>
    I recounted(I const &, I i, DifferenceType<I>)
    {
        return i;
    }
    
    template<WeakIterator I>
    counted_iterator<I> recounted(counted_iterator<I> const &j, I i, DifferenceType<I> n)
    {
        return {i, j.n_ - n};
    }
    

    uncounted の助けを借りて と recounted 、最適化された copy_n を書くことができます 一度だけ:

    template<WeakInputIterator I,
             WeakOutputIterator<ValueType<I>> O>
    pair<I, O> copy_n(I in_, DifferenceType<I> n_, O out)
    {
        auto in = uncounted(in_);
        for(auto n = n_; n != 0; ++in, --n, ++out)
            *out = *in;
        return {recounted(in_, in, n_), out};
    }
    

    このバージョンは、カウントされるイテレータとカウントされないイテレータの両方で最適に機能します。しかし、それは美しいものではありません。 uncounted しなければならないのは少し面倒です。 /recounted しかし、それは主にカウントされたアルゴリズムでのみ必要です.

    最後の注意として、advance のオーバーロード カウントされたイテレータは uncounted の助けを借りて排除できます と recounted .結局、advance カウントアルゴリズムです。

    ベンチマーク:挿入ソート

    カウント範囲とカウント イテレータのコストをテストするために、ベンチマークを作成しました。ベンチマーク ピットは、専用の _n に対して範囲をカウントしました 挿入ソートのアルゴリズム。プログラムはこの要旨に記載されています。

    プログラムは insertion_sort_n の両方を実装しています 、専用のカウント アルゴリズム、および insertion_sort は、カウントされた範囲を渡す任意の Iterable を受け入れる一般的なアルゴリズムです。後者は、汎用 upper_bound の観点から実装されています Range v3 ライブラリによって提供されるように、前者には専用の upper_bound_n が必要です アルゴリズムも提供されています。

    このテストは、生のポインター (したがって、ランダム アクセス) と、ForwardIterator のみをモデル化するイテレーター ラッパーの両方を使用して実行されます。各テストは 3 回実行され、結果の時間は平均されます。テストは g++ でコンパイルされました -O3 -std=gnu++11 -DNDEBUG のバージョン 4.9.0 Linux マシンで実行します。 N ==30,000 の場合の結果を以下に報告します:

    insertion_sort_n insertion_sort
    ランダムアクセス 2.692 秒 2.703 秒
    フォワード 23.853 秒 23.817 秒

    パフォーマンスの違いがあったとしても、ノイズの中で失われます。少なくともこの場合、このコンパイラ、このハードウェアでは、専用の _n のパフォーマンスを正当化する理由はありません。

    まとめ

    要するに、カウントされたイテレータは完璧ではありません 抽象化。ここには前例があります。 deque の反復子 、およびセグメント化されたデータ構造に対しては、非効率的であることが知られています (Segmented Iterators and Hierarchical Algorithms、Austern 1998 を参照)。その問題の修正、新しい反復子の抽象化と個別の階層アルゴリズムの実装は侵襲的であり、私が知っている STL 実装では試みられていません。それに比べて、カウントされた反復子に伴う追加の複雑さは非常に小さいように見えます。セグメント化された反復子の利点は、反復子の抽象化の単純さと統一性です。カウントされた範囲と反復子の場合、利点は反復可能な概念の単純さと統一性です。アルゴリズムに必要な形式は 1 つだけであり、境界付き、カウント済み、およびセンチネル形式を分離する必要はありません。ベンチマークは、統一的な抽象化のためにパフォーマンスを犠牲にしすぎていないという合理的な保証を与えてくれます.

    "\e"
    "\e"