Indexing atoms vs. pairs -- performance

Just a little experiment:

i0(N) :-
    forall(between(1, N, X),
           assertz(d0(X,X))),
    time(forall(between(1, N, X),
                d0(X, _))),
    time(forall(between(1, N, X),
                d0(_, X))).

i1(N) :-
    forall(between(1, N, X),
           assertz(d1(X-X))),
    time(forall(between(1, N, X),
                d1(X-_))),
    time(forall(between(1, N, X),
                d1(_-X))).
101 ?- i0(1 000 000).
% 2,000,001 inferences, 0.739 CPU in 0.745 seconds (99% CPU, 2706333 Lips)
% 2,000,000 inferences, 0.728 CPU in 0.734 seconds (99% CPU, 2748151 Lips)
true.

102 ?- i1(1 000 000).
% 2,000,000 inferences, 0.894 CPU in 0.894 seconds (100% CPU, 2238378 Lips)
% 2,000,000 inferences, 0.803 CPU in 0.803 seconds (100% CPU, 2491910 Lips)
true.

103 ?- jiti_list(d0).
Predicate                                     Indexed  Buckets Speedup Flags
============================================================================
user:d0/2                                       1        1,048,576 1000000.0   
                                                2        1,048,576 1000000.0   
true.

104 ?- jiti_list(d1).
Predicate                                     Indexed  Buckets Speedup Flags
============================================================================
user:d1/1                                       1            2     1.0  L
                                                1/1      1,048,576 1000000.0   
                                                1/2      1,048,576 1000000.0   
true.

I think that explains it all: the second is a little slower because it it first uses the indexing stuff to find the clauses (all of them) using the -/2 functor after which it is in the same situation having to deal with two arguments.

The lesson is, as a very old advice: use as few compound terms as you can for the storage and write a wrapper around it that turns the data in the shape you want to have it. That makes the clauses shorter and builds fewer indexes. Of course, this is mostly interesting if you have a lot of clauses and notably memory is getting a problem.

3 Likes