Performance #1513

Fflath · 2022-06-17T17:37:51Z

Fflath
Jun 17, 2022

I started playing around with prolog recently. Built the hello world of genetic algorithms (onemax). Evolve from a random list of ones and zeros a list of all ones. It works but it is slow.

I'm not really looking for ways to super optimize this. I'm hoping for some advice on how to make this fast enough to just play around with more complex evolution tasks without having to go crazy with optimizations. Are there some simple things that I can change to make this usably performant? Anything I did that was dumb from a prolog programming standpoint?

I replaced append and flatten with dcgs.

:- use_module(library(random)).
:- use_module(library(clpz)).
:- use_module(library(lists)).
:- use_module(library(lambda)).
:- use_module(library(serialization/abnf)).


test :- run(100,100,500,PN),
	[H|_] = PN,
	write(H).

run(Count,Length,MaxAge,PN) :- 
	genPop(Count,Length,P0),
	evolve(P0,PN,MaxAge).

% sorts the population by order of decreasing fitness
evaluate(P0, P1, Max) :-
	maplist(sum_list, P0, S0),
	zip(S0,P0, S1),
	keysort(S1, S2),
	reverse(S2, S3),
	[Max|_]=S3,
	zip(_, P1,S3).

% group pairs of members together as parents for the next gen
selection(P0, P1) :-
	findall(W,sliding_window(P0,2,W),T0), every_other(T0, P1).
	
% generate the next population from the list of parents
crossover(P0, P1) :-
	maplist(\X^mutate(X),P0, T0),
	mix(P1,T0).
 
% evolution loop run until Age or early stopping
evolve(P0,PN, Age) :- evolve(P0,PN,0,Age).

evolve(PN,PN, _, _) :- % early stopping branch
	[H|_]=PN,
	length(H, L),
	sum_list(H,L).
evolve(PN,PN, Age, Age). % stopped by max age

evolve(P0,PN, Acc, Age) :-
	Acc #< Age,
	NAcc #= Acc + 1,
	evaluate(P0, E0, M),
	S-_ = M,
	write(S), nl,
	selection(E0,S0),
	crossover(S0, P1),
	evolve(P1, PN, NAcc, Age).

% get a list of 1s and 0s
genPop_single(Length, Member) :- length(T,Length), maplist(\_^random_integer(0,2), T, Member).
genPop(Count, Length, Population) :- length(T,Count), maplist(\_^genPop_single(Length), T, Population).

% generate children from parents
mutate([A,B],[C,D]) :-
	length(A,L),random_integer(0,L,H),
	split(A, Af, Ab, H), split(B, Bf, Bb, H),
	split(C, Af, Bb, H), split(D, Bf, Ab, H).

% utilities

sliding_window(List, Size, Window) :- phrase((...,{length(Window,Size)},Window,...), List).

every_other([],[]).
every_other([X],[X]).
every_other([X,_|Xs], [X|Ys]) :- every_other(Xs,Ys).

split(Ls, F, B, Len) :- phrase(split(F,B,Len),Ls).
split(F,B,L)	--> {length(F,L)},list(F), list(B).
list([])	--> [].
list([H|T])	--> [H],list(T).

%flatten/deflatten one level of lists
mix([],[]).
mix([H|T1],[[H]|T2]) :- mix(T1,T2).
mix([H|T1],[[H|T]|T2]) :- mix(T1,[T|T2]).


zip([],[],[]).
zip([H1|T1],[H2|T2],[H1-H2|T3]) :- zip(T1,T2,T3).

Answered by triska

Jun 18, 2022

sum_list/2 is currently quite slow: It internally uses foldl/4, and that currently doesn't compile away the dynamic call. You can implement sum_list/2 manually much faster:

my_sum_list([], 0).
my_sum_list([L|Ls], S) :-
        sum_list_(Ls, L, S).

sum_list_([], S, S).
sum_list_([L|Ls], S0, S) :-
        S1 is S0 + L,
        sum_list_(Ls, S1, S).

Even further speedups can be achieved by moving the implementation to Rust, and that may be worth doing for a very small set of very frequently needed predicates (such as length/2). In general, it is better to instead work on improving the Prolog engine, since that will benefit all programs instead of only these few primitives.

View full answer

triska · 2022-06-17T19:32:38Z

triska
Jun 17, 2022

Thank you a lot for sharing this! From a quick glance, I noticed a few things:

When using random numbers, I strongly recommend to use set_random/1 so that all results are reproducible (i.e., all runs with the same arguments stay the same). You can add an argument to specify the seed, so that the code becomes more relational. This will make it simpler to compare the performance impact of changes to your code. You can use time/1 from library(time) to time results.
The directive :- use_module(library(dcgs)). is apparently missing in the code. You can start Scryer Prolog with the -f switch to ignore any configuration file you have defined.
~~maplist(\X^mutate(X),P0, T0) is equivalent to: maplist(mutate(P0), T0)~~ (No it isn't!). But maybe uses of maplist/N can be somewhat simplified? A good implementation of maplist/N would remove the overhead of the meta-call by rewriting it to a version that uses the specified predicate directly instead of using call/N.
sliding_window/3 can be written as:
```
 sliding_window(Ls, Size, Ws) :-
         length(Ws, Size),
         phrase((...,Ws,...), Ls).
```
As naming convention, I recommend variables ending with ...s (plural) to denote lists, such as Ws for a window.
You can omit the definition of list//1, and use seq//1 from library(dcgs) instead.
It is best to avoid findall/3; can selection/2 be defined without it?
Explicit unifications such as [H|_] = PN are rarely needed in Prolog. Simply use [H|_] instead of PN where it occurs, and S-_ where M currently occurs in the code.

Regarding performance: It is best to compute the things you need at most once. For example, we can write selection/2 like this:

selection(P0, P1) :-
        Ws = [_,_],
	findall(Ws, phrase((...,Ws,...), P0), Ts0),
        every_other(Ts0, P1).

This "pulls" the goal Ws = [_,_] in front of the findall/3, thus avoiding this operation (originally: a call of length/2) for each individual solution.

2 replies

Fflath Jun 17, 2022
Author

Thanks for the detailed feed back!

I've implemented most of these. However I'm not sure about #3.

?- set_random(seed(1)), genPop(4,4,P0), evaluate(P0,E0,_), selection(E0,S0), maplist(mutate(S0),T0).
   P0 = [[0,1,1,0],[1,0,1,0],[0,1,0,1],[1,0,0,0]], E0 = [[0,1,0,1],[1,0,1,0],[0,1,1,0],[1,0,0,0]], S0 = [[[0,1,0,1],[1,0,1,0]],[[0,1,1,0],[1,0,0,0]]], T0 = []
;  ... .
?- set_random(seed(1)), genPop(4,4,P0), evaluate(P0,E0,_), selection(E0,S0), maplist(\X^mutate(X),S0,T0).
   P0 = [[0,1,1,0],[1,0,1,0],[0,1,0,1],[1,0,0,0]], E0 = [[0,1,0,1],[1,0,1,0],[0,1,1,0],[1,0,0,0]], S0 = [[[0,1,0,1],[1,0,1,0]],[[0,1,1,0],[1,0,0,0]]], T0 = [[[0,1,0,0],[1,0,1,1]],[[0,1,1,0],[1,0,0,0]]]

triska Jun 19, 2022

Yes, you are right: (3) is wrong, I corrected this!

One other thing I noticed is that zip/3 is available with slightly different argument order as pairs_keys_values/3 in library(pairs), which you can use instead.

triska · 2022-06-17T19:43:22Z

triska
Jun 17, 2022

Another important thing regarding timing: I think it would be best to model the entire task as a relation between states of interest, so that we get each intermediate step also as a solution on the toplevel instead of only "printing" it manually on the terminal. In this way, we can get timings for each individual step instead of only for the entire sequence. Scryer Prolog makes it easy to see the entire sequence by pressing "a" on the toplevel to see all answers.

2 replies

Fflath Jun 17, 2022
Author

I'm not sure I follow. Do you mean something like this?

steps(_,[]).
steps(P0, [B|T]) :- step(P0,P1,B), steps(P1,T).

step(P0,P1,SP0) :-
        evaluate(P0,E0,SP0),
        selection(E0,S0),
        crossover(S0,P1).

triska Jun 18, 2022

I mean the following pattern:

state0_state(S, S).
state0_state(S0, S) :-
        step(S0, S1),
        state0_state(S1, S).

You can now query, starting from an initial state S0:

?- state0_state(S0, S).

and get the successive states reported as answer substitutions for S on the toplevel! Therefore, you do not have to manually print them, and also, you can get the timing information after each step by simply using:

?- time(state0_state(S0, S)).

In addition, you can press a to see the sequence of successive states.

Fflath · 2022-06-18T12:22:53Z

Fflath
Jun 18, 2022
Author

The code after most of the suggested tweeks. Still pondering how to avoid the findall.

It is faster.

The slowest part is maplist(sum_list, P0, S0). I'm not really sure if there is any way to speed that up.

Repurposed the * operator from your book power of prolog and declarative debugging. Super cool.

:- use_module(library(random)).
:- use_module(library(clpz)).
:- use_module(library(lists)).
:- use_module(library(lambda)).
:- use_module(library(dcgs)).
:- use_module(library(time)).
:- use_module(library(pairs)).

:- op(920,fy, *).
*G :- time(G).

% set_random(seed(2)), genPop(100,100,P0), state0_state(P0,PN,B0,B).

step(E0,E1,B1) :-
	selection(E0,S0),
	crossover(S0,P1),
	evaluate(P1,E1,B1).

state0_state(S, S,B,B).
state0_state(S0, S, _, B) :-
	step(S0, S1, B1),
	state0_state(S1, S, B1, B).

% sorts the population by order of decreasing fitness
evaluate(P0, P1, Max) :-
	maplist(sum_list, P0, S0),
	pairs_keys_values(S1,S0,P0),
	keysort(S1, S2),
	reverse(S2, S3),
	[Max|_]=S3,
	pairs_keys_values(S3,_,P1).

% group pairs of members together as parents for the next gen
selection(P0, P1) :-
	Ws = [_,_],
	findall(Ws,phrase((...,Ws,...),P0),Ts0),
	every_other(Ts0, P1).
	
% generate the next population from the list of parents
crossover(P0, P1) :-
	maplist(mutate,P0, T0),
	mix(P1,T0).
 
% get a list of 1s and 0s
genPop_single(Length, Member) :- length(T,Length), maplist(\_^random_integer(0,2),T, Member).
genPop(Count, Length, Population) :- length(T,Count), maplist(\_^genPop_single(Length), T, P0),evaluate(P0,Population,_).

% generate children from parents
mutate([A,B],[C,D]) :-
	length(A,L),random_integer(0,L,H),
	split(A, Af, Ab, H), split(B, Bf, Bb, H),
	split(C, Af, Bb, H), split(D, Bf, Ab, H).

% utilities
every_other([],[]).
every_other([X],[X]).
every_other([X,_|Xs], [X|Ys]) :- every_other(Xs,Ys).

split(Ls, Fs, Bs, Len) :- length(Fs,Len),phrase((seq(Fs),seq(Bs)),Ls).

%flatten/deflatten one level of lists named after apl operator
mix([],[]).
mix([H|T1],[[H]|T2]) :- mix(T1,T2).
mix([H|T1],[[H|T]|T2]) :- mix(T1,[T|T2]).

1 reply

triska Jun 19, 2022

(*)/1 is used to generalize away a goal by library(debug). It is best to use a different operator for timing. For example, consider $$ or ¤ (#1515).

triska · 2022-06-18T16:47:58Z

triska
Jun 18, 2022

sum_list/2 is currently quite slow: It internally uses foldl/4, and that currently doesn't compile away the dynamic call. You can implement sum_list/2 manually much faster:

my_sum_list([], 0).
my_sum_list([L|Ls], S) :-
        sum_list_(Ls, L, S).

sum_list_([], S, S).
sum_list_([L|Ls], S0, S) :-
        S1 is S0 + L,
        sum_list_(Ls, S1, S).

Even further speedups can be achieved by moving the implementation to Rust, and that may be worth doing for a very small set of very frequently needed predicates (such as length/2). In general, it is better to instead work on improving the Prolog engine, since that will benefit all programs instead of only these few primitives.

4 replies

mthom Jun 18, 2022
Maintainer

I'm working on improving the performance of expand_goal/3. It's the cause of primitives like maplist, foldl, findall, anything using call/N really, being slow.

triska Jun 18, 2022

Thank you a lot!

An important point in all these cases is the following: If the first argument of any of these meta-predicates is known at compilation time (which is the most common case), then there is no need at all for a meta-call. They can all be statically expanded to auxiliary predicates where the call is hard-coded as a normal predicate call.

For example, if we have maplist(p, Ls) as one of the goals in a predicate, then this can be replaced by aux(Ls), where the auxiliary predicate aux/1 is defined as: aux([]). aux([L|Ls]) :- p(L), aux(Ls). Hence, the predicate p/1 is directly invoked without ever being meta-called by this goal.

This can likely even be implemented via term expansion definitions in library(lists), it need not be hardcoded in the engine. The somewhat involved part is to keep track of which auxiliary predicates have already been generated at compilation time, and to call the right one for each of the arising maplist/N, foldl/N etc. goals that occur in a program.

mthom Jun 18, 2022
Maintainer

A similar effect can be achieved by expanding an instantiating meta-predicate goal with expand_goal/3 at compile time, and compiling the call site with $call/N instead of call/N to avoid calling expand_goal/3 at run time.

triska Jun 19, 2022

Thank you, I have filed #1514 for this.

Fflath · 2022-06-18T17:52:57Z

Fflath
Jun 18, 2022
Author

Big thank you. With the new sum_list it is blazing fast. Thanks for all the other suggestions as well.

0 replies

triska · 2022-07-23T19:05:26Z

triska
Jul 23, 2022

Good news: With the recent rebis-dev development branch, sum_list/2 is very fast.

For example, try the following query:

?- length(Ls, 1_000_000),
   maplist(=(1), Ls),
   sum_list(Ls, S).
   Ls = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...], S = 1000000.

This is very slow in master, and very fast with rebis-dev!

0 replies

UWN · 2022-07-24T07:38:26Z

UWN
Jul 24, 2022

?- time(( length(Ls, 1_000_000),
   maplist(=(1), Ls),
   sum_list(Ls, S) )).

On g1, produces in master 36.397s and in rebis-dev 0.443s. Which is a factor of 82. It could be faster, if #1390 would be addressed, too. There is still too much indirection in between.

0 replies

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Performance #1513

{{title}}

Replies: 7 comments 9 replies

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

Select a reply

Performance #1513

Replies: 7 comments · 9 replies

Fflath Jun 17, 2022 Author

Fflath Jun 17, 2022 Author

Fflath Jun 18, 2022 Author

mthom Jun 18, 2022 Maintainer

mthom Jun 18, 2022 Maintainer

Fflath Jun 18, 2022 Author

Replies: 7 comments 9 replies

Fflath Jun 17, 2022
Author

Fflath Jun 17, 2022
Author

Fflath
Jun 18, 2022
Author

mthom Jun 18, 2022
Maintainer

mthom Jun 18, 2022
Maintainer

Fflath
Jun 18, 2022
Author