summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNick Vatamaniuc <vatamane@gmail.com>2022-07-06 02:49:15 -0400
committerNick Vatamaniuc <nickva@users.noreply.github.com>2022-07-06 13:49:52 -0400
commit29ac7853f203afec40adde85fe4fc2e0e230f565 (patch)
tree83c0aace7220ad60cdd1e1a2d394cfbcbc380b14
parente41465ec852be4f97685309b4644e796395ada74 (diff)
downloadcouchdb-29ac7853f203afec40adde85fe4fc2e0e230f565.tar.gz
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).
-rw-r--r--src/couch/src/couch_doc.erl2
-rw-r--r--src/couch/src/couch_passwords.erl4
-rw-r--r--src/couch/src/couch_util.erl83
-rw-r--r--src/couch/src/couch_uuids.erl2
-rw-r--r--src/couch/src/test_util.erl2
-rw-r--r--src/couch/test/eunit/couch_auth_cache_tests.erl2
-rw-r--r--src/couch/test/eunit/couch_key_tree_tests.erl2
-rw-r--r--src/couch/test/eunit/couch_util_tests.erl43
-rw-r--r--src/couch_index/src/couch_index_util.erl2
9 files changed, 111 insertions, 31 deletions
diff --git a/src/couch/src/couch_doc.erl b/src/couch/src/couch_doc.erl
index 5d44e456c..95b1c8b41 100644
--- a/src/couch/src/couch_doc.erl
+++ b/src/couch/src/couch_doc.erl
@@ -74,7 +74,7 @@ to_json_revisions(Options, Start, RevIds0) ->
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 828d2f68b..b89104603 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 @@ pbkdf2(Password, Salt, Iterations, DerivedLength) when
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 d71fc059c..84691d14e 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 @@ validate_utf8_fast(B, O) ->
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)).
-
-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.
+ binary_to_list(to_hex_bin(list_to_binary(List))).
+
+% 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 @@ version_to_binary(Ver) when is_list(Ver) ->
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 be6089dff..9726d5428 100644
--- a/src/couch/src/couch_uuids.erl
+++ b/src/couch/src/couch_uuids.erl
@@ -37,7 +37,7 @@ new() ->
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 0f3d57b72..165a5be2f 100644
--- a/src/couch/src/test_util.erl
+++ b/src/couch/src/test_util.erl
@@ -482,7 +482,7 @@ revs1(Pos, {Rev, _Val, Nodes}) ->
).
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 a4c31083a..f8475ac32 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 @@ update_user_doc(DbName, UserName, Password, Rev) ->
{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 4898c21da..a277a5652 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 @@ should_not_use_excessive_memory_when_stemming() ->
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 c07ddc093..62ec20775 100644
--- a/src/couch/test/eunit/couch_util_tests.erl
+++ b/src/couch/test/eunit/couch_util_tests.erl
@@ -139,11 +139,54 @@ should_fail_for_missing_cb() ->
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 3a7d283bf..db8aad470 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([{LName, LCode} | Rest], LAcc) ->
sort_lib(Rest, [{LName, LCode} | LAcc]).
hexsig(Sig) ->
- couch_util:to_hex(binary_to_list(Sig)).
+ couch_util:to_hex(Sig).