mitsunari@cybozu labs

Visual StudioのC++開発環境ではsizeof(wchar_t) == 2なのでstd::wstringではサロゲートペアを考慮する必要があります．
それを避けるためにUTF32文字列で文字列処理を行いたい場合があると思います．その場合，

typedef unsigned int uint32_t;
typedef std::basic_string<uint32_t> u32stirng;

などの定義をして文字列を使うことになるでしょう．これらの型はC++0xでは標準になる予定です．
実際には利便性のためにchar*との自然な変換メソッドなどを追加すると思いますが，ここでは省略します．

boost::regexでもstd::stringと同様にテンプレートパラメータに文字の型を与えることができ，

typedef boost::basic_regex<uint32_t> u32regex;
typedef boost::match_results<u32string::const_iterator> u32match;

などと定義するとu32stringに対しても正規表現が使えるようになります．

が，\w, \s, \dや[:digit:]などを使うとややこしい問題が発生します．
これらを使うと現在の実装(boost 1.38)では内部的にuint32_tからcharにキャストしてから判別するようで，全然関係のない文字がマッチしてしまうことがあります(これはboostが悪いというわけではありません)．

たとえば

/* これはUTF-8 */
const uint32_t str_[] = { 0x3053, 0x308c, 0x306f, 'U', 'T', 'F', '-', '8', 0 };
にたいして"\w+"をマッチさせると，先頭の一文字がマッチしてしまいます．これは0x3053はcharにキャストされ，0x53になり'S'と看做されてしまうからです．

ここではこれを回避する最低限の修正について説明します．

boost::regexでは上記の文字の型の判定にstd::ctypeを利用します．
したがって，その特殊化を用意すればひとまず問題を回避できます．
std::ctypeが持つべきメソッドはctype - C++ Referenceなどを参考にして用意します．
ざっと調べたところではis, tolower, widenの三つを用意すればよいようでした(本当は全て用意すべきですが)．

それぞれの特殊化を用意しましょう．

namespace std {
template<>
bool ctype<uint32_t>::is(std::ctype_base::mask m, uint32_t c) const
{
    if (c & ~0xFFU) return false;
    return use_facet<ctype<char> >(std::locale()).is(m, static_cast<char>(c));
}
template<>
uint32_t ctype<uint32_t>::tolower(uint32_t c) const
{
    if ('A' <= c && c <= 'Z') return c - 'A' + 'a';
    return c;
}
template<>
uint32_t ctype<uint32_t>::widen(char c) const
{
    return c;
}
}

本来はstd::ctype_base::maskにはspace, upperなど文字の特性を判別するフラグが入ってくるのでUnicodeの規格に応じて正しく分岐したほうがよいかもしれません．
しかし純粋にasciiだけをチェックしたい場合もあるでしょうから，ここでは1byte文字でなければfalseにして，1byteのときは既存のcharに対するctypeを呼ぶことにしました．
スペースをasciiの0x20だけでなく全角スペース(0x3000)や，他のUnicodeのスペースを判別したい場合はisを適宜修正してください．

この特殊化を追加することで，上記のマッチングは正しく"UTF"を返すようになります．
サンプルコード

(注意)Linux上のgccではこれらの修正だけでは正しく動作しませんが，今回は触れません．

なお，isの中のuse_facetをする部分

return use_facet<ctype<char> >(std::locale()).is(m, static_cast<char>(c));

は極めて重たい処理ですので，static変数にキャッシュしておきそれを使うのがよいです．

static const std::ctype<char>& cache = use_facet<ctype<char> >(std::locale());
return cache.is(m, static_cast<char>(c));

あるいは，std::ctypeがもつtable()メソッドを引き出して，

static struct Custom : public std::ctype<char> {
    const mask * table() const { return std::ctype<char>::table(); }
} custom;
static const mask* maskTbl = custom.table();
return (maskTbl[(unsigned char)c] & m) != 0;

などとするのがよいでしょう．

1年ほど前に作ったsha1.jsをgoogle Chrome上でベンチマークをとってみました(Win Xp@Core2Dup 2.6GHz)．
結果はpajhomeさんの実装では20倍以上もの凄まじい速度向上がありましたが，もともと最適化していた私ものものはあまり速くなっていません．
これはループアンロールなどの(つまらない)努力は不要になるということで，すばらしいことです．
ただ数値計算に限っては，もともと十分に最適化されていればIE6と大きく変わるものでもないとも言えます．
ちなみにC++でのSHA-1では0.0056msecでした．まだ100倍ほどの開きはあるようです．

ところでchromeのJIT部分で使ってるassembler-ia32.ccなんかみるとxbyak使ってほしいなとか思ったり．x86-64への対応が簡単になると思いますがいかがでしょう．

strlen()とmemchr()のSIMD版を作ってみました．

今回は最速よりもお手軽さを重視したのでアセンブリ言語ではなくintrinsic関数を使っています．そのためVisual Studio 2008, gcc 4.xの両方でコンパイルでき32-bit, 64-bit OS上で動作します．
WindowsとLinuxでのみ確認していますが恐らくIntel Mac OS X上でも動作するでしょう(sample source)．

ベンチマークはランダムな長さの文字列の平均長(average length)を変化させつつ取りました．数値は1byteあたりにかかった処理時間比で小さいほど速いことを表します．
strlenが3種類(ANSI, BLOG, SSE2)とmemchrが2種類(ANSI, SSE2)あります．BLOGというのは今回試してみようというきっかけになったCounting Characters in UTF-8 Strings Is Fastの中のCバージョンです．

結果は極端に短いところではSIMDが使えず，かつそのチェックのためのオーバーヘッドがありそれほど速くなりませんが，32文字以上ではは2～5倍高速であることが分かります．
なお，gccのstrlen()は今となっては遅い命令を使っているためよくありません(なぜこうなっているのかちょっと理解に苦しみます)．

一つ細かい注意点としては，高速化のために与えられた範囲外の空間を少しアクセスします(readはするがその値は捨てます)．16byteアライメントされたところを超えることはないのでバグで16byte超えることがあったのですが修正しましたのでページングエラーにはなりませんが，purifyなどのツールを使うと警告がでるかもしれません．

intrinsic関数はVCとgccとで共通化され，しかも32bit, 64bit両対応なため汎用性も高いです．strlenSSE2のように30行未満の関数でも十分は効果はでます．利用しない手はないと思われます．

size_t strlenSSE2(const char *p)
{
    const char *const top = p;
    __m128i c16 = _mm_set1_epi8(0);
    /* 16 byte alignment */
    size_t ip = reinterpret_cast(p);
    size_t n = ip & 15;
    if (n > 0) {
        ip &= ~15;
        __m128i x = *(const __m128i*)ip;
        __m128i a = _mm_cmpeq_epi8(x, c16);
        unsigned long mask = _mm_movemask_epi8(a);
        mask &= 0xffffffffUL << n;
        if (mask) {
            return bsf(mask) - n;
        }
        p += 16 - n;
    }
    /*
        thanks to egtra-san
    */
    assert((reinterpret_cast(p) & 15) == 0);
    if (reinterpret_cast(p) & 31) {
        __m128i x = *(const __m128i*)&p[0];
        __m128i a = _mm_cmpeq_epi8(x, c16);
        unsigned long mask = _mm_movemask_epi8(a);
        if (mask) {
            return p + bsf(mask) - top;
        }
        p += 16;
    }
    assert((reinterpret_cast(p) & 31) == 0);
    for (;;) {
        __m128i x = *(const __m128i*)&p[0];
        __m128i y = *(const __m128i*)&p[16];
        __m128i a = _mm_cmpeq_epi8(x, c16);
        __m128i b = _mm_cmpeq_epi8(y, c16);
        unsigned long mask = (_mm_movemask_epi8(b) << 16) | _mm_movemask_epi8(a);
        if (mask) {
            return p + bsf(mask) - top;
        }
        p += 32;
    }
}

追記(2008/6/13)
64bit Windowsで_BitScanForwardの引数の型を勘違いしていたので修正．
ソースにライセンスを修正BSDライセンスと明記．

追記(2008/7/16)
strlenSSE2でループアンロールのため32byte単位で読み込んでいたため，ページングの境界を超えてしまうことがあったバグを修正(thanks to egtraさん)．

最近，Visual C++ のことを高機能なマクロアセンブラだと思っている光成です．
その考えを64bit Windows/Linuxにも押し進めるため，64bitに対応したJITアセンブラXbyakを公開しました．
64bit Visual Studioではインラインアセンブラが廃止されたため，何かと便利になるのではないかと思います．

ところでWikipediaのAMD64などには64bit Windowsに関して

64ビットアプリケーションではx87命令・MMX命令及び3DNow!命令をサポートしない（x87レジスタをコンテキストスイッチの際にセーブしない）

テスト方法
test_mmx.cppをコンパイルして(binary)
コマンドプロンプトを二つ開いて

test_mmx 1
test_mmx 3

と実行します．それぞれスレッドを起動して，1, 2, 3, 4という数値が表示され続けました．

もしMMXレジスタがコンテクストスイッチで保存されていなければ全て同じものになるはずなので，保存されていると推測されます．

Legacy Floating-Point Supportにも

The MMX and floating-point stack registers (MM0-MM7/ST0-ST7) are preserved across context switches

とあるので保存されているように思われます．

一つ気になるのは私がテストしたのは32bit WindowsのVMware上の64bit Xpだったという点です．素の64bit環境でテストした場合どうなるかどなたか試していただけますでしょうか．

追記
奥さんから英語版Wikipediaには使えると書いてますよという情報をいただきました．
#見るの忘れてました．迂闊だった…．

SEA & FSIJ 合同フォーラムでビット演算による最適化の妙味とJITアセンブラの中でデモに使ったVMを紹介します．
JITの紹介のために前日に2時間ででっちあげたVMなので本当に小さい(200行程度)ですが，エッセンスは楽しめるかなと思います．

ソースはXbyak.zipです．この中のxbyak/sample/toyvm.cppが今回作ったVMです(Win, Linuxと多分Intel Macでも動きます)．
このサンプルはフィボナッチ数列を計算して表示するだけのものです．
ここではどのように作ったかの説明をします．一つ前のエントリの資料も参考にしてください．

話の流れ

1. toyVMのスペック，命令セットと命令フォーマットを決める
   
2. toyVMのアセンブラを作る
   
3. toyVMの実行部分を作る
   
4. toyVM用のフィボナッチ数列プログラムを作って実行する
   
5. toyVMのマシン語をx86に変換するリコンパイラを作る
   
6. パフォーマンスを見る
   
7. リコンパイラを改良する
   

1. toyVMのスペックを決める

• 32bitレジスタA, Bの二つ．あとPC(program counter)
  
• メモリは4byte単位のみでのアクセス．4byte x 65536
  
• すべての命令は4byte固定
  
• 即値は全て16bit
  

命令群は次のものを用意しました．

メモリとレジスタの間の転送命令と加算，減算命令にレジスタの内容を出力する命令と，分岐命令だけです．
スタックが無いのでcall/retもありません．興味があれば自分で作ってみるのもよいかもしれません．
命令は4byteのうち先頭1byteに命令種別(code)，次の1byteにレジスタ種別(r)，最後の2byteに即値(imm)を入れることにします．
使われない場合は全て0にします．(code, r, imm)のペアと4byteデータの変換方法は次のようにします．簡単ですね．

void decode(uint32& code, uint32& r, uint32& imm, uint32 x)
{
    code = x >> 24;
    r = (x >> 16) & 0xff;
    imm = x & 0xffff;
}
void encode(Code code, Reg r, uint16 imm = 0)
{
    uint32 x = (code << 24) | (r << 16) | imm;
    code_.push_back(x);
}

2. toyVMのアセンブラを作る

void vldi(Reg r, uint16 imm) { encode(LDI, r, imm); }
void vld(Reg r, uint16 idx) { encode(LD, r, idx); }
void vst(Reg r, uint16 idx) { encode(ST, r, idx); }
void vadd(Reg r, uint16 idx) { encode(ADD, r, idx); }
void vaddi(Reg r, uint16 imm) { encode(ADDI, r, imm); }
void vsub(Reg r, uint16 idx) { encode(SUB, r, idx); }
void vsubi(Reg r, uint16 imm) { encode(SUBI, r, imm); }
void vjnz(Reg r, int offset) { encode(JNZ, r, static_cast(offset)); }
void vput(Reg r) { encode(PUT, r); }

3. toyVMの実行部分を作る

void run()
{
    uint32 reg[2] = { 0, 0 }; // A, B
    const uint32 end = code_.size();
    uint32 pc = 0;
    for (;;) {
        uint32 code, r, imm;
        decode(code, r, imm, code_[pc]);
        switch (code) {
           ...
        }
        pc++;
        if (pc >= end) break;
    } // for (;;)
}

switch (code) {
case LDI:
    reg[r] = imm;
    break;
case LD:
    reg[r] = mem_[imm];
    break;
case ST:
    mem_[imm] = reg[r];
    break;
case ADD:
    reg[r] += mem_[imm];
    break;
case ADDI:
    reg[r] += imm;
    break;
case SUB:
    reg[r] -= mem_[imm];
    break;
case SUBI:
    reg[r] -= imm;
    break;
case PUT:
    printf("%c %8d(0x%08x)\n", 'A' + r, reg[r], reg[r]);
    break;
case JNZ:
    if (reg[r] != 0) pc += static_cast<signed short>(imm);
    break;
default:
    assert(0);
    break;
}

void fibC(uint32 n)
{
    uint32 p, c, t;
    p = 1;
    c = 1;
lp:
    t = c;
    c += p;
    p = t;
    n--;
    if (n != 0) goto lp;
    printf("c=%d(0x%08x)\n", c, c);
}

Fib(int n)
{
    vldi(A, 1); // c = 1
    vst(A, 0); // p = 1
    vldi(B, n);
    vst(B, 2); // n
// lp
    vst(A, 1); // t = c
    vadd(A, 0); // c += p
    vld(B, 1); // mem[1]の値をBを経由してmem[2]に移動する
    vst(B, 0); // p = t
    vld(B, 2);
    vsubi(B, 1);
    vst(B, 2); // n--
    vjnz(B, -8); // PCを8減らせばlpのところにもどる．
    vput(A);
}

Fib fib(10);
fib.run();
>A      144(0x00000090)

void recompile()
{
    push(ebx);
    push(esi);
    push(edi);
 
    const Reg32 reg[2] = { esi, edi };
    const Reg32 mem(ebx);
 
    xor(reg[0], reg[0]);
    xor(reg[1], reg[1]);
    mov(mem, (int)mem_);
    const uint32 end = code_.size();
    uint32 pc = 0;
    uint32 labelNum = 0;
    for (;;) {
        uint32 code, r, imm;
        decode(code, r, imm, code_[pc]);
    L(toStr(labelNum++));
        switch (code) {
        ...
        pc++;
        if (pc >= end) break;
    } // for (;;)
 
    pop(edi);
    pop(esi);
    pop(ebx);
    ret();

    switch (code) {
    case LDI:
        mov(reg[r], imm);
        break;
    case LD:
        mov(reg[r], ptr[mem + imm * 4]);
        break;
    case ST:
        mov(ptr [mem + imm * 4], reg[r]);
        break;
    case ADD:
        add(reg[r], ptr [mem + imm * 4]);
        break;
    case ADDI:
        add(reg[r], imm);
        break;
    case SUB:
        sub(reg[r], ptr [mem + imm * 4]);
        break;
    case SUBI:
        sub(reg[r], imm);
        break;

    L(toStr(labelNum++));
        switch (code) {
        ...
        case JNZ:
            test(reg[r], reg[r]);
            jnz(toStr(labelNum + static_cast<signed short>(imm)));
            break;

.lp:
  mov   dword ptr [ebx+4],esi 
  add   esi,dword ptr [ebx] 
  mov   edi,dword ptr [ebx+4] 
  mov   dword ptr [ebx],edi 
  mov   edi,dword ptr [ebx+8] 
  sub   edi,1 
  mov   dword ptr [ebx+8],edi 
  test  edi,edi 
  jne   .lp

const Reg32 memTbl[] = { eax, ecx, edx };
const size_t memTblNum = NUM_OF_ARRAY(memTbl);
for (size_t i = 0; i < memTblNum; i++) xor(memTbl[i], memTbl[i]);

case ADD:
    if (imm < memTblNum) {        //
        add(reg[r], memTbl[imm]);    // 追加部分
    } else {                         //
        add(reg[r], ptr [mem + imm * 4]);
    }
    break;

.lp:
   mov         ecx,esi 
   add         esi,eax 
   mov         edi,ecx 
   mov         eax,edi 
   mov         edi,edx 
   sub         edi,1 
   mov         edx,edi 
   test        edi,edi 
   jne         .lp