タグ

関連タグで絞り込む (1)

タグの絞り込みを解除

algorithmとdbmに関するlizyのブックマーク (2)

  • mixi Engineers’ Blog » Inside Tokyo Cabinet その五

    先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです(その時の資料)。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。 なぜdynamic hashingを使わないか Brianさん達とTCの実装についても少し議論したのですが、その際にdynamic hashingをなぜ使わないのかと問われました。その背景として、TCやQDBMではハッシュのバケット数(=格納するレコード数を予測してその数倍に設定すべき値)をデータベース作成時に指定しなければならないという問題があります。バケット数が大きすぎると空間効率が劣化し、小さすぎると時間効率が劣化するというトレード

    mixi Engineers’ Blog » Inside Tokyo Cabinet その五
  • mixi Engineers’ Blog » Inside Tokyo Cabinet その弐

    予定を立てた途端にやりたくなくなる症候群に堪えて連載を続けるmikioです(こんな私でもエアーマンくらいは倒せます)。前回はDBMの基について説明しましたが、それを忠実に実装しても実際には使いものにはならないことにも触れました。今回は、実用的なDBMに進化すべく、Tokyo Cabinet(およびその前身のQDBM)で考えた工夫についてお話します。 ハッシュ関数についてもう少し 前回の記事に関して、「ハッシュ関数はビットシフト使って実装した方が早いよ」という旨のお便りをいただきました(ありがとうございます)。まさにその通りで、乗算命令(ここではimull)より左シフト命令(ここではsall)の方が速いみたいです(Intelの資料によると、mulが15から18で、salが4とのこと)。しかし、DBMの場合はファイルI/Oにかかる時間が支配的になるというのが重要な点です。したがって、ハッシュ

    mixi Engineers’ Blog » Inside Tokyo Cabinet その弐
  • 1