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`を使います。

```rust
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()`でバッファを確保しておけば余計なメモリアロケートが無くて速いんじゃね？ということでやってみました。

```rust
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 使ったらもっと速いんじゃね？ということでやってみました。たぶんこれが一番速いと思います。

```rust
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|
う～ん:thinking:。安全な`decode_with_capacity`を使いましょう。

##PGO
Rust 1.37.0 から [PGO がサポートされました](https://blog.rust-lang.org/2019/08/15/Rust-1.37.0.html#profile-guided-optimization)。リンク先の[手順](https://doc.rust-lang.org/rustc/profile-guided-optimization.html#a-complete-cargo-workflow)通りに進めて行けば OK ですが、Windows 環境だとちょっと異なる点もあるので書いておきます。

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

```powershell
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`に設定する必要があります。


```powershell
PS> $env:RUSTFLAGS="-Cprofile-generate=C:\tmp\pgo-data -Cpanic=abort"
PS> cargo build --release
```
できたバイナリを実行すると`C:\tmp\pgo-data`内に`.profraw`ファイルが生成されます。

###プロファイルデータのマージ
```powershell
PS> llvm-profdata merge -o C:\tmp\pgo-data\merged.profdata C:\tmp\pgo-data
```

###マージしたデータを使ってビルド
```powershell
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`だけ速くなりました。う～ん:thinking:。最適化には向かないのかな？

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