From 81eb0eb3dbd047c926482d011244403f68c5dad4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Sun, 19 Apr 2015 09:45:53 +0200 Subject: v3_life: Optimize updating of the variable data base Updating of the variable data base takes most of the time. --- lib/compiler/src/v3_life.erl | 117 ++++++++++++++++++++----------------------- 1 file changed, 53 insertions(+), 64 deletions(-) (limited to 'lib/compiler') diff --git a/lib/compiler/src/v3_life.erl b/lib/compiler/src/v3_life.erl index 75bd188479..4b1f1c3f71 100644 --- a/lib/compiler/src/v3_life.erl +++ b/lib/compiler/src/v3_life.erl @@ -45,7 +45,7 @@ -export([vdb_find/2]). --import(lists, [member/2,map/2,foldl/3,reverse/1,sort/1]). +-import(lists, [member/2,map/2,reverse/1,sort/1]). -import(ordsets, [add_element/2,intersection/2,union/2]). -include("v3_kernel.hrl"). @@ -68,7 +68,7 @@ functions([], Acc) -> reverse(Acc). function(#k_fdef{anno=#k{a=Anno},func=F,arity=Ar,vars=Vs,body=Kb}) -> try As = var_list(Vs), - Vdb0 = foldl(fun ({var,N}, Vdb) -> new_var(N, 0, Vdb) end, [], As), + Vdb0 = init_vars(As), %% Force a top-level match! B0 = case Kb of #k_match{} -> Kb; @@ -94,14 +94,14 @@ function(#k_fdef{anno=#k{a=Anno},func=F,arity=Ar,vars=Vs,body=Kb}) -> body(#k_seq{arg=Ke,body=Kb}, I, Vdb0) -> %%ok = io:fwrite("life ~w:~p~n", [?LINE,{Ke,I,Vdb0}]), A = get_kanno(Ke), - Vdb1 = use_vars(A#k.us, I, new_vars(A#k.ns, I, Vdb0)), + Vdb1 = use_vars(union(A#k.us, A#k.ns), I, Vdb0), {Es,MaxI,Vdb2} = body(Kb, I+1, Vdb1), E = expr(Ke, I, Vdb2), {[E|Es],MaxI,Vdb2}; body(Ke, I, Vdb0) -> %%ok = io:fwrite("life ~w:~p~n", [?LINE,{Ke,I,Vdb0}]), A = get_kanno(Ke), - Vdb1 = use_vars(A#k.us, I, new_vars(A#k.ns, I, Vdb0)), + Vdb1 = use_vars(union(A#k.us, A#k.ns), I, Vdb0), E = expr(Ke, I, Vdb1), {[E],I,Vdb1}. @@ -150,12 +150,12 @@ expr(#k_try_enter{anno=A,arg=Ka,vars=Vs,body=Kb,evars=Evs,handler=Kh}, I, Vdb) - %% the body and handler. Add try tag 'variable'. Ab = get_kanno(Kb), Ah = get_kanno(Kh), - Tdb1 = use_vars(Ab#k.us, I+3, use_vars(Ah#k.us, I+3, Tdb0)), + Tdb1 = use_vars(union(Ab#k.us, Ah#k.us), I+3, Tdb0), Tdb2 = vdb_sub(I, I+2, Tdb1), Vnames = fun (Kvar) -> Kvar#k_var.name end, %Get the variable names {Aes,_,Adb} = body(Ka, I+2, add_var({catch_tag,I+1}, I+1, 1000000, Tdb2)), - {Bes,_,Bdb} = body(Kb, I+4, new_vars(map(Vnames, Vs), I+3, Tdb2)), - {Hes,_,Hdb} = body(Kh, I+4, new_vars(map(Vnames, Evs), I+3, Tdb2)), + {Bes,_,Bdb} = body(Kb, I+4, new_vars(sort(map(Vnames, Vs)), I+3, Tdb2)), + {Hes,_,Hdb} = body(Kh, I+4, new_vars(sort(map(Vnames, Evs)), I+3, Tdb2)), #l{ke={try_enter,#l{ke={block,Aes},i=I+1,vdb=Adb,a=[]}, var_list(Vs),#l{ke={block,Bes},i=I+3,vdb=Bdb,a=[]}, var_list(Evs),#l{ke={block,Hes},i=I+3,vdb=Hdb,a=[]}}, @@ -171,7 +171,7 @@ expr(#k_receive{anno=A,var=V,body=Kb,timeout=T,action=Ka,ret=Rs}, I, Vdb) -> %% Work out imported variables which need to be locked. Rdb = vdb_sub(I, I+1, Vdb), M = match(Kb, add_element(V#k_var.name, A#k.us), I+1, [], - new_var(V#k_var.name, I, Rdb)), + new_vars([V#k_var.name], I, Rdb)), {Tes,_,Adb} = body(Ka, I+1, Rdb), #l{ke={receive_loop,atomic(T),variable(V),M, #l{ke=Tes,i=I+1,vdb=Adb,a=[]},var_list(Rs)}, @@ -199,12 +199,12 @@ body_try(#k_try{anno=A,arg=Ka,vars=Vs,body=Kb,evars=Evs,handler=Kh,ret=Rs}, %% the body and handler. Add try tag 'variable'. Ab = get_kanno(Kb), Ah = get_kanno(Kh), - Tdb1 = use_vars(Ab#k.us, I+3, use_vars(Ah#k.us, I+3, Tdb0)), + Tdb1 = use_vars(union(Ab#k.us, Ah#k.us), I+3, Tdb0), Tdb2 = vdb_sub(I, I+2, Tdb1), Vnames = fun (Kvar) -> Kvar#k_var.name end, %Get the variable names {Aes,_,Adb} = body(Ka, I+2, add_var({catch_tag,I+1}, I+1, locked, Tdb2)), - {Bes,_,Bdb} = body(Kb, I+4, new_vars(map(Vnames, Vs), I+3, Tdb2)), - {Hes,_,Hdb} = body(Kh, I+4, new_vars(map(Vnames, Evs), I+3, Tdb2)), + {Bes,_,Bdb} = body(Kb, I+4, new_vars(sort(map(Vnames, Vs)), I+3, Tdb2)), + {Hes,_,Hdb} = body(Kh, I+4, new_vars(sort(map(Vnames, Evs)), I+3, Tdb2)), #l{ke={'try',#l{ke={block,Aes},i=I+1,vdb=Adb,a=[]}, var_list(Vs),#l{ke={block,Bes},i=I+3,vdb=Bdb,a=[]}, var_list(Evs),#l{ke={block,Hes},i=I+3,vdb=Hdb,a=[]}, @@ -400,79 +400,68 @@ is_gc_bif(Bif, Arity) -> erl_internal:new_type_test(Bif, Arity) orelse erl_internal:comp_op(Bif, Arity)). -%% new_var(VarName, I, Vdb) -> Vdb. +%% Keep track of life time for variables. +%% +%% init_vars([{var,VarName}]) -> Vdb. %% new_vars([VarName], I, Vdb) -> Vdb. -%% use_var(VarName, I, Vdb) -> Vdb. %% use_vars([VarName], I, Vdb) -> Vdb. %% add_var(VarName, F, L, Vdb) -> Vdb. +%% +%% The list of variable names for new_vars/3 and use_vars/3 +%% must be sorted. -new_var(V, I, Vdb) -> - vdb_store_new(V, I, I, Vdb). +init_vars(Vs) -> + sort([{V,0,0} || {var,V} <- Vs]). -new_vars(Vs, I, Vdb0) -> - foldl(fun (V, Vdb) -> new_var(V, I, Vdb) end, Vdb0, Vs). +new_vars([], _, Vdb) -> Vdb; +new_vars([V], I, Vdb) -> vdb_store_new(V, {V,I,I}, Vdb); +new_vars(Vs, I, Vdb) -> vdb_update_vars(Vs, Vdb, I). -use_var(V, I, Vdb) -> +use_vars([], _, Vdb) -> + Vdb; +use_vars([V], I, Vdb) -> case vdb_find(V, Vdb) of - {V,F,L} when I > L -> vdb_update(V, F, I, Vdb); + {V,F,L} when I > L -> vdb_update(V, {V,F,I}, Vdb); {V,_,_} -> Vdb; - error -> vdb_store_new(V, I, I, Vdb) - end. - -use_vars([], _, Vdb) -> Vdb; -use_vars([V], I, Vdb) -> use_var(V, I, Vdb); -use_vars(Vs, I, Vdb) -> - Res = use_vars_1(sort(Vs), Vdb, I), - %% The following line can be used as an assertion. - %% Res = foldl(fun (V, Vdb) -> use_var(V, I, Vdb) end, Vdb, Vs), - Res. - -%% Measurements show that it is worthwhile having this special -%% function that updates/inserts several variables at once. - -use_vars_1([V|_]=Vs, [{V1,_,_}=Vd|Vdb], I) when V > V1 -> - [Vd|use_vars_1(Vs, Vdb, I)]; -use_vars_1([V|Vs], [{V1,_,_}|_]=Vdb, I) when V < V1 -> - %% New variable. - [{V,I,I}|use_vars_1(Vs, Vdb, I)]; -use_vars_1([V|Vs], [{_,F,L}=Vd|Vdb], I) -> - %% Existing variable. - if - I > L ->[{V,F,I}|use_vars_1(Vs, Vdb, I)]; - true -> [Vd|use_vars_1(Vs, Vdb, I)] + error -> vdb_store_new(V, {V,I,I}, Vdb) end; -use_vars_1([V|Vs], [], I) -> - %% New variable. - [{V,I,I}|use_vars_1(Vs, [], I)]; -use_vars_1([], Vdb, _) -> Vdb. +use_vars(Vs, I, Vdb) -> vdb_update_vars(Vs, Vdb, I). add_var(V, F, L, Vdb) -> - vdb_store_new(V, F, L, Vdb). + vdb_store_new(V, {V,F,L}, Vdb). vdb_find(V, Vdb) -> - %% Performance note: Profiling shows that this function accounts for - %% a lot of the execution time when huge constant terms are built. - %% Using the BIF lists:keyfind/3 is a lot faster than the - %% original Erlang version. case lists:keyfind(V, 1, Vdb) of false -> error; Vd -> Vd end. -%vdb_find(V, [{V1,F,L}=Vd|Vdb]) when V < V1 -> error; -%vdb_find(V, [{V1,F,L}=Vd|Vdb]) when V == V1 -> Vd; -%vdb_find(V, [{V1,F,L}=Vd|Vdb]) when V > V1 -> vdb_find(V, Vdb); -%vdb_find(V, []) -> error. +vdb_update(V, Update, [{V,_,_}|Vdb]) -> + [Update|Vdb]; +vdb_update(V, Update, [Vd|Vdb]) -> + [Vd|vdb_update(V, Update, Vdb)]. -vdb_update(V, F, L, [{V1,_,_}=Vd|Vdb]) when V > V1 -> - [Vd|vdb_update(V, F, L, Vdb)]; -vdb_update(V, F, L, [{V1,_,_}|Vdb]) when V == V1 -> - [{V,F,L}|Vdb]. +vdb_store_new(V, New, [{V1,_,_}=Vd|Vdb]) when V > V1 -> + [Vd|vdb_store_new(V, New, Vdb)]; +vdb_store_new(V, New, [{V1,_,_}|_]=Vdb) when V < V1 -> + [New|Vdb]; +vdb_store_new(_, New, []) -> [New]. -vdb_store_new(V, F, L, [{V1,_,_}=Vd|Vdb]) when V > V1 -> - [Vd|vdb_store_new(V, F, L, Vdb)]; -vdb_store_new(V, F, L, [{V1,_,_}|_]=Vdb) when V < V1 -> [{V,F,L}|Vdb]; -vdb_store_new(V, F, L, []) -> [{V,F,L}]. +vdb_update_vars([V|_]=Vs, [{V1,_,_}=Vd|Vdb], I) when V > V1 -> + [Vd|vdb_update_vars(Vs, Vdb, I)]; +vdb_update_vars([V|Vs], [{V1,_,_}|_]=Vdb, I) when V < V1 -> + %% New variable. + [{V,I,I}|vdb_update_vars(Vs, Vdb, I)]; +vdb_update_vars([V|Vs], [{_,F,L}=Vd|Vdb], I) -> + %% Existing variable. + if + I > L -> [{V,F,I}|vdb_update_vars(Vs, Vdb, I)]; + true -> [Vd|vdb_update_vars(Vs, Vdb, I)] + end; +vdb_update_vars([V|Vs], [], I) -> + %% New variable. + [{V,I,I}|vdb_update_vars(Vs, [], I)]; +vdb_update_vars([], Vdb, _) -> Vdb. %% vdb_sub(Min, Max, Vdb) -> Vdb. %% Extract variables which are used before and after Min. Lock -- cgit v1.2.3