Add support for simultaneously updating multiple key-value pairs in maps and keyword lists

[Paul Alexander]

Hi everyone,

I would like to discuss the possibility of adding two new functions to each of the Map and Keyword modules; replace_many/2 and update_many/3. Their purpose is to update maps and keyword lists providing either a keyword list of the key-value pairs which need to updated, or a list of keys and a function which operates on the existing values of those keys.

Far too often I find myself needing to call replace!/3 or update!/3 several times from within a pipeline, or even needing to use a for-comprehension or Enum.reduce/3 to update a map in "one shot", when it feels like there should be a function for this. 

There are a number of reasons as to why I think these functions should be considered, but I'll provide only two for now:

1. There is already a way of updating multiple key-value pairs simultaneously for maps using %{map | k1 => v1, k2 => v2}. But this unfortunately does not support passing a literal keyword list after the cons operator.
   • My first instinct was to see if I could expand the special update syntax to handle keyword lists, but I wasn't able to find where it is in the codebase. If someone could point that out for me because I'd like to learn how it works, I'd greatly appreciate it.
2. It would be somewhat analogous to Kernel.struct!/2, where keyword lists can be passed as the second argument to update several fields within a struct. Seeing as how structs are maps, it only makes sense there should be a way that maps could be updated in a similar manner from within the Map module.

I have already implemented the four functions, complete with docs, examples, and passing tests. But I wanted confirmation from the core team if a PR is welcome for this addition. Any opinions?

[José Valim]

Hi Paul,

Thanks for the proposal. My personal take is that a Enum.reduce/3 + the relevant Map operation should be the way to go, because this can easily lead to a combination of replace_many, update_many, put_new_many, etc. Especially because the many operations likely wouldn't be any more efficient than the Enum.reduce/3 call.

--
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 on the web visit https://groups.google.com/d/msgid/elixir-lang-core/7c79a2b8-3a3c-48f9-a4d0-7d2e07c851e4n%40googlegroups.com.

[Paul Alexander]

Thanks for offering your opinion, José. I very much understand where you're coming in regards to using Enum.reduce/3 for such an operation, but I have found it to cause a fair amount of needless overhead especially when there are other operations going on and the updating should be the most trivial. Since you brought up the efficiency tradeoffs, I've put together a few simple benchmarks below for the Map functions where the results are from averaging 10k iterations. As you can see the performance improvement is quite drastic, with both *_many functions being 130%+ .

iex> map

%{a: 1, b: 2, c: 3, d: 4, e: 5, f: 6, g: 7, h: 8, i: 9, j: 10}

iex> kv

[a: 11, d: 22, g: 33, j: 44]

iex> keys

[:a, :d, :g, :j]

iex(32)> Benchmark.measure(10_000, "reduce + replace!", fn -> Enum.reduce(kv, map, fn {k, v}, acc -> Map.replace!(acc, k, v) end) end)

reduce + replace! avg: 18.2396

iex(33)> Benchmark.measure(10_000, "replace_many", fn -> Map.replace_many(map, kv) end)

replace_many avg: 1.0979

iex(34)> Benchmark.measure(10_000, "reduce + update!", fn -> Enum.reduce(keys, map, fn k, acc -> Map.update!(acc, k, &(&1*2)) end) end)

reduce + update! avg: 48.284

iex(35)> Benchmark.measure(10_000, "update_many", fn -> Map.update_many(map, keys, &(&1*2)) end)

update_many avg: 9.8719

[José Valim]

Don’t benchmark in the shell. Code in the shell is evaluated and not compiled.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/63cf4231-5747-4f8e-99f7-87a68a7ab664n%40googlegroups.com.

[Paul Alexander]

Sorry. Would putting them in a test case be better practice? If not, do you mind telling me of the correct way which would produce the most indicative results?

[Wiebe-Marten Wijnja]

Putting them in a module in any file (with e.g. a `.ex` or `.exs` extension) and running them from there will work.
You might also like to look into libraries such as `Benchee` which make benchmarking easier and prevent some of the pitfalls which a homebrew benchmarking implementation might have.

Hope this helps, and happy old year/new year :-),

~Marten

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/cb88ccf3-ece7-47b5-a6d6-7ba5253482bfn%40googlegroups.com.

[Paul Alexander]

Thank you, Marten, for the suggestion. And Happy New Year!

I actually ended up doing that before your reply, except I had used a "homebrew benchmarking" implementation. I also did it with Benchee, and the results really weren't all that different but I've included only the results from Benchee below.  

Name                                 ips        average  deviation         median         99th %

map replace_many                  2.69 M      371.13 ns ±10368.06%           0 ns         990 ns

map for + replace                 2.32 M      430.38 ns  ±8111.30%           0 ns         990 ns

map reduce + replace!             2.32 M      431.63 ns  ±8167.48%           0 ns         990 ns

map update_many                   2.05 M      488.47 ns  ±9258.19%           0 ns         990 ns

map for + update!                 1.64 M      609.13 ns  ±5804.57%           0 ns         990 ns

map reduce + update!              1.66 M      600.64 ns  ±5698.26%           0 ns         990 ns

keywords replace_many             1.91 M      523.22 ns  ±6849.81%           0 ns         990 ns

keywords for + replace!           1.84 M      544.19 ns  ±6432.10%           0 ns         990 ns

keywords reduce + replace!        1.82 M      550.39 ns  ±6488.68%           0 ns         990 ns

keywords update_many              1.78 M      561.74 ns  ±6508.52%           0 ns         990 ns

keywords for + update!            1.49 M      670.96 ns  ±6347.76%           0 ns         990 ns

keywords reduce + update!         1.46 M      686.43 ns  ±6250.71%           0 ns         990 ns

[Paul Alexander]

I believe this is easier to read/follow: 

Name                            ips        average  deviation         median         99th %

map replace_many             1.93 M      517.77 ns  ±9182.17%           0 ns        1000 ns

map reduce + replace!        1.58 M      631.47 ns  ±7266.46%           0 ns        2000 ns

map for + replace            1.58 M      634.43 ns  ±8194.35%           0 ns        2000 ns

Comparison:

map replace_many             1.93 M

map reduce + replace!        1.58 M - 1.22x slower +113.70 ns

map for + replace            1.58 M - 1.23x slower +116.66 ns

Name                           ips        average  deviation         median         99th %

map update_many             1.43 M      701.44 ns  ±7768.55%           0 ns        2000 ns

map for + update!           1.20 M      832.54 ns  ±5683.86%        1000 ns        2000 ns

map reduce + update!        1.17 M      851.53 ns  ±4816.16%        1000 ns        2000 ns

Comparison:

map update_many             1.43 M

map for + update!           1.20 M - 1.19x slower +131.09 ns

map reduce + update!        1.17 M - 1.21x slower +150.08 ns

Name                                 ips        average  deviation         median         99th %

keywords replace_many             1.49 M      669.04 ns  ±5836.31%         980 ns        1980 ns

keywords reduce + replace!        1.41 M      710.24 ns  ±5503.07%         980 ns        1980 ns

keywords for + replace!           1.40 M      714.06 ns  ±5791.74%         980 ns        1980 ns

Comparison:

keywords replace_many             1.49 M

keywords reduce + replace!        1.41 M - 1.06x slower +41.19 ns

keywords for + replace!           1.40 M - 1.07x slower +45.02 ns

Name                                ips        average  deviation         median         99th %

keywords update_many             1.35 M      742.22 ns  ±5371.88%        1000 ns        2000 ns

keywords reduce + update!        1.02 M      976.57 ns  ±5363.65%        1000 ns        2000 ns

keywords for + update!           1.01 M      986.09 ns  ±5456.16%        1000 ns        2000 ns

Comparison:

keywords update_many             1.35 M

keywords reduce + update!        1.02 M - 1.32x slower +234.34 ns

keywords for + update!           1.01 M - 1.33x slower +243.87 ns

Does this sway your opinion on the proposal, José?

[José Valim]

Thank you for sharing!

Can you please share the implementations too? But generally speaking, I don’t think the performance difference is relevant enough to  justify the inclusion.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/7e87dd44-3348-46b9-a0bf-bf4d6a806dffn%40googlegroups.com.

[Paul Alexander]

I understand. I'll scrap this branch then. 

Here are the implementations (if there is any feedback, I'd like to hear it even if it won't be included):

  @spec replace_many(map, keyword) :: map
  def replace_many(map, pairs) when is_list(pairs) do
    replace_pairs(map, pairs, map)
  end

  defp replace_pairs(map, [], _original), do: map

  defp replace_pairs(map, [{key, value} | pairs], original) do
    case original do
      %{^key => _} -> replace_pairs(%{map | key => value}, pairs, original)
      %{} -> raise KeyError, key: key, term: original
      other -> :erlang.error({:badmap, other})
    end
  end

  @spec update_many(map, [atom | String.t()], (existing_value :: value -> new_value :: value)) :: map
  def update_many(map, keys, fun) when is_list(keys) and is_function(fun, 1) do
    update_keys(map, keys, fun, map)
  end

  defp update_keys(map, [], _fun, _original), do: map

  defp update_keys(map, [key | keys], fun, original) do
    case original do
      %{^key => value} -> update_keys(%{map | key => fun.(value)}, keys, fun, original)
      %{} -> raise KeyError, key: key, term: original
      other -> :erlang.error({:badmap, other})
    end
  end

______________________________________________________________________________________________________________________________________

  @spec replace_many(keyword, keyword) :: keyword
  def replace_many(keywords, pairs) when is_list(pairs) do
    replace_pairs(keywords, pairs, keywords)
  end

  defp replace_pairs(keywords, [], _original), do: keywords

  defp replace_pairs(keywords, [{key, value} | pairs], original) do
    replace_pairs(replace!(keywords, key, value, original), pairs, original)
  end

  @spec update_many(keyword, [atom], (existing_value :: value -> new_value :: value)) :: keyword
  def update_many(keywords, keys, fun) when is_list(keys) and is_function(fun) do
    update_keys(keywords, keys, fun, keywords)
  end

  defp update_keys(keywords, [], _fun, _original), do: keywords

  defp update_keys(keywords, [key | keys], fun, original) do
    update_keys(update!(keywords, key, fun, original), keys, fun, original)
  end

Would you also mind directing me to where I can find the implementation of %{map | key => value}? I wasn't able to find it and I'm very curious as to how it works under-the-hood.