[ターン]。 NETパフォーマンス最適化 - リストコレクションを迅速にトラバース

管理者 · 掲載地 2022/08/28 20:51:16

簡単な紹介

System.Collections.Generic.List <T>は.NETの汎用コレクションクラスで、その利便性と豊富なAPIによりあらゆる種類のデータを保存可能で、日常生活で広く使われており、最も使われているコレクションクラスと言えるでしょう。

コード作成では、ビジネス<T>処理のためにListコレクションの要素を取得するために反復処理を行うことがよくあります。通常、セット内の要素は多くなく、移動も非常に速いです。しかし、ビッグデータ処理や統計、リアルタイムコンピューティングなどでは<T>、数万、あるいは数十万のデータリストを素早く移動するにはどうすればよいのでしょうか? それが今日、皆さんに伝えたいことです。

トラバーサルモード

異なるトラバーサル手法のパフォーマンスを見て、異なる桁数の収集トラバーサルを用いて異なる手法のパフォーマンスを評価し、次のパフォーマンスベンチマークを構築しましょう。コードスニペットは以下の通りです:

ログインが見えます。

foreach文を使います

foreachはコレクションをトラバースする最も一般的な方法であり、イテレーターパターンの構文によるシュガー実装であり、この時期のベンチマークとしても使われます。

ログインが見えます。

foreach文は構文シュガーであるため、コンパイラは最終的にGetEnumerator()とMoveNext()をwhileループで呼び出して機能を実装します。コンパイルされたコードは次のようになります:

MoveNext()メソッドの実装は、反復中コレクションを他のスレッドが変更しないようにし、もし変更が発生した場合はInvalidOperationException例外を投げ、現在のインデックスが正当かどうかを確認するオーバーフローチェックを行い、対応する要素を列挙子に割り当てる必要があります。現在の属性、つまり、実際には性能が最高とは言えません、コードスニペットは次のようになります:

異なるセットサイズでどのように機能するかを見てみると、結果は次のようになります:

異なるサイズの場合、時間のかかるプロセスの線形成長関係が必要であり、たとえ100Wのデータを処理ロジックなしで走査しても、少なくとも1秒かかります。

ForEachメソッドのリストを活用してください

もう一つの一般的な方法はListを使う<T>ことです。 ForEach() メソッドは、Action <T>delegateを渡し、Action delegateが要素を反復処理する際に呼び出すことができます<T>。

ログインが見えます。

これは<T>Listの内部実装手法であり、プライベート配列に直接アクセスしオーバーフローチェックを回避できます。理論上は速いはずですが、しかし、私たちのシナリオでは空メソッドは1つしかなく、foreachメソッドへの完全インライン呼び出しではうまく動作しない可能性があります。以下はForEachメソッドのソースコードで、オーバーフローチェックはないものの、同時バージョン番号チェックは保持していることを示しています。

さらに、ForEachメソッドにデリゲートを渡す必要があるため、呼び出しコードではクロージャ生成クラスのデリゲートオブジェクトが空であるかどうかを毎回チェックし、そうでなければ新しいAction()を以下のように確認します<T>。

パフォーマンス面でforeachキーワードと比べてどうか見てみましょう。以下の画像はベンチマークの結果を示しています。

テスト結果を見る限り、foreachキーワードを直接使うよりも40%遅いようです。必要がなければforeachを直接使う方が良いようですが、もっと速い方法はありますか?

ループトラバーサルに対して

最も古い方法に戻ると、forキーワードを使ってコレクションをトラバースします。現時点では最もパフォーマンスが良いトラバーサル手法であるはずです。なぜなら、前述のような冗長なコードを必要としないからです(ただしインデクサーはオーバーフロー防止のためにチェックされます)。また、明らかにバージョン番号もチェックしないので、マルチスレッド環境ではコレクションが変更され、for使用時に例外が出ません。テストコードは以下の通りです:

ログインが見えます。

どうなるか見てみましょう。

これが私たちが予想している通りのようです。forループを直接使うとforeachより60%速いですかつては1秒で通過していたセットは、現在ではわずか400ミリ秒で済みます。もっと速い方法はありますか?

CollectionsMarshal をご利用ください

.NET5以降、dotnetコミュニティはコレクション操作のパフォーマンスを向上させるためにCollectionsMarshalクラスを実装しました。このクラスは、コレクションタイプのネイティブ配列にアクセスする方法を実装しています(私の[ .NETパフォーマンス最適化 - コレクションタイプの初期サイズを設定するべきだという記事で、多くのデータ構造の基盤となる実装は配列であることはご存知でしょう)。そのため、あらゆる検出をスキップして、最も高速であるはずの元の配列に直接アクセスできます。コードは以下の通りです:

ログインが見えます。

コンパイラが生成するコードは非常に効率的であることがわかります。

基礎となる配列に直接アクセスするのは非常に危険なので、各コードの行で何をしているかを理解し、十分なテストを行う必要があります。ベンチマークの結果は以下の通りです:

ワウCollectionsMarshalを使うのはforeachを使うより79%速いですしかし、それがJIT最適化の理由であるべきであり、foreachを使うのとキーワードループのSpanを使うことに大きな違いはありません。

概要

今日はListコレクションを素早く移動する方法についてお話ししましたが、ほとんどの場合、オーバーフローチェックとマルチスレッドバージョン番号制御を備えたforeachキーワードの使用が推奨されており、正しいコードを書きやすくなります。

高性能かつ大量のデータ量が必要な場合は、CollectionsMarshal.AsSpanを直接利用してコレクションをトラバースすることをおすすめします。

この記事のソースコードリンク:

ハイパーリンクのログインが見えます。

元のリンク:ハイパーリンクのログインが見えます。

トビウオ · 掲載地 2022/09/04 22:15:52

学ぶために

ZGY0209ZGY · 掲載地 2022/09/08 10:33:05

学ぶために

SK4956 · 掲載地 2023/06/27 22:39:13

もしもし12306、データ付きプライベートメッセージを送ってもらえますか?

[出典] [ターン]。 NETパフォーマンス最適化 - リストコレクションを迅速にトラバース

関連記事

閲覧したセクション