Proposal - fast path for decode_www_form and few other places

[Daniel Kukula]

●

I've recently been looking at places where we can avoid building intermediate strings and just copy the existing data instead.

There are two proposals here; the second one is at the end and is independent of the first. For example, unescape in elixir_interpolation.erl, or URI.decode_www_form, which builds an intermediate string: def decode_www_form(string) when is_binary(string), do: unpercent(string, "", true) But if there is no percent sign, we don't need to traverse the string at all: def decode_www_form(string) when is_binary(string) do case :binary.match(string, "%") do :nomatch -> string _ -> unpercent(string, "", true) end end Proposal 1: a fast path Two things fall out of this: - we can return the original binary untouched when there is no percent sign, skipping the traversal entirely - :binary.match returns the position of the first match, so when there is one, we can copy everything up to it into the accumulator in one go instead of byte by byte This is local to each function and doesn't require any new machinery. Proposal 2: precompiled patterns in persistent_term :binary.match has to compile the pattern on every call. We could pass a precompiled one instead, but it then has to be either a parameter to the function or stored somewhere. One such place is persistent_term. Elixir already stores a few things there, so I'd like to precompile the common patterns on application start and look them up: :binary.match(string, :persistent_term.get({:precompiled_pattern, :percent}))

This is something only Elixir can do for its own call sites - a library can already put its own compiled patterns in persistent_term, but nobody outside core can change what URI.decode_www_form matches against.

I'd like to hear your opinion on both.

[José Valim]

I recently sent a PR to Erlang/OTP to precompile patterns when they are loaded. Although I believe the single character patterns are very efficient to compile, so unlikely my recent PR will make a large difference.

So to answer question 1, If benchmarks show a gain across the board without persistent term, we can adopt it today, otherwise we wait.

José Valim

https://dashbit.co/

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/elixir-lang-core/4375e915-c5ad-4c09-9d84-690c952aa938n%40googlegroups.com.

[Daniel Kukula]

Since the gain is not exactly linear, I used Claude to put the benchmarks and charts in a Livebook that runs against a real Elixir checkout, so you can rerun it yourself -- the numbers are promising: https://github.com/dkuku/livebooks/blob/master/unescape_fast_path.livemd I benchmarked elixir_interpolation:unescape_chars/2 rather than decode_www_form, since the compiler provides a real-world corpus: tokenizing the Elixir repo itself collects the exact binaries the tokenizer unescapes -- 50,447 literals, ~2.7 MB per compile pass, 94% with no backslash. Escapes are rarest where literals are most common (~5% at the 11-byte median), and most bytes live in doc heredocs, which are ~90% escape-free. Variants, one pass over the whole repo (medians): A: current code 116 ms, 108 MB allocated B: one-line binary:match guard 19 ms, 13 MB (6x) C: B + copy prefix in one go 12 ms, 7 MB (10x) D: C + precompiled pattern 9 ms, 7 MB (13x) The only regression is an escape at the very first byte: a flat ~100 ns, so ~2x on a 4-byte literal and inside the noise from a few hundred bytes up. Only ~6% of literals miss the guard at all, and C turns a late escape into a win instead

[Daniel Kukula]

Correction to the table above: one variant's accumulator made the compiler allocate a fresh binary per iteration instead of growing one in place -- for every variant in the module, baseline included. Corrected numbers:

    A: current code                            21.96 ms   5.02 MB
    B: one-line binary:match guard   6.39 ms   0.37 MB   (3.4x)
    C: B + copy prefix in one go     5.32 ms   0.44 MB   (4.1x)
    D: C + precompiled pattern       2.84 ms   0.44 MB   (7.7x)

  Everything else in the post stands, I updated the livebook.

[José Valim]

Sounds good to me!

José Valim

https://dashbit.co/

To view this discussion visit https://groups.google.com/d/msgid/elixir-lang-core/93626d1d-d1d6-4762-82d1-b0a6237be966n%40googlegroups.com.