From 6753bbcc3fdb0dd15c8025902d22dc4ec8c33575 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 20 Oct 2017 06:11:04 +0200 Subject: Optimize matching of literals for single-valued types If a type only has one clause and if the pattern is literal, the matching can be done more efficiently by directly comparing with the literal. Example: find(String, "") -> String; find(String, <<>>) -> String; find(String, SearchPattern) -> . . . Without this optimization, the relevant part of the code would look this: {test,bs_start_match2,{f,3},2,[{x,1},0],{x,2}}. {test,bs_test_tail2,{f,4},[{x,2},0]}. return. {label,3}. {test,is_nil,{f,4},[{x,1}]}. return. {label,4}. . . . That is, if {x,1} is a binary, a match context will be built to test whether {x,1} is an empty binary. With the optimization, the code will look this: {test,is_eq_exact,{f,3},[{x,1},{literal,<<>>}]}. return. {label,3}. {test,is_nil,{f,4},[{x,1}]}. return. {label,4}. . . . --- lib/compiler/src/v3_codegen.erl | 11 +++ lib/compiler/src/v3_kernel.erl | 147 +++++++++++++++++++++++++++++++--------- 2 files changed, 126 insertions(+), 32 deletions(-) diff --git a/lib/compiler/src/v3_codegen.erl b/lib/compiler/src/v3_codegen.erl index e705aefb96..ee5bafbc5c 100644 --- a/lib/compiler/src/v3_codegen.erl +++ b/lib/compiler/src/v3_codegen.erl @@ -654,6 +654,8 @@ select_cg(#l{ke={type_clause,bin_end,[S]}}, {var,V}, Tf, _Vf, Bef, St) -> select_bin_end(S, V, Tf, Bef, St); select_cg(#l{ke={type_clause,map,S}}, {var,V}, Tf, Vf, Bef, St) -> select_map(S, V, Tf, Vf, Bef, St); +select_cg(#l{ke={type_clause,literal,S}}, {var,V}, Tf, Vf, Bef, St) -> + select_literal(S, V, Tf, Vf, Bef, St); select_cg(#l{ke={type_clause,Type,Scs}}, {var,V}, Tf, Vf, Bef, St0) -> {Vis,{Aft,St1}} = mapfoldl(fun (S, {Int,Sta}) -> @@ -695,6 +697,15 @@ add_vls([V|Vs], Lbl, Acc) -> add_vls(Vs, Lbl, [V, {f,Lbl}|Acc]); add_vls([], _, Acc) -> Acc. +select_literal(S, V, Tf, Vf, Bef, St) -> + Reg = fetch_var(V, Bef), + F = fun(ValClause, Fail, St0) -> + {Val,Is,Aft,St1} = select_val(ValClause, V, Vf, Bef, St0), + Test = {test,is_eq_exact,{f,Fail},[Reg,{literal,Val}]}, + {[Test|Is],Aft,St1} + end, + match_fmf(F, Tf, St, S). + select_cons(#l{ke={val_clause,{cons,Es},B},i=I,vdb=Vdb}, V, Tf, Vf, Bef, St0) -> {Eis,Int,St1} = select_extract_cons(V, Es, I, Vdb, Bef, St0), {Bis,Aft,St2} = match_cg(B, Vf, Int, St1), diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl index 1fc05109c5..cbc8bb1303 100644 --- a/lib/compiler/src/v3_kernel.erl +++ b/lib/compiler/src/v3_kernel.erl @@ -82,7 +82,8 @@ -export([module/2,format_error/1]). -import(lists, [map/2,foldl/3,foldr/3,mapfoldl/3,splitwith/2,member/2, - keymember/3,keyfind/3,partition/2,droplast/1,last/1,sort/1]). + keymember/3,keyfind/3,partition/2,droplast/1,last/1,sort/1, + reverse/1]). -import(ordsets, [add_element/2,del_element/2,union/2,union/1,subtract/2]). -import(cerl, [c_tuple/1]). @@ -1589,23 +1590,18 @@ match_var([U|Us], Cs0, Def, St) -> %% according to type, the order is really irrelevant but tries to be %% smart. -match_con(Us, [C], Def, St) -> - %% There is only one clause. We can keep literal tuples and - %% lists, but we must convert []/integer/float/atom literals - %% to the proper record (#k_nil{} and so on). - Cs = [expand_pat_lit_clause(C, false)], - match_con_1(Us, Cs, Def, St); match_con(Us, Cs0, Def, St) -> - %% More than one clause. Remove literals at the top level. - Cs = [expand_pat_lit_clause(C, true) || C <- Cs0], + %% Expand literals at the top level. + Cs = [expand_pat_lit_clause(C) || C <- Cs0], match_con_1(Us, Cs, Def, St). match_con_1([U|_Us] = L, Cs, Def, St0) -> %% Extract clauses for different constructors (types). %%ok = io:format("match_con ~p~n", [Cs]), - Ttcs = select_types([k_binary], Cs) ++ select_bin_con(Cs) ++ - select_types([k_cons,k_tuple,k_map,k_atom,k_float,k_int, - k_nil,k_literal], Cs), + Ttcs0 = select_types([k_binary], Cs) ++ select_bin_con(Cs) ++ + select_types([k_cons,k_tuple,k_map,k_atom,k_float, + k_int,k_nil], Cs), + Ttcs = opt_single_valued(Ttcs0), %%ok = io:format("ttcs = ~p~n", [Ttcs]), {Scs,St1} = mapfoldl(fun ({T,Tcs}, St) -> @@ -1618,28 +1614,14 @@ match_con_1([U|_Us] = L, Cs, Def, St0) -> select_types(Types, Cs) -> [{T,Tcs} || T <- Types, begin Tcs = select(T, Cs), Tcs =/= [] end]. - -expand_pat_lit_clause(#iclause{pats=[#ialias{pat=#k_literal{anno=A,val=Val}}=Alias|Ps]}=C, B) -> - P = case B of - true -> expand_pat_lit(Val, A); - false -> literal(Val, A) - end, + +expand_pat_lit_clause(#iclause{pats=[#ialias{pat=#k_literal{anno=A,val=Val}}=Alias|Ps]}=C) -> + P = expand_pat_lit(Val, A), C#iclause{pats=[Alias#ialias{pat=P}|Ps]}; -expand_pat_lit_clause(#iclause{pats=[#k_literal{anno=A,val=Val}|Ps]}=C, B) -> - P = case B of - true -> expand_pat_lit(Val, A); - false -> literal(Val, A) - end, +expand_pat_lit_clause(#iclause{pats=[#k_literal{anno=A,val=Val}|Ps]}=C) -> + P = expand_pat_lit(Val, A), C#iclause{pats=[P|Ps]}; -expand_pat_lit_clause(#iclause{pats=[#k_binary{anno=A,segs=#k_bin_end{}}|Ps]}=C, B) -> - case B of - true -> - C; - false -> - P = #k_literal{anno=A,val = <<>>}, - C#iclause{pats=[P|Ps]} - end; -expand_pat_lit_clause(C, _) -> C. +expand_pat_lit_clause(C) -> C. expand_pat_lit([H|T], A) -> #k_cons{anno=A,hd=literal(H, A),tl=literal(T, A)}; @@ -1659,6 +1641,107 @@ literal(Val, A) when is_atom(Val) -> literal(Val, A) when is_list(Val); is_tuple(Val) -> #k_literal{anno=A,val=Val}. +%% opt_singled_valued([{Type,Clauses}]) -> [{Type,Clauses}]. +%% If a type only has one clause and if the pattern is literal, +%% the matching can be done more efficiently by directly comparing +%% with the literal (that is especially true for binaries). + +opt_single_valued(Ttcs) -> + opt_single_valued(Ttcs, [], []). + +opt_single_valued([{_,[#iclause{pats=[P0|Ps]}=Tc]}=Ttc|Ttcs], TtcAcc, LitAcc) -> + try combine_lit_pat(P0) of + P -> + LitTtc = Tc#iclause{pats=[P|Ps]}, + opt_single_valued(Ttcs, TtcAcc, [LitTtc|LitAcc]) + catch + not_possible -> + opt_single_valued(Ttcs, [Ttc|TtcAcc], LitAcc) + end; +opt_single_valued([Ttc|Ttcs], TtcAcc, LitAcc) -> + opt_single_valued(Ttcs, [Ttc|TtcAcc], LitAcc); +opt_single_valued([], TtcAcc, []) -> + reverse(TtcAcc); +opt_single_valued([], TtcAcc, LitAcc) -> + Literals = {k_literal,reverse(LitAcc)}, + %% Test the literals as early as possible. + case reverse(TtcAcc) of + [{k_binary,_}=Bin|Ttcs] -> + %% The delayed creation of sub binaries requires + %% bs_start_match2 to be the first instruction in the + %% function. + [Bin,Literals|Ttcs]; + Ttcs -> + [Literals|Ttcs] + end. + +combine_lit_pat(#ialias{pat=Pat0}=Alias) -> + Pat = combine_lit_pat(Pat0), + Alias#ialias{pat=Pat}; +combine_lit_pat(Pat) -> + case do_combine_lit_pat(Pat) of + #k_literal{val=Val} when is_atom(Val) -> + throw(not_possible); + #k_literal{val=Val} when is_number(Val) -> + throw(not_possible); + #k_literal{val=[]} -> + throw(not_possible); + #k_literal{}=Lit -> + Lit + end. + +do_combine_lit_pat(#k_atom{anno=A,val=Val}) -> + #k_literal{anno=A,val=Val}; +do_combine_lit_pat(#k_float{anno=A,val=Val}) -> + #k_literal{anno=A,val=Val}; +do_combine_lit_pat(#k_int{anno=A,val=Val}) -> + #k_literal{anno=A,val=Val}; +do_combine_lit_pat(#k_nil{anno=A}) -> + #k_literal{anno=A,val=[]}; +do_combine_lit_pat(#k_binary{anno=A,segs=Segs}) -> + Bin = combine_bin_segs(Segs), + #k_literal{anno=A,val=Bin}; +do_combine_lit_pat(#k_cons{anno=A,hd=Hd0,tl=Tl0}) -> + #k_literal{val=Hd} = do_combine_lit_pat(Hd0), + #k_literal{val=Tl} = do_combine_lit_pat(Tl0), + #k_literal{anno=A,val=[Hd|Tl]}; +do_combine_lit_pat(#k_literal{}=Lit) -> + Lit; +do_combine_lit_pat(#k_tuple{anno=A,es=Es0}) -> + Es = [begin + #k_literal{val=Lit} = do_combine_lit_pat(El), + Lit + end || El <- Es0], + #k_literal{anno=A,val=list_to_tuple(Es)}; +do_combine_lit_pat(_) -> + throw(not_possible). + +combine_bin_segs(#k_bin_seg{size=Size0,unit=Unit,type=integer, + flags=[unsigned,big],seg=Seg,next=Next}) -> + #k_literal{val=Size1} = do_combine_lit_pat(Size0), + #k_literal{val=Int} = do_combine_lit_pat(Seg), + Size = Size1 * Unit, + if + 0 < Size, Size < 64 -> + Bin = <>, + case Bin of + <> -> + NextBin = combine_bin_segs(Next), + <>; + _ -> + %% The integer Int does not fit in the segment, + %% thus it will not match. + throw(not_possible) + end; + true -> + %% Avoid creating huge binary literals. + throw(not_possible) + end; +combine_bin_segs(#k_bin_end{}) -> + <<>>; +combine_bin_segs(_) -> + throw(not_possible). + %% select_bin_con([Clause]) -> [{Type,[Clause]}]. %% Extract clauses for the k_bin_seg constructor. As k_bin_seg %% matching can overlap, the k_bin_seg constructors cannot be -- cgit v1.2.3