Rust で UTF-16 → UTF-8 変換をちょっと速くする小ネタと PGO を使ってみる

##環境
toolchain: stable-i686-pc-windows-msvc
rustc 1.38.0 (625451e37 2019-09-23)

##UTF-8 変換
Windows で Rust を触っていると UTF-16 → UTF-8 変換する場面があります。変換はstd::char::decode_utf16を使います。

use std::char::{decode_utf16, REPLACEMENT_CHARACTER};

fn decode(source: &[u16]) -> String {
    decode_utf16(source.iter().cloned())
        .map(|r| r.unwrap_or(REPLACEMENT_CHARACTER))
        .collect()
}

NULL 文字で終わる UTF-16 文字列へのポインタを引数に取るなら、source.iter().cloned()のところをsource.iter().take_while(|&v| *v != 0).cloned()として NULL 文字までをスライスとして取得すれば良いです。

decode_utf16のソースを追っかけていくと、どうやら UTF-16 をcharに変換してそのcharをString::new()で作ったバッファに一文字ずつpushしているようです。

##ちょっと速くする
UTF-8 に変換後のバイト数があらかじめ分かっているなら、String::with_capacity()でバッファを確保しておけば余計なメモリアロケートが無くて速いんじゃね？ということでやってみました。

fn decode_with_capacity(source: &[u16], capacity: usize) -> String {
    let decoded = decode_utf16(source.iter().cloned());
    let mut buf = String::with_capacity(capacity);
    for r in decoded {
        buf.push(r.unwrap_or(REPLACEMENT_CHARACTER));
    }
    buf
}

ベンチマーク結果

function	ns
decode	1510
decode_with_capacity	484
3 倍くらい速くなりました。やったぜ。

##もう少し速くする
Stack 使ったらもっと速いんじゃね？ということでやってみました。たぶんこれが一番速いと思います。

use std::char::{decode_utf16, REPLACEMENT_CHARACTER};
use std::str;
use std::ptr;

fn decode_using_stack<'a>(source: &[u16], buf: &'a mut [u8]) -> &'a str {
    unsafe {
        let decoded = decode_utf16(source.iter().cloned());
        let mut p = buf.as_mut_ptr();
        for r in decoded {
            let c = r.unwrap_or(REPLACEMENT_CHARACTER);
            let len = c.len_utf8();
            ptr::copy_nonoverlapping(c.encode_utf8(&mut [0; 4]).as_ptr(), p, len);
            p = p.add(len);
        }
        str::from_utf8_unchecked(buf)
    }
}

fn main() {
    //"🦀蟹crab"
    let utf16 = [0x87F9, 0xD83E, 0xDD80, 0x0063, 0x0072, 0x0061, 0x0062];
    let mut buf = [0; 11];
    let utf8 = decode_using_stack(&utf16, buf.as_mut());
    println!("{}", utf8);
}

見るからに危険なコードです。

ベンチマーク結果

function	ns
decode	1510
decode_with_capacity	484
decode_using_stack	358
う～ん。安全なdecode_with_capacityを使いましょう。

##PGO
Rust 1.37.0 から PGO がサポートされました。リンク先の手順通りに進めて行けば OK ですが、Windows 環境だとちょっと異なる点もあるので書いておきます。

###llvm-tools-preview のインストール
簡単インストール。

PS> rustup component add llvm-tools-preview

環境変数の PATH に下記追加。
C:\Users\{your_user_name}\.rustup\toolchains\stable-i686-pc-windows-msvc\lib\rustlib\i686-pc-windows-msvc\bin

###RUSTFLAGS の設定
MSVC ツールチェインでは -Cpanic=unwindは動かないという警告が出てビルドできないので-Cpanic=abortをRUSTFLAGSに設定する必要があります。

PS> $env:RUSTFLAGS="-Cprofile-generate=C:\tmp\pgo-data -Cpanic=abort"
PS> cargo build --release

できたバイナリを実行するとC:\tmp\pgo-data内に.profrawファイルが生成されます。

###プロファイルデータのマージ

PS> llvm-profdata merge -o C:\tmp\pgo-data\merged.profdata C:\tmp\pgo-data

###マージしたデータを使ってビルド

PS> $env:RUSTFLAGS="-Cprofile-use=C:\tmp\pgo-data\merged.profdata"
PS> cargo build --release

以上。

ベンチマーク結果

function	ns
decode	1510
decode_with_capacity	484
decode_using_stack	358
(PGO) decode	1610
(PGO) decode_with_capacity	490
(PGO) decode_using_stack	235

decode_using_stackだけ速くなりました。う～ん。最適化には向かないのかな？

##まとめ
要素数がある程度分かっているならVec::with_capacity()を使おう。