Reverse reader for HUGE files

なんとなく StackOverflow を読んでいると「大きいベクタ/リストを reverse したいけどパフォーマンスが気になるしどうしたらいい?」みたいな質問をたまに見かける。

で、その大きいベクタ/リストって何処からくるんだって考えたときに、ひとつは巨大なファイルだろうと思う。ログファイルとか。 ログファイルみたいなものは特に下の方が最新になるので、一番最後の行から走査したくなると思うんだけど、次のようなコードを書くのは流石に気が引ける。

(with-open [r (io/reader huge-file)]
    (take 10 (filter warn-log? (reverse (line-seq r)))))

なんでかというと、折角 line-seq で lazy になってるのに、それを reverse で適用したタイミングで lazy じゃなくなってしまうから。出来る限り lazy のままにしたいと考えると、逆から読み込むような reader が欲しくなってくる。ので書いた。

ayato_p/rr

README 読んでもらえれば使い方はわかると思うけど、逆から読み込む速度を測ると以下のような結果が出る。

(c/bench (last-line-via-stdio))
;; Evaluation count : 300 in 60 samples of 5 calls.
;;              Execution time mean : 209.071375 ms
;;     Execution time std-deviation : 2.580759 ms
;;    Execution time lower quantile : 205.964662 ms ( 2.5%)
;;    Execution time upper quantile : 214.501153 ms (97.5%)
;;                    Overhead used : 9.982297 ns

;; Found 2 outliers in 60 samples (3.3333 %)
;;      low-severe   2 (3.3333 %)
;;  Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

(c/bench (last-line-via-rr))
;; Evaluation count : 7811880 in 60 samples of 130198 calls.
;;              Execution time mean : 7.842190 µs
;;     Execution time std-deviation : 68.214523 ns
;;    Execution time lower quantile : 7.743285 µs ( 2.5%)
;;    Execution time upper quantile : 8.001377 µs (97.5%)
;;                    Overhead used : 9.982297 ns

;; Found 2 outliers in 60 samples (3.3333 %)
;;      low-severe   2 (3.3333 %)
;;  Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

その差は歴然というか、だいぶ早い気がする。まぁそんな感じです。 もうちょっと色々足したい気もするけど、とりあえずこれだけ出来れば満足なのでいいかなと。