対象

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までのサイズのバリエーションがある)

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

この計時結果を基準に、次回以降で最適化を行い、その効果を比較してみる。