Skip to content

Instantly share code, notes, and snippets.

@equal-l2
Last active June 6, 2023 06:33
Show Gist options
  • Save equal-l2/afda48a947e9c3b6d0c9413a663fd812 to your computer and use it in GitHub Desktop.
Save equal-l2/afda48a947e9c3b6d0c9413a663fd812 to your computer and use it in GitHub Desktop.
情報科学実験I 超高性能化課題の進捗つぶやき

TL;DR

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

実装したもの一覧

元の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)に落としても変わらないので、探索時間の問題ではない
        • 謎だけど、まあ何もしないで速いなら嬉しいしいいか……
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment