チーム「にゃーん」で ISUCON 6 予選参加して惨敗してきました。厳しい。というわけで記録です。といっても、結局自分が担当した部分以外はあまり把握していないので、それは各自がブログか何かを書くのを待ちます。
まず、インスタンスを起動して、あまり分ける必要がない二つのアプリケーションが動いていることを確認したので、れにが二つをマージしていました。その間に DB のインデックスで露骨にまずいものがないか見ていましたが、一応張ったもののそれほど大幅ということはありませんでした。
htmlify なる関数があり、これが今回のメインのようでした。記事（初期状態で約七千）のタイトルを本文中から自動抽出してリンクに変換するものですが、全ての記事のタイトルを抽出したうえで正規表現や SHA1 を活用した実装になっていて遅いこと遅いこと。
なお、今回は Ruby だったこともあり初期実装は0点でした。
そのあと、他のチームメンバーは Web 周りのチューニングなどをしてそれなりに点数を伸ばしていたようですがあまり把握しておらず、僕は htmlify をなんとか早くしようとしていました。
他のメンバーと違い、僕は Ruby の知識があまりなかった状態でこれを見たので、 Ruby の置換が同様に書かれたほかの言語と比べても遅いことに絶望して、なんとか早くするアルゴリズムを模索しました。とりあえずなんにしてもその部分を Ruby で書くのは諦めて、 C++ で書いて外部コマンドで呼び出すことにしました。（引数で辞書と入力を渡し、出力は標準出力）
二分探索をしようとしたりさまよっていましたが、最終的にはハッシュマップで実装しました。与えられた文字列に対して短いほうから辞書にある最大の長さまで試す、ただし途中で打ち切るための情報を埋め込む、というものです。ポインタでいろいろ扱える方が楽だったのでポインタをベースとし、何かとコピー回数の増える std::string はなるべく使わないように変更、 C++ の std::map は hashmap ではないことを思い出して std::unordered_map に変えましたが、パフォーマンス計測値、スコアともに改善はしたものの依然遅いままでした。
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <unistd.h>
#include <map>
#include <iostream>
#include <unordered_map>
using namespace std;
void urlwrite(const char *str) {
while(*str!='\0'){
if ((*str>='a' && *str<='z') || (*str>='A' && *str<='Z') || (*str>='0' && *str<='9') || *str=='.' || *str=='-' || *str == '_' || *str == '~') {
fwrite(str, 1, 1, stdout);
++str;
continue;
}
int t = *((unsigned char*)str);
int b1 = t/16;
int b2 = t%16;
char tmp[3];
tmp[0]='%';
tmp[1]=(b1<10)?(b1+'0'):(b1+'A'-10);
tmp[2]=(b2<10)?(b2+'0'):(b2+'A'-10);
fwrite(tmp,1,3,stdout);
++str;
}
}
void htmlwrite(const char *str) {
while(*str!='\0'){
switch (*str) {
case '&':
fwrite("&", 1, 5,stdout);
break;
case '<':
fwrite("<", 1, 4, stdout);
break;
case '>':
fwrite(">", 1, 4, stdout);
break;
case '\'':
fwrite("'", 1, 6, stdout);
break;
case '\"':
fwrite(""", 1, 6, stdout);
break;
case '\n':
fwrite("<br />\n",1,7,stdout);
break;
case '\r':
fwrite("<br />\r",1,7,stdout);
break;
default:
fwrite(str,1,1,stdout);
}
++str;
}
}
int main (int argc, char *argv[]) {
unordered_map <string, int> dic;
setvbuf(stdout, NULL, _IOFBF, 102400);
size_t longest=0;
for(int i=2;i<argc; ++i){
string key=string(argv[i]);
for(int j=1;j<4;++j){
string tmp=key.substr(0,j);
if(!dic.count(tmp)){
dic[key.substr(0,j)]=1;
}
}
{
int j=6;
string tmp=key.substr(0,j);
if(!dic.count(tmp)){
dic[key.substr(0,j)]=1;
}
}
dic[key]=2;
longest=max(longest, key.length());
}
while (*argv[1]!='\0') {
int skiplen=1;
string title;
int flag=0;
for(int i=1;i<=longest;++i){
char tmp=argv[1][i];
argv[1][i]='\0';
string key=string(argv[1]);
argv[1][i]=tmp;
if(dic.count(key)){
if(dic[key]==2){
title=key;
flag=1;
}
}else{
if(i<4 || i==6){
break;
}
}
}
if(flag){
fwrite("<a href=\"/keyword/", 1,18,stdout);
urlwrite(title.c_str());
fwrite("\">", 1,2,stdout);
htmlwrite(title.c_str());
fwrite("</a>", 1,4,stdout);
skiplen=title.length();
}else{
char tmp=argv[1][1];
argv[1][1]='\0';
htmlwrite(argv[1]);
argv[1][1]=tmp;
}
argv[1]+=skiplen;
}
}
※ちなみに、<a href=”/keyword/～～”> の部分は、 Ruby の見本実装では <a href=”http://192.0.2.1/keyword/～～”> のように URL 変換済み、 PHP の見本実装では <a href=”/keyword/～～”> のように path 部分のみでした。後者で書きましたが、不思議でした。
その後、 Trie 木を実装しましたが、初期化コストが大きく辞書を作るのに 100ms 程度かかってしまいました。外部コマンドなので毎回初期化していたのと、特にバイナリでいい感じに複数のデータを受け渡す実装の時間もなく、トップページを表示するのに 10 回読みだしてしまい、却って遅かったのでこちらは導入に至りませんでした。Trie 木生成後の処理は一桁速くなったように思われる（雑な計測からの体感）ので、 Ruby のモジュールにするか、これ専用のサーバを立てて記事追加・削除・データ変換が毎回行えるようにすればかなり高速化できたものと思われますが、すでに終盤でそこまでする時間がありませんでした。
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <unistd.h>
#include <map>
#include <iostream>
#include <unordered_map>
using namespace std;
void urlwrite(const char *str) {
while(*str!='\0'){
if ((*str>='a' && *str<='z') || (*str>='A' && *str<='Z') || (*str>='0' && *str<='9') || *str=='.' || *str=='-' || *str == '_' || *str == '~') {
fwrite(str, 1, 1, stdout);
++str;
continue;
}
int t = *((unsigned char*)str);
int b1 = t/16;
int b2 = t%16;
char tmp[3];
tmp[0]='%';
tmp[1]=(b1<10)?(b1+'0'):(b1+'A'-10);
tmp[2]=(b2<10)?(b2+'0'):(b2+'A'-10);
fwrite(tmp,1,3,stdout);
++str;
}
}
void htmlwrite(const char *str) {
while(*str!='\0'){
switch (*str) {
case '&':
fwrite("&", 1, 5,stdout);
break;
case '<':
fwrite("<", 1, 4, stdout);
break;
case '>':
fwrite(">", 1, 4, stdout);
break;
case '\'':
fwrite("'", 1, 6, stdout);
break;
case '\"':
fwrite(""", 1, 6, stdout);
break;
case '\n':
fwrite("<br />\n",1,7,stdout);
break;
case '\r':
fwrite("<br />\r",1,7,stdout);
break;
default:
fwrite(str,1,1,stdout);
}
++str;
}
}
class Trie {
public:
Trie* children[256];
uint32_t ex[8];
int exist=0;
Trie(){
memset(ex,'\0',32);
}
void insert(unsigned char *str) {
if(*str=='\0') {
exist=1;
return;
}
if(!((ex[(*str)/32]>>((*str)%32))&1)){
children[*str]=new Trie();
ex[(*str)/32]|=1UL<<((*str)%32);
}
children[*str]->insert(str+1);
}
int find(unsigned char *str) {
int tmp=-2;
if (exist) {
tmp=-1;
}
if((ex[(*str)/32]>>((*str)%32))&1){
tmp=max(tmp, children[*str]->find(str+1));
}
if(tmp==-2)
return -2;
else
return tmp+1;
}
};
int main (int argc, char *argv[]) {
unordered_map <string, size_t> dic;
Trie trie;
setvbuf(stdout, NULL, _IOFBF, 102400);
for(int i=2;i<argc; ++i){
trie.insert((unsigned char*)argv[i]);
}
cout<<"<br>clock="<<clock()<<"<br>";
while (*argv[1]!='\0') {
int ret = trie.find((unsigned char*)argv[1]);
int skiplen=1;
if(ret>0){
char tmp=argv[1][ret];
argv[1][ret]='\0';
fwrite("<a href=\"/keyword/", 1,18,stdout);
urlwrite(argv[1]);
fwrite("\">", 1,2,stdout);
htmlwrite(argv[1]);
fwrite("</a>", 1,4,stdout);
skiplen=strlen(argv[1]);
argv[1][ret]=tmp;
}else{
char tmp=argv[1][1];
argv[1][1]='\0';
htmlwrite(argv[1]);
argv[1][1]=tmp;
}
argv[1]+=skiplen;
}
cout<<"<br>clock="<<clock()<<"<br>";
}
この辺をバックグラウンドで走らせる準備などが必要なのだと学ぶことができました。
