SWI absurdly slow

[Julio Di Egidio]

Hi all,

I was playing with a prime number generator and making it work on both
SWI and GProlog, and I got an "interesting" performance result, where
the code is just pure Prolog with cut plus lists and some arithmetic:

=== SWI-Prolog (Windows, threaded, 64 bits, version 9.0.4): ==========

```prolog

?- consult('C:/Users/Julio/Desktop/prime_gen.pl').
true.

?- test_prime_gen(100).

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Elapsed CPU time: 0 ms
true.

?- test_prime_gen(100000, []).

Elapsed CPU time: 1813 %% (was 3657 ms in SWI 8.2.0)
true.

```

=== GNU Prolog 1.5.0 (Windows, 64 bits)*: =============================

*```prolog

| ?- consult('C:/Users/Julio/Desktop/prime_gen.pl').
compiling C:/Users/Julio/Desktop/prime_gen.pl for byte code...
C:/Users/Julio/Desktop/prime_gen.pl compiled, 93 lines read - 5924 bytes
written, 11 ms

yes
| ?- test_prime_gen(100).

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Elapsed CPU time: 0 ms

(15 ms) yes
| ?- test_prime_gen(100000, []).

Elapsed CPU time: 375 ms

(375 ms) yes

```

Source code is on Gist:
<https://gist.github.com/jp-diegidio/5d5855b555ebdbe4a1fec134fea4ce78>

Julio

[Mild Shock]

Your GitHub says:
- SWI-Prolog (threaded, 64 bits, version 9.0.4)

Try SWI-Prolog 9.1.16, its a little bit better.
Around 16% faster. Might still not beat GNU Prolog though.

Julio Di Egidio schrieb:

[peter.l...@gmail.com]

I ran the profiler on your code with SWI-Prolog, and the top items were:
94.6% append/3
10.4% $garbage_collect/1
4.8% prime_gen_comp/2

append/3 is just a regular predicate in SWI-Prolog; I don't know how it's implemented in GNU-Prolog, but if it's written in C, that could account for a lot of the difference.

PS: I got about 5% improvement with SWI-Prolog by specifying the "-O" (optimise) flag ... that would made the calls to is/2 and >/2 faster.

PPS: it's easy to get rid of the call to append/3. For example, you can change prime_gen_do/4 to prime_gen_do//4.

[Julio Di Egidio]

On 10/10/2023 17:13, peter.l...@gmail.com wrote:
> On Tuesday, October 10, 2023 at 4:41:46 AM UTC-7, Julio Di Egidio wrote:<snip>

> I ran the profiler on your code with SWI-Prolog, and the top items were:
> 94.6% append/3
> 10.4% $garbage_collect/1
> 4.8% prime_gen_comp/2
>
> append/3 is just a regular predicate in SWI-Prolog; I don't know how it's
> implemented in GNU-Prolog, but if it's written in C, that could account for
> a lot of the difference.

Thanks, that makes sense. I shall get rid of that append with a
difference list, then the comparison should be fair (as to the
pure Prolog with cut plus basic arithmetic fragment).

Meanwhile, I guess I should rename the thread "append absurdly
slow in SWI". ;)

Julio

[Mild Shock]

GNU Prolog append/3 is a little faster, which is strange,
since GNU Prolog is more known to be faster for
arithmetic, since it doesn't have bigint,

but append/3 seems to be faster:

/* GNU Prolog (interpreted) */
?- between(1,1000000,_), fail; true.
(15 ms) yes

?- between(1,1000000,_), append([1,2,3,4,5],[6],_), fail; true
(109 ms) yes

/* SWI-Prolog */
?- time((between(1,1000000,_), fail; true)).
% 999,998 inferences, 0.031 CPU in 0.028 seconds (111% CPU, 31999936 Lips)
true.

?- time((between(1,1000000,_), append([1,2,3,4,5],[6],_), fail; true)).
% 6,999,998 inferences, 0.156 CPU in 0.155 seconds
(100% CPU, 44799987 Lips)
true.

Subtracting Loop Time I get:
GNU Prolog (interpreted): 94 ms
SWI-Prolog: 155-28 = 127 ms

GNU Prolog has a native implementation of append,
by Pl_Append_3 in a file list_c.c. Woa!

Julio Di Egidio schrieb:

[Julio Di Egidio]

On 10/10/2023 17:33, Julio Di Egidio wrote:
> On 10/10/2023 17:13, peter.l...@gmail.com wrote:
>> On Tuesday, October 10, 2023 at 4:41:46 AM UTC-7, Julio Di Egidio
>> wrote:
> <snip>
>> I ran the profiler on your code with SWI-Prolog, and the top items were:
>>    94.6%  append/3
>>    10.4%  $garbage_collect/1
>>      4.8%  prime_gen_comp/2
>>
>> append/3 is just a regular predicate in SWI-Prolog; I don't know how it's
>> implemented in GNU-Prolog, but if it's written in C, that could
>> account for a lot of the difference.
>
> Thanks, that makes sense.  I shall get rid of that append with a
> difference list, then the comparison should be fair (as to the
> pure Prolog with cut plus basic arithmetic fragment).

I have published the updated version (with the diff list):
<https://gist.github.com/jp-diegidio/5d5855b555ebdbe4a1fec134fea4ce78>

Now indeed GNU Prolog seems just some 20% faster
(the difference might very well have to do with the
arithmetic, since SWI has arbitrary integers as well as
the rationals, plus of course floating point and maybe
something else by now, I have not been following: all
under one and the same predicate...):

?- forall(member(Max, [100000,200000]), test_prime_gen(Max, [rounds(30)])).

SWI:
Elapsed CPU time: 383 ms (avg. over 30 rounds)
Elapsed CPU time: 902 ms (avg. over 30 rounds)

GProlog:
Elapsed CPU time: 306 ms (avg. over 30 rounds)
Elapsed CPU time: 734 ms (avg. over 30 rounds)

And I'll leave it at that, as I cannot do anything really
precise. In fact, I cannot even be sure the 'statistics'
I am using are exactly the same on the two systems.

Julio

[Mild Shock]

Because GNU Prolog has a hand written append/3,
this here doesn't run indefinitely:

test(X) :- append(Y, X, [1,2,3|Y]).

Whereas in SWI-Prolog it runs indefinitely. So the hand
written C code lacks some garbage collection.

Here are the run results:

/* GNU Prolog 1.5.0 */
?- test(X).
X = [1,2,3] ? ;
X = [2,3,1] ? ;
X = [3,1,2] ?

?- test(X), fail; true.
%%% Dialog Window with global stack overflow
%%% After dismissing the Dialog Window GNU Prolog exists

/* SWI-Prolog 9.1.6 */
?- test(X).
X = [1, 2, 3] ;
X = [2, 3, 1] ;
X = [3, 1, 2] .

?- test(X), fail; true.
%%% runs indefinitely, you can watch the thread monitor, see how memory is reclaimed
%%% Responds to Ctrl-C and can be aborted, will gracefully return to top-level

[Mild Shock]

Credits go to:

Marquee in Prolog
https://stackoverflow.com/questions/77061142/marquee-in-prolog