diff options
author | Nick Vatamaniuc <vatamane@gmail.com> | 2022-07-06 02:49:15 -0400 |
---|---|---|
committer | Nick Vatamaniuc <nickva@users.noreply.github.com> | 2022-07-06 13:49:52 -0400 |
commit | 29ac7853f203afec40adde85fe4fc2e0e230f565 (patch) | |
tree | 83c0aace7220ad60cdd1e1a2d394cfbcbc380b14 | |
parent | e41465ec852be4f97685309b4644e796395ada74 (diff) | |
download | couchdb-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.erl | 2 | ||||
-rw-r--r-- | src/couch/src/couch_passwords.erl | 4 | ||||
-rw-r--r-- | src/couch/src/couch_util.erl | 83 | ||||
-rw-r--r-- | src/couch/src/couch_uuids.erl | 2 | ||||
-rw-r--r-- | src/couch/src/test_util.erl | 2 | ||||
-rw-r--r-- | src/couch/test/eunit/couch_auth_cache_tests.erl | 2 | ||||
-rw-r--r-- | src/couch/test/eunit/couch_key_tree_tests.erl | 2 | ||||
-rw-r--r-- | src/couch/test/eunit/couch_util_tests.erl | 43 | ||||
-rw-r--r-- | src/couch_index/src/couch_index_util.erl | 2 |
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). |