c - Cでのmemset関数の複雑さ

Question

私は何人かの友人とコードの一部について話し合っていました。Cでmemset関数を使用することについて話し合いました。これは、サイズNの配列を初期化する場合のこの関数のBig-O表記の順序です。

Answer 1

ページテーブルに直接アクセスでき、それらが階層的に格納されているシステムでは、仮想アドレスマッピング全体を、指定されたバイト値で満たされた単一ページへのコピーオンライト参照に置き換えるmemsetことで実装できます。 O(log n)。ただし、オブジェクトに将来変更を加える場合は、ページフォールトに通常のO(n)コストmemsetが延期され、変更時にページの個別のコピーがインスタンス化されることに注意してください。

Answer 2

あなたは複雑さについて尋ねましたが、おそらくパフォーマンスについて尋ねることを意図していました。

表記O（n）で参照される複雑さは、問題のサイズが大きくなるにつれて、アルゴリズムの操作の数をどのように増やすかに関する概念です。O（n）は、入力サイズに比例するいくつかのステップを実行する必要があることを意味します。その割合が何であるかはわかりません。memsetはO（n）です。O（n ^{2 ）は、 n2}に比例するいくつかのステップを実行する必要があることを意味します。memsetはO（n ²）ではありません。これは、2nバイトの設定には、一般に4倍の作業ではなく、nバイトの2倍の作業しかかからないためです。

memsetのライブラリバージョンは、作成するCバージョンよりもはるかに高速に実行されるため、memsetのパフォーマンスに関心がある可能性があります。

ライブラリバージョンは、特殊な命令を使用するため、はるかに高速に実行されます。最近の最も一般的なプロセッサには、1つの命令で16バイトをメモリに書き込むことができる命令があります。ライブラリの実装者は、memsetなどの重要な関数をアセンブリ言語またはそれに近いもので記述しているため、これらすべての命令にアクセスできます。

Cで書く場合、コンパイラがこれらの命令を利用することは困難です。たとえば、設定しているメモリへのポインタが16バイトの倍数に揃えられていない可能性があります。memsetの作成者は、ポインターをテストし、ケースごとに異なるコードに分岐するコードを記述します。これは、いくつかのバイトを個別に設定してから、ポインターを整列させることを目的としているため、16バイトを格納する高速命令を使用できます。時間。これは、ライブラリの実装者がmemsetなどのルーチンを作成するときに対処する多くの問題の1つにすぎません。

これらの複雑さのために、コンパイラはmemsetのC実装を簡単に取得して、専門家が作成する高速コードに変換することはできません。コンパイラは、Cコードで、一度に1バイトを書き込むループを検出すると、通常、一度に1バイトを書き込むアセンブリ言語を生成します。オプティマイザーはよりスマートになっていますが、複雑さにより、めったに発生しない可能性のあるケースを処理するための多くのコードを生成せずに、実行できる量と実行できる量が制限されます。

Answer 3

複雑さはO（n）です。これは基本的なものです。

Answer 4

一部のCライブラリは、のベクトル化されたバージョンを提供しますmemset()。コンパイラが自動ベクトル化とループ展開を行わない限り、forループはベクトル化よりもはるかに遅くなりますmemset()。ベクトル化されているかどうかは、memset()メモリ帯域幅によって制限され、最小時間はアレイサイズをメモリ帯域幅で割った値に比例します。つまり、メモリ帯域幅は一定であるため、O（n）演算です。

NUMAマシンでは、NUMAノードの数のオーダーの高速化を実現するために、非常に大きな配列をmemsettingするスレッドを作成できます。いくつかのベンチマークについては、この回答を参照してください。