5

2 バイトを 1 つにパックする最速の方法は何でしょうか? 大きなバイト配列があります。各バイトは、15 (4 ビット数) 以下の数値を表します。そのため、最初のバイトを上位ニブルに配置し、後のバイトを下位ニブルに配置して、2 バイトを 1 つにパックすることができます。

私の現在のアプローチは、元のサイズの半分の 2 番目の配列を作成し、それをシフトして元の配列を反復処理することです。ニブルを取得します。これは機能しますが、配列のサイズによっては時間がかかります。配列は、数千から数百万のエントリです。壊滅的ではありませんが、最適化は役に立ちます

4

2 に答える 2

4

配列が大きい場合は、明らかに時間がかかります。すべてを調べる必要があります。

最初に行うことは、2 バイトから 1 バイトへのルックアップ テーブルを作成することです。そのため、次の 2 バイトを取得してオフセットを検索し、結果のバイトを取得します。

このルックアップ テーブルには 2^12 エントリ (最上位バイトから 4 バイトだけが必要) があり、CPU の L1 キャッシュにうまく収まる必要があります。shift-and-or よりも速いかもしれません。

一方、一度に 8 バイトをロードする場合 (現在はすべて 64 ビット CPU で)、それを 4 バイトに変換して格納できます。これを並列化できます (配列を 4 つの部分に分割し、各コアが 1 つの部分を処理するようにします)。

64 ビット レジスタからバイト 0、2、4、および 6 を取得し、それらを 32 ビット レジスタに格納する命令があれば、完了です。

更新:質問で、数百万バイトあると述べました。その場合は、気にしないでください。高度に最適化されたアセンブリと C での単純な実装との違いは、問題に値するものではありません。一度に 2 バイトずつデータをロードし、2 ニブルを 1 バイトにシフトして、ターゲット配列に格納するだけです。1MB のデータの処理は瞬時に行われるべきです。

于 2014-05-02T19:11:09.637 に答える
0

最初に C または C++ でアプローチし、測定してから、パフォーマンスが許容できない場合にのみアセンブリに頼ります。C:

void packarray(unsigned char *buff, int len)
{ 
    unsigned char *packed;
    unsigned char byte;
    assert(len >= 2);  /* len must be at least 2 bytes */
    assert((len & 1) != 1);   /* len must be an even number */
    for (packed = buff; len>0; len-=2) {
        byte= *buff++;
        *packed++ = (byte << 4) | *buff++;
    }
}

警告:テストされていないコード

于 2014-05-02T19:39:11.707 に答える