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, "&", 5);
dst += 5;
break;
case '>':
memcpy(dst, ">", 4);
dst += 4;
break;
case '<':
memcpy(dst, "<", 4);
dst += 4;
break;
case '"':
memcpy(dst, """, 6);
dst += 6;
break;
case '\'':
memcpy(dst, "'", 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, "`", 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, "{", 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, "}", 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, "&", ">", "<", """, "'", "`", "{", "}"};
const static int dl[] = {0, 5, 4, 4, 6, 5, 5, 6, 6};
#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 に頼るのも良いけど、カリカリチューニングでもまだまだやれるんですよ。皆さん。
