Improved maps:with/2 and maps:without/2 algorithm

The current implementation is roughly O(N*M) where N is the number of items to be removed, and M is the number of items in the map. This does not include the cost of `maps:from_list` or `maps:to_list`. This leads to pretty horrifying execution times on large maps regardless of how many or few keys are to be removed.

The new implementation is O(N) where N is the number of items to be removed. For each N there's the cost of removing a key from a map, and but in practice that turns out to be a vast improvement for all map sizes I tested

The new maps:take/2 implementation similarly builds a list of keys and values by iterating only the list of desired keys, and then hands it off to maps:from_list. This turned out to be faster than N maps:put calls.

1 files changed, 11 insertions, 3 deletions

diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl
index 3c798b7a04..43d10f4800 100644
--- a/lib/stdlib/src/maps.erl
+++ b/lib/stdlib/src/maps.erl
@@ -205,7 +205,7 @@ size(Val) ->
     K :: term().
 
 without(Ks,M) when is_list(Ks), is_map(M) ->
-    maps:from_list([{K,V}||{K,V} <- maps:to_list(M), not lists:member(K, Ks)]);
+    lists:foldl(fun(K, M1) -> ?MODULE:remove(K, M1) end, M, Ks);
 without(Ks,M) ->
     erlang:error(error_type(M),[Ks,M]).
 
@@ -216,8 +216,16 @@ without(Ks,M) ->
     Map2 :: map(),
     K :: term().
 
-with(Ks,M) when is_list(Ks), is_map(M) ->
-    maps:from_list([{K,V}||{K,V} <- maps:to_list(M), lists:member(K, Ks)]);
+with(Ks,Map1) when is_list(Ks), is_map(Map1) ->
+    Fun = fun(K, List) ->
+      case ?MODULE:find(K, Map1) of
+          {ok, V} ->
+              [{K, V} | List];
+          error ->
+              List
+      end
+    end,
+    ?MODULE:from_list(lists:foldl(Fun, [], Ks));
 with(Ks,M) ->
     erlang:error(error_type(M),[Ks,M]).