improve masking function memory/speed

[the-mikedavis]

Currently we use Stream.cycle/1 and Enum.reduce_while/3 for the implementation of the masking function.

This is probably very suboptimal in terms of speed and memory consumption. If I understand Elixir/Erlang performance correctly, binary matches are always to be preferred for speed/memory. Also we're only doing the xor of 1 byte (unsigned big integer) at a time and we could be doing it with up to four bytes (the size of the mask)

[the-mikedavis]

after giving this a glance http://erlang.org/doc/efficiency_guide/myths.html#myth--tail-recursive-functions-are-much-faster-----than-recursive-functions

I tried it with a body-recursive implementation and wow that's slow

Operating System: Linux
CPU Information: Intel(R) Core(TM) i7-9700KF CPU @ 3.60GHz
Number of Available Cores: 8
Available memory: 31.30 GB
Elixir 1.12.1
Erlang 24.0

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 2 s
parallel: 1
inputs: Large, Medium, Small
Estimated total run time: 2.80 min

Benchmarking body with input Large...
Benchmarking body with input Medium...
Benchmarking body with input Small...
Benchmarking compile with input Large...
Benchmarking compile with input Medium...
Benchmarking compile with input Small...
Benchmarking match with input Large...
Benchmarking match with input Medium...
Benchmarking match with input Small...
Benchmarking stream with input Large...
Benchmarking stream with input Medium...
Benchmarking stream with input Small...

##### With input Large #####
Name              ips        average  deviation         median         99th %
compile         99.81       10.02 ms     ±3.17%       10.03 ms       10.72 ms
match           73.71       13.57 ms     ±3.24%       13.54 ms       14.65 ms
stream          13.54       73.86 ms     ±4.06%       74.25 ms       78.82 ms
body           0.0152    65666.52 ms     ±0.00%    65666.52 ms    65666.52 ms

Comparison: 
compile         99.81
match           73.71 - 1.35x slower +3.55 ms
stream          13.54 - 7.37x slower +63.84 ms
body           0.0152 - 6554.43x slower +65656.50 ms

Memory usage statistics:

Name       Memory usage
compile        23.84 MB
match          38.15 MB - 1.60x memory usage +14.31 MB
stream        206.00 MB - 8.64x memory usage +182.15 MB
body           34.62 MB - 1.45x memory usage +10.78 MB

**All measurements for memory usage were the same**

##### With input Medium #####
Name              ips        average  deviation         median         99th %
compile        5.34 K      187.26 μs    ±33.76%      191.52 μs      338.91 μs
match          3.77 K      265.34 μs    ±25.08%      258.18 μs      409.38 μs
body           1.11 K      896.89 μs     ±4.81%      882.93 μs     1026.21 μs 
stream         0.83 K     1205.38 μs    ±28.13%     1196.79 μs     1932.71 μs

Comparison: 
compile        5.34 K 
match          3.77 K - 1.42x slower +78.08 μs
body           1.11 K - 4.79x slower +709.63 μs
stream         0.83 K - 6.44x slower +1018.12 μs

Memory usage statistics:

Name       Memory usage
compile       245.31 KB
match         391.83 KB - 1.60x memory usage +146.52 KB
body          411.38 KB - 1.68x memory usage +166.06 KB
stream       2111.56 KB - 8.61x memory usage +1866.25 KB

**All measurements for memory usage were the same**

##### With input Small #####
Name              ips        average  deviation         median         99th %
compile      196.45 K        5.09 μs  ±2237.32%        1.57 μs        4.11 μs
match        155.04 K        6.45 μs  ±1752.01%        1.95 μs        5.37 μs
body         125.88 K        7.94 μs  ±1503.12%        2.65 μs        7.25 μs
stream        46.30 K       21.60 μs   ±513.21%        7.01 μs      433.76 μs

Comparison: 
compile      196.45 K
match        155.04 K - 1.27x slower +1.36 μs
body         125.88 K - 1.56x slower +2.85 μs
stream        46.30 K - 4.24x slower +16.51 μs

Memory usage statistics:

Name       Memory usage
compile         3.61 KB
match           5.11 KB - 1.42x memory usage +1.50 KB
body            5.32 KB - 1.47x memory usage +1.71 KB
stream         23.28 KB - 6.45x memory usage +19.67 KB

**All measurements for memory usage were the same**

bench file:

Mix.install([:benchee])

defmodule Foo do
  def stream_mask(payload, <<a, b, c, d>>) do
    [a, b, c, d]
    |> Stream.cycle()
    |> Enum.reduce_while({payload, _acc = <<>>}, fn
      _mask_key, {<<>>, acc} ->
        {:halt, acc}

      mask_key, {<<part_key::integer, payload_rest::binary>>, acc} ->
        {:cont, {payload_rest, <<acc::binary, Bitwise.bxor(mask_key, part_key)::integer>>}}
    end)
  end

  def match_mask(payload, mask, acc \\ <<>>)

  def match_mask(payload, nil, _acc), do: payload

  # n=4 is the happy path
  # n=3..1 catches cases where the remaining byte_size/1 of the payload is shorter
  # than the mask
  for n <- 4..1 do
    def match_mask(
          <<part_key::integer-size(8)-unit(unquote(n)), payload_rest::binary>>,
          <<mask_key::integer-size(8)-unit(unquote(n)), _::binary>> = mask,
          acc
        ) do
      match_mask(
        payload_rest,
        mask,
        <<acc::binary, Bitwise.bxor(mask_key, part_key)::integer-size(8)-unit(unquote(n))>>
      )
    end
  end

  def match_mask(<<>>, _mask, acc), do: acc

  @compile {:inline, compile_mask: 2, compile_mask: 3}
  def compile_mask(payload, mask, acc \\ <<>>)

  def compile_mask(payload, nil, _acc), do: payload

  # n=4 is the happy path
  # n=3..1 catches cases where the remaining byte_size/1 of the payload is shorter
  # than the mask
  for n <- 4..1 do
    def compile_mask(
          <<part_key::integer-size(8)-unit(unquote(n)), payload_rest::binary>>,
          <<mask_key::integer-size(8)-unit(unquote(n)), _::binary>> = mask,
          acc
        ) do
      compile_mask(
        payload_rest,
        mask,
        <<acc::binary, Bitwise.bxor(mask_key, part_key)::integer-size(8)-unit(unquote(n))>>
      )
    end
  end

  def compile_mask(<<>>, _mask, acc), do: acc

  def body_mask(payload, mask)

  def body_mask(payload, nil), do: payload

  # n=4 is the happy path
  # n=3..1 catches cases where the remaining byte_size/1 of the payload is shorter
  # than the mask
  for n <- 4..1 do
    def body_mask(
          <<part_key::integer-size(8)-unit(unquote(n)), payload_rest::binary>>,
          <<mask_key::integer-size(8)-unit(unquote(n)), _::binary>> = mask
        ) do
      <<
        Bitwise.bxor(mask_key, part_key)::integer-size(8)-unit(unquote(n)),
        body_mask(payload_rest, mask)::binary
      >>
    end
  end

  def body_mask(<<>>, _mask), do: <<>>
end

mask = :crypto.strong_rand_bytes(4)

Benchee.run(
  %{
    "stream" => fn payload -> Foo.stream_mask(payload, mask) end,
    "match" => fn payload -> Foo.match_mask(payload, mask) end,
    "body" => fn payload -> Foo.body_mask(payload, mask) end,
    "compile" => fn payload -> Foo.compile_mask(payload, mask) end
  },
  time: 10,
  memory_time: 2,
  inputs: %{
    "Small" => :crypto.strong_rand_bytes(100),
    "Medium" => :crypto.strong_rand_bytes(10_000),
    "Large" => :crypto.strong_rand_bytes(1_000_000)
  }
)