ここ数日は何故か以前にErlangで実装したJSONライブラリを最適化するのにはまっていた。
いくつか知見も得られたので、試したことを何回かに分けてメモとして残しておく。
対象
JSONのデコード処理を題材とする。
やる気が続けば、エンコード処理の話も書く予定。
なお、コードを簡潔にするために今回の実装では「数値は非負の整数のみ」および「文字列はASCII文字コードの範囲内のみ」を扱うようにする。
シンプルな実装
まずは最適化前の基本形となるシンプルな実装のJSONデコード関数を載せておく。
json_decode_1.erl
-module(json_decode_1).
-export([decode/1]).
-type json_value() :: null | boolean() | json_number() |
json_string() | json_array() | json_object().
-type json_number() :: non_neg_integer().
-type json_string() :: binary().
-type json_array() :: [json_value()].
-type json_object() :: {[json_object_member()]}.
-type json_object_member() :: {json_string(), json_value()}.
%% @doc JSON文字列をデコードする
%%
%% 不正なJSON文字列が渡された場合は、badargエラーが送出される
-spec decode(binary()) -> json_value().
decode(Json) ->
{Value, _RestBin} = value(skip_whitespace(Json)),
Value.
-spec skip_whitespace(binary()) -> binary().
skip_whitespace(<<$ , Bin/binary>>) -> skip_whitespace(Bin);
skip_whitespace(<<$\t, Bin/binary>>) -> skip_whitespace(Bin);
skip_whitespace(<<$\r, Bin/binary>>) -> skip_whitespace(Bin);
skip_whitespace(<<$\n, Bin/binary>>) -> skip_whitespace(Bin);
skip_whitespace(Bin) -> Bin.
-spec value(binary()) -> {json_value(), binary()}.
value(<<"null", Bin/binary>>) -> {null, Bin};
value(<<"false", Bin/binary>>) -> {false, Bin};
value(<<"true", Bin/binary>>) -> {true, Bin};
value(<<$[, Bin/binary>>) -> array(skip_whitespace(Bin));
value(<<${, Bin/binary>>) -> object(skip_whitespace(Bin));
value(<<$", Bin/binary>>) -> string(Bin, "");
value(<<C, Bin/binary>>) when $0 =< C, C =< $9 -> number(C - $0, Bin);
value(Bin) -> error(badarg, [Bin]).
-spec array(binary()) -> {json_array(), binary()}.
array(<<$], Bin/binary>>) -> {[], Bin};
array(Bin) -> array(Bin, []).
-spec array(binary(), [json_value()]) -> {json_array(), binary()}.
array(Bin, Values) ->
{Value, Bin2} = value(Bin),
Values2 = [Value | Values],
case skip_whitespace(Bin2) of
<<$], Bin3/binary>> -> {lists:reverse(Values2), Bin3};
<<$,, Bin3/binary>> -> array(skip_whitespace(Bin3), Values2);
_ -> error(badarg, [Bin, Values])
end.
-spec object(binary()) -> {json_object(), binary()}.
object(<<$}, Bin/binary>>) -> {{[]}, Bin};
object(Bin) -> object(Bin, []).
-spec object(binary(), [json_object_member()]) -> {json_object(), binary()}.
object(<<$", Bin/binary>>, Members) ->
{Key, Bin2} = string(Bin, ""),
case skip_whitespace(Bin2) of
<<$:, Bin3/binary>> ->
{Value, Bin4} = value(skip_whitespace(Bin3)),
Members2 = [{Key, Value} | Members],
case skip_whitespace(Bin4) of
<<$}, Bin5/binary>> -> {{lists:reverse(Members2)}, Bin5};
<<$,, Bin5/binary>> -> object(skip_whitespace(Bin5), Members2);
_ -> error(badarg, [<<$", Bin/binary>>, Members])
end;
_ -> error(badarg, [<<$", Bin/binary>>, Members])
end;
object(Bin, Members) -> error(badarg, [Bin, Members]).
-spec string(binary(), string()) -> {json_string(), binary()}.
string(<<$", Bin/binary>>, Acc) -> {list_to_binary(lists:reverse(Acc)), Bin};
string(<<$\\, $", Bin/binary>>, Acc) -> string(Bin, [$" | Acc]);
string(<<$\\, $/, Bin/binary>>, Acc) -> string(Bin, [$/ | Acc]);
string(<<$\\, $\\, Bin/binary>>, Acc) -> string(Bin, [$\\ | Acc]);
string(<<$\\, $b, Bin/binary>>, Acc) -> string(Bin, [$\b | Acc]);
string(<<$\\, $f, Bin/binary>>, Acc) -> string(Bin, [$\f | Acc]);
string(<<$\\, $n, Bin/binary>>, Acc) -> string(Bin, [$\n | Acc]);
string(<<$\\, $r, Bin/binary>>, Acc) -> string(Bin, [$\r | Acc]);
string(<<$\\, $t, Bin/binary>>, Acc) -> string(Bin, [$\t | Acc]);
string(<<$\\, Bin/binary>>, Acc) -> error(badarg, [<<$\\, Bin/binary>>, Acc]);
string(<<0:1, C:7, Bin/binary>>, Acc) -> string(Bin, [C | Acc]);
string(Bin, Acc) -> error(badarg, [Bin, Acc]).
-spec number(json_number(), binary()) -> {json_number(), binary()}.
number(N, <<C, Bin/binary>>) when $0 =< C, C =< $9 -> number(N * 10 + C - $0, Bin);
number(N, Bin) -> {N, Bin}.
網羅的なテストを行っていないのでバグがあるかもしれないが、だいたいこのような感じのコードとなる。
コンパイルおよび実行してみる。
shell
$ erl
Erlang R16B03-1 (erts-5.10.4) [source] [64-bit] [smp:2:2] [async-threads:10] [hipe]
Eshell V5.10.4 (abort with ^G)
%% コンパイル
> c(json_decode_1).
{ok, json_decode_1}
%% デコード: null
> json_decode_1:decode(<<"null">>).
null
%% デコード: 文字列
> json_decode_1:decode(<<"\"abc\\t123\"">>).
<<"abc\t123">>
%% デコード: 配列
> json_decode_1:decode(<<"[1, 2, 3]">>).
[1,2,3]
%% デコード: オブジェクト
> json_decode_1:decode(<<"{\"key\": \"value\", \"array\": [1, 2, 3]}">>).
{[{<<"key">>,<<"value">>},{<<"array">>,[1,2,3]}]}
%% 入力値が不正な場合
> json_decode_1:decode(<<"[1, abc, 2]">>). % abc が不正
** exception error: bad argument
in function json_decode_1:value/1
called as json_decode_1:value(<<"abc, 2]">>)
in call from json_decode_1:array/2 (json_decode_1.erl, line 44)
in call from json_decode_1:decode/1 (json_decode_1.erl, line 18)
とりあえず動いている。
計時
後の最適化の効果を図るために、この実装の処理速度を計測しておく。
計測にはerl_json_testを利用させて貰った。 (commit: 7ae5a254943ce3e5d9e4d5eb9cd2e86b92ce8e83)
このテスト(計時方法)は、以下のようなJSON文字列に対してデコード関数を300回適用し、その平均処理時間を求める、という内容となっている。
(入力JSONは、500Bから122KBまでのサイズのバリエーションがある)
json:erl_json_test/priv/1x.json
{
"id": 1,
"jsonrpc": "2.0",
"total": 1,
"result": [
{
"id": 1,
"avatar": "images/user_1.png",
"age": 38,
"admin": false,
"name": "Феликс Швец",
"company": "Genland",
"phone": "+70955600298",
"email": "feliks@genland.com",
"registerDate": "Tue, 18 Aug 2009 14:09:40 GMT",
"friends": [
{
"id": 1,
"name": "Яков Олейник",
"phone": "+70950177368"
},
{
"id": 2,
"name": "Антон Коваленко",
"phone": "+70958920708"
},
{
"id": 3,
"name": "Леонид Приходько",
"phone": "+70958423612"
}
],
"field": "field value"
}
]
}
また、今回作成したjson_decode_1モジュール用に以下の内容のpatchを当てている。
erl_json_test/src/erl_json_test.erl.patch
diff --git src/erl_json_test.erl src/erl_json_test.erl
index a912a29..c5b634e 100644
--- src/erl_json_test.erl
+++ src/erl_json_test.erl
@@ -4,6 +4,8 @@
-define(NUM_TESTS, 300).
-define(PARSERS,
[{"jsonx", fun jsonx:encode/1, fun jsonx:decode/1},
+ %% json_decode_1モジュールをテスト対象に登録する
+ {"json_decode_1", fun (_) -> ok end, fun json_decode_1:decode/1},
{"yawsjson2", fun json2:encode/1, fun json2:decode/1},
{"jiffy", fun jiffy:encode/1, fun jiffy:decode/1},
{"jsonerl", fun jsonerl:encode/1, fun jsonerl:decode/1},
@@ -20,14 +22,20 @@
start() ->
JSONs = [begin
FullName = "priv/" ++ FileName,
{ok, File} = file:read_file(FullName),
- {Name, File}
+
+ %% 入力JSONに 負の整数 および 非ASCII文字 が入力に含まれないように変換する
+ File2 = [case C =:= $- orelse C >= 16#80 of
+ true -> $ ;
+ false -> C
+ end || <<C>> <= File],
+ {Name, list_to_binary(File2)}
end
|| {Name, FileName} <- ?TESTFILES],
_A = [ jsonx:encode(jsonx:decode(File)) || {_, File} <- JSONs],
_B = [ jiffy:encode(jiffy:decode(File)) || {_, File} <- JSONs],
_C = [ mochijson2:encode(mochijson2:decode(File)) || {_, File} <- JSONs],
_D = [ jsx:term_to_json(jsx:json_to_term(File)) || {_, File} <- JSONs],
+ _E = [ json_decode_1:decode(File) || {_, File} <- JSONs],
ResultsDeep = [[begin
T = {ParserName, TestName, size(JSON),
bench(EncFun, DecFun, JSON)},
計時結果
入力JSON(ファイル)の種類とサイズ:
| 1x.json | 3x.json | 9x.json | 27x.json | 81x.json | 243x.json |
|---|---|---|---|---|---|
| 0.5KB | 1.5KB | 4.5KB | 13.5KB | 40.5KB | 121.8KB |
各入力に対する平均デコード処理時間:
| 平均処理時間 | 1x.json | 3x.json | 9x.json | 27x.json | 81x.json | 243x.json |
|---|---|---|---|---|---|---|
| json_decode_1:decode/1 | 49μs | 153μs | 412μs | 1163μs | 4089μs | 11780μs |
この計時結果を基準に、次回以降で最適化を行い、その効果を比較してみる。