Recently I found an optimization I wanted to make in some string processing code - it was making multiple passes that could be replaced with a single pass using pattern matching and IO Lists.

Here is the commit that escapes XML entities in a string where we replace multiple regular expressions with a single recursive pass. There are two questions - does the code produce the same results, and is it faster?

Verifying with Propcheck

We can use propcheck to generate strings which may or may not contain XML entities and verify the two methods against each other:

use PropCheck

def ascii_char, do: oneof([choose(?a, ?z), choose(32, 126), elements(["&", ">", "<"])])

def sentence do
  let cs <- list(ascii_char()) do
    to_string(cs)
  end
 end

def doc do
  let xs <- list(sentence()) do
    {:doc, %{}, Enum.map(xs, fn s -> {:p, %{}, s} end)}
  end
end

We have three cases to test:

1. simple words
2. ascii characters that may contain escapable XML characters
3. XML entities that the library passes through and does not escape

Each generated string can be classified and we get a report showing that our test coverage includes all three cases:

def classify(doc) do
    s = inspect(doc)
    [
        {:amp, String.contains?(s, "&")},
        {:lt, String.contains?(s, "<")},
        {:gt, String.contains?(s, ">")}
    ]
end

Modify the library so we can pass in the original or modified escape function:

  def generate(any, options \\ []) do
    options = Keyword.merge([escape: &escape/1], options)
    any
    |> format(0,options)
    |> IO.chardata_to_string()
  end

Then we can test that the escape functions have the same behaviour:

  property "Compare default regex vs IO list pattern matching", @num_tests do
    forall doc <- doc() do
      doc1 = XmlBuilder.generate(doc1)
      doc2 = XmlBuilder.generate(doc2, [escape: &Escape.IOList2.escape/1])
      aggregate(assert_equal(doc1, doc2), classify(doc))
    end
  end

Now we are sure we have the same behaviour, is it worth making the change?

Benchmarking with Benchee

Benchee allows benchmarking of functions, warms up the VM, and has a detail report.

Benchee.run(
  %{
    "regex" => fn -> XmlBuilder.generate(document, []) end,
    "pattern-match" => fn -> XmlBuilder.generate(document, [escape: &Escape.IOList2.escape/1]) end
  },
  time: 120,
  memory_time: 120
)

Running this on an EC2 Computer instance generated this report:

Operating System: Linux
CPU Information: Intel(R) Xeon(R) CPU E5-2666 v3 @ 2.90GHz
Number of Available Cores: 2
Available memory: 3.67 GB
Elixir 1.11.2
Erlang 23.1

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 2 min
memory time: 2 min
parallel: 1
inputs: none specified
Estimated total run time: 8.07 min

Benchmarking pattern-match...
Benchmarking regex...

Name                    ips        average  deviation         median         99th %
pattern-match        4.10 K      243.86 μs    ±32.09%      212.75 μs      663.75 μs
regex                1.17 K      856.42 μs    ±10.13%      839.00 μs     1091.22 μs

Comparison: 
pattern-match        4.10 K
regex                1.17 K - 3.51x slower +612.56 μs

Memory usage statistics:

Name             Memory usage
pattern-match        74.09 KB
regex               144.71 KB - 1.95x memory usage +70.62 KB

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

The code with a single pass is 3x faster and uses half the memory. The PR was accepted and merged.