From 4a500f9b898847afdf5c5441fb21d962cd75b90a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Fri, 16 Sep 2016 11:33:20 +0200 Subject: compiler: Allow for unaligned match argument in value groups At this stage in match compilation we are allowed to change the alignment of arguments and constructors as long as they are the same aligned in the same group. --- lib/compiler/src/v3_kernel.erl | 36 ++++++++++++++++++------------------ 1 file changed, 18 insertions(+), 18 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl index f8e99905b5..450547d691 100644 --- a/lib/compiler/src/v3_kernel.erl +++ b/lib/compiler/src/v3_kernel.erl @@ -1350,10 +1350,10 @@ select(T, Cs) -> [ C || C <- Cs, clause_con(C) =:= T ]. %% At this point all the clauses have the same constructor, we must %% now separate them according to value. -match_value(Us, T, Cs0, Def, St0) -> - Css = group_value(T, Cs0), +match_value(Us0, T, Cs0, Def, St0) -> + UCss = group_value(T, Us0, Cs0), %%ok = io:format("match_value ~p ~p~n", [T, Css]), - mapfoldl(fun (Cs, St) -> match_clause(Us, Cs, Def, St) end, St0, Css). + mapfoldl(fun ({Us,Cs}, St) -> match_clause(Us, Cs, Def, St) end, St0, UCss). %% group_value([Clause]) -> [[Clause]]. %% Group clauses according to value. Here we know that @@ -1361,30 +1361,30 @@ match_value(Us, T, Cs0, Def, St0) -> %% 2. The clauses in bin_segs cannot be reordered only grouped %% 3. Other types are disjoint and can be reordered -group_value(k_cons, Cs) -> [Cs]; %These are single valued -group_value(k_nil, Cs) -> [Cs]; -group_value(k_binary, Cs) -> [Cs]; -group_value(k_bin_end, Cs) -> [Cs]; -group_value(k_bin_seg, Cs) -> group_bin_seg(Cs); -group_value(k_bin_int, Cs) -> [Cs]; -group_value(k_map, Cs) -> group_map(Cs); -group_value(_, Cs) -> +group_value(k_cons, Us, Cs) -> [{Us,Cs}]; %These are single valued +group_value(k_nil, Us, Cs) -> [{Us,Cs}]; +group_value(k_binary, Us, Cs) -> [{Us,Cs}]; +group_value(k_bin_end, Us, Cs) -> [{Us,Cs}]; +group_value(k_bin_seg, Us, Cs) -> group_bin_seg(Us,Cs); +group_value(k_bin_int, Us, Cs) -> [{Us,Cs}]; +group_value(k_map, Us, Cs) -> group_map(Us,Cs); +group_value(_, Us, Cs) -> %% group_value(Cs). Cd = foldl(fun (C, Gcs0) -> dict:append(clause_val(C), C, Gcs0) end, dict:new(), Cs), - dict:fold(fun (_, Vcs, Css) -> [Vcs|Css] end, [], Cd). + dict:fold(fun (_, Vcs, Css) -> [{Us,Vcs}|Css] end, [], Cd). -group_bin_seg([C1|Cs]) -> +group_bin_seg(Us, [C1|Cs]) -> V1 = clause_val(C1), {More,Rest} = splitwith(fun (C) -> clause_val(C) == V1 end, Cs), - [[C1|More]|group_bin_seg(Rest)]; -group_bin_seg([]) -> []. + [{Us,[C1|More]}|group_bin_seg(Us,Rest)]; +group_bin_seg(_, []) -> []. -group_map([C1|Cs]) -> +group_map(Us, [C1|Cs]) -> V1 = clause_val(C1), {More,Rest} = splitwith(fun (C) -> clause_val(C) =:= V1 end, Cs), - [[C1|More]|group_map(Rest)]; -group_map([]) -> []. + [{Us,[C1|More]}|group_map(Us,Rest)]; +group_map(_, []) -> []. %% Profiling shows that this quadratic implementation account for a big amount %% of the execution time if there are many values. -- cgit v1.2.3 From caa3c36a331009fa69c7a524090f455e9e296987 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 6 Sep 2016 08:05:32 +0200 Subject: compiler: Optimize maps pattern matching --- lib/compiler/src/v3_kernel.erl | 65 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 63 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl index 450547d691..a535cc4fc1 100644 --- a/lib/compiler/src/v3_kernel.erl +++ b/lib/compiler/src/v3_kernel.erl @@ -151,6 +151,7 @@ include_attribute(optional_callbacks) -> false; include_attribute(_) -> true. function({#c_var{name={F,Arity}=FA},Body}, St0) -> + %%io:format("~w/~w~n", [F,Arity]), try St1 = St0#kern{func=FA,ff=undefined,vcount=0,fcount=0,ds=cerl_sets:new()}, {#ifun{anno=Ab,vars=Kvs,body=B0},[],St2} = expr(Body, new_sub(), St1), @@ -1351,9 +1352,69 @@ select(T, Cs) -> [ C || C <- Cs, clause_con(C) =:= T ]. %% now separate them according to value. match_value(Us0, T, Cs0, Def, St0) -> - UCss = group_value(T, Us0, Cs0), + {Us1,Cs1,St1} = partition_intersection(T, Us0, Cs0, St0), + UCss = group_value(T, Us1, Cs1), %%ok = io:format("match_value ~p ~p~n", [T, Css]), - mapfoldl(fun ({Us,Cs}, St) -> match_clause(Us, Cs, Def, St) end, St0, UCss). + mapfoldl(fun ({Us,Cs}, St) -> match_clause(Us, Cs, Def, St) end, St1, UCss). + +%% partition_intersection +%% Partitions a map into two maps with the most common keys to the first map. +%% case of +%% <#{a}> +%% <#{a,b}> +%% <#{a,c}> +%% <#{c}> +%% end +%% becomes +%% case of +%% <#{a}, #{ }> +%% <#{a}, #{b}> +%% <#{ }, #{c}> +%% <#{a}, #{c}> +%% end +%% The intention is to group as many keys together as possible and thus +%% reduce the number of lookups to that key. +partition_intersection(k_map, [U|_]=Us0, [_,_|_]=Cs0,St0) -> + Ps = [clause_val(C) || C <- Cs0], + case find_key_partition(Ps) of + no_partition -> + {Us0,Cs0,St0}; + Ks -> + {Cs1,St1} = mapfoldl(fun(#iclause{pats=[Arg|Args]}=C, Sti) -> + {{Arg1,Arg2},St} = partition_key_intersection(Arg, Ks, Sti), + {C#iclause{pats=[Arg1,Arg2|Args]}, St} + end, St0, Cs0), + {[U|Us0],Cs1,St1} + end; +partition_intersection(_, Us, Cs, St) -> + {Us,Cs,St}. + +partition_key_intersection(#k_map{es=Pairs}=Map,Ks,St0) -> + F = fun(#k_map_pair{key=Key}) -> member(map_key_clean(Key), Ks) end, + {Ps1,Ps2} = partition(F, Pairs), + {{Map#k_map{es=Ps1},Map#k_map{es=Ps2}},St0}; +partition_key_intersection(#ialias{pat=Map}=Alias,Ks,St0) -> + %% only alias one of them + {{Map1,Map2},St1} = partition_key_intersection(Map, Ks, St0), + {{Map1,Alias#ialias{pat=Map2}},St1}. + +% Only check for the complete intersection of keys and not commonality +find_key_partition(Ps) -> + Sets = [sets:from_list(Ks)||Ks <- Ps], + Is = sets:intersection(Sets), + case sets:to_list(Is) of + [] -> no_partition; + KeyIntersection -> + %% Check if the intersection are all keys in all clauses. + %% Don't split if they are since this will only + %% infer extra is_map instructions with no gain. + All = foldl(fun (Kset, Bool) -> + Bool andalso sets:is_subset(Kset, Is) + end, true, Sets), + if All -> no_partition; + true -> KeyIntersection + end + end. %% group_value([Clause]) -> [[Clause]]. %% Group clauses according to value. Here we know that -- cgit v1.2.3 From 3ea07934071541d70d8016447b0194c8b551c104 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Fri, 16 Sep 2016 17:36:26 +0200 Subject: compiler: Add regression tests --- lib/compiler/test/regressions_SUITE.erl | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/compiler/test/regressions_SUITE.erl b/lib/compiler/test/regressions_SUITE.erl index 7d2c2ac974..7a6fe08c73 100644 --- a/lib/compiler/test/regressions_SUITE.erl +++ b/lib/compiler/test/regressions_SUITE.erl @@ -24,7 +24,7 @@ -export([all/0,groups/0,init_per_testcase/2,end_per_testcase/2,suite/0]). -export([maps/1]). -groups() -> +groups() -> [{p,test_lib:parallel(), [maps]}]. @@ -38,7 +38,7 @@ suite() -> [{ct_hooks,[ts_install_cth]}, {timetrap,{minutes,2}}]. -all() -> +all() -> test_lib:recompile(?MODULE), [{group,p}]. @@ -48,7 +48,18 @@ maps(Config) when is_list(Config) -> Ts = [{beam_bool_get_elements, <<"century(#{ron := operator}, _century) -> if 0.0; _century, _century, _century -> _century end. - ">>}], + ">>}, + {empty_map_clauses, + <<"politics(#{}, researchers) -> concerned; + politics(#{[] := _}, workers) -> dot; + politics(#{[] := ct}, counsel) -> calls. + ">>}, + {empty_map_clauses_variable, + <<"georgia(#{a := effectively}, ratio, is, eventually) -> teens; + georgia(#{a := government}, knowledge, poker, partly) -> signed; + georgia(#{}, recording, bring, vital) -> divided; + georgia(#{0 := 0}, articles, brought, #{true := true, a := There}) -> There. + ">>}], ok = run(Config, Ts), ok. @@ -58,7 +69,7 @@ run(Config, Tests) -> F = fun({N,P}) -> io:format("Compiling test for: ~w~n", [N]), case catch run_test(Config, P) of - {'EXIT', Reason} -> + {'EXIT', Reason} -> io:format("~nTest ~p failed.~nReason: ~p~n", [N, Reason]), fail(); -- cgit v1.2.3