"arg/3" is about 100 times faster than "nth1/3": a benchmark.

[Kuniaki Mukai]

Dear All,

There is a technique to use a term as an array using
functor/3 for array creation, arg/3 for accessing array elements,
and setarg/3. How much difference is in speed compared
with use a list as an array using length/2 for array creation,
nth1/nth0 for accessing elements ? (this benchmarked codes do not use setarg/3 ).

The benchmark is taken from the partition_number/2, which have
I posted a couple of days ago.

The result is this:

=== Term as array version ===
% ?- time(integer_partition:partition_number(10000, X)).
%@ % 9,639,711 inferences, 1.303 CPU in 1.311 seconds (99% CPU, 7395314 Lips)

=== List as array version ===
% ?- time(integer_partition:partition_number_list(10000, X)).
%@ % 1,462,659,709 inferences, 85.862 CPU in 85.970 seconds (100% CPU, 17035085 Lips)

I never have noticed this big difference exists;
now I come to think we can enjoy fast matrix calculation also
in SWI-Prolog. Although the setarg/3 is a so called "non-logical"
operation, I don't see any dangerous things
in using the setarg/3 more than in doing assert/retract or
nb_setval/nb_getval. It's a safe operation as others, I believe.

Kuniaki Mukai

[Raivo Laanemets]

I think this is even mentioned somewhere in the SWI manual. Besides functor/3 you

can also use the =.. operator to construct these "array" terms. I recently needed dot product

between vectors and thanks to this I got to the point where runtime was dominated by

of is/2.

[Kuniaki Mukai]

Hi Raive,

Thank you for the comment, especially that is/2 dominates runtime,
though it is difficult for me to guess reasons of the dominance of is/2.

Kuniaki Mukai

> --
> You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
> Visit this group at https://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.

[Jan Wielemaker]

On 25/02/16 15:39, Kuniaki Mukai wrote:
> Hi Raive,
>
> Thank you for the comment, especially that is/2 dominates runtime,
> though it is difficult for me to guess reasons of the dominance of is/2.

is/2 without optimization (-O or the optimise flag) is not compiled.
This means the right-hand term is created, evaluated and the result is
unified with the left hand. When using optimizaton, it is compiled into
a stack engine where the evaluation steps point directly at the
implementation of the arithmetic operations. That saves both creating
the garbage right-hand term and recursively processing it while
resolving the arithmetic function implementations.

Sounds great, but optimized arithmetic cannot be traced and on typical
Prolog programs that do only a little arithmetic it turns out that
simple arithmetic is sometimes even faster than the optimized version,
most likely due to cache behavior, although I never really investigated
this.

Cheers --- Jan

[Boris Vassilev]

Hello Kuniaki and others,

sorry for the noise if I am just pointing out things everyone knows:

If I have understood correctly, arg/3 gives constant time access to any of the arguments of a term. It is also more memory efficient than a list of the same length. In theory, this should make terms perfect for implementing algorithms that assume constant time random access ("arrays"). In practice, I had to find out the hard way that this is usually not the real bottleneck.

The code becomes clumsy; there are no nice built-ins for mapping, folding, etc. Using a list and a theoretically less optimal algorithm that works well on linked lists (so Prolog lists) was always faster. Plus you don't have to convert from lists to terms and back to talk to the rest of the program. I am sure that problems as Raivo described profit from using terms instead of lists, but this seems to a niche use. Especially since we have dicts, too.

I would be very grateful is someone shows me I am wrong!

Cheers,

Boris

Currently in the EET time zone: This is UTC +2:00
Save our in-boxes! http://emailcharter.org

[Kuniaki Mukai]

Hi Boris,

Although I am far from appropriate to talk about efficiency issues,
IMHO, if the following conditions 1 and 2 are satisfied,
then efficient matrix calculus even comparative to mathematica !
is possible on the current SWI-Prolog.

1. constant time random access to elements by index

2. fast arithmetics (is/2) for index calculation to access elements of the array.

I think 1. is already satisfied as you have pointed,
and also 2. is satisfied if we give an appropriate compiling option
(according to Jan's comment, thanks).
Therefore efficient matrix calculus must be real on
current SWI-Prolog.

I have been writing codes so far on the famous Grobner-base from time to time
and little by little as hobby, implementing several known strategies
using only lists, but without arrays. The current version already solves
non-trivial examples, but, it is --I have to admit-- still short
for the "poor man's mathematica”. I wish I could rewrite the codes
into array version to compare efficiency.

Kuniaki Mukai

[Markus Triska]

Dear Kuniaki,

this is really an impressive speedup!

As a good compromise between declarative soundness and acceptable performance, I have often found balanced trees a good representation. For example, with library(assoc), you can associate positions to items, and access and change the items at each position in O(log(N)) while preserving declarative properties that setarg/3 destroys.

That's admittedly not in O(1); however, it scales very predictably, is very portable to other Prolog systems, and I have often found library(assoc) efficient enough in such situations to eschew setarg/3 and destructive modifications which, even if not worse than assert/1 etc., are still impure.

In many cases, the operations can be arranged in such a way that the elements are always accessed sequentially, and in such situations I agree with Boris's observations: The availability of many dedicated library predicates, pure language elements and built-in optimizations for handling them often still puts lists among the most suitable and natural representations.

Still, it's nice that other representations are useful to you when you need them. It would be interesting to compare these performance results with an "indexing scheme" based on library(assoc), where association lists (in the case of library(assoc): a balanced tree) is used to map integral positions to elements.

Thank you for sharing!

All the best,
Markus

[Kuniaki Mukai]

Dear Markus,

Thank you for recommending to library(assoc). Wiht no doubt, the
assoc library works well for sparse arrays. It may be also useful
for handling polynomials over given a field with multi variables,
which is basic in Grobner-Base method.

However, I can't believe, at least for now,
that it works fast well also for the usual arrays like seen in C language.
I may be missing something in your message, but this reaction comes
from some related experience of mine.

Once about 30 years ago, I wrote a library similar to the current
library(assoc), together with 'naive' Boolean constraint library based
on the idea of freeze/2. Those days, I was working on unification over
feature strucures with "naive boolean constraint", (record-like
structure, attribute value matrix, psi-term, lexical function structure, and the like)
inspired by Colmerauer's beautiful unification theory over ratinal trees, and
Peter Aczel's theory on non-well-founded sets. My small contribution on the
library variant/2 is just a corollary of them, I think.

I know such experience above is limited, and already belongs
to the ancient; I have no intention to insist my experience at all;
rather, I am willing to accept any results with delight
even when it's in favor of your insight.

Kuniaki Mukai

[Fred Mesnard]

Dear Kuniaki,

> Le 25 févr. 2016 à 21:50, Kuniaki Mukai <kuniak...@gmail.com> a écrit :
>
> I have been writing codes so far on the famous Grobner-base from time to time
> and little by little as hobby, implementing several known strategies
> using only lists, but without arrays. The current version already solves
> non-trivial examples, but, it is --I have to admit-- still short
> for the "poor man's mathematica”. I wish I could rewrite the codes
> into array version to compare efficiency.

I like your "poor man's mathematica" idea very much!

Can you please consider publishing your Grobner-base solver
as a SWI-Prolog pack, for instance? Thanks in advance!


Fred

[Jan Wielemaker]

Hi Kuniaki,

On 02/26/2016 05:52 AM, Kuniaki Mukai wrote:
> Dear Markus,
>
> Thank you for recommending to library(assoc). Wiht no doubt, the
> assoc library works well for sparse arrays. It may be also useful
> for handling polynomials over given a field with multi variables,
> which is basic in Grobner-Base method.

Roughly, the story is easy:

- Lists
- 3 cells per element (in SWI, two on many others)
- O(n) random access
- O(1) sequential access
- O(n) and complete copy for random update
- Pure
- library(assoc)
- 6 cells per element
- O(log(n)) random access
- O(1) sequential access
- O(log(n)) and log(n) copy for random update
- Pure
- Terms and [set]arg/3
- 1 cell per element (and 1 overhead for the entire array)
- O(1) random access
- O(1) sequential access
- arg/3 update
- O(n) and complete copy for random update
- Pure
- setarg/3 update
- O(1) random update
- Impure
- dicts
- 2 cells per element
- O(log(n)) random access
- O(1) sequential access
- Using put_dict/3
- O(n) and n copy for random update
- Pure
- Using b_set_dict/3
- O(log(n)n) for random update
- Impure

In the above, it should be noted that the constant factor for the
performance
is low for terms and dicts, a little higher for lists and much higher for
assoc.

Note that ECliPSE has arrays, which are terms using [] as functor, e.g.,
[](a,b) is an array {a,b}. These can be accessed using Array[Index]. All
this can be realised for SWI-Prolog as a library (all required
infrastrucure is present AFAIK). The ECliPSE logical loops also work for
term arguments which allows for sequential mapping like operations
without significant overhead.

... but, I agree with Markus that if you can manage the desired
operations using sequential access to the arrays, lists are a good
representation. The problem with Prolog here is that it has a large
number of reasonable ways to represent arrays but no `perfect' one. That
makes the choice for general purpose array package hard. Note that this
problem is the immediate consequence of having immutable data structures
and is problem is thus shared by all logical and functional languages.

I have the impression that the most sensible thing to do is to implement
ECliPSE arrays and logical loops. I have made a port of Joachims
original publication version of logical loops. When I talked to Joachim,
he convinced me to port the current ECliPSE one. No time yet ...

> Peter Aczel's theory on non-well-founded sets. My small contribution on the
> library variant/2 is just a corollary of them, I think.

This surely was not a small contribution. I'm still impressed!

Cheers --- Jan

[Kuniaki Mukai]

Hi Jan,

Thank you for comments. I have to take time to digest them.
I feel I have eaten too much stuff at this thread as a person
who is doing Prolog programming as a hobby. Perhaps
I am too much excited to have found the time efficiency
of terms as arrays of SWI-Prolog, forgetting other important
points of logic programming. However, I would like
to walk in this direction further to see what will happens there.

I want to rewrite my codes on Grobner-method. In fact,
a half year ago, I merged several independent stratgies into one
'generic' modules for mixed strageties available. It was so complex
work for me, the merge failed, and worse,
I lost some part of codes. After that I have been using GIT
for not losing codes. GIT is really great !

Anyway I hope a "poor man's methematica" version of Grobner-base codes
will be available some point in the coming April, which would be based
on the feedbacks offered at this thread ( library(assoc), and
setarg/3, sorry for the latter).

BTW, skimming a paper on logical loops,
I have got to feel that my pac package might be
related to "logical loops". In other words,
the pac package, so far, compiles the following
"logical loops".


logical loops? source
------------- --------------
regex expand-word.pl
unix_sed expand-etc.pl
foldl expand-etc.pl
foldr expand-etc.pl
repeat expand-etc.pl
collect expand-etc.pl
for expand-etc.pl
kind expand-pac.pl

Of course, I am saying without exact understanding
of logical loops, but it is enough for me to be interested
in logical loops.

Kuniaki Mukai

[Markus Triska]

Dear Kuniaki,

On Friday, February 26, 2016 at 5:52:44 AM UTC+1, Kuniaki Mukai wrote:

My small contribution on the library variant/2 is just a corollary of them, I think.

Your contribution of variant/2 still is one of the most amazing contributions I have seen to SWI-Prolog. If that's just the corollary, I suppose the main work is impressive beyond all comprehension.
 

I know such experience above is limited, and already belongs
to the ancient;  I have no intention to insist my experience at all;
rather,  I am willing to accept any results with delight
even when it's in favor of your insight.

Please consider a very small and simple-minded benchmark just to get an impression how the three approaches (nth/3, library(assoc), arg/3) fair in one fundamental aspect: Simply accessing all elements once and by their index. Note that there are ways to make this more efficient for each of these approaches, but for the current benchmark, I only want to measure access times for selecting elements (and these elements need not be accessed sequentially, although they are in the codes below).

Here are the three ways:

/* Using nth/3 */

run_nth(L) :-
        length(Ls, L),
        numlist(1, L, Is),
        maplist(nth_(Ls), Is).

nth_(Ls, I) :- nth1(I, Ls, _).


/* Using library(assoc) */

run_assoc(L) :-
        numlist(1, L, Is),
        pairs_keys_values(Pairs, Is, _),
        list_to_assoc(Pairs, A),
        maplist(assoc_(A), Is).

assoc_(A, I) :- get_assoc(I, A, _).


/* Using arg/3 */

run_arg(L) :-
        length(Ls, L),
        T =.. [t|Ls],
        numlist(1, L, Is),
        maplist(arg_(T), Is).

arg_(T, I) :- arg(I, T, _).

And here is code to obtain timing results:

timings(N) :-
        maplist(call_time, [run_nth(N),
                            run_assoc(N),
                            run_arg(N)], [T2,T3]),
        format("nth:   ~t~3f~20|\n", [T1]),
        format("assoc: ~t~3f~20|\n", [T2]),
        format("arg:   ~t~3f~20|\n", [T3]).

call_time(Goal, T) :-
        statistics(cputime, T0),
        Goal,
        statistics(cputime, T1),
        T is T1 - T0.

So now we have for example:

%?- timings(10 000).
%@ nth:           1.901
%@ assoc:         0.103
%@ arg:           0.004

So using assoc is already faster than using nth/3 by an order of magnitude in this case. arg/3 is way faster still!

The interesting thing is of course how these operations scale:

%?- timings(20 000).
%@ nth:           7.589
%@ assoc:         0.208
%@ arg:           0.008

and further:

%?- timings(30 000).
%@ nth:          17.190
%@ assoc:         0.327
%@ arg:           0.014
%@ true.

and further (let us eliminate the nth/3 version):

%?- timings(1 000 000).
%@ assoc:        15.272
%@ arg:           0.453

So yes, arg/3 may be worth using in several cases. But setarg/3 is just so impure!

Therefore, I hope you consider using library(assoc), and then use destructive term modifications as a last resort in those parts of your program that truly benefit from it.

All the best!
Markus

[Kuniaki Mukai]

Dear Markus and All,

Thank you, Markus, for useful advice for measuring of time. I
will keep them in mind for the future.

For those who like Grobner-base things:

I have uploaded the unfinised codes on Groebner-base (GB), which was
mentioned by myself in this thread. It is on the half way of
developing, and perhaps will be so forever.

Main source of the codes is a book:

"Fundamental of Calculation Groebner Base"
by M. Noro and K. Yokomama,
from Tokyo University Publishing
ISBN = 4130614045,
2003
(in Japanese)

Among many books on GB, I was strongly recommended to read
this book by an active expert on the topics, though
I have not read it in technical details yet.

According to the book, the authors are also developers of Risa/Asir:

http://www.math.sci.kobe-u.ac.jp/Asir/asir.html

The following sample are taken from the above text book.
According to it, the example is already impossibly hard for humem
to calculate by hand, and also for programs of naive algorithm.

?- pack_install(pac) % pac-0.8.8
?- use_module(library(pac)).
?- use_module(gb('gb-top')). % gb is a file_search_path prefix.

?- F1 = x^5+y^4+z^3-1, F2=x^3+y^3+z^2-1, time(gb:gb(F1;F2, X, [vars([z,y,x])])).
% 126,513,226 inferences, 14.528 CPU in 14.602 seconds (99% CPU, 8708474 Lips)

?- F1 = x^5+y^4+z^3-1, F2=x^3+y^3+z^2-1, time(gb:gb(F1;F2, X, [vars([z,y,x]),vector(true)])).
% 262,864,010 inferences, 42.968 CPU in 43.186 seconds (99% CPU, 6117654 Lips)

?- F1 = x^5+y^4+z^3-1, F2=x^3+y^3+z^2-1, time(gb:gb(F1;F2, X, [vars([x,y,z]),vector(true)])).
% 2,063,663 inferences, 0.227 CPU in 0.233 seconds (98% CPU, 9086823 Lips)

?- pack_remove(pac).
?- halt.


The codes are under pac/grobner directory.


Kuhiaki Mukai

[Fred Mesnard]

Dear Kuniaki,

I was able to run your examples after a
?- pack_install(regex).
Many thanks for sharing your work!

Fred

[Kuniaki Mukai]

Hi Fred,

I am not the author of the package regex, but that of a package pac.
However, the pac package integrates regex into DCG phrase based on the pac core engine
as a state minimised finite automata, which work so far so good seamlessly
in my personal uses.

Kuniaki Mukai

[Fred Mesnard]

Hi Kuniaki,

> Le 7 mars 2016 à 14:20, Kuniaki Mukai <kuniak...@gmail.com> a écrit :
>
> I am not the author of the package regex, but that of a package pac.
> However, the pac package integrates regex into DCG phrase based on the pac core engine
> as a state minimised finite automata, which work so far so good seamlessly
> in my personal uses.

I mean:
- if I don’t install regex first, I have an error (see below).
- if I install regex first, it runs as expected.

Best regards,
Fred

--------------------------------------------------------------------------------------------------------
% swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.17)
...

?- pack_install(pac).
...
true.

?- use_module(library(pac)).
Warning: /Users/fred/lib/swipl/pack/pac/prolog/pac/setup-pac.pl:57:
Goal (directive) failed: pac: (env_dict(paths_to_exec,_G481),atomics_to_string(_G481,":",_G510),assert(env_dict(path,_G510)))
ERROR: /Users/fred/lib/swipl/pack/pac/prolog/pac/pac-loader.pl:10:
source_sink `library(regex)' does not exist
Warning: /Users/fred/lib/swipl/pack/pac/prolog/pac/pac-loader.pl:10:
Goal (directive) failed: pac:use_module(library(regex))
true.