Dif - potential performance improvement?

Discussion
1

The start of dif/2 contains:

dif(X,Y) :-
    ?=(X,Y),
    !,
    X \== Y.

Couldn’t the combination of ?=/2 and \==/2 instead be \=/2, to compare once instead of twice? I.e.:

dif(X,Y) :-
    X \= Y,
    !.

Ah, might also need, after that:

dif(X,Y) :-
    X == Y,
    !,
    fail.

I suppose my question is, isn’t it better to optimize with the expectation that dif/2 will succeed?

Examples of performance improvement:

?- X = Y, time((between(1, 50000000, N), ?=(X, Y), X \== Y)).
% 149,999,999 inferences, 3.734 CPU in 3.734 seconds (100% CPU, 40175184 Lips)

?- X = Y, time((between(1, 50000000, N), X \= Y)).
% 99,999,999 inferences, 2.170 CPU in 2.170 seconds (100% CPU, 46092564 Lips)

and

?- X = 1, Y = 2, time((between(1, 50000000, N), ?=(X, Y), X \== Y, fail)).
% 149,999,999 inferences, 3.702 CPU in 3.702 seconds (100% CPU, 40522201 Lips)

?- X = 1, Y = 2, time((between(1, 50000000, N), X \= Y, fail)).
% 99,999,999 inferences, 2.065 CPU in 2.065 seconds (100% CPU, 48417016 Lips)
2

I don’t know. Typically you use dif/2 if it needs to be delayed. The difference is in relative sense significant, but in absolute sense not so much. How much would that differ in practice? Is it worthwhile to make the definition less obvious?

Another approach would be to call unifiable/3 right away. To help, we’d probably also have to get rid of dif_unifiable/3 in the code, which may be a good idea anyway (i.e., shouldn’t unifiable/3 deal itself with the occurs_check flag?

3

My line of thinking was that the existing use of ?=/2 doesn’t optimize for dif/2 succeeding or failing.

Just had another idea: how about a new ?=/4, which adds a Boolean argument for whether the 2 variables are definitely equal/different? This should provide some speedup, by not having to duplicate the comparison effort.

So:

  • true means the variables are definitely equal
  • false means the variables are definitely different

Surely ?= already knows this answer - doesn’t seem right to keep the answer hidden :grinning:

4

I would say that dif/2 is typically used if it might need to be delayed – that is, you can’t be sure that the arguments are sufficiently instantiated, but putting the test in a place where you’re sure that that the arguments are sufficiently instantiated would cause more backtracking.
The “probably will be delayed” situation shows up in things like “all different” (e.g., in a Sudoku solver), and for those, some additional constraint propagation might be useful. (BTW, it’d be nice to have an “all different” that works for anything, not just integers as in all_different/1 or all_distinct/1.)

(PS: A.9.17 (SWI-Prolog -- CLP(FD) predicate index) in the manual has a dead link: SWI-Prolog manual)

5

Here’s some examples to indicate performance improvement:

dif_optim(X, Y) :-
    (   X \= Y
    ->  !
    ;   X == Y
    ->  !,
        fail
    ;   dif_c_c(X, Y, _)
    ).

This is faster than the current ?=/2 method, in both situations (certain equality or certain inequality):

For certain match:

?- X = Y, time((between(1, 50000000, N), dif(X, Y))).
% 149,999,999 inferences, 6.842 CPU in 6.842 seconds (100% CPU, 21923335 Lips)

?- X = Y, time((between(1, 50000000, N), dif_optim(X, Y))).
% 199,999,999 inferences, 4.524 CPU in 4.524 seconds (100% CPU, 44212779 Lips)

… or matching on value:

?- X = 2, Y = 2, time((between(1, 50000000, N), dif(X, Y))).
% 149,999,999 inferences, 6.457 CPU in 6.457 seconds (100% CPU, 23230852 Lips)

?- X = 2, Y = 2, time((between(1, 50000000, N), dif_optim(X, Y))).
% 199,999,999 inferences, 4.570 CPU in 4.570 seconds (100% CPU, 43766494 Lips)

For certain mismatch:

?- X = 1, Y = 2, time((between(1, 50000000, N), dif(X, Y), false)).
% 199,999,999 inferences, 6.941 CPU in 6.941 seconds (100% CPU, 28815598 Lips)

?- X = 1, Y = 2, time((between(1, 50000000, N), dif_optim(X, Y), false)).
% 199,999,999 inferences, 4.812 CPU in 4.812 seconds (100% CPU, 41560302 Lips)

For the 3rd situation (no certainty of match or mismatch, so calling dif_c_c/3), performance is roughly the same:

?- time((between(1, 2000000, N), dif(X, Y), false)).
% 59,999,999 inferences, 2.799 CPU in 2.802 seconds (100% CPU, 21434227 Lips)

?- time((between(1, 2000000, N), dif_optim(X, Y), false)).
% 61,999,999 inferences, 2.589 CPU in 2.592 seconds (100% CPU, 23946143 Lips)

Also: ->/2 is faster than using multiple rules having the same head.