char[] から 16 進文字列への変換の練習

https://stackoverflow.com/questions/69115

09-06-2019
|

質問

以下は、現在の char* から 16 進文字列への関数です。ビット操作の練習として書きました。AMD Athlon MP 2800+ では、1,000 万バイトの配列を 16 進化するのに約 7 ミリ秒かかります。私に欠けているトリックや他の方法はありますか？

どうすればこれを高速化できますか?

g++ で -O3 を指定してコンパイル

static const char _hex2asciiU_value[256][2] =
     { {'0','0'}, {'0','1'}, /* snip..., */ {'F','E'},{'F','F'} };

std::string char_to_hex( const unsigned char* _pArray, unsigned int _len )
{
    std::string str;
    str.resize(_len*2);
    char* pszHex = &str[0];
    const unsigned char* pEnd = _pArray + _len;

    clock_t stick, etick;
    stick = clock();
    for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {
        pszHex[0] = _hex2asciiU_value[*pChar][0];
        pszHex[1] = _hex2asciiU_value[*pChar][1];
    }
    etick = clock();

    std::cout << "ticks to hexify " << etick - stick << std::endl;

    return str;
}

アップデート

タイミングコードを追加しました

ブライアン R.ボンディ:std::string をヒープ割り当てバッファに置き換え、ofs*16 を ofs << 4 に変更します。ただし、ヒープ割り当てバッファのせいで速度が低下しているようです。- 結果 ~11ms

アンティ・シカリ: 内側のループを次のように置き換えます

 int upper = *pChar >> 4;
 int lower = *pChar & 0x0f;
 pszHex[0] = pHex[upper];
 pszHex[1] = pHex[lower];

結果 ~8ms

ロバート:交換する _hex2asciiU_value 完全な 256 エントリのテーブルを使用すると、メモリ領域が犠牲になりますが、結果は最大 7 ミリ秒になります。

ホイホイ:間違った結果が生成されていたことに気づきました

解決

より多くのメモリを犠牲にして、16 進コードの完全な 256 エントリのテーブルを作成できます。

static const char _hex2asciiU_value[256][2] =
    { {'0','0'}, {'0','1'}, /* ..., */ {'F','E'},{'F','F'} };

次に、テーブルに直接インデックスを作成します。多少の操作は必要ありません。

const char *pHexVal = pHex[*pChar];
pszHex[0] = pHexVal[0];
pszHex[1] = pHexVal[1];

他のヒント

このアセンブリ関数 (ここでの前回の投稿に基づいていますが、実際に動作させるには概念を少し変更する必要がありました) は、Core 2 Conroe 3Ghz の 1 つのコアで 1 秒あたり 33 億の入力文字 (66 億の出力文字) を処理します。おそらくペンリンの方が速いでしょう。

%include "x86inc.asm"

SECTION_RODATA
pb_f0: times 16 db 0xf0
pb_0f: times 16 db 0x0f
pb_hex: db 48,49,50,51,52,53,54,55,56,57,65,66,67,68,69,70

SECTION .text

; int convert_string_to_hex( char *input, char *output, int len )

cglobal _convert_string_to_hex,3,3
    movdqa xmm6, [pb_f0 GLOBAL]
    movdqa xmm7, [pb_0f GLOBAL]
.loop:
    movdqa xmm5, [pb_hex GLOBAL]
    movdqa xmm4, [pb_hex GLOBAL]
    movq   xmm0, [r0+r2-8]
    movq   xmm2, [r0+r2-16]
    movq   xmm1, xmm0
    movq   xmm3, xmm2
    pand   xmm0, xmm6 ;high bits
    pand   xmm2, xmm6
    psrlq  xmm0, 4
    psrlq  xmm2, 4
    pand   xmm1, xmm7 ;low bits
    pand   xmm3, xmm7
    punpcklbw xmm0, xmm1
    punpcklbw xmm2, xmm3
    pshufb xmm4, xmm0
    pshufb xmm5, xmm2
    movdqa [r1+r2*2-16], xmm4
    movdqa [r1+r2*2-32], xmm5
    sub r2, 16
    jg .loop
    REP_RET

x264 アセンブリ構文を使用しているため、移植性が高くなります (32 ビット対 64 ビットなど)。これを好みの構文に変換するのは簡単です。r0、r1、r2 は、レジスタ内の関数への 3 つの引数です。それは疑似コードに少し似ています。または、x264 ツリーから common/x86/x86inc.asm を取得し、それをインクルードしてネイティブに実行することもできます。

追伸スタックオーバーフロー、こんなつまらないことに時間を浪費するのは間違っているでしょうか?それともこれはすごいですか？

より高速な C 実装

これは、C++ 実装よりもほぼ 3 倍高速に実行されます。かなり似ているので理由はわかりません。私が投稿した最後の C++ 実装では、2 億文字の配列を実行するのに 6.8 秒かかりました。導入にはわずか 2.2 秒かかりました。

#include <stdio.h>
#include <stdlib.h>

char* char_to_hex(const unsigned char* p_array, 
                  unsigned int p_array_len,
                  char** hex2ascii)
{
    unsigned char* str = malloc(p_array_len*2+1);
    const unsigned char* p_end = p_array + p_array_len;
    size_t pos=0;
    const unsigned char* p;
    for( p = p_array; p != p_end; p++, pos+=2 ) {
       str[pos] = hex2ascii[*p][0];
       str[pos+1] = hex2ascii[*p][1];
    }
    return (char*)str;
}

int main()
{
  size_t hex2ascii_len = 256;
  char** hex2ascii;
  int i;
  hex2ascii = malloc(hex2ascii_len*sizeof(char*));
  for(i=0; i<hex2ascii_len; i++) {
    hex2ascii[i] = malloc(3*sizeof(char));    
    snprintf(hex2ascii[i], 3,"%02X", i);
  }
  size_t len = 8;
  const unsigned char a[] = "DO NOT WANT";
  printf("%s\n", char_to_hex((const unsigned char*)a, len, (char**)hex2ascii));
}

enter image description here

一度に 32 ビット (4 文字) を操作し、必要に応じて末尾を処理します。URL エンコードを使用してこの演習を行ったとき、各文字の完全なテーブル検索はロジック構造よりもわずかに高速でした。そのため、キャッシュの問題を考慮するために、これをコンテキスト内でテストすることもできます。

それは私にとってはうまくいきます unsigned char:

unsigned char  c1 =  byteVal >> 4;
unsigned char  c2 =  byteVal & 0x0f;

c1 +=  c1 <= 9 ? '0' : ('a' - 10);
c2 +=  c2 <= 9 ? '0' : ('a' - 10);

std::string sHex("  ");
sHex[0] = c1 ;
sHex[1] = c2 ;


//sHex - contain what we need. For example "0f"

まず、乗算する代わりに、 16 をする bitshift << 4

また、使用しないでください std::string, 代わりに、ヒープ上にバッファを作成してから、 delete それ。文字列から必要なオブジェクトの破棄よりも効率的です。

大きな違いはないだろう...*pChar-(ofs*16) は [*pCHAR & 0x0F] で実行できます

これは私のバージョンです。OP のバージョンとは異なり、次のことを前提としていません。 std::basic_string 連続領域にデータがあります:

#include <string>

using std::string;

static char const* digits("0123456789ABCDEF");

string
tohex(string const& data)
{
    string result(data.size() * 2, 0);
    string::iterator ptr(result.begin());
    for (string::const_iterator cur(data.begin()), end(data.end()); cur != end; ++cur) {
        unsigned char c(*cur);
        *ptr++ = digits[c >> 4];
        *ptr++ = digits[c & 15];
    }
    return result;
}

これは Windows + IA32 だと思います。
2 つの 16 進文字の代わりに short int を使用してください。

short int hex_table[256] = {'0'*256+'0', '1'*256+'0', '2'*256+'0', ..., 'E'*256+'F', 'F'*256+'F'};
unsigned short int* pszHex = &str[0];

stick = clock();

for (const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) 
    *pszHex++ = hex_table[*pChar];

etick = clock();

変化

    ofs = *pChar >> 4;
    pszHex[0] = pHex[ofs];
    pszHex[1] = pHex[*pChar-(ofs*16)];

に

    int upper = *pChar >> 4;
    int lower = *pChar & 0x0f;
    pszHex[0] = pHex[upper];
    pszHex[1] = pHex[lower];

約 5% の速度向上が得られます。

で提案されているように、結果を一度に 2 バイトずつ書き込むロバート約 18% の速度向上が得られます。コードは次のように変更されます。

_result.resize(_len*2);
short* pszHex = (short*) &_result[0];
const unsigned char* pEnd = _pArray + _len;

const char* pHex = _hex2asciiU_value;
for(const unsigned char* pChar = _pArray;
    pChar != pEnd;
    pChar++, ++pszHex )
{
    *pszHex = bytes_to_chars[*pChar];
}

必要な初期化:

short short_table[256];

for (int i = 0; i < 256; ++i)
{
    char* pc = (char*) &short_table[i];
    pc[0] = _hex2asciiU_value[i >> 4];
    pc[1] = _hex2asciiU_value[i & 0x0f];
}

で指摘されているように、一度に 2 バイトまたは一度に 4 バイト実行すると、おそらくさらに高速化されるでしょう。アラン・ウィンド, しかし、奇妙な文字を処理しなければならない場合、さらに難しくなります。

冒険したいと感じているなら、適応してみるのもいいかもしれませんダフの装置これをする。

結果は Intel Core Duo 2 プロセッサー上でのものであり、 gcc -O3.

常に測定する 実際にはより速い結果が得られるということです。最適化のふりをした悲観は、まったく価値がありません。

常にテストする 正しい結果が得られることを保証します。最適化を装ったバグはまったく危険です。

そして 常に心に留めておいてください 速度と可読性のトレードオフ — 可読性のないコードを維持するには、誰にとっても寿命は短すぎます。

(必須の参照先のコーディングにあなたがどこに住んでいるか知っている暴力的なサイコパス.)

コンパイラの最適化が最高の作業レベルに設定されていることを確認してください。

gcc の「-O1」から「-03」のようなフラグです。

ポインタではなく配列へのインデックスを使用すると、ティックを高速化できることがわかりました。それはすべて、コンパイラーが最適化をどのように選択するかによって異なります。重要なのは、プロセッサには [i*2+1] のような複雑な処理を 1 つの命令で実行する命令があるということです。

ここで速度にかなりこだわる場合は、次のことができます。

各文字は 1 バイトで、2 つの 16 進値を表します。したがって、各文字は実際には 2 つの 4 ビット値です。

したがって、次のことができます。

乗算または同様の命令を使用して、4 ビット値を 8 ビット値にアンパックします。
SSSE3 命令である pshufb を使用します (ただし、Core2 のみ)。16 個の 8 ビット入力値の配列を受け取り、2 番目のベクトル内の 16 個の 8 ビットインデックスに基づいてそれらをシャッフルします。使用できる文字は 16 文字だけなので、これは完全に当てはまります。入力配列は 0 ～ F 文字のベクトルで、インデックス配列は 4 ビット値のアンパックされた配列です。

したがって、 単一の命令, を実行したことになります。 16 テーブルルックアップ 通常 1 つだけ実行するのにかかるクロックよりも少ないクロックで実行されます (Penryn では pshufb は 1 クロックのレイテンシです)。

したがって、計算ステップでは次のようになります。

A B C D E F G H I J K L M N O P (入力値の 64 ビットベクトル、「ベクトル A」) -> 0A 0B 0C 0D 0E 0F 0G 0H 0I 0J 0K 0L 0M 0N 0O 0P (インデックスの 128 ビットベクトル、「ベクトル B」)。最も簡単な方法は、おそらく 2 つの 64 ビット乗算です。
pshub [0123456789ABCDEF]、ベクトル B

一度にもっと多くのバイトを実行した方が良いかどうかはわかりません...おそらく、大量のキャッシュミスが発生し、速度が大幅に低下するだけです。

ただし、ループを展開し、ループを通過するたびに、より大きなステップを実行し、より多くの文字を実行して、ループのオーバーヘッドの一部を取り除くことを試みることもできます。

Athlon 64 4200+ では一貫して ~4ms を取得しています (元のコードでは ~7ms)

for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++) {
    const char* pchars = _hex2asciiU_value[*pChar];
    *pszHex++ = *pchars++;
    *pszHex++ = *pchars;
}

これを書いているときに示されている関数は、_hex2asciiU_value が完全に指定されている場合でも、間違った出力を生成します。次のコードは機能し、私の 2.33GHz Macbook Pro では、200,000,000 万文字を約 1.9 秒で実行します。

#include <iostream>

using namespace std;

static const size_t _h2alen = 256;
static char _hex2asciiU_value[_h2alen][3];

string char_to_hex( const unsigned char* _pArray, unsigned int _len )
{
    string str;
    str.resize(_len*2);
    char* pszHex = &str[0];
    const unsigned char* pEnd = _pArray + _len;
    const char* pHex = _hex2asciiU_value[0];
    for( const unsigned char* pChar = _pArray; pChar != pEnd; pChar++, pszHex += 2 ) {
       pszHex[0] = _hex2asciiU_value[*pChar][0];
       pszHex[1] = _hex2asciiU_value[*pChar][1];
    }
    return str;
}


int main() {
  for(int i=0; i<_h2alen; i++) {
    snprintf(_hex2asciiU_value[i], 3,"%02X", i);
  }
  size_t len = 200000000;
  char* a = new char[len];
  string t1;
  string t2;
  clock_t start;
  srand(time(NULL));
  for(int i=0; i<len; i++) a[i] = rand()&0xFF;
  start = clock();
  t1=char_to_hex((const unsigned char*)a, len);
  cout << "char_to_hex conversion took ---> " << (clock() - start)/(double)CLOCKS_PER_SEC << " seconds\n";
}

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow