equal-l2/tsubuyaki.md

## tsubuyaki.md

      
    Raw
  

              tsubuyaki.md
            
          
    TL;DR

GeoTagの構造体を頑張って小さくしてメモリに載せて、actix-webでゴリ押ししたら早くなった
実装したもの一覧


https://github.com/equal-l2/tag-pp : CSV前処理(元データの性質とかも書いてある)
https://github.com/equal-l2/tag-geotag : Tag、GeoTagの構造体の具体的な定義（Rustだと構造体のメンバを勝手に並び替えてパディングを小さくしてくれるけど、他言語ではそうでもないこともあるので注意）
https://github.com/equal-l2/tag-search : 検索システム(あんまり面白いことしてない)

元のCSVファイルを読んでいた春


PHP遅いん……
Rustで書くか -> まだ遅い
ファイル分割してマルチスレッドで読む -> ちょっと速い

前処理の夏


tag.csvは1タグあたり1行にまとめるべ -> 454MBから260MBへ
geotagの前処理 (どれくらい減ったか調べてない)

URL

120文字くらいあるので、共通部分を取り除く
非共通部分も規則があるのでそれに合わせて設計する

1文字だけの差分があるのでそこはchar
他はまとまって変化しているのでStringで持っておく


タグのないgeotagは消すべ -> 1.1GBから471MBへ
tagとgeotag合わせて700MBちょい -> メモリに丸ごと載るのでは? -> ハッシュテーブルにしてみる

メモリに乗らない秋


Macだと載るんだけどなー
項目がアホみたいに多いタグは処理結果を出しといて削減できんか? -> できるっちゃできるけど……
tag.csvを削るのは労力に対して成果が小さい(1タグに10万件対応があったとしても所詮u64なので1MBも減らない)
まあgeotag.csv削るわな
とは言っても良さげな案も浮かばない
GeoTag構造体を見直すか

泥臭い冬


DateTimeはDate部i32,Time部u32×2(整数部、小数部)の計12Byteで構成

与えられたタイムスタンプは小数部がないのでunix time(i64)にできそう
2038年より前なのでi32で十分 -> 4Byte削減(総計23MB減)


整数型は差分にしてフィールド幅を小さくできないか(全部の整数型が半分になればtagに対応するVecの容量も概ね半分になる)

idは無理だった(値のばらつきが大きい)
time

最小値 1341100800、最大値1375228746、差は34127946


u16にできるほど小さい差ではなかった


文字列をできるだけ数字で解釈してu64に納められないか(Stringは結局Vecで、usize(多分64ビット)の長さフィールドを持っているので、u64に入るならそっちの方が得)

URLの非共通文字列(最大26文字)

元は大雑把に考えて最大 8 (len) + 26 = 34バイト
部分ごとに分けて考える

/の前は最大4桁の整数 -> u16に入る
その後_の前は最大10桁の整数 -> u32では足りず、u64が必要
そのあとは10桁の16進数 -> u32では足りず、u64が必要


全部整数型にすると2+8+8=18Byte


あれ、ID、URLに含まれてない？ (_の前の最大10桁の整数がそれ)

u64のフィールドが1つ減った


元が 12 (time) + 8 (lat) + 8 (lon) + 1 (domain_num) + 34 (url_part) = 63Byteだった
これが 4 (time) + 8 (lat) + 8 (lon) + 1 (domain_num) + 2 (url_num1) + 8 (url_num2) = 31 Byteになった

メモリに載った冬


載った！！！！！！
もうちょっと減らせるか？

domain_num

Rustのcharって4バイトらしいですよ……
ASCIIなので1バイト(というか7ビット)に収まる
もっと言っちゃえば数字1桁なので4ビットで足りる
どっかのフィールドにビット演算でくっつけられないか?

url_num1

最大値が8560なので2ビットしか余っていない


url_num2

10桁の16進数が最大値FFFFFFFFFFをとったとして、上位3バイト(24ビット)は空く
4ビットくらいなら全然入る
入れてみたけどパディングで減らした分が無駄になる


u8にしよう


いっそバイト列にしてみるか

パディングがなくなるので小さくはなる
そこまで小さくしたいか？


そろそろ他の面でパフォーマンスをあげよう

最新100件を取ってくるのが遅い

一旦Vecにしてからソートするのでデータ件数に比例して時間がかかる
ヒープを使って最新100件を取れるようにする

件数が少ないとき(1000件未満くらい)はVecの方が速いので件数に応じて切り替えする


HTMLの生成が少し遅い

format!で毎回Stringを生成しているから

あらかじめStringを確保
そこにwrite!で書き込む


ポスト・モーテム


スライドがゴミすぎて誰にも発表せずに終わってしまった
でもたぶん一番早いと思います[要出典]

actix-webのおかげ


サーバの起動(データ読み込み)がめちゃくちゃ遅い

なぜかラズパイの方が早い
調べてみたらFailureのオブジェクト生成が原因だった

ok_or から ok_or_else にしたらめちゃくちゃ早くなった


最新100件、毎回ソートして取ってくるの無駄では?

tagをロードするときにgeotagの時間情報を使って上位100件のIDだけ載せるようにした
キャッシュしてもしなくても変わらないくらい早くなって泣いた

ラズパイだとキャッシュしない方が速い？？？

スレッドローカル変数とRefCellの組み合わせにしても変わらなかったので、RwLockのせいではない
キャッシュの探索をO(N)からO(1)に落としても変わらないので、探索時間の問題ではない
謎だけど、まあ何もしないで速いなら嬉しいしいいか……