Optimize couch_util:to_hex/1
When profiling [1] a cluster acting as a replication source, noticed a lot of
time spent in `couch_util:to_hex/1`. That function is used to emit revision ids
amongst other things. When processing a million documents with a 1000 revisions
each, it ends up in the hotpath, so to speak.
Remembering that in Erlang/OTP 24 there is a new `binary:encode_hex/1` [2]
function, decided to benchmark ours vs the OTP implementation. It turns ours is
slower [3] so let's try to use the OTP one.
One difference from the OTP's version is ours emits lower case hex letters,
while the OTP one emits upper case ones. That's why the lookup table had all
the "A"s replaced with "a"s, "B"s with "b"s, etc.
As a bonus, replaced a few calls to `couch_util:to_hex/1` wrapped in `?l2b/1`
or `list_to_binary/1` with just a single call to `couch_util:to_hex_bin/1`.
Existing `couch_util:to_hex/1` version, returning a list ,was left as is and
just calls `to_hex_bin/1` internally and converts the result to a list.
This altered the peak memory usage for the key tree stemming test so had to
alter the magic constants there a bit to avoid flakiness.
[1]
```
> ... eprof:analyze(total,[{sort, time}, {filter, [{time, 1000}, {calls, 100}]}]).
FUNCTION CALLS % TIME [uS / CALLS]
-------- ----- ------- ---- [----------]
...
couch_doc:revid_to_str/1 1165641 1.71 402860 [ 0.35]
couch_key_tree:get_key_leafs_simple/4 1304102 1.85 435700 [ 0.33]
erlang:list_to_integer/2 873172 2.00 471140 [ 0.54]
gen_server:loop/7 62209 2.11 496932 [ 7.99]
couch_key_tree:map_simple/3 1829235 2.36 554429 [ 0.30]
couch_util:nibble_to_hex/1 37334650 16.67 3917127 [ 0.10]
couch_util:to_hex/1 19834192 34.37 8077050 [ 0.41]
--------------------------------------------------------------- -------- ------- -------- [----------]
Total: 91072005 100.00% 23503072 [ 0.26]
```
[2] https://www.erlang.org/doc/man/binary.html#encode_hex-1
[3]
```
% ~/src/erlperf/erlperf 'hex:to_hex1(<<210,90,95,232,68,185,66,248,160,33,184,103,181,221,158,96>>).' 'hex:to_hex3(<<210,90,95,232,68,185,66,248,160,33,184,103,181,221,158,96>>).'
Code || QPS Time Rel
hex:to_hex3(<<210,90,95,232,68,185,66,248,160,33,184,103,181,221,158,96>>). 1 2746 Ki 364 ns 100%
hex:to_hex1(<<210,90,95,232,68,185,66,248,160,33,184,103,181,221,158,96>>). 1 1593 Ki 627 ns 58%
```
(`to_hex1/1` is the existing version and `to_hex3/1` is the OTP version).
diff --git a/src/couch/src/couch_doc.erl b/src/couch/src/couch_doc.erl
index 5d44e45..95b1c8b 100644
--- a/src/couch/src/couch_doc.erl
+++ b/src/couch/src/couch_doc.erl
@@ -74,7 +74,7 @@
end.
revid_to_str(RevId) when size(RevId) =:= 16 ->
- ?l2b(couch_util:to_hex(RevId));
+ couch_util:to_hex_bin(RevId);
revid_to_str(RevId) ->
RevId.
diff --git a/src/couch/src/couch_passwords.erl b/src/couch/src/couch_passwords.erl
index 828d2f6..b891046 100644
--- a/src/couch/src/couch_passwords.erl
+++ b/src/couch/src/couch_passwords.erl
@@ -23,7 +23,7 @@
%% legacy scheme, not used for new passwords.
-spec simple(binary(), binary()) -> binary().
simple(Password, Salt) when is_binary(Password), is_binary(Salt) ->
- ?l2b(couch_util:to_hex(crypto:hash(sha, <<Password/binary, Salt/binary>>)));
+ couch_util:to_hex_bin(crypto:hash(sha, <<Password/binary, Salt/binary>>));
simple(Password, Salt) when is_binary(Salt) ->
Msg = io_lib:format("Password value of '~p' is invalid.", [Password]),
throw({forbidden, Msg});
@@ -116,7 +116,7 @@
L = ceiling(DerivedLength / ?SHA1_OUTPUT_LENGTH),
<<Bin:DerivedLength/binary, _/binary>> =
iolist_to_binary(pbkdf2(Password, Salt, Iterations, L, 1, [])),
- {ok, ?l2b(couch_util:to_hex(Bin))}.
+ {ok, couch_util:to_hex_bin(Bin)}.
-spec pbkdf2(binary(), binary(), integer(), integer(), integer(), iolist()) ->
iolist().
diff --git a/src/couch/src/couch_util.erl b/src/couch/src/couch_util.erl
index d71fc05..84691d1 100644
--- a/src/couch/src/couch_util.erl
+++ b/src/couch/src/couch_util.erl
@@ -17,7 +17,7 @@
-export([rand32/0, implode/2]).
-export([abs_pathname/1, abs_pathname/2, trim/1, drop_dot_couch_ext/1]).
-export([encodeBase64Url/1, decodeBase64Url/1]).
--export([validate_utf8/1, to_hex/1, parse_term/1, dict_find/3]).
+-export([validate_utf8/1, to_hex/1, to_hex_bin/1, parse_term/1, dict_find/3]).
-export([get_nested_json_value/2, json_user_ctx/1]).
-export([proplist_apply_field/2, json_apply_field/2]).
-export([to_binary/1, to_integer/1, to_list/1, url_encode/1]).
@@ -212,29 +212,36 @@
false
end.
-to_hex(<<Hi:4, Lo:4, Rest/binary>>) ->
- [nibble_to_hex(Hi), nibble_to_hex(Lo) | to_hex(Rest)];
-to_hex(<<>>) ->
- [];
+to_hex(Binary) when is_binary(Binary) ->
+ binary_to_list(to_hex_bin(Binary));
to_hex(List) when is_list(List) ->
- to_hex(list_to_binary(List)).
+ binary_to_list(to_hex_bin(list_to_binary(List))).
-nibble_to_hex(0) -> $0;
-nibble_to_hex(1) -> $1;
-nibble_to_hex(2) -> $2;
-nibble_to_hex(3) -> $3;
-nibble_to_hex(4) -> $4;
-nibble_to_hex(5) -> $5;
-nibble_to_hex(6) -> $6;
-nibble_to_hex(7) -> $7;
-nibble_to_hex(8) -> $8;
-nibble_to_hex(9) -> $9;
-nibble_to_hex(10) -> $a;
-nibble_to_hex(11) -> $b;
-nibble_to_hex(12) -> $c;
-nibble_to_hex(13) -> $d;
-nibble_to_hex(14) -> $e;
-nibble_to_hex(15) -> $f.
+% Optimized encode_hex/1 function from Erlang/OTP binary module starting with OTP 24+ [1].
+% One exception is we are emitting lower case hex characters instead of upper case ones.
+%
+% [1] https://github.com/erlang/otp/blob/master/lib/stdlib/src/binary.erl#L365.
+%
+
+-define(HEX(X), (hex(X)):16).
+
+%% erlfmt-ignore
+to_hex_bin(Data) when byte_size(Data) rem 8 =:= 0 ->
+ << <<?HEX(A), ?HEX(B), ?HEX(C), ?HEX(D), ?HEX(E), ?HEX(F), ?HEX(G), ?HEX(H)>> || <<A, B, C, D, E, F ,G, H>> <= Data >>;
+to_hex_bin(Data) when byte_size(Data) rem 7 =:= 0 ->
+ << <<?HEX(A), ?HEX(B), ?HEX(C), ?HEX(D), ?HEX(E), ?HEX(F), ?HEX(G)>> || <<A, B, C, D, E, F, G>> <= Data >>;
+to_hex_bin(Data) when byte_size(Data) rem 6 =:= 0 ->
+ << <<?HEX(A), ?HEX(B), ?HEX(C), ?HEX(D), ?HEX(E), ?HEX(F)>> || <<A, B, C, D, E, F>> <= Data >>;
+to_hex_bin(Data) when byte_size(Data) rem 5 =:= 0 ->
+ << <<?HEX(A), ?HEX(B), ?HEX(C), ?HEX(D), ?HEX(E)>> || <<A, B, C, D, E>> <= Data >>;
+to_hex_bin(Data) when byte_size(Data) rem 4 =:= 0 ->
+ << <<?HEX(A), ?HEX(B), ?HEX(C), ?HEX(D)>> || <<A, B, C, D>> <= Data >>;
+to_hex_bin(Data) when byte_size(Data) rem 3 =:= 0 ->
+ << <<?HEX(A), ?HEX(B), ?HEX(C)>> || <<A, B, C>> <= Data >>;
+to_hex_bin(Data) when byte_size(Data) rem 2 =:= 0 ->
+ << <<?HEX(A), ?HEX(B)>> || <<A,B>> <= Data >>;
+to_hex_bin(Data) when is_binary(Data) ->
+ << <<?HEX(N)>> || <<N>> <= Data >>.
parse_term(Bin) when is_binary(Bin) ->
parse_term(binary_to_list(Bin));
@@ -792,3 +799,33 @@
Ver1 = lists:reverse(lists:dropwhile(IsZero, lists:reverse(Ver))),
Ver2 = [erlang:integer_to_list(N) || N <- Ver1],
?l2b(lists:join(".", Ver2)).
+
+-compile({inline, [hex/1]}).
+
+%% erlfmt-ignore
+hex(X) ->
+ % We are encoding hex directly as lower case ASCII here and it's just a lookup table
+ % for all the 00..ff combinations. 0x00 -> "00", 0xf1-> "f1", etc.
+ %
+ % 00, ..., 0f,
+ % .. ..
+ % f0, ..., ff
+ %
+ element(X + 1, {
+ 16#3030, 16#3031, 16#3032, 16#3033, 16#3034, 16#3035, 16#3036, 16#3037, 16#3038, 16#3039, 16#3061, 16#3062, 16#3063, 16#3064, 16#3065, 16#3066,
+ 16#3130, 16#3131, 16#3132, 16#3133, 16#3134, 16#3135, 16#3136, 16#3137, 16#3138, 16#3139, 16#3161, 16#3162, 16#3163, 16#3164, 16#3165, 16#3166,
+ 16#3230, 16#3231, 16#3232, 16#3233, 16#3234, 16#3235, 16#3236, 16#3237, 16#3238, 16#3239, 16#3261, 16#3262, 16#3263, 16#3264, 16#3265, 16#3266,
+ 16#3330, 16#3331, 16#3332, 16#3333, 16#3334, 16#3335, 16#3336, 16#3337, 16#3338, 16#3339, 16#3361, 16#3362, 16#3363, 16#3364, 16#3365, 16#3366,
+ 16#3430, 16#3431, 16#3432, 16#3433, 16#3434, 16#3435, 16#3436, 16#3437, 16#3438, 16#3439, 16#3461, 16#3462, 16#3463, 16#3464, 16#3465, 16#3466,
+ 16#3530, 16#3531, 16#3532, 16#3533, 16#3534, 16#3535, 16#3536, 16#3537, 16#3538, 16#3539, 16#3561, 16#3562, 16#3563, 16#3564, 16#3565, 16#3566,
+ 16#3630, 16#3631, 16#3632, 16#3633, 16#3634, 16#3635, 16#3636, 16#3637, 16#3638, 16#3639, 16#3661, 16#3662, 16#3663, 16#3664, 16#3665, 16#3666,
+ 16#3730, 16#3731, 16#3732, 16#3733, 16#3734, 16#3735, 16#3736, 16#3737, 16#3738, 16#3739, 16#3761, 16#3762, 16#3763, 16#3764, 16#3765, 16#3766,
+ 16#3830, 16#3831, 16#3832, 16#3833, 16#3834, 16#3835, 16#3836, 16#3837, 16#3838, 16#3839, 16#3861, 16#3862, 16#3863, 16#3864, 16#3865, 16#3866,
+ 16#3930, 16#3931, 16#3932, 16#3933, 16#3934, 16#3935, 16#3936, 16#3937, 16#3938, 16#3939, 16#3961, 16#3962, 16#3963, 16#3964, 16#3965, 16#3966,
+ 16#6130, 16#6131, 16#6132, 16#6133, 16#6134, 16#6135, 16#6136, 16#6137, 16#6138, 16#6139, 16#6161, 16#6162, 16#6163, 16#6164, 16#6165, 16#6166,
+ 16#6230, 16#6231, 16#6232, 16#6233, 16#6234, 16#6235, 16#6236, 16#6237, 16#6238, 16#6239, 16#6261, 16#6262, 16#6263, 16#6264, 16#6265, 16#6266,
+ 16#6330, 16#6331, 16#6332, 16#6333, 16#6334, 16#6335, 16#6336, 16#6337, 16#6338, 16#6339, 16#6361, 16#6362, 16#6363, 16#6364, 16#6365, 16#6366,
+ 16#6430, 16#6431, 16#6432, 16#6433, 16#6434, 16#6435, 16#6436, 16#6437, 16#6438, 16#6439, 16#6461, 16#6462, 16#6463, 16#6464, 16#6465, 16#6466,
+ 16#6530, 16#6531, 16#6532, 16#6533, 16#6534, 16#6535, 16#6536, 16#6537, 16#6538, 16#6539, 16#6561, 16#6562, 16#6563, 16#6564, 16#6565, 16#6566,
+ 16#6630, 16#6631, 16#6632, 16#6633, 16#6634, 16#6635, 16#6636, 16#6637, 16#6638, 16#6639, 16#6661, 16#6662, 16#6663, 16#6664, 16#6665, 16#6666
+ }).
diff --git a/src/couch/src/couch_uuids.erl b/src/couch/src/couch_uuids.erl
index be6089d..9726d54 100644
--- a/src/couch/src/couch_uuids.erl
+++ b/src/couch/src/couch_uuids.erl
@@ -37,7 +37,7 @@
gen_server:call(?MODULE, create).
random() ->
- list_to_binary(couch_util:to_hex(crypto:strong_rand_bytes(16))).
+ couch_util:to_hex_bin(crypto:strong_rand_bytes(16)).
init([]) ->
ok = config:listen_for_changes(?MODULE, nil),
diff --git a/src/couch/src/test_util.erl b/src/couch/src/test_util.erl
index 0f3d57b..165a5be 100644
--- a/src/couch/src/test_util.erl
+++ b/src/couch/src/test_util.erl
@@ -482,7 +482,7 @@
).
random_rev() ->
- ?l2b(couch_util:to_hex(crypto:strong_rand_bytes(16))).
+ couch_util:to_hex_bin(crypto:strong_rand_bytes(16)).
shuffle(List) ->
Paired = [{couch_rand:uniform(), I} || I <- List],
diff --git a/src/couch/test/eunit/couch_auth_cache_tests.erl b/src/couch/test/eunit/couch_auth_cache_tests.erl
index a4c3108..f8475ac 100644
--- a/src/couch/test/eunit/couch_auth_cache_tests.erl
+++ b/src/couch/test/eunit/couch_auth_cache_tests.erl
@@ -288,7 +288,7 @@
{ok, couch_doc:rev_to_str(NewRev)}.
hash_password(Password) ->
- ?l2b(couch_util:to_hex(crypto:hash(sha, iolist_to_binary([Password, ?SALT])))).
+ couch_util:to_hex_bin(crypto:hash(sha, iolist_to_binary([Password, ?SALT]))).
shutdown_db(DbName) ->
{ok, AuthDb} = couch_db:open_int(DbName, [?ADMIN_CTX]),
diff --git a/src/couch/test/eunit/couch_key_tree_tests.erl b/src/couch/test/eunit/couch_key_tree_tests.erl
index 4898c21..a277a56 100644
--- a/src/couch/test/eunit/couch_key_tree_tests.erl
+++ b/src/couch/test/eunit/couch_key_tree_tests.erl
@@ -564,7 +564,7 @@
Opts = [
monitor,
{max_heap_size, #{
- size => 13000000,
+ size => 15000000,
error_logger => false,
kill => true
}}
diff --git a/src/couch/test/eunit/couch_util_tests.erl b/src/couch/test/eunit/couch_util_tests.erl
index c07ddc0..62ec207 100644
--- a/src/couch/test/eunit/couch_util_tests.erl
+++ b/src/couch/test/eunit/couch_util_tests.erl
@@ -139,11 +139,54 @@
to_hex_test_() ->
[
?_assertEqual("", couch_util:to_hex([])),
+ ?_assertEqual(<<>>, couch_util:to_hex_bin(<<>>)),
+ ?_assertEqual(<<"00">>, couch_util:to_hex_bin(<<0>>)),
+ ?_assertEqual(<<"01">>, couch_util:to_hex_bin(<<1>>)),
?_assertEqual("010203faff", couch_util:to_hex([1, 2, 3, 250, 255])),
+ ?_assertEqual(<<"010203faff">>, couch_util:to_hex_bin(<<1, 2, 3, 250, 255>>)),
?_assertEqual("", couch_util:to_hex(<<>>)),
?_assertEqual("010203faff", couch_util:to_hex(<<1, 2, 3, 250, 255>>))
].
+to_hex_range_test() ->
+ lists:foreach(
+ fun(PrefixSize) ->
+ lists:foreach(
+ fun(I) ->
+ Prefix = list_to_binary(lists:duplicate(PrefixSize, 1)),
+ Bin = <<Prefix/binary, I:8/integer>>,
+ ?assertEqual(list_to_binary(to_hex_simple(Bin)), couch_util:to_hex_bin(Bin))
+ end,
+ lists:seq(0, 16#ff)
+ )
+ end,
+ lists:seq(0, 8)
+ ).
+
+% Use previous implementation from couch_util for validation
+%
+to_hex_simple(<<Hi:4, Lo:4, Rest/binary>>) ->
+ [nibble_to_hex(Hi), nibble_to_hex(Lo) | to_hex_simple(Rest)];
+to_hex_simple(<<>>) ->
+ [].
+
+nibble_to_hex(0) -> $0;
+nibble_to_hex(1) -> $1;
+nibble_to_hex(2) -> $2;
+nibble_to_hex(3) -> $3;
+nibble_to_hex(4) -> $4;
+nibble_to_hex(5) -> $5;
+nibble_to_hex(6) -> $6;
+nibble_to_hex(7) -> $7;
+nibble_to_hex(8) -> $8;
+nibble_to_hex(9) -> $9;
+nibble_to_hex(10) -> $a;
+nibble_to_hex(11) -> $b;
+nibble_to_hex(12) -> $c;
+nibble_to_hex(13) -> $d;
+nibble_to_hex(14) -> $e;
+nibble_to_hex(15) -> $f.
+
json_decode_test_() ->
[
?_assertEqual({[]}, couch_util:json_decode(<<"{}">>)),
diff --git a/src/couch_index/src/couch_index_util.erl b/src/couch_index/src/couch_index_util.erl
index 3a7d283..db8aad4 100644
--- a/src/couch_index/src/couch_index_util.erl
+++ b/src/couch_index/src/couch_index_util.erl
@@ -71,4 +71,4 @@
sort_lib(Rest, [{LName, LCode} | LAcc]).
hexsig(Sig) ->
- couch_util:to_hex(binary_to_list(Sig)).
+ couch_util:to_hex(Sig).
