From 73b7692a1b9f3b8e810e5528f574b230f4299788 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 10 Dec 2013 16:10:58 +0100 Subject: Eliminate bottlenecks in sys_core_fold Compiling programs with very many uses of the "dot notation" for extracting a record element could be very slow. The reason is that each extraction of a record element (R#r.a) would first be transformed to code like this: case R of {r,rec0,_,_} -> rec0; _ -> error({badrecord,r}) end In Core Erlang, each '_' would be become a new variable. The resulting code would be optimized by sys_core_fold, but the optimization process could be very slow. Profiling shows that sub_del_var/2 was the worst bottleneck, and the sub_is_val/2 the second worst bottleneck. In both cases, the culprit is the linear traversal of a very long list (the list of variable substitutions). Fortunately, there already is a gb_set (the scope) which contains all variables that are currently live. If a variable is not known to be live, it is no point in doing the linear operation on the list. --- lib/compiler/src/sys_core_fold.erl | 35 +++++++++++++++++++++++++---------- 1 file changed, 25 insertions(+), 10 deletions(-) diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl index 6b0ae87172..e2002c8e48 100644 --- a/lib/compiler/src/sys_core_fold.erl +++ b/lib/compiler/src/sys_core_fold.erl @@ -1452,14 +1452,14 @@ let_subst_list([], [], _) -> {[],[],[]}. %%pattern(Pat, Sub) -> pattern(Pat, Sub, Sub). -pattern(#c_var{name=V0}=Pat, Isub, Osub) -> +pattern(#c_var{}=Pat, Isub, Osub) -> case sub_is_val(Pat, Isub) of true -> V1 = make_var_name(), Pat1 = #c_var{name=V1}, {Pat1,sub_set_var(Pat, Pat1, scope_add([V1], Osub))}; false -> - {Pat,sub_del_var(Pat, scope_add([V0], Osub))} + {Pat,sub_del_var(Pat, Osub)} end; pattern(#c_literal{}=Pat, _, Osub) -> {Pat,Osub}; pattern(#c_cons{anno=Anno,hd=H0,tl=T0}, Isub, Osub0) -> @@ -1522,6 +1522,9 @@ is_subst(_) -> false. %% chains so we never have to search more than once. Use orddict so %% we know the format. %% +%% In addition to the list of substitutions, we also keep track of +%% all variable currently live (the scope). +%% %% sub_subst_scope/1 adds dummy substitutions for all variables %% in the scope in order to force renaming if variables in the %% scope occurs as pattern variables. @@ -1548,8 +1551,17 @@ sub_set_name(V, Val, #sub{v=S,s=Scope,t=Tdb0}=Sub) -> Tdb = copy_type(V, Val, Tdb1), Sub#sub{v=orddict:store(V, Val, S),s=gb_sets:add(V, Scope),t=Tdb}. -sub_del_var(#c_var{name=V}, #sub{v=S,t=Tdb}=Sub) -> - Sub#sub{v=orddict:erase(V, S),t=kill_types(V, Tdb)}. +sub_del_var(#c_var{name=V}, #sub{v=S,s=Scope,t=Tdb}=Sub) -> + %% Profiling shows that for programs with many record operations, + %% sub_del_var/2 is a bottleneck. Since the scope contains all + %% variables that are live, we know that V cannot be present in S + %% if it is not in the scope. + case gb_sets:is_member(V, Scope) of + false -> + Sub#sub{s=gb_sets:insert(V, Scope)}; + true -> + Sub#sub{v=orddict:erase(V, S),t=kill_types(V, Tdb)} + end. sub_subst_var(#c_var{name=V}, Val, #sub{v=S0}) -> %% Fold chained substitutions. @@ -1559,13 +1571,16 @@ sub_subst_scope(#sub{v=S0,s=Scope}=Sub) -> S = [{-1,#c_var{name=Sv}} || Sv <- gb_sets:to_list(Scope)]++S0, Sub#sub{v=S}. -sub_is_val(#c_var{name=V}, #sub{v=S}) -> - v_is_value(V, S). +sub_is_val(#c_var{name=V}, #sub{v=S,s=Scope}) -> + %% When the bottleneck in sub_del_var/2 was eliminated, this + %% became the new bottleneck. Since the scope contains all + %% live variables, a variable V can only be the target for + %% a substitution if it is in the scope. + gb_sets:is_member(V, Scope) andalso v_is_value(V, S). -v_is_value(Var, Sub) -> - any(fun ({_,#c_var{name=Val}}) when Val =:= Var -> true; - (_) -> false - end, Sub). +v_is_value(Var, [{_,#c_var{name=Var}}|_]) -> true; +v_is_value(Var, [_|T]) -> v_is_value(Var, T); +v_is_value(_, []) -> false. %% clauses(E, [Clause], TopLevel, Context, Sub) -> [Clause]. %% Trim the clauses by removing all clauses AFTER the first one which -- cgit v1.2.3