Replace `b64url` with Erlang/OTP stdlib `base64`

[Benjamin-Philip]

Presently, url-safe base64 encoding is handled by b64url NIF at src/b64url. However, support for RFC 4648 compliant url-safe encoding was added to Erlang stdlib's base64 in Erlang/OTP 26.0. Additionally, encoding was made upto 4 times faster thanks to the JIT compiler that was merged in the same release.

Benchmarking base64 and b64url with benchee¹, with the following benchmark, we find that the built-in base64 is faster:

Mix.install([:benchee, {:b64url, github: "apache/couchdb", sparse: "src/b64url/"}])

defmodule B64Bench do
  def main do
    [workers, min_size, max_size, duration, entries] =
      Enum.map(System.argv(), &String.to_integer/1)

    bytes =
      1..entries
      |> Enum.to_list()
      |> Enum.map(fn _ ->
        :crypto.strong_rand_bytes(min_size + :rand.uniform(max_size - min_size))
      end)

    Benchee.run(
      %{
        "b64url" => fn input -> process(input, &:b64url.encode/1, &:b64url.decode/1) end,
        "base64 (standard) + re" => fn input ->
          process(
            input,
            fn url ->
              url = :erlang.iolist_to_binary(:re.replace(:base64.encode(url), "=+$", ""))
              url = :erlang.iolist_to_binary(:re.replace(url, "/", "_", [:global]))
              :erlang.iolist_to_binary(:re.replace(url, "\\+", "-", [:global]))
            end,
            fn url64 ->
              url64 = :erlang.iolist_to_binary(url64)
              url64 = :erlang.iolist_to_binary(:re.replace(url64, "-", "+", [:global]))
              url64 = :erlang.iolist_to_binary(:re.replace(url64, "_", "/", [:global]))

              padding =
                :erlang.list_to_binary(
                  :lists.duplicate(rem(4 - rem(:erlang.size(url64), 4), 4), 61)
                )

              :base64.decode(<<url64::binary, padding::binary>>)
            end
          )
        end,
        "base64 (urlsafe)" => fn input ->
          process(
            input,
            &:base64.encode(&1, %{mode: :urlsafe}),
            &:base64.decode(&1, %{mode: :urlsafe})
          )
        end
      },
      parallel: workers,
      time: duration,
      inputs: %{"generated" => bytes}
    )

    IO.inspect(:erlang.byte_size(Enum.join(bytes)), label: "Total size (B)")
  end

  def process(bytes, encode, decode) do
    Enum.each(bytes, fn bin -> decode.(encode.(bin)) end)
  end
end

B64Bench.main()

$ elixir b64_bench.exs 4 10 100 60 100
Operating System: Linux
CPU Information: 12th Gen Intel(R) Core(TM) i7-1255U
Number of Available Cores: 12
Available memory: 15.31 GB
Elixir 1.18.4
Erlang 28.0.2
JIT enabled: true

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 1 min
memory time: 0 ns
reduction time: 0 ns
parallel: 4
inputs: generated
Estimated total run time: 3 min 6 s
Excluding outliers: false

Benchmarking b64url with input generated ...
Benchmarking base64 (standard) + re with input generated ...
Benchmarking base64 (urlsafe) with input generated ...
Calculating statistics...
Formatting results...

##### With input generated #####
Name                             ips        average  deviation         median         99th %
base64 (urlsafe)              8.18 K      122.31 μs    ±44.53%      110.85 μs      296.40 μs
b64url                        6.18 K      161.88 μs    ±56.17%      139.65 μs      609.83 μs
base64 (standard) + re        0.74 K     1345.47 μs    ±32.12%     1076.60 μs     2221.58 μs

Comparison: 
base64 (urlsafe)              8.18 K
b64url                        6.18 K - 1.32x slower +39.57 μs
base64 (standard) + re        0.74 K - 11.00x slower +1223.16 μs
Total size (B): 5491

Therefore I propose we drop b64url in favour of the stdlib functions. This has the following benefits:

• Less code to maintain
• (marginally) better peformance
• Enhanced safety (by way of eliminating an NIF)

Footnotes

1. I found updating the existing benchmarks to compare 3 or more implementations tedious. The new benchmark's arguments are similar to the previous benchmark, with the exception of an extra parameter entries, which is the number of random binaries to encode. The ips results are directly proportional to the previous bps and can be converted to bps by multiplying by total size. ↩

[nickva]

A good idea to investigate @Benjamin-Philip

With the built-in script I still see that the nif is faster even with the jit. Without the jit it's even more pronounced. Maybe we could do a length limit, if it's < 100 bytes we use the built-ins, otherwise use the nif? Pretty sure there is a way to check if we're running a jitted emulator build too.

I patched the built-in script like this:

--- i/src/b64url/test/benchmark.escript
+++ w/src/b64url/test/benchmark.escript
@@ -116,25 +116,18 @@ run_worker(St, Started) ->

 do_round_trip(St) ->
     Size = St#st.minsize + rand:uniform(St#st.maxsize - St#st.minsize),
-    Data = crypto:strong_rand_bytes(Size),
+    Data = rand:bytes(Size),
     Encoded = (St#st.module):encode(Data),
     Data = (St#st.module):decode(Encoded),
     St#st{total_bytes=St#st.total_bytes+Size}.


 encode(Url) ->
-    Url1 = iolist_to_binary(re:replace(base64:encode(Url), "=+$", "")),
-    Url2 = iolist_to_binary(re:replace(Url1, "/", "_", [global])),
-    iolist_to_binary(re:replace(Url2, "\\+", "-", [global])).
+    base64:encode(Url, #{mode => urlsafe, padding => false}).


 decode(Url64) ->
-    Url1 = re:replace(iolist_to_binary(Url64), "-", "+", [global]),
-    Url2 = iolist_to_binary(
-        re:replace(iolist_to_binary(Url1), "_", "/", [global])
-    ),
-    Padding = list_to_binary(lists:duplicate((4 - size(Url2) rem 4) rem 4, $=)),
-    base64:decode(<<Url2/binary, Padding/binary>>).
+    base64:decode(Url64, #{mode => urlsafe, padding => false}).

Probably don't need to do the re replacement, in this part, I think we only handle the urlsafe version. We also don't use padding.

url64 = :erlang.iolist_to_binary(:re.replace(url64, "-", "+", [:global]))
url64 = :erlang.iolist_to_binary(:re.replace(url64, "_", "/", [:global]))

[davisp]

First things first, I absolutely don’t care at all about the switch to stdlib, but I do feel required to refute one point in particular:

• Enhanced safety (by way of eliminating an NIF)

The last bug fix in b64url near as I can tell was this commit from almost exactly twelve years ago. Which means that at least in terms of bugs per LoC, b64url has been safer than the Erlang VM itself for more than a decade.

This PR comment is brought to you by @nickva making a joke and me feeling a bit cheeky. I haven’t spent much (any) time thinking about this PR in terms of actual performance, so I’ll leave that to y’all. I’ll even +1 the b64url removal if that’s the decision!

[Benjamin-Philip]

I patched the built-in script like this:

I left the regex implementation for completeness, but since we don't need to bench the old version, replacing it with the url-safe version works too.

Pretty sure there is a way to check if we're running a jitted emulator build too

I'm not too familiar with how you package and distribute couchdb. I believe that the JIT is included in the default build, so it shouldn't be a problem in most deployments.

Maybe we could do a length limit, if it's < 100 bytes we use the built-ins, otherwise use the nif?

Are you getting different results in this range? Typically how large are the bytes you encode?

With the built-in script I still see that the nif is faster even with the jit.

Could you share the parameters you benchmarked with so that I can investigate?

[Benjamin-Philip]

Looking through the built-in benchmark, I noticed a few flaws:

Firstly, the overhead of generating the random bytes and (some of) the benchmarking logic is included in the benchmark. This was mentioned in the Readme.

Now, the overhead itself is fine if it is constant - the difference in bytes per second is the speed difference. However, :crypto:rand takes longer in an increase in N. Even if N was constant, we don't know if the deviation in the time it takes is significant. This is the second flaw.

Finally, we're benchmarking the two implementations with two random different inputs. Is this still an apples to apples comparison? Maybe a better approach would be to benchmark with a common random input?

I'm not sure if my benchmark suffers from some of the same flaws, but maybe moving from handwritten benchmarks to some benchmarking framework would be better?

[nickva]

Could you share the parameters you benchmarked with so that I can investigate?

I am using

./test/benchmark.escript 1 100 10000 60
nif :     4803827309 bytes /  60 seconds =    80063788.48 bps
erl :     3093572433 bytes /  60 seconds =    51559540.55 bps

On an intel i5, ubuntu, with erlang 26 compiled with jit

Erlang/OTP 26 [erts-14.2.5.11] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] [jit:ns]

 cat /proc/cpuinfo 
processor	: 0
vendor_id	: GenuineIntel
cpu family	: 6
model		: 142
model name	: Intel(R) Core(TM) i5-8365U CPU @ 1.60GHz
...

Firstly, the overhead of generating the random bytes and (some of) the benchmarking logic is included in the benchmark. This was mentioned in the Readme.

Now, the overhead itself is fine if it is constant - the difference in bytes per second is the speed difference. However, :crypto:rand takes longer in an increase in N. Even if N was constant, we don't know if the deviation in the time it takes is significant. This is the second flaw.

Yeah good point, that should taken out of the timing loop. Pre-generate a few and then select between them or just go through some length ranges individually (benchmark with length 10, 100, 1000, 10000). Or if we stick with random go use a common seed value.

Finally, we're benchmarking the two implementations with two random different inputs. Is this still an apples to apples comparison? Maybe a better approach would be to benchmark with a common random input?

I'm not sure if my benchmark suffers from some of the same flaws, but maybe moving from handwritten benchmarks to some benchmarking framework would be better?

Well the benchmarking script is already there so we just updated it to use the latest built-in functions. But something like benchee or even better erlperf is nice, too.

Are you getting different results in this range? Typically how large are the bytes you encode?

Yeah the ranges I am looking are 100 - 10000. A place b64 encoding would matter is when emitting changes feeds sequences. For Q=64, N=1 db the size of sequence string is about 1200 bytes. For Q=2 would it closer to 120 bytes and such. This also used for attachment encoding when they are in-line in the document body (as opposed to updated directly).