読者です 読者をやめる 読者になる 読者になる

by shigemk2

当面は技術的なことしか書かない

HPACK の実装と解析 #http2study

HTTP

今日のお題

圧縮率 と 高速化

HPACKについて

  • 圧縮率がよくなるよ
  • おもったより圧縮率できないよ
  • もっと圧縮しないと…

みたいな悪☆循☆環

HPACK

  • 復号化は一意
  • でも符号化はの仕様はすごいふんわりしてる(とりあえず6種類に区分けしてみた)

悲報

ゆーてそんな圧縮できないアルゴリズムがある

高速化

ボトルネック

  • インデックスの探索
  • ハフマン復号化
  • ハフマン符号化

逆インデックス

  • ヘッダ名とヘッダ値からインデックスを見つける
  • (それすらなかったら)ヘッダ名からインデックスを見つける
  • 外側と内側の辞書両方で探索を行う

ハフマン符号

  • 符号化は高速O(1)だが復号化は低速O(log N)
  • 論文 Fast Prefix Code Processing
  • ビット列の連結は遅い

まとめ

  • インデックスを使えば高い圧縮率を誇る
  • リファレンスセットは結構複雑なのでいくばくか削るべき
  • ハフマン符号 圧縮率はそれなり