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).

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).