PHPでbtree

golangで書かれた google/btree をPHP7.1に移植してみた。
移植する事が目的ではなく google/btree のソースリーディングだったので、かなり雑な移植になっている。

github.com

ソースの移植 golang --> PHP

golangをPHP7.1に書き換えた訳だけど、配列周りでクラス定義の工夫が必要だったものの、ほぼそのまま書き換えるだけで済んだと思う。メソッドの中身を見ると分かるけどgolangとPHPはほぼ同じ行数になっていて、1対1でプログラムを書き換える事ができた。

↓golang

func (n *node) get(key Item) Item {
    i, found := n.items.find(key)
    if found {
        return n.items[i]
    } else if len(n.children) > 0 {
        return n.children[i].get(key)
    }
    return nil
}

↓PHP

<?php
public function get(Item $key) : ?Item
{
    list($i, $found) = $this->items->find($key);
    if($found){
        return $this->items[$i];
    }else if($this->children->count() > 0){
        return $this->children[$i]->get($key);
    }
    return null;
}

またgolangでは下記のように組み込み型にエイリアスやメソッド追加ができるため、PHPへの書き換えが難しく悩んだ箇所だった。PHPと比較して、golangにはこういうパフォーマンスに配慮した機能があるのが特徴的だなぁ、と書き換えながら感じた。

type Int int

// Less returns true if int(a) < int(b).
func (a Int) Less(b Item) bool {
    return a < b.(Int)
}

パフォーマンス

せっかくなのでパフォーマンス比較をしておこうと思う。
そもそも実用目的に移植した訳ではないのでパフォーマンスや可読性などは気にもしていなかった訳で、PHP版は1レコードあたり1インスタンスを生成する作りになっていたりと、パフォーマンスがでるはずはないのだけれど。

以下の通りbtreeにデータを流し込んだ時の速度を比較した。検索速度は比較するのが面倒なのでしていない。

↓golang（10万件データを投入）

$ time go run btree_mem.go --size=100000
   ....省略...
real    0m0.311s
user    0m0.301s
sys 0m0.118s

↓PHP（10万件データを投入）

$ time php btree_mem.php
   ....省略...
real    0m6.016s
user    0m5.851s
sys 0m0.145s

上記の通り処理時間も google/btree の圧勝だったし（0.3秒：6秒）、google/btree の方が圧倒的に省メモリだった。
※100万件の投入でも google/btree は数秒で終わったが、PHP版は数分間待っても戻ってこなかったので強制終了した

一応念押ししておくと、決してPHP言語そのもののパフォーマンスが悪いとか、golangが優れているとか、そういう事を言いたい訳ではない。
パフォーマンスがでないのはソースが悪いという事とと、そもそもこうした比較をする事が間違っていると思っている。※じゃあ比較すんなよ的な