データを16進数出力に素早く変換する

任意のバイト列を16進数文字列に変換するには、各バイトの下位4ビットと上位4ビットを01...9A...Fの文字に対応付ける方法があります。3バイトを4文字にマッピングするbase64のような、より効率的な手法もあります。しかし、16進数出力は理解しやすく、しばしば十分に簡潔です。

短いルックアップテーブルを使ったシンプルな変換関数は次のようになります。

static const char hex[] = "0123456789abcdef";
for (size_t i = 0, k = 0; k < dlen; i += 1, k += 2) {
    uint8_t val = src[i];
    dst[k + 0] = hex[val >> 4];
    dst[k + 1] = hex[val & 15];
}

This code snippet implements a straightforward byte-to-hexadecimal string conversion loop in C++. It iterates over an input byte array (src), processing one byte at a time using index i, while simultaneously building the output string in dst with index k that advances twice as fast (by 2) since each input byte produces two hexadecimal characters. For each byte, it extracts the value as an unsigned 8-bit integer (val), then isolates the high 4 bits (via right shift by 4) and low 4 bits (via bitwise AND with 15) to index into a static lookup table (hex) containing the characters ‘0’ through ‘9’ and ‘a’ through ‘f’. The loop continues until k reaches the expected output length (dlen), which should be twice the input length, ensuring all bytes are converted without bounds errors.

このルックアップテーブル方式は、人気のNode.js JavaScriptランタイムでも採用されています。Skovoroda氏は最近、このルックアップテーブル方式を算術演算バージョンに置き換えることを提案しました。

char nibble(uint8_t x) { return x + '0' + ((x > 9) * 39); }
for (size_t i = 0, k = 0; k < dlen; i += 1, k += 2) {
    uint8_t val = src[i];
    dst[k + 0] = nibble(val >> 4);
    dst[k + 1] = nibble(val & 15];
}

意外かもしれませんが、この手法ははるかに高速で、使用する命令数も大幅に少なくなります。一見すると、テーブル参照は安価であり、新しいnibble関数はより多くの処理を行っているように見えます。

Skovoroda氏が利用しているトリックは、コンパイラが賢いという点です。コンパイラはこうした数値演算関数を「自動ベクトル化」します（運が良ければ）。つまり、通常の命令でバイト値を処理する代わりに、16バイト以上を一度に処理するSIMD命令を使用します。

もちろん、コンパイラに頼る代わりに、SIMD組み込み関数を通じて手動でSIMD命令を呼び出すこともできます。ARMプロセッサ（例：Apple Silicon）をお使いだと仮定しましょう。すると、32バイトのブロックを次のように処理できます。

size_t maxv = (slen - (slen%32));
for (; i < maxv; i += 32) {
    uint8x16_t val1 = vld1q_u8((uint8_t*)src + i);
    uint8x16_t val2 = vld1q_u8((uint8_t*)src + i + 16);
    uint8x16_t high1 = vshrq_n_u8(val1, 4);
    uint8x16_t low1 = vandq_u8(val1, vdupq_n_u8(15));
    uint8x16_t high2 = vshrq_n_u8(val2, 4);
    uint8x16_t low2 = vandq_u8(val2, vdupq_n_u8(15));
    uint8x16_t high_chars1 = vqtbl1q_u8(table, high1);
    uint8x16_t low_chars1 = vqtbl1q_u8(table, low1);
    uint8x16_t high_chars2 = vqtbl1q_u8(table, high2);
    uint8x16_t low_chars2 = vqtbl1q_u8(table, low2);
    uint8x16x2_t zipped1 = {high_chars1, low_chars1};
    uint8x16x2_t zipped2 = {high_chars2, low_chars2};
    vst2q_u8((uint8_t*)dst + i*2, zipped1);
    vst2q_u8((uint8_t*)dst + i*2 + 32, zipped2);
}

このSIMDコードはARM NEON組み込み関数を活用し、32バイトの入力データを同時に処理することで16進数エンコーディングを高速化します。まずvld1q_u8を使ってソース配列から2つの16バイトベクトル（val1とval2）を読み込みます。各ベクトルに対して、vshrq_n_u8で上位ニブルを抽出（4ビット右シフト）し、vandq_u8とvdupq_n_u8で下位ニブルを抽出（15とのビットAND）します。ニブルはvqtbl1q_u8を使って事前に読み込んだ16進テーブルへのインデックスとして使用され、対応するASCII文字を取得します。高位と低位の文字ベクトルはvzipq_u8でインターリーブされ、入力ペアごとに2つの出力ベクトルを生成します。最後にvst1q_u8で結果を宛先配列に格納し、効率的なメモリ操作を実現しています。

同様の処理はx64などの他のシステムでも可能です。最近のIntelおよびAMDプロセッサ向けのAVX-512を使用した同じコードは、おそらく驚異的に効率的でしょう。

10,000バイトのランダムデータセットでこれらの実装をベンチマークした結果、大きなパフォーマンス差が明らかになりました。基本的なルックアップテーブル版は約3 GB/sを達成し、コンパイラの自動ベクトル化の恩恵を受けた算術演算版は23 GB/sに達します。手動SIMD NEON版はさらに性能を向上させ、テストでは42 GB/sを記録しました。

教訓の1つは、パフォーマンスを評価しようとする際、直感はあまり良い指針にならないということです。

ソースコードはこちらで入手できます。

Published by

Post navigation