2016年に作ったもの

一年は長いのか短いのか, その一年で作ったものは多いのか少ないのか, そんなことを考えながら (考えていない) 今年作ったものを振り返りドヤ顔するだけの記事.

( ゚д゚ )彡

est

統計計算用簡易スクリプト言語.

github.com

実験データを集計するのに awk で計算のロジックを書いたり R でファイルを読み込んだりとかを書くのが面倒だったので, 適当に作りました.

ベクトル演算みたいなことができて, 例えば awk で,

awk '{sum+=$1}END{print sum}' foobar.dat

などと書くところを,

est 'sum $1' foobar.dat

とか書けて便利.

Lazy-Jiro

エイプリルフールネタで作った神域プログラミング言語. ここで試せます.

github.com

もはや懐かしい某アカウントのツイートのような文章でプログラムを書けます. echo を書くとこんな感じ.

平成28年4月1日金曜日、ラメーン二郎 歯舞店、ラメーン 700YEN
麺、極めて柔らか、汁染みまくってて、ウンメ〜ッ!
汁、醤油利いててメッチャ俺好みのもの。濃厚でウンメ〜ッ!
ブタ、プリリとした食感。脂身甘くてウンメ〜ッ!
完飲。

名前の通り (?) Lazy K ベースで, 去年作った JS 製の Lazy K インタプリタを流用しつつ, Web Worker とか使って動かしています.

Whitespace 関連

OUCC の部誌に Whitespace 超入門を寄稿しました. 紙媒体で一度はやってみたいネタだったので満足です.

ついでにサンプルコードの動作確認やらなんやらに使うために, インタプリタとか簡易コード生成ツールとか作りました.

github.com

Grass 関連

LT で難解プログラミング言語を紹介するついでに, 処理系の一つも実装できないのに紹介しちゃまずかろうということで Grass のインタプリタを作りました.

github.com

その後 Grass に (なぜか) ハマり, 型無しラムダ計算のプログラムから Grass に変換するツール (コンパイラ?) も作りました.

github.com

来年は型をつけたいですね (?)

dotris

Flash で作った, ほとんど自由にサイズを変えられるテトリスの JS 版. ここで遊べます.

github.com

canvas の標準の機能が乏しかったり, Flash とは使い勝手が異なったりして色々苦労しました.

loquat

一昨年くらいに作った JS 製パーサコンビネータ式年遷宮しています.

github.com

まだテストが不完全だったり, 機能が十分か確認したりしている途中で, 年内に終わりませんでした. 1月中にはどうにかしたい?

その他

BFJS

Brainf*ck インタプリタ. 書いてなかったので書いたというだけで特に目新しいことはないです.

github.com

npm-sum

npm view の結果を整形して見やすくしてくれるやつ. brew info とか cabal info とかと同じようなものだと思ってもらえれば良いです.

github.com

その他のその他

https://github.com/susisu を見れば中途半端な状態で止まっているものが...

来年の目標

うに.

String.fromCodePoint が遅かった

発端

ある日, 私は文字列の先頭を切り出すために次のような関数を書いていました.

https://github.com/susisu/loquat-core/blob/dcd37f885b5f5b1b0dfdc0e15680375a16239318/lib/utils.js#L97-L113

function unconsString(str, unicode) {
    if (unicode) {
        const cp = str.codePointAt(0);
        if (cp === undefined) {
            return { empty: true };
        }
        else {
            const char = String.fromCodePoint(cp);
            return { empty: false, head: char, tail: str.substr(char.length) };
        }
    }
    else {
        return str === ""
            ? { empty: true }
            : { empty: false, head: str[0], tail: str.substr(1) };
    }
}

unicode = false のときは別に特に変わったことはしていないのですが, unicode = true のときは String.prototype.codePointAt を使って code point 単位で文字コードを取り出し, それを String.fromCodePoint を使って文字列に変換しています.

要するに unicode = true のときは, サロゲートペア (絵文字とか) をペアのまま取り出してくれるというやつです.

const str = "🍣🍤"; // === "\uD83C\uDF63\uD83C\uDF64";
console.log(unconsString(str, false));
// -> { empty: false, head: "\uD83C", tail: "\uDF63🍤" }
console.log(unconsString(str, true));
// -> { empty: false, head: "🍣", tail: "🍤" }

ところで unconsString 関数のパフォーマンスを調べてみましょう (Node.js v7.3.0, 雑に2回実行して平均とってます).

ASCII, unicode = false

const N = 10000000;

console.time("uncons");
let str = "abcd";
for (let i = 0; i < N; i++) {
    unconsString(str, false);
}
console.timeEnd("uncons");

400 ms.

ASCII, unicode = true

const N = 10000000;

console.time("uncons");
let str = "abcd";
for (let i = 0; i < N; i++) {
    unconsString(str, true);
}
console.timeEnd("uncons");

1620 ms. 既に雲行きが怪しいとかそういうレベルではない.

サロゲートペア, unicode = false

const N = 10000000;

console.time("uncons");
let str = "🍣🍤";
for (let i = 0; i < N; i++) {
    unconsString(str, false);
}
console.timeEnd("uncons");

790ms. ASCII と比べて遅いのは内部表現の都合だろうか?

サロゲートペア, unicode = true

const N = 10000000;

console.time("uncons");
let str = "🍣🍤";
for (let i = 0; i < N; i++) {
    unconsString(str, true);
}
console.timeEnd("uncons");

4300 ms. もうダメだ.

何が遅いのか

unconsString 関数内では特に複雑なこともしていないので, 遅いことが疑われるのは String.prototype.codePointAtString.fromCodePoint のどちらかしかないわけで, 結局タイトルの通り, String.fromCodePoint が犯人だったというわけです.

書き直す

そんなこんなで以下のように書き直しました.

https://github.com/susisu/loquat-core/blob/6fbcffecb21b415547d20e728b1ef259f5975571/lib/utils.js#L97-L123

function unconsString(str, unicode) {
    const len = str.length;
    if (unicode) {
        if (len === 0) {
            return { empty: true };
        }
        else if (len === 1) {
            return { empty: false, head: str[0], tail: str.substr(1) };
        }
        else {
            const first = str.charCodeAt(0);
            if (first < 0xD800 || 0xDBFF < first) {
                return { empty: false, head: str[0], tail: str.substr(1) };
            }
            const second = str.charCodeAt(1);
            if (second < 0xDC00 || 0xDFFF < second) {
                return { empty: false, head: str[0], tail: str.substr(1) };
            }
            return { empty: false, head: String.fromCharCode(first, second), tail: str.substr(2) };
        }
    }
    else {
        return len === 0
            ? { empty: true }
            : { empty: false, head: str[0], tail: str.substr(1) };
    }
}

String.fromCodePoint の代わりに String.fromCharCode を使っています. その過程で code point を code unit に分割する処理が必要だったりして, 結局 String.prototype.codePointAt の中身も仕様書を見ながら再実装したりしています (色々省いてはいますが).

実際これでパフォーマンスが改善したのか, 再度計測して比べてみましょう.

ASCII, unicode = true

const N = 10000000;

console.time("uncons");
let str = "abcd";
for (let i = 0; i < N; i++) {
    unconsString(str, true);
}
console.timeEnd("uncons");

1620 ms → 460 ms. unicode = false の場合とほぼ変わらない速度が出るようになりました.

サロゲートペア, unicode = true

const N = 10000000;

console.time("uncons");
let str = "🍣🍤";
for (let i = 0; i < N; i++) {
    unconsString(str, true);
}
console.timeEnd("uncons");

4300 ms → 680 ms. むしろ unicode = false より速くなった.

まとめ

というわけで無事 String.fromCodePoint を避けることで高速化に成功しました. パフォーマンスが気になる場合は代わりに旧来通りの String.fromCharCode を使いましょう. あまりちゃんと調べていませんが, Firefox でも効果があるっぽいです.

(追記: なぜ遅いのかと V8 の中身をざっと見た感じでは String.fromCharCode がかなり最適化されたような実装になっているのに対して, String.fromCodePoint はほぼ仕様書見たままのナイーブな実装になっている雰囲気だった. 雰囲気しかわからないので正しくないかもしれない.)

unconsString 関数はパーサライブラリの中で使っていて, 文字列分割は頻繁に行われるため, 全体のパフォーマンスにそこそこ影響を及ぼします. 適当に JSON パーサで調べたら unicode = true の場合に 20 〜 30 % くらい高速化しました. Cookie Cliker なら 2000 時間放置後の ascension くらいの威力ですね (人に依るのでは?).