2016/08/17


SSEを使ってHTMLエスケープを高速化してみた - k0kubun's blog

高速なHTMLエスケープをするライブラリを作った ある日HTMLエスケープを速くしたくなって、hescapeというライブラリを作った。 github.com とにかく速いHTMLエスケープがしたい R...

http://k0kubun.hatenablog.com/entry/hescape

以前、moznion 氏の petit-html-escaper を勝手に高速化した時の話。

GitHub - moznion/petit-html-escaper: A simple and small escaper for HTML with SSE4.2 function

Author moznion ( moznion@gmail.com ) mattn License The MIT License (MIT) Copyright © 2015 moznion, h...

https://github.com/moznion/petit-html-escaper

速くしたと言っても SSE 部分ではない。ベンチマークの比較元である非 SSE な実装の方。元のベンチマーク結果が README.md に残っている。

petit-html-escaper: 3.935205 [sec]
simple-impl: 5.634651 [sec]

petit-html-escaper is faster 143.185715% than simple implementation

以下がその時の比較元のコード。思いつくままに実装された単純なコードです。

static void simple_escape_html(char *dst, const char *input, size_t input_size) {
  for (int i = 0; i < input_size; i++) {
    const char c = *(input++);
    switch (c) {
      case '&':
        memcpy(dst, "&amp;"5);
        dst += 5;
        break;
      case '>':
        memcpy(dst, "&gt;"4);
        dst += 4;
        break;
      case '<':
        memcpy(dst, "&lt;"4);
        dst += 4;
        break;
      case '"':
        memcpy(dst, "&quot;"6);
        dst += 6;
        break;
      case '\'':
        memcpy(dst, "&#39;"5);
        dst += 5;
        break;
      case '`':
        // For IE. IE interprets back-quote as valid quoting characters
        // ref: https://rt.cpan.org/Public/Bug/Display.html?id=84971
        memcpy(dst, "&#96;"5);
        dst += 5;
        break;
      case '{':
        // For javascript templates (e.g. AngularJS and such javascript frameworks)
        // ref: https://github.com/angular/angular.js/issues/5601
        memcpy(dst, "&#123;"6);
        dst += 6;
        break;
      case '}':
        // For javascript templates (e.g. AngularJS and such javascript frameworks)
        // ref: https://github.com/angular/angular.js/issues/5601
        memcpy(dst, "&#125;"6);
        dst += 6;
        break;
      default:
        memcpy(dst, &c, 1);
        dst += 1;
    }
  }
  *dst++ = *"\0";
}

ソースも見渡しが良いし悪いコードではないと思いましたが、SSE だから速くなるという言葉にカッとして勢いだけでこの実装を直してみました。そのコードが以下。

static void simple_escape_html(char *dst, const char *input, size_t input_size) {
  const char *ptr = input, *end = input + input_size;
  const static int pp[UCHAR_MAX+1] = {
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,4,0,0,0,1,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,2,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,0,8,0,0
    /* following zero(s) */
  };
  const static char* dd[] = {NULL"&amp;""&gt;""&lt;""&quot;""&#39;""&#96;""&#123;""&#125;"};
  const static int dl[] = {054465566};
#define _ESC_AND_COPY(d,s,n) { memcpy(d,s,n); d += n; }
  while (ptr < end) {
    unsigned char c = *ptr++;
    int i = pp[c];
    if (i == 0) *dst++ = c;
    else _ESC_AND_COPY(dst, dd[i], dl[i]);
  }
#undef _ESC_AND_COPY
  *dst++ = 0;
}

memcpy を相手にしても結果は変わらないので、処理分岐を相手にした。switch 文は遅くなるので文字の ASCII コードをインデックスに使い、置換すべき文字列とオフセットを得る処理です。

ベンチマークがどの様に変わったかというと。。。

petit-html-escaper: 4.954000 [sec]
simple-impl: 4.323000 [sec]
petit-html-escaper is faster 87.262817% than simple implementation

なんと非 SSE の方が速くなってしまいました。もちろん入力データによっては SSE を使って1命令で処理できるバイト数を増やす事は出来るのですが、switch 文や if 文を削るだけでも十分 SSE と戦えるという結果を出せました。現在このコードは moznion 氏の petit-html-escaper の比較元コードとしてマージされています。一部 macOSX で使われている CPU アーキテクチャでは若干 simple_escape_html の方が遅くなるケースがある様ですが、僕が調べた限り Windows/Linux では同程度か、このコードの方が速いという結果が得られました。

SSE に頼るのも良いけど、カリカリチューニングでもまだまだやれるんですよ。皆さん。


2016/08/08


Gopher

僕がプログラミング言語「Go言語」を知り、使い始めてからそろそろ7年目に入ろうとしています。

当初 Google が作っているという鳴り物があった為、色々なメディアに取り上げられ色々な方がブログ等でGo言語を紹介し、色々な意見でGo言語が語られました。大抵の場合、プログラミング言語とは始めはチヤホヤと取り出され、落ち着いてからが本当の人気を表すという傾向にあります。皆さんもそう思っていたかもしれませんし、僕もそう思っていたと思います。

僕がGo言語を触りだした頃、まだ色々と足りない部分がありました。Linux で動いている多くの機能が Windows では未実装になっていました。しかしそんなGo言語であっても高速なビルドと実行速度で僕の好奇心を揺さぶるには十分な物でした。


その後、僕はGo言語にパッチを送る様になりました。その内幾らかはマージされました。現時点ではコアのリポジトリで79個のコミットがマージされていますが、マージされると今でも嬉しくなります。毎日朝にリポジトリを最新にしてビルドし、安定動作しているのを確認する日々が続きました。

気付いた頃には僕は新規で何かをプログラミングする場合には必ずGo言語で実装を始める様になっていました。

僕のこのサイトにも多くのGo言語の情報が書かれています。今では業務のプロダクションの一部にもGo言語を使っていますし、誰にも見せない様な個人のツールにもGo言語を使っています。

Go言語は僕にとって既に無くてはならない存在になってしまいました。

またGo言語にパッチを送った事で良い経験が出来ました。雲の上の人だと思っていた Rob Pike 氏や Russ Cox 氏、Brad Fitzpatrick 氏たちが僕の書いたパッチのレビューをしてくれたり、メールにコメントしてくれた時の事は今でも忘れられないくらい興奮したのを覚えています。そして彼らの適切すぎるソースコードレビューに感動したのも覚えています。正直いって彼らには敵いません。Go言語の開発者メーリングリストを見ていると自分の技術力との差に愕然とする事も多々あります。

そして次第に僕の周りでもGo言語が使われ始め、Twitter のタイムラインでもGo言語に関する発言が増えてきました。海外から比べると1年遅れていると言われていた日本企業でのGo言語導入も今では多くの有名企業がGo言語を採用しプロダクションでも利用される様になって来ました。僕がGo言語を作った訳ではないし大したパッチを送った訳では無いですが、昔を知っているだけにとても感慨深い思いです。

そろそろGo言語も一般のユーザに認知されてきたのだと思っています。そしてGo言語を操る有名なエンジニアも多く現れました。

そしてその彼らが1冊の本を書く事になりました。

みんなのGo言語【現場で使える実践テクニック】 みんなのGo言語【現場で使える実践テクニック】
松木雅幸, mattn, 藤原俊一郎, 中島大一, 牧 大輔, 鈴木健太
技術評論社 / ¥ 2,138 (2016-09-09)
 
発送可能時間:在庫あり。

技術評論社様から依頼を頂いた際には快諾させて頂きました。その際、執筆メンバの紹介をお願いされ、何名かをご紹介させて頂きました。結果見渡すと、Go言語界隈ではスターエンジニアと言ってもいい位に豪華なメンバが執筆に参加して頂ける事になりました。なかなかこの面子は集まらないと思います。

songmu さん、fujiwara さん、deeeetさん、lestrrat さん、suzuken さん、そして僕。計6が執筆メンバです。

彼らが元々Go言語の使い手では無かった事をご存じの方も多いと思います。Go言語の良いところも良くないところも知っているこのGo言語エンジニア達が現場で得たノウハウやテクニックを惜しげもなく書き連ねて下さっています。

僕も現場で得た開発テクニックやハマリ所などを書かせて頂きました。このブログでも出していないネタばかりです。他の執筆陣の方の記事も含め、Go言語を触った事がある方であればきっと面白いと思いながら読んで頂けると思っています。

「みんなのGo言語」というタイトルも皆で考え決めました。「みんGo」と呼んで下さい。そしてぜひお手に取って読んでみて下さい。

この本でGo言語を好きになってくれる方が少しでも増えてくれる事を、そしてこの本で誰かが抱えていた問題が少しでも解決する事を、一執筆者として願っています。


2016/08/05


昨日僕の Twitter タイムラインで q というツールが話題に上がっていました。

GitHub - harelba/q: q - Run SQL directly on CSV or TSV files

Text as Data q is a command line tool that allows direct execution of SQL-like q...

https://github.com/harelba/q

標準入力を SQL で抽出できるという物です。ただ個人的には「こういうの python じゃなくて Go でビルドされてると助かるよなー」と思ったので q と同じ様な動作になるツールを作ってみました。

GitHub - mattn/qq

Select stdin with query

https://github.com/mattn/qq

例えば msys2 のシェル上で ps を実行すると以下の様になりますが

$ ps
      PID    PPID    PGID     WINPID   TTY         UID    STIME COMMAND
     4876    2000    4876      13840  pty1     1061251 18:31:09 /usr/bin/ps
     2000   11384    2000       8804  pty1     1061251 18:30:45 /usr/bin/bash
    11384       1   11384      11384  ?        1061251 18:30:45 /usr/bin/mintty
     7552   13692   13692       9428  pty0     1061251 17:51:39 /usr/bin/ssh
    13692   12148   13692      18360  pty0     1061251 17:51:39 /usr/bin/ssh
     7828       1    7828       7828  ?        1061251 16:11:41 /usr/bin/ssh-agent
    12148       1   12148      12148  ?        1061251 17:51:39 /usr/bin/mintty

これを qq に食わせると

$ ps | qq -q 'select pid from stdin'
2000
11384
9596
7552
13692
7828
12148

この様に表形式のコマンド出力を SQL で抽出ます。

q と違う所は、日本語の幅をきちんと見ている所です。

aaa bb
a b あ

この様なテキストの場合、カラム aaa には a b が、カラム bb には が入る事を期待してしまいます。q の場合

$ cat nihongo.txt | q -H 'select bb from -'
b

この様にカラム bb には b が入っていますが、qq だと

$ cat nihongo.txt | qq -q 'select bb from stdin'

が格納されています。q の場合、日本語が多く混じると異なるカラムに値が入ってしまいますが、qq だと大丈夫。また qq では q と同じ動作にさせる事もできます。-ip オプションでデリミタを正規表現として渡せるので

$ cat nihongo.txt | qq -ip '\s+' -q 'select bb from stdin'
b

こうすれば b が得られます。また -ic オプションを付けるとカンマセパレータの CSV (ダブルクオート可)で、-it でタブセパレートな TSV で入力データを扱う事ができます。さらに -e オプションでエンコーディング名を指定できるので Windows の Excel で作った CSV ファイルでも安心して扱えます。

品目,単価
みかん,120
りんご,100
トマト,180
$ cat meisai.csv | qq -ic -e cp932 -q "select 単価 from stdin where 品目 = 'みかん'"
120
出力フォーマットはデフォルトが CSV です。-oh を付けるとヘッダカラムが出力されます。-oj を付けると JSON 形式で出力されるのでシステムの一部として使う事も出来るかもしれません。また -or で raw 出力しますので、
$ ps | qq -q "select pid from stdin where command = '/usr/bin/grep'" | xargs kill

の様に awk や grep の代わりに使う事もできます。もちろん golang なのでバイナリ1つで動きますし、python が無い環境でも動きます。SQL なので grep では難しい抽出方法も可能ですね。

最初は q を golang に移植するだけのつもりでしたが、思ったより便利そうなので公開してみました。よろしければどうぞお使い下さい。

後で引数からファイルを取ってunionとか出来る様にする予定なので、その場合は標準入力と区別するために - を採用する予定です。その場合、実行方法が上記の記事と異なる可能性があります。