Path: ...!news.mixmin.net!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.prolog
Subject: Re: variant_term/2 is faster than variant/1 (Was: Request for
 comments, Novacore the sequel to ISO modules)
Date: Sat, 12 Oct 2024 23:16:30 +0200
Message-ID: <veeove$bbu7$1@solani.org>
References: <db8a6771-3e54-485b-b391-310658dd6f52n@googlegroups.com>
 <aa869ef6-7f90-405b-a84a-2c11ac7979a3n@googlegroups.com>
 <vcukob$n3q2$1@solani.org> <veekkd$b9uf$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 12 Oct 2024 21:16:30 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="372679"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.19
Cancel-Lock: sha1:T4GojxNlWPI0E/YmFj2rSXfE5zw=
In-Reply-To: <veekkd$b9uf$1@solani.org>
X-User-ID: eJwFwQkBACAIA8BKImxoHD77R/AOSmG5ETQ8vCaL05kWV2WyolMNsSY0avykVrvmdqlLJGyhi3143mzBB4r0Fnk=
Bytes: 3331
Lines: 96

How much faster is it?

Here some test harness:

test :- length(L, 6), length(R, 6),
    enum_list(_, L), enum_list(_, R),
    variant(L, R), fail; true.

test2 :- length(L, 6), length(R, 6),
    enum_list(_, L), enum_list(_, R),
    variant_term(L, R), fail; true.

Here some results:

- SWI-Prolog 9.3.11:

?- time(test).
% 2,126,498 inferences, 0.734 CPU in 0.752 seconds
(98% CPU, 2895657 Lips)
true.

?- time(test2).
% 2,159,795 inferences, 0.234 CPU in 0.236 seconds
(99% CPU, 9215125 Lips)
true.

- Trealla Prolog 2.57.16:

?- time(test).
% Time elapsed 3.128s, 14827949 Inferences, 4.741 MLips
    true.

?- time(test2).
% Time elapsed 1.079s, 7775516 Inferences, 7.206 MLips
    true.

- Scryer Prolog :

?- time(test3).
    % CPU time: 5.653s, 5_192_831 inferences
    true.

?- time(test2).
    % CPU time: 1.544s, 6_116_163 inferences
    true.

Note: test3 is like test, only it uses builtins:variant/2.

Mild Shock schrieb:
> The ISO core standard probably set the
> stage for a couple of performance sins.
> In 7.1.6.1 Variants of a term we find
> 
> these test cases:
> 
> - f(A, B, A) is a variant of f(X, Y, X).
> - g(A, B) is a variant of g(_, _).
> - P+Q is a variant of P+Q.
> 
> What is doubious here, is the last test
> case with P+Q. Do we need to test terms
> that have common variables?
> 
> Lets assume we have situations where we
> don't need variant working with common
> variables in the two argument terms, what
> 
> about then using this bootstrapping:
> 
> variant_term(X, Y) :-
>     subsumes_term(X, Y),
>     subsumes_term(Y, X).
> 
> Here some testing, does it work ok? Take this code:
> 
> enum_arg(_, 1).
> enum_arg(_, _).
> enum_arg(X, X).
> 
> enum_list(_, []).
> enum_list(X, [H|T]) :- enum_arg(X, H), enum_list(X, T).
> 
> boole(G, 1) :- G, !.
> boole(_, 0).
> 
> nok(L, R) :- length(L, 6), length(R, 6),
>       enum_list(_, L), enum_list(_, R),
>       boole(variant(L, R), A), boole(variant_term(L, R), B),
>       A \== B.
> 
> Seems to work fine:
> 
> ?- nok(L, R).
> false.
> 
>