Hatena::ブログ(Diary)

あどけない話

2014-04-15

複数のGHCを共存させる

GHC 7.8.1 がリリースされ、type family がうまく扱えない問題が発覚したため、すぐに GHC 7.8.2 がリリースされました。このおかげで Yesod が、うまくビルドできるようになりました。しばらくして、GHC 7.8.3 もリリースされる気配があります。また、一ヶ月を目処に Haskell Platform 2014.2 が出るようです。

こうなると、GHC をうまく共存させてくれる Haskell Platform 2014.2 のリリースを待とうかと思うかもしれませんが、そんな必要はありません。GHC 自体に複数のバージョンと共存できる仕組みがあるからです。

GHC 7.8.2 を試したい人は、気軽にインストールしましょう。GHC 7.8.3 や Haskell Platform 2014.2 がリリースされたら、GHC 7.8.2 は消せばいいのです。ここでは、後で消しやすくするためのコツを紹介します。対象は、Unix 系の OS です。Windows のことは、誰かに任せます。

インストール

GHC 7.8.2のダウンロードサイトから、必要なバイナリを取ってきて展開します。以下、Mac の例:

% wget http://www.haskell.org/ghc/dist/7.8.2/ghc-7.8.2-x86_64-apple-darwin-mavericks.tar.xz
% tar zxvf ghc-7.8.2-x86_64-apple-darwin-mavericks.tar.xz
% cd ghc-7.8.2

ここで、単に configure を実行すると、/usr/local の下にインストールする設定になります。これでだと、インストールするファイルが散らばって、後から消しにくくなります。そこで、例えば /usr/local/ghc-7.8 というディレクトリの下にインストールするように決めます。

% ./configure --prefix=/usr/local/ghc-7.8

次に /usr/local/ghc-7.8 というディレクトリを作ります。僕は、このディレクトリを自分の所有にしています。root の所有でもいいですが、make install するときに sudo を使わないといけません。おかしなことは起りませんが、不安な人は自分の権限でインストールするのがいいでしょう。GHC 自体が自分の所有になっていても、GHC を壊した経験は僕にはありません。

% sudo mkdir /usr/local/ghc-7.8
% sudo chown あなたのアカウント /usr/local/ghc-7.8
% sudo make install

PATH に /usr/local/ghc-7.8/bin を追加すれば、GHC 7.8.2 のインストールは完了です。

削除

削除したくなったら、3つのディレクトを消します。

~/.ghc や ~/.cabal 自体は消してはいけません。こうすれば、~/.cabal/bin 以下のコマンドは残ります。コマンドは、静的リンクされているので、引き続き使えます。ただし、alex や happy のように lib に設定ファイルを置いているコマンドはうごかなくなるので、インストールし直す必要があります。

応用

この方法は、何も GHC 本体を消したい場合だけではなく、cabal でインストールしたユーザライブラリがおかしくなったときにも使えます。~/.ghc と ~/.cabal 以下のサブディレクトリを消せば、一から世界を構築できるようになります。

2014-03-01

RSSリーダ BazQux と DNS キャッシュ

BazQux(バズクックス)は、Google Reader代替として密かに注目されている RSS リーダです。実装と運用を一人でやっている Vladimir Shabanov さんによると、BazQux のウリは、

  • 高速である
  • ブログのコメントも表示できる
  • 複数のビューがある
  • モバイルに対応している

などらしいです。

BazQux のフロントエンドは、Ur/Web で記述されたコードから生成された JavaScript、バックエンドは Haskell だそうです。高速なのは、Haskell のおかげであると Vladimir さんは言っています。我々が開発している HTTP エンジンの Warp も使われているそうです。

現在、僕は Haskell 用の HTTP/2 ライブラリの作成に取り組んでおり、必要な技術を調べている過程で、redditでの議論のことを思い出しました。今回、よくよく読んでみると、僕が実装している DNS ライブラリを使っているが、ADNS (のラッパーである hsdns)と比べて安定しているものの、ドメインを検索できないことがあると書かれていました。

僕がDNSライブラリを書いたのは、不安定なADNSを見限ったためなので、安定しているのは当然として、ドメインの検索率が悪い点は気になりました。そこで、Vladimir さんにメールを書いたところ、すぐに返事が返ってきました。彼のコードと実際のドメインリストを見せてもらったところ、

  • DNSライブラリの使い方が間違っている
  • MVarを多用していて性能が悪そう (Vladimir は、そこはボトルネックではないと言っている)
  • HashMapで持っているキャッシュを定期的に枝刈りしてないのでメモリをたくさん使いそう

ということが分かりました。

奮い立ってしまった僕は、使ってもらえるか分かりませんでしたが、おもむろに concurrent-dns-cache というライブラリを作り始めました。設計のポイントは以下の通り。

  • DNSライブラリを正しく使う
  • セマフォを STM で実装する
    • 高並行な状況では MVar よりよいはず
  • キャッシュは Priority Search Queue で持つ
    • 優先度に指定した時刻で枝刈りできる。もちろん、ドメイン名で検索もできる。
  • ドメイン名を ShortByteString として扱う
    • ByteString は pinned オブジェクトなので、メモリが断片化する。このため Vladimir さんは Text を使っていたが、ShortByteString の方がメモり利用効率がよい
  • 高速な検索を実現するためにキーの第一要素としてハッシュ値を持つ

concurrent-dns-cache は、めでたく BazQux に採用され、以前よりもドメインの検索率が高く、少ないメモリで安定して動いているようです。高性能で高並列で安定しているネットワークコードをすばやく実装できるのが Haskell のよい点の一つですね。

今回の経験は HTTP/2 の実装にも役立ちそうでよかったし、現場の人と議論できたのはのは楽しい経験でした。

今少し悩んでいることは2つ。

一つ目:キーの定義は以下のようになっています。

type Hash = Int

data Key = Key !Hash            -- making lookup faster
               !ShortByteString -- avoiding memory fragmentation
               -- Haskell 2010 says: Derived comparisons always
               -- traverse constructors from left to right.
               deriving (Eq,Ord,Show)

実際のキーをハッシュ値と一緒にくるむことで、(MapからHashMapへの変更とは違って)コンテナの構造を変えることなく、検索速度を高速にします。みんな使いたいとは思いますが、ライブラリにするには小さすぎるので、どうしようかなぁという感じです。まだベンチマークを取っていないのですが、本当に有用そうなら小さくてもライブラリにするかもしれません。

二つ目:Priority Search Queue の本家本元のライブラリである PSQueueには、ある優先順位以上の要素を取り出す API はあるのですが、要素を取りさらった木を返す API はありません。そこで、僕は GHCソースコードから PSQ.hs をコピーしました。PSQueue の API はあまりよくないし、PSQ.hs はキーと優先順位の型が固定です。両者の API はまっく違うので、PSQueue を PSQ.hs で置き換えてバージョンアップするということもできません。

そもそも、Priority Queue がヒープの別名であることを知らない人は多く混乱の元なので、search-heap という名の別ライブラリでリリースしようかなぁ、どうしようかなぁ、という感じです。

2014-02-06

Real World Haskell の古いところ

Real World Haskell の内容が古くなってきたので、どこが古いかとか、それに変わる新しいものは何とか、まとめたいと思う。

1章 始めましょう

今でも通用する。

2章 型と関数

今でも通用する。

3章 型を定義し、関数単純化する

今でも通用する。

4章 関数プログラミング

ghc に --make オプションはもう不要。

5章 ライブラリを書く

5.14節では、"runghc Setup build" のように Setup.hs を実行しているが、現在では "cabal" コマンドを使うのが一般的だ。

% cabal configure
% cabal build
% cabal install

なお、以前よく起っていたライブラリの依存地獄は、cabal が sandbox をサポートしたことにより解決している。使い方は、@ma0e さんのブログを参照。

6章 型クラスを使う

6.11節の NoMonomorphismRestriction は、GHC 7.8 からはデフォルトとなっているので、指定しなくてよい。

7章 入出力

今でも通用する。

8章 効率的なファイル処理、正規表現、ファイル名マッチング

今でも通用する。

9章 入出力事例研究

9.9節は読まずに、conduitfilesystem-conduitライブラリを理解する方がよいと思われる。

9.10節のレイアウトスタイルよりも、Johan のレイアウトスタイルのほうがいいだろう。

10章 コード事例研究

今でも通用する。

11章 テストと品質保証

QuickCheck はバージョンが1から2になった。だいたい今でも通用でするが、generate 関数はなくなった。また、Test.Quickcheck.Batch モジュールもなくなった。テストを一括処理したい場合は、Haskellの単体テスト最前線を参照のこと。

12章 バーコード認識

僕試した限りでは、この章のコードはちゃんと動かない。バーコードのコードはスルーして、配列、リスト内包表記、および Data.Map を勉強するのがよい。

13章 データ構造

今でも通用でする。

差分リストを理解したら、ByteString を効率よく連結する blaze-builder も勉強しよう。

14章 モナド

今でも通用でする。

15章 モナドを使ったプログラミング

  • liftM は忘れて <$> を使う
  • ap は忘れて <*> を使う
  • MonadPlus は忘れて Alternative を使う
    • mplus は忘れて <|> を使う
    • mzero は忘れて empty を使う

15.8節では、型クラスが使われているが、最近では Free モナドや Operational モナドの方がいいかもしれない。

16章 Parsec を使う

Text.ParserCombinators.Parsec は使わない。代わりに、

import Text.Parsec

とする。入力の型が、String、ByteString、Text から選べる。たとえば String の場合は、以下も import。

import Text.Parsec.String

Applicative スタイルを導入した後に、liftA2 などを使っているのは、修正ミスだと思われる。(Bryan は RWH 執筆時に Applicative スタイルを教えてもらったと思われる。)

17章 CとのインターフェイスFFI

今でも通用する。

18章 モナド変換子

@objectxplosive さん、@khibinoさんとの議論から:mtl が依存している transformersを勉強しよう。これには MaybeT が定義されている。

19章 エラー処理

この章は読まなくてよい。以下を読もう。

20章 Haskellのシステムプログラミング

時間に関するライブラリについては、以下を参照。

21章 データベースを使う

@khibinoさんより:今でも通用する。

22章 規模の大きい例

http-clientxml-conduit ライブラリを使う方がいいと思われる。

23章 gtk2hsを使ったGUIプログラミング

@ma0eさんのブログの後半を参照。

24章 並行マルチコアプログラミング

素直に Parallel and Concurrent Programming in Haskellを読む方がよい。なお、この本は将来翻訳される予定。

25章 プロファイリング最適化

@ma0eさんのブログの前半を参照。

26章 高度なライブラリ設計

ST モナドだけ読めばよい。

27章 ソケットと syslog

今では、Network.Socket ではなく、Network.Socket.ByteString を使うのが普通。

sClose の代わりに Network.Socket.close を使おう。

28章 ソフトウェアトランザクショナル・メモリ

今でも通用するが、Parallel and Concurrent Programming in Haskell を読む方がよい。

2014-01-29

Implementation and Analysis of HPACK 05

HPACK 05 has following compression mechanisms:

Index
By sharing learning dictionary of headers, a header can be represented as a small integer.
Reference set
By comparing a set of the previous indices and that of the current indices, difference can be calculated.
Huffman code
Strings (header names and header values) themselves can be shorten.

Since "reference set" depends on "index", we can consider 6 kinds of HPACK encoding. For convenience, I give a name for each.

IndexRefsetHuffman
Naive---
NaiveH--X
LinearX--
LinearHX-X
DiffXX-
DiffHXXX

To implement Naive and Linear, an HPACK encoder first sends index 0 to clear reference set and encodes the headers in order (see Appendix in detail). The algorithm for Diff was posted to ietf-http-wg ML by Tsujii, the author of "nghttp2". The last "H" means using huffman encoding.

Note that the order of headers is kept in Naive and Linear while not in Diff.

I implemented the 6 encodings above in my implementation, the http2 library in Haskell. We Japanese community provides test cases for HPACK. My http2 library passed the all inter-operability tests.

As you can see, we provides 31 stories where 21 stories for HTTP request and 10 stories for HTTP response. Of course, each story targets the same :authority in it.

Correction: it appeared that multiple :authority values are mixed together. We should make another experiment with better input.

We can also use these test cases to calculate compression ratio. Compression ration is calculated by dividing the length of result representation by that of header set.

Here is the results.

I confirmed the following things.

  • The "hpack" library in Go uses NaiveH. I verified that my NaiveH encoding produces the same results as it.
  • "nghttp2" uses DiffH. I verified that my DiffH encoding produces the same results as it.

Here is a chart to visualize the results:

f:id:kazu-yamamoto:20140130125413p:image

As you can see, Diff(H) has almost the same compression ratio as Linear(H). My calculation leads to the following conclusion.

  • Diff(H) saves only 1.57 byte per HEADERS frame in average against Linear(H).
  • Huffman encoding saves 31.36 bytes per HEADERS frame in average against non-huffman.

So, I would suggest the designers of HPACK to remove reference set. This has the following advantages:

  • Implementation of HPACK encoder becomes much easier.
  • Inter-operability is improved.
  • The order of headers are always kept.
  • The compression ratio does not go worse.

Implementation notes

I first implemented HPACK with simple data structures and algorithms. Profiling tells me there were three bottlenecks:

  1. Converting a header to an index in HPACK encoding.
  2. Converting bit sequence to a character in Huffman decoding.
  3. Concatenating bit sequences in Huffman encoding.

Linear search is slow for the purpose of 1). To solve this problem, I created a reverse index. To avoid hash DOS attacks, I used search trees to implement it. Since we need to find either an index for a pair of header key and header value OR an index for a header key, search trees should be nested. When the outer search tree is looked up with a header key, an inner search tree cab be obtained if exists. Then the inner search tree is looked up with a header value.

My choice is as follows:

Bit-by-bit traversing on a binary tree is slow for the purpose of 2). So, I adopted Fast Prefix Code Processing. I prepared state transition tables for 4 bits. The reason why I chose 4 bits, not 8 bits, is that 4 bits can ensure one character is generated at most.

To solve problem 3, I prepared N shifted bytes for bit sequences in advance where N is from 0 to 7. Concatenation can be done just by copying bytes and ORed a seam point if necessary.

Conclusion

  • Index
    • It has good compression ratio.
    • Fast implementation is possible.
  • Reference set
    • It has poor compression ratio.
    • It should be removed from HPACK.
  • Huffman encoding
    • Its compression ratio is so so.
    • Fast implementation is possible.

Appendix

To see the difference between Naive and Linear, let's see examples. Suppose that the first header set is as follows:

key1: value1
key2: value2
key3: value3

Both Naive and Linear encodes this to:

Indexed 0
Literal NotAdd (Lit "key1") "value1"
Literal NotAdd (Lit "key2") "value2"
Literal NotAdd (Lit "key3") "value3"

Then suppose that the next header set is as follows:

key1: value1
key2: value2
key3: value3'

Naive encodes this to:

Indexed 0
Literal NotAdd (Lit "key1") "value1"
Literal NotAdd (Lit "key2") "value2"
Literal NotAdd (Lit "key3") "value3'"

Linear encodes this to:

Indexed 0
Indexed 3
Indexed 2
Literal Add (Idx 1) "value3'"

2014-01-14

ByteString あれこれ

Haskell で高速なプログラムを書くには ByteString の深い知識が必要となる。鍵となるのは、Data.ByteString.Internal というモジュールである。このモジュールは公開されているが、ドキュメントは隠されているので、詳しく知るためにはソースを読まないといけない。

定義

ByteString の定義は以下の通り。

data ByteString = PS {-# UNPACK #-} !(ForeignPtr Word8) -- payload
                     {-# UNPACK #-} !Int                -- offset
                     {-# UNPACK #-} !Int                -- length

なぜ構成子が BS ではなく、PS なのだろう? (追記:元々 PackedString という型名だったからと @ma0e さんに教えて頂きました。)

ForeignPtr Word8 は、いわゆるバッファーを指してる。このバッファーは複数の ByteString から共有される。バッファー中のどこを使っているかを示すために、メタ情報として offset と length がある。

Haskell ポインタープログラミングを読んだ人なら、バッファーを読み書きする方法は分かるだろう。以下のようにするのが定石である。

import Data.ByteString.Internal (ByteString(..))
import Foreign.ForeignPtr (withForeignPtr)
import Foreign.Ptr (plusPtr)

foo :: ByteString -> IO 適当な型
foo (PS fptr off len) = withForeignPtr fptr $ \ptr -> do
    let beg = ptr `plusPtr` off
        end = beg `plusPtr` len
    -- beg から end の間(endは含まない)を読み書きする

書き換えてバッファー溢れを起こさないのは自己責任だし、書き換えるバッファーが共有されてないことを保証するのも自己責任である。

大きさの分かっている ByteString を作る

バッファー操作とともに ByteString を作りたい場合、あらかじめできあがる ByteString の大きさが分かっているなら、create が使える。

create :: Int -> (Ptr Word8 -> IO ()) -> IO ByteString
create l f = do
    fp <- mallocByteString l
    withForeignPtr fp $ \p -> f p
    return $! PS fp 0 l

Int は、バッファーのバイト数である。Ptr Word8 -> IO () という関数で、バッファー全体(オフセット 0 から指定したバイト数)を初期化すればよい。

副作用がないと確信できるなら、unsafeCreate を使おう。

unsafeCreate :: Int -> (Ptr Word8 -> IO ()) -> ByteString
unsafeCreate l f = unsafeDupablePerformIO (create l f)

大きさが分からない ByteString を作る

できあがる ByteString の大きさが分からない場合、どうすればいいだろうか? 3つぐらい方法がある。

createAndTrim

一つ目は createAndTrim を使う方法だ。十分な大きさのバッファーを用意してデータを作り、大きさが分かった時点で、新しい ByteString を作る。渡す関数は、できあがったデータのバイト数を返さないといけない。

以下のソースコードが示すように、はじめに用意したバッファーぴったりのデータができたときに限り、コピーが発生しない。

createAndTrim :: Int -> (Ptr Word8 -> IO Int) -> IO ByteString
createAndTrim l f = do
    fp <- mallocByteString l
    withForeignPtr fp $ \p -> do
        l' <- f p
        if assert (l' <= l) $ l' >= l
            then return $! PS fp 0 l
            else create l' $ \p' -> memcpy p' p l'
リスト

二つ目は中間データとしてリストを作る方法。たとえば、[Word8]というリストを作っておいて、pack すればいい。

[Word8]を作る際は、リストが後ろに伸びて行くだろう。逆順のリストを作って reverse してもよいが、差分リストを使う手もある。いずれの場合も、作成中に大きさを管理できるかもしれない。

[Word8]の大きさがあらかじめ分かっているなら、pack を使うよりも、create して自前でリストの内容をバッファーへコピーする方がいいだろう。

Builder を使う

三つ目は、Builder を使う方法である。

二つ目の方法は、単一の Word8 という型だけを使う場合に有効であった。一方、Builder は、さまざまな型のデータから作れる。

詳しい理由は省略するが、

を使うといいだろう。

Builder差分リストの一種と言われているが、それは誤解を招きやすい。Builder とは、与えられたデータをバッファーへコピーする関数であり、Builder をくっつけることは、関数合成をすることである。この関数は継続を用いて実装されているので、最終的に走らせた場合、「左から右へ」バファーのコピー関数が走る。(差分リストのように、右結合になる訳ではない。)

Builder には、最終的な大きさを予測できないという問題がある。だから、以下のように使われる。

  • バッファーを1つ用いて、出力をする。すなわち、バッファーが溢れそうになると書き出し、そのバッファーを再利用することを繰り返す。具体的には、blaze-builder では toByteStringIO を使えばよい。
  • バッファーが溢れたそうになったら、新たなバッファーを用意して利用する。Strict な ByteString が複数できることになり、それはすなわち Lazy ByteString である。具体的には、blze-builder では toLazyByteString を使う。

mallocByteString

create などで使われている mallocByteString を調べてみよう。

mallocByteString :: Int -> IO (ForeignPtr a)
mallocByteString = mallocPlainForeignPtrBytes

mallocPlainForeignPtrBytes は、GHC.GHC.ForeignPtr にある。

mallocPlainForeignPtrBytes :: Int -> IO (ForeignPtr a)
mallocPlainForeignPtrBytes (I# size) = IO $ \s ->
    case newPinnedByteArray# size s      of { (# s', mbarr# #) ->
       (# s', ForeignPtr (byteArrayContents# (unsafeCoerce# mbarr#))
                         (PlainPtr mbarr#) #)
     }

newPinnedByteArray# は、その名が示すようにピン止めされたデータを割り当てる。コピーCGで動かされることのないデータである。つまり、ByteString のバッファーは常に固定されているので、GC を気にせずに読み書きしてよい。

newPinnedByteArray# は、rts/PrimOps.cmm:stg_newPinnedByteArrayzh のことであり、allocatePinned を呼んでいる。

allocatePinned は rts/sm/Storage.c にあり、以下のように C で実装されている。

StgPtr
allocatePinned (Capability *cap, W_ n)
{
    StgPtr p;
    bdescr *bd;

    // If the request is for a large object, then allocate()
    // will give us a pinned object anyway.
    if (n >= LARGE_OBJECT_THRESHOLD/sizeof(W_)) {
        p = allocate(cap, n);
        Bdescr(p)->flags |= BF_PINNED;
        return p;
    }
    ...

LARGE_OBJECT_THRESHOLD/sizeof(W_) 以上の大きさの場合、allocate を呼び出すことが分かる。allocate は同じファイルに存在し、コードを読むと必ずロックするのが分かる。

StgPtr
allocate (Capability *cap, W_ n) {
...
        ACQUIRE_SM_LOCK
        bd = allocGroup(req_blocks);
        dbl_link_onto(bd, &g0->large_objects);
        g0->n_large_blocks += bd->blocks; // might be larger than req_blocks
        g0->n_new_large_words += n;
        RELEASE_SM_LOCK;
...

つまり、ある大きさ以上のバッファーを持つ ByteString を作成する場合は、必ずグローバルなロックが利用されるのだ。このことは、特に +RTS -N<x> を指定して複数のコアを使うようにしたアプリケーションの性能に著しく影響を及ぼす。

定義をたくさん調べて LARGE_OBJECT_THRESHOLD/sizeof(W_) を計算してみると、以下のようになる。

注:Simon Marlow 先生の指摘により数値を修正。

  • 32ビット環境では 3276 バイト(819ワード)以上の ByteString を作成する場合グローバルロックが使われる
  • 64ビット環境では 3272 バイト(409ワード)以上の ByteString を作成する場合グローバルロックが使われる

大きな ByteString の作成には慎重になること。createAndTrim に 4,096 を渡したのに、できあがった ByteString の大きさは 3,300 なんてのは最悪だ。そんな関数の例としては、Network.Socket.ByteString.recv がある。