Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

SSE4.2 の文字列処理

SSSE3 / SSE4 命令一覧」では,SSE4.2の PCMPESTRI / PCMPESTRM / PCMPISTRI / PCMPISTRMの4命令については動作説明部分を「文字列比較」として説明書きを端折っていました(あのスペースでは書ききれませんので)。これらの命令の動作についてメモしておきます。

これら4命令は文字列の比較を行うものですが,文字列長の指定の仕方(2通り)と結果の受け取り方(2通り)との組合せで4命令に分かれています。

  比較結果をビットマスクで受け取る 比較結果でビットが1となった最上位/最下位ビットの位置を受け取る
文字列長をEAX,EDXで指定する
(Explicit Length)
PCMPESTRM
PCMPESTRI
文字列長を\0で指定する
(Implicit Length)
PCMPISTRM
PCMPISTRI

C/C++ Intrinsicを見ると,PCMPESTRxは文字列長を指定するint型の引数を伴います。PCMPISTRxは伴いません。

比較モード

比較方法には,いくつかの種類があり8bitの即値でモードを指定します。C/C++ Intrinsicでは,const intの引数が付きます。

PCMPxSTRy命令の動作は,次のように説明されます。

128bit長データを比較し結果をIntRes1へ入れます。IntRes1に極性変換を施しIntRes2を生成します。IntRes2から出力選択を経てビットマスク値,またはインデックス値(最上位/最下位ビット位置)を生成します。
それぞれの動作について,動作モードが次のように定義されています。

▼ データ形式
モード値のビット0,1でデータ形式を指定します。

00B unsigned byte
01B unsigned word
10B signed byte
11B signed word

▼ 比較
モード値のビット2,3で比較方法を指定します。

00B Equal any (find characters from a set)
XMM2の要素jが,XMM1の要素iのいずれかに一致するとtrue
01B Ranges (find characters from ranges)
XMM2の要素jが,XMM1で指定される範囲ペアに収まるとtrue
10B Equal each (string compare)
XMM2の要素jが,XMM1の要素jと一致するとtrue
11B Equal ordered (substring compare)
XMM2の要素j以降が,XMM1の要素0以降の有効長文字列と一致するとtrue

▼ 極性
モード値のビット4,5で極性を指定します。

00B No Change
IntRes2 = IntRes1
01B Invert
IntRes2 = ~IntRes1
10B No Change
IntRes2 = IntRes1
11B Mask Negative
XMM2の要素iが無効 → IntRes2[i] = IntRes1[i]
XMM2の要素iが有効 → IntRes2[i] = ~IntRes1[i]

▼ 出力選択
モード値のビット6で出力形式を指定します。
[PCMPxSTRI] 

0B IntRes2で1となるビットのLSBからの位置をECXに入れる
1B IntRes2で1となるビットのMSBからの位置をECXに入れる

[PCMPxSTRM] 

0B IntRes2をXMM1に入れる。上位ビットは0で埋める。
1B IntRes2の各ビットを,byte/wordのマスク値(0xFF/0xFFFF)に拡張してXMM1に入れる。

※ 要素無効時の比較結果
XMM1,XMM2の要素が無効のときの比較結果は次の通りです。

XMM1の要素

XMM2の要素

Equal any

Ranges

Equal each

Equal ordered

Invalid Invalid false false true true
Invalid Valid false false false true
Valid Invalid false false false false

EFLAGS

PCMPxSTRy命令を実行により,下記の通りにフラグが設定されます。

CF IntRes2==0 で Reset,それ以外はSet
ZF XMM2に無効要素があれば Set,それ以外はReset
SF XMM1が無効要素があれば Set,それ以外はReset
OF IntRes2[0]
AF Reset

C/C++ Intrinsicでは,これらフラグを個別に取得します。
int _mm_cmpestra (__m128i a, int la, __m128i b, int lb, const int mode);
int _mm_cmpestrc (__m128i a, int la, __m128i b, int lb, const int mode);
int _mm_cmpestro (__m128i a, int la, __m128i b, int lb, const int mode);
int _mm_cmpestrs (__m128i a, int la, __m128i b, int lb, const int mode);
int _mm_cmpestrz (__m128i a, int la, __m128i b, int lb, const int mode);

int _mm_cmpistra (__m128i a, __m128i b, const int mode);
int _mm_cmpistrc (__m128i a, __m128i b, const int mode);
int _mm_cmpistro (__m128i a, __m128i b, const int mode);
int _mm_cmpistrs (__m128i a, __m128i b, const int mode);
int _mm_cmpistrz (__m128i a, __m128i b, const int mode);

コード例

PCMPxSTRyの詳細な解説,コード例は「インテル 64アーキテクチャーおよび IA-32アーキテクチャー最適化リファレンス・マニュアル」にあります。

ここでは,strlen()とWordCnt()について,C/C++ Intrinsicで記述したコードを示します。(アセンブラでチューニングされたコードは上述のマニュアルに記載されています)

▼ strlen
int strlen_sse42( const char* cszStr )
{
  __m128i  r = _mm_load_si128((const __m128i*)range);
  __m128i* p = (__m128i*)cszStr;

  while( !_mm_cmpistrz( r, *p, 0x14 ) ){
    p++;
  }
  int residual = _mm_cmpistri( r, *p, 0x14 );

  return ((const char*)p-cszStr) + residual;
}
PCMPISTRIを実行し,ZFがSetされる(\0が現れる)までループします。ループを抜けた後は16文字(128bit)に満たない分の文字数をIndex値から取得します。

C/C++ Intrinsicでは,フラグと結果を別々に取得しなければならないため,ループ後に再度PCMPISTRIを実行するコードとなってしまいます。

▼ WordCnt

__declspec(align(16)) static const char alpha_num[16] =
 {0x27,0x27, 0x30,0x39, 0x41,0x5a, 0x61,0x7a, 0,};

int WordCnt( const char* cszStr )
{
  __m128i  r = _mm_load_si128((const __m128i*)alpha_num);
  __m128i* p = (__m128i*)cszStr;
  __m128i rslt = _mm_cmpistrm( r, *p, 0x4 );
  __m128i work = _mm_slli_epi16( rslt, 1 );
  __m128i back = _mm_srli_epi32( rslt, 15 );// MSBは次の処理で使う
  work = _mm_xor_si128( work, rslt );
  int cnt = _mm_popcnt_u32(_mm_cvtsi128_si32(work));

  do{
    p++;
    rslt = _mm_cmpistrm( r, *p, 0x4 );
    work = _mm_slli_epi16( rslt, 1 );
    work = _mm_or_si128( back, work );
    back = _mm_srli_epi32( rslt, 15 );
    work = _mm_xor_si128( work, rslt );
    cnt += _mm_popcnt_u32(_mm_cvtsi128_si32(work));
  }while( !_mm_cmpistrz( r, *p, 0x4 ) );

  return cnt/2;
}
Rangesを使って,各文字の文字コードが英数字の範囲内であるかを比較します。
隣合う文字が「英数字→それ以外」「それ以外→英数字」と変化する部分を数え上げます。このため,PCMPISTRMの結果を1ビットシフトしてxorをとることで変化した部位のビットをsetし,popcntで数え上げます。
速度比較

上述のstrlen(),WordCnt()について,速度比較を行ってみました。

比較対象は,strlen()は VC++2005の標準ライブラリ,WordCnt()は「インテル 64アーキテクチャーおよび IA-32アーキテクチャー最適化リファレンス・マニュアル」に記載される次のCコードを使いました。

#include 
static char alphnrange[16]=
 {0x27, 0x27, 0x30, 0x39, 0x41, 0x5a, 0x61, 0x7a, 0x0};
static char alp_map8[32] =
 {0x0,0x0,0x0,0x0,0x80,0x0,0xff,0x3,0xfe,0xff,0xff,0x7,0xfe,0xff,0xff,0x7};
int wordcnt_c(const char* s1)
{
  int i, j, cnt = 0;
  char cc, cc2;
  char flg[3]; // capture the a wavelet to locate a falling edge
  cc2 = cc = s1[0];
  // use the compacted bit pattern
  //   to consolidate multiple comparisons into one look up
  if( alp_map8[cc>>3] & ( 1<< ( cc & 7) ) )
  { flg[1] = 1; } // non-white-space char that is part of a word,
  // we're including apostrophe in this example since counting the
  // following 's' as a separate word would be kind of silly
  else
  { flg[1] = 0; }
  // 0: whitespace, punctuations not be considered as part of a word

  i = 1;// now we’re ready to scan through the rest of the block
  // we'll try to pick out each falling edge of the bit pattern
  // to increment word count.
  // this works with consecutive white spaces,
  // dealing with punctuation marks, and
  // treating hyphens as connecting two separate words.
  while (cc2 )
  { cc2 = s1[i];
    if( alp_map8[cc2>>3] & ( 1<< ( cc2 & 7) ) )
    { flg[2] = 1;} // non-white-space
    else
    { flg[2] = 0;} // white-space-like
    if( !flg[2] && flg[1] )
    { cnt ++; } // found the falling edge
    flg[1] = flg[2];
    i++;
  }
  return cnt;
}

 

計測環境: Xeon W3580 3.33GHz
結果:

 
C
SSE4.2
strlen()  142678文字
178.481 usec
17.5102 usec
WordCnt()  25923語
1362.72 usec
51.3017 usec

strlen()では約10倍,WordCnt()では約26倍高速化しています。

参考文献

     ※ 頻繁に改定されるためにリンク切れ時は検索してください

スポンサーサイト

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。