Protocol Buffersは遅い - Blog by Sadayuki Furuhashi

Google の Protocol Buffers は、同技術と競合するバイナリシリアライズ形式である MessagePack と比べて、場合によっては 19倍以上遅く、シリアライズ後のデータサイズは 7倍以上になることがあります。平均的に見ると MessagePack の方が高速であり、高い性能が必要とされるなら Protocol Buffers より MessagePack を選択するべきです。

…とはいえどちらも非常に高速なので、実際にはそのAPIの違いで選んだ方が良い。Protocol Buffers と MessagePack は重視している点が異なり、使い勝手は大きく異なる。

Protocol Buffers とは何か

Protocol BuffersはGoogleが開発したバイナリエンコード手法で、以下のような要素が提供されます：

データフォーマットを記述するための言語（IDL）
IDLで記述されたフォーマットを実際に格納するためのバイナリベースのエンコード形式
IDLから各種言語（C++, Python, Java）用のシリアライザ・デシリアライザを生成するコードジェネレータ

Protocol Buffersのエンコード形式の実態は整数をキーとした連想配列です(エンコーディング − Protocol Buffers - ずっと君のターン)。未知のキーは単純に無視される仕組みになっているので、既存のプログラムとの互換性を保ちつつ後からフィールドを追加（データフォーマットを拡張）することができます。

MessagePack とは何か

MessagePackは効率を重視したデータ交換用のフォーマットで、言うなれば「速いJSON」です。シリアライズ・デシリアライズの速度は非常に高速で、シリアライズされたデータも非常に小さくなります。
その汎用的で動的なエンコード形式にもかかわらず、静的型付け言語であるC++からでも効率的に気持ちよく扱えるインターフェイスを提供しています。templateを巧みに利用することによって、外部の設定ファイルとコードジェネレータに頼ることなく型安全なデータフォーマットを定義できます。
今のところC, C++, Ruby用のバインディングが実装されています。

ベンチマーク

以下の４つのメッセージについて、シリアライズ・デシリアライズするのにかかった時間をそれぞれ計測しました。

Test1: 2つの符号無し整数
Test2: 2つの符号付き整数
Test3: 8KBのバイト列
Test4: Test1 + Test2 + Test3

Test1とTest2は2^23個、Test3とTest4は2^15個のメッセージをシリアライズするのにかかった時間を測定しています。そしてそれをもう一度デシリアライズするのにかかった時間を測定しました。

環境：

MessagePack 0.2.0
Protocol Buffers r74
g++ 4.3.2
linux 2.6.27 x86_64
CPU: AMD Athlon64 X2 5000+; Memory: DDR2 8GB

Test1: 符号無し整数×2

	時間	サイズ	Protocol Buffers比
Protocol Buffers 　シリアライズ	0.82 sec	40 MB	-
Protocol Buffers デシリアライズ	0.41 sec	40 MB	-
MessagePack 　シリアライズ	0.42 sec	24 MB	2.0倍速い・1.7倍小さい
MessagePack デシリアライズ	2.00 sec	24 MB	4.9倍遅い・1.7倍小さい

シリアライズは MessagePack の方が高速ですが、デシリアライズは Protocol Buffers の方が高速です。

Test2: 符号付き整数×2

	時間	サイズ	Protocol Buffers比
Protocol Buffers シリアライズ	1.46 sec	184 MB	-
Protocol Buffers デシリアライズ	0.76 sec	184 MB	-
MessagePack 　シリアライズ	0.56 sec	24 MB	2.6倍速い・7.7倍小さい
MessagePack デシリアライズ	2.03 sec	24 MB	2.7倍遅い・7.7倍小さい

符号無し整数の場合と同じく、シリアライズは MessagePack の方が高速ですが、デシリアライズは Protocol Buffers の方が高速です。
Protocol Buffers でのシリアライズ後のサイズが非常に大きくなってしまっています。一方 MessagePack は非常に効率的にシリアライズしていることが分かります。

Test3: 8KBのバイト列

	時間	サイズ	Protocol Buffers比
Protocol Buffers 　シリアライズ	1.28 sec	256 MB	-
Protocol Buffers デシリアライズ	0.083 sec	256 MB	-
MessagePack 　シリアライズ	0.35 sec	256 MB	3.7倍速い
MessagePack デシリアライズ	0.0048 sec	256 MB	17倍速い

シリアライズ・デシリアライズ共に MessagePack の方が高速です。デシリアライズに至っては17倍も高速です。

Test4: Test1 + Test2 + Test3

	時間	サイズ	Protocol Buffers比
Protocol Buffers 　シリアライズ	1.27 sec	257 MB	-
Protocol Buffers デシリアライズ	0.090 sec	257 MB	-
MessagePack 　シリアライズ	0.34 sec	256 MB	3.7倍速い
MessagePack デシリアライズ	0.027 sec	256 MB	3.3倍速い

Test4は一般的に利用されるネットワークプロトコルを想定したものです。Test4の１つのメッセージには整数が４個と、バイト列が１個入っています。
MessagePack の方が3倍以上高速です。

考察

サイズはさておき、速度だけを取り上げると、Protocol Buffers のバイト列のデシリアライズが遅すぎます。
ソースを読めば理由は単純で、Protocol Buffers はデシリアライズ時にデータをコピーしているためメッセージのサイズが大きければ大きいほどデシリアライズ速度が遅くなります。一方MessagePackはコピーせずにポインタを保持するので、バイト列のサイズが大きければ大きいほど相対的に高速になります。
ポインタを保持すると参照されているバッファの寿命管理に手間がかかるので、Protocol Buffersはコピーする戦略のとったのだと思われます。MessagePackのストリームデシリアライザはバッファリング機構までライブラリの中で実装し、オブジェクトの寿命をすべてメモリプールで管理することで、寿命管理の問題に対処しています。

しかしこれを言っては元も子もありませんが、バイト列をデシリアライズを除けばどちらも「十分高速」なので、どちらを採用しても性能は大差はないとないと思われます（MessagePackでTest4を１つデシリアライズする時間は 0.8マイクロ秒）。
どちらを使うかはむしろAPIの違いで選んだ方が良いと思います。どうも両者は思想が違うらしく、使い勝手は大きく異なります。

IDLがいいのか、コードとして書けた方がいいのか
IDLを覚えるか、templateを使いこなすか
コピーで持ち運ぶか、参照 + メモリプールで持ち運ぶか
動的型付けか否か

Protocol BuffersはIDLを使って必ず静的に型付けしてメッセージを扱いますが、MessagePackは基本的に動的型付けで、必要になったときに静的型に変換するというアーキテクチャになっています。（※整数のデシリアライズの遅さはここに原因がありそうです）
動的型の段階では型をチェックしないので、互換性を損なわずにプロトコルを拡張するのは容易です。
またメッセージ全体のうち一部分だけを静的型に変換し、他の部分は動的型のまま扱う、という処理ができます。これはRPCを実装するときに特に有効で、最初にメソッド名だけを静的型に変換し、メソッドを呼ぶときになって初めて引数の部分を静的型に変換するという処理が簡単に書けます。

最後に Protocol Buffers と MessagePack の両方で同じメッセージを定義したコードを載せておくので、比べてみてください。

付録

Protocol BuffersのIDL

package proto_protobuf;
option optimize_for = SPEED;

message Test1 {
    required uint32 a = 1;
    required uint32 b = 2;
}

message Test2 {
    required int32 a = 3;
    required int32 b = 4;
}

message Test3 {
    required string str = 5;
}

message Test4 {
    required Test1 test1 = 6;
    required Test2 test2 = 7;
    required Test3 test3 = 8;
}

MessagePackのプロトコル定義部分

namespace proto_msgpack {

using msgpack::define;
namespace t {
    using namespace msgpack::type;
}

struct Test1 : define< t::tuple<uint16_t,uint32_t> > {
    uint16_t& a() { return get<0>(); }
    uint32_t& b() { return get<1>(); }
};

struct Test2 : define< t::tuple<int16_t,int32_t> > {
    int16_t& a() { return get<0>(); }
    int32_t& b() { return get<1>(); }
};

struct Test3 : define<t::raw_ref> {
    t::raw_ref& ref() { return *this; }
    std::string str() { return std::string(ref().ptr, ref().size); }
};

struct Test4 : define< t::tuple<Test1,Test2,Test3> > {
    Test1& test1() { return get<0>(); }
    Test2& test2() { return get<1>(); }
    Test3& test3() { return get<2>(); }
};

}  // namespace proto_msgpack

ベンチマークプログラム

#include <string.h>
#include <sys/time.h>
#include <iostream>
#include <stdexcept>
#include <string>
#include <limits>

#include <msgpack.hpp>
#include "proto_msgpack.h"

#include <google/protobuf/io/coded_stream.h>
#include <google/protobuf/io/zero_copy_stream_impl.h>
#include "proto_protobuf.pb.h"
#include "proto_protobuf.pb.cc"


static const unsigned int TASK_STR_LEN = 1<<13;
static const char* TASK_STR_PTR;
static const unsigned int TEST1_NUM = 1<<23;
static const unsigned int TEST2_NUM = TEST1_NUM;
static const unsigned int TEST3_NUM = 1<<15;
static const unsigned int TEST4_NUM = 1<<15;


class simple_timer {
public:
    void reset() { gettimeofday(&m_timeval, NULL); }
    void show_stat(size_t bufsz)
    {
        struct timeval endtime;
        gettimeofday(&endtime, NULL);
        double sec = (endtime.tv_sec - m_timeval.tv_sec)
            + (double)(endtime.tv_usec - m_timeval.tv_usec) / 1000 / 1000;
        std::cout << sec << " sec" << std::endl;
        std::cout << (double(bufsz)/1024/1024) << " MB" << std::endl;
        std::cout << (bufsz/sec/1000/1000*8) << " Mbps" << std::endl;
    }
private:
    timeval m_timeval;
};


class sbuffer {
public:
    static const size_t INITIAL_ALLOCATION_SIZE = 8192;

    sbuffer() :
        m_free(INITIAL_ALLOCATION_SIZE),
        m_used(0),
        m_storage((char*)::malloc(INITIAL_ALLOCATION_SIZE))
    {
        if(!m_storage) { throw std::bad_alloc(); }
    }

    ~sbuffer()
    {
        free(m_storage);
    }

public:
    void write(const char* buf, size_t len)
    {
        if(m_free < len) {
            expand_buffer(len);
        }
        memcpy(m_storage + m_used, buf, len);
        m_used += len;
        m_free -= len;
    }

    char* data()
    {
        return m_storage;
    }

    size_t size() const
    {
        return m_used;
    }

    void release()
    {
        m_storage = NULL;
        m_free = 0;
        m_used = 0;
    }

private:
    void expand_buffer(size_t req)
    {
        size_t nsize;
        if(!m_storage) { nsize = INITIAL_ALLOCATION_SIZE; }
        else { nsize = (m_free + m_used) * 2; }
        while(nsize < m_used + req) { nsize *= 2; }
        char* tmp = (char*)realloc(m_storage, nsize);
        if(!tmp) { throw std::bad_alloc(); }
        m_storage = tmp;
        m_free = nsize - m_used;
    }

private:
    size_t m_free;
    size_t m_used;
    char* m_storage;

private:
    sbuffer(const sbuffer&);
};

template <typename Message>
void test_msgpack(Message target, unsigned int num)
{
    simple_timer timer;
    sbuffer buf;

    std::cout << "---- MessagePack serialize" << std::endl;
    timer.reset();
    {
        msgpack::packer<sbuffer> pk(buf);
        for(unsigned int i=0; i < num; ++i) {
            pk << target;
        }
    }
    timer.show_stat(buf.size());


    std::cout << "---- MessagePack deserialize" << std::endl;

    timer.reset();
    {
        msgpack::zone z;
        size_t off = 0;
        Message msg;
        for(unsigned int i=0; i < num; ++i) {
            msgpack::object obj = msgpack::unpack(buf.data(), buf.size(), z, &off);
            msg = obj.convert();
        }
    }
    timer.show_stat(buf.size());
}

template<typename Message>
static void test_protobuf(Message target, unsigned int num)
{
    simple_timer timer;
    std::string buf;

    std::cout << "-- Protocol Buffers serialize" << std::endl;
    timer.reset();
    {
        google::protobuf::io::StringOutputStream output(&buf);
        google::protobuf::io::CodedOutputStream encoder(&output);
        for(unsigned int i=0; i < num; ++i) {
            encoder.WriteVarint32(target.ByteSize());
            target.SerializeToCodedStream(&encoder);
        }
    }
    size_t sz = buf.size();
    timer.show_stat(sz);

    std::cout << "-- Protocol Buffers deserialize" << std::endl;
    timer.reset();
    {
        Message msg;
        google::protobuf::io::ArrayInputStream input(buf.data(), buf.size());
        google::protobuf::io::CodedInputStream decoder(&input);
        decoder.SetTotalBytesLimit(std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
        for(unsigned int i=0; i < num; ++i) {
            uint32_t limit = 0;
            decoder.ReadVarint32(&limit);
            int old = decoder.PushLimit(limit);
            msg.ParseFromCodedStream(&decoder);
            decoder.PopLimit(old);
        }
    }
    timer.show_stat(sz);
}


int main(int argc, char* argv[])
{
    char* str = (char*)malloc(TASK_STR_LEN);
    memset(str, 'a', TASK_STR_LEN);
    TASK_STR_PTR = str;

    std::cout << "\n==== Test1 (unsigned integer)" << std::endl;
    {
        proto_msgpack::Test1 msg;
        msg.a() = 1;
        msg.b() = 2;
        test_msgpack(msg, TEST1_NUM);
    }

    {
        proto_protobuf::Test1 msg;
        msg.set_a(1);
        msg.set_b(2);
        test_protobuf(msg, TEST1_NUM);
    }


    std::cout << "\n==== Test2 (signed integer)" << std::endl;
    {
        proto_msgpack::Test2 msg;
        msg.a() = -1;
        msg.b() = -2;
        test_msgpack(msg, TEST2_NUM);
    }

    {
        proto_protobuf::Test2 msg;
        msg.set_a(-1);
        msg.set_b(-2);
        test_protobuf(msg, TEST2_NUM);
    }
    

    std::cout << "\n==== Test3 (string)" << std::endl;
    {
        proto_msgpack::Test3 msg;
        msg.ref().ptr = TASK_STR_PTR;
        msg.ref().size = TASK_STR_LEN;
        test_msgpack(msg, TEST3_NUM);
    }

    {
        proto_protobuf::Test3 msg;
        msg.set_str( std::string(TASK_STR_PTR, TASK_STR_LEN) );
        test_protobuf(msg, TEST3_NUM);
    }
    

    std::cout << "\n==== Test4 (nested integer+string)" << std::endl;
    {
        proto_msgpack::Test4 msg;
        msg.test1().a() = 1;
        msg.test1().b() = 2;
        msg.test2().a() = -1;
        msg.test2().b() = -2;
        msg.test3().ref().ptr = TASK_STR_PTR;
        msg.test3().ref().size = TASK_STR_LEN;
        test_msgpack(msg, TEST4_NUM);
    }

    {
        proto_protobuf::Test4 msg;
        msg.mutable_test1()->set_a(1);
        msg.mutable_test1()->set_b(2);
        msg.mutable_test2()->set_a(-1);
        msg.mutable_test2()->set_b(-2);
        msg.mutable_test3()->set_str( std::string(TASK_STR_PTR, TASK_STR_LEN) );
        test_protobuf(msg, TEST4_NUM);
    }
    
    return 0;
}

Treasure Data MessagePack Embulk Fluentd @twitter