13

「比較」して、2 つの間で等しい要素の数を確認する必要がある 16 要素 (文字) の 2 つの配列があります。

このルーチンは何百万回も使用されることになるため (通常の実行は約 6,000 万回から 7,000 万回)、できるだけ高速にする必要があります。私はC++に取り組んでいます（記録のためにC++Builder 2007）

今、私は簡単です：

matches += array1[0] == array2[0];

16回繰り返します（プロファイリングは、forループで実行するよりも30％高速であるように見えます）

より速く機能する他の方法はありますか？

環境とデータ自体に関するいくつかのデータ:

  • 私は C++Builder を使用していますが、考慮すべき速度の最適化はありません。最終的には別のコンパイラを試してみますが、今のところこれで行き詰まっています。
  • ほとんどの場合、データは異なります。通常、100% 等しいデータは非常にまれです (おそらく 1% 未満)。
4

15 に答える 15

17

更新: この回答は、私のコメントが以下のソース コードと一致するように変更されました。

SSE2 および popcnt 命令を使用できる場合は、最適化を利用できます。

たまたま 16 バイトが SSE レジスタにうまく収まります。C++ とアセンブリ/組み込み関数を使用して、2 つの 16 バイト配列を xmm レジスタにロードし、それらを cmp します。これにより、比較の真/偽の条件を表すビットマスクが生成されます。次に、movmsk 命令を使用して、ビットマスクのビット表現を x86 レジスタにロードします。これはビット フィールドになり、すべての 1 を数えて真の値がいくつあるかを判断できます。ハードウェア popcnt 命令は、レジスタ内のすべての 1 をすばやくカウントする方法です。

これには、特にアセンブリ/組み込み関数と SSE の知識が必要です。両方の Web リソースを見つけることができるはずです。

SSE2 も popcnt もサポートしていないマシンでこのコードを実行する場合は、配列を繰り返し処理し、アンロール ループ アプローチで差異をカウントする必要があります。

幸運を

編集：あなたはアセンブリを知らなかったと述べたので、私の答えを説明するサンプルコードを次に示します。

#include "stdafx.h"
#include <iostream>
#include "intrin.h"

inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
    __m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
    __m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );

    return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}

int _tmain( int argc, _TCHAR* argv[] )
{
    unsigned count = 0;
    char    arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
    char    arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };

    count = __popcnt( cmpArray16( arr1, arr2 ) );

    std::cout << "The number of equivalent bytes = " << count << std::endl;

    return 0;
}

いくつかのメモ: この関数は、SSE2 命令と、Phenom プロセッサ (私が使用しているマシン) に導入された popcnt 命令を使用します。SSE4 を搭載した最新の Intel プロセッサにも popcnt があると思います。この関数は、CPUID による命令のサポートをチェックしません。SSE2 または popcnt を備えていないプロセッサで使用した場合、関数は未定義です (無効な opcode 命令を取得する可能性があります)。その検出コードは別のスレッドです。

私はこのコードの時間を計測していません。高速だと思う理由は、ブランチレスで一度に 16 バイトを比較するためです。これを自分の環境に合わせて変更し、それが機能するかどうかを自分で時間をかけて確認してください。私はVS2008 SP1でこれを書いてテストしました。

SSE は、自然な 16 バイト境界に整列されたデータを優先します。追加の速度向上が得られることを保証できれば、_mm_loadu_si128 命令を _mm_load_si128 に変更できます。これにはアライメントが必要です。

于 2008-09-22T18:30:55.593 に答える
7

重要なのは、CPUがサポートする最大のレジスタを使用して比較を行い、必要に応じてバイトにフォールバックすることです。

以下のコードは4バイト整数を使用して示していますが、SIMDアーキテクチャ（最新のIntelまたはAMDチップ）で実行している場合は、整数ベースのループにフォールバックする前に、1つの命令で両方の配列を比較できます。最近のほとんどのコンパイラは128ビットタイプを本質的にサポートしているため、ASMは必要ありません。

（SIMD比較の場合、配列は16バイトに整列する必要があり、一部のプロセッサ（MIPSなど）では、intベースの比較のために配列を4バイトに整列する必要があることに注意してください。

例えば

int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];

int same = 0;

for (int i = 0; i < 4; i++)
{
  // test as an int
  if (array1[i] == array2[i])
  {
    same += 4;
  }
  else
  {
    // test individual bytes
    char* bytes1 = (char*)(array1+i);
    char* bytes2 = (char*)(array2+i);

    for (int j = 0; j < 4; j++)
    {
      same += (bytes1[j] == bytes2[j];
    }
  }
}

MSVCコンパイラがSIMDに対して何をサポートしているかを正確に思い出せませんが、次のようなことができます。

// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];

// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
    same = 16;
}
else
{
    // do int/byte testing
}
于 2008-09-22T18:23:05.893 に答える
2

配列の位置を制御する機能がある場合、たとえばメモリ内に配列を次々と配置すると、最初のアクセスで配列が CPU のキャッシュに読み込まれる可能性があります。

これは、CPU とそのキャッシュ構造に依存し、マシンによって異なります。

Henessy & Patterson の Computer Architecture: A Quantitative Approachでメモリ階層とキャッシュについて読むことができます。

于 2008-09-22T18:12:43.703 に答える
2

絶対に最小のフットプリントが必要な場合は、アセンブリ コードを使用します。私はしばらくこれを行っていませんでしたが、MMX (または SSE2/3 の可能性が高い) には、非常に少ない命令で正確にそれを実行できる命令があるに違いありません。

于 2008-09-22T18:15:20.500 に答える
2

一致が一般的なケースである場合は、値を 16 ではなく 32 ビット整数としてロードしてみてください。これにより、2 つを一度に比較できます (そして、2 つの一致としてカウントします)。

2 つの 32 ビット値が同じでない場合は、別々にテストする必要があります (上位と下位の 16 ビット値の AND を計算します)。

コードはより複雑になりますが、より高速になるはずです。

64 ビット システムをターゲットにしている場合は、64 ビット int で同じトリックを実行できます。本当に制限を押し上げたい場合は、アセンブラーにドロップして、128 ビットで動作するさまざまなベクトル ベースの命令を使用することを検討してください。すぐに。

于 2008-09-22T18:18:17.467 に答える
1

配列の値の間に何らかの関係がありますか？一部のバイトは他のバイトよりも同じである可能性が高いですか？値に固有の順序があるのでしょうか？次に、最も可能性の高いケースに合わせて最適化できます。

于 2008-09-22T19:09:17.983 に答える
1

データが実際に何を表しているかを説明すると、メモリ内のデータを表すためのまったく異なる方法が存在する可能性があり、このタイプのブルート フォースは不要になります。データが実際に何を表しているか詳しく説明してください??

于 2008-09-23T01:00:05.597 に答える
1

これはプラットフォームに依存しない必要がありますか? それとも、このコードは常に同じタイプの CPU で実行されますか? 最新の x86 CPU に制限する場合は、MMX命令を使用できる場合があります。これにより、1 クロック ティックで 8 バイトの配列を操作できるはずです。私の知る限り、gcc を使用すると C コードにアセンブリを埋め込むことができ、Intel のコンパイラ (icc) は特定のアセンブリ命令を直接呼び出すことができるラッパーである組み込み関数をサポートしています。SSE などの他の SIMD 命令セットも、これに役立つ場合があります。

于 2008-09-22T18:32:05.513 に答える
1

魔法のコンパイラ オプションは、時間を大幅に変化させます。特に、SSE ベクトル化を生成するようにすると、大幅な速度向上が得られる可能性があります。

于 2008-09-22T18:15:15.663 に答える
0

追加の可能な最適化の1つ：ほとんどの場合、配列が同一であると予想される場合は、最初のステップとしてmemcmp（）を実行し、テストがtrueを返した場合の答えとして「16」を設定する方がわずかに速い場合があります。もちろん、配列が非常に頻繁に同一であると期待していない場合、それは物事を遅くするだけです。

于 2008-09-22T21:34:23.297 に答える
0

配列の保存方法を変更する方法はありますか？おそらく32ビットコンパイラを使用していることを考えると、一度に1バイトを比較するのは非常に遅くなります。代わりに、16バイトを4つの整数（32ビット）または2つのロング（64ビット）で格納した場合、それぞれ4つまたは2つの比較を実行するだけで済みます。

自問する質問は、データを4整数または2長配列として格納するコストはいくらかということです。データなどにアクセスする必要がある頻度。

于 2008-09-22T18:25:12.050 に答える
0

1つのステートメントとして高速ですか？

matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;
于 2008-09-22T18:12:05.563 に答える
0

その 16 回の書き込みが単純なループよりも速い場合は、コンパイラがうまくいかないか、最適化が有効になっていません。

簡単な答え: 並列ハードウェアでベクトル演算を実行しない限り、これより速い方法はありません。

于 2008-09-22T18:14:58.987 に答える
0

古き良き x86 REPNE CMPS 命令が常にあります。

于 2008-09-22T18:26:40.877 に答える
0

配列の代わりにポインターを使用してみてください。

p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.

もちろん、これを他のアプローチと比較して、どちらが最速かを確認する必要があります。

そして、このルーチンが処理のボトルネックになっていると確信していますか? これを最適化することで、実際にアプリケーション全体のパフォーマンスを高速化していますか? 繰り返しますが、測定だけが教えてくれます。

于 2008-09-22T18:19:19.617 に答える