Is this a known bug on `term_factorized/3`?

General
1

EDIT
I can’t reproduce what I reported below. Rather I have found the term_factorized/3 is robust for the stress test. I changed the number of hydra heads to is 2^10000 !!, and saw that it terminates without freezing, which is amazing.

% ?- time((hydra(10000, _X), hydra(10000, _Y, _Y),
%	term_factorized(g(_X, _Y), _Skel, _Coa), length(_Coa, Len))),
%	writeln(unifying),
%	maplist(unify_pair, _Coa), writeln(unified), _Skel == g(_X, _Y),
%	writeln(verified).
%@ % 2,680,468 inferences, 41.321 CPU in 55.699 seconds (74% CPU, 64869 Lips)
%@ unifying
%@ unified
%@ verified
%@ Len = 10000 .

END of edit

Is this a known bug on term_factorized/3, which freezes at the very exit of a stress test query ? If this is really a bug, it would be a great pity. It’s fifty times faster than the naïve code I came up with, though mine does not freeze, at least.

% ?- time((hydra(2000, _X), hydra(2000, _Y, _Y),  term_factorized(g(_X, _Y), Is, _Coa), length(_Coa, Len))),
%	writeln(unify), maplist(call, _Coa), writeln(check_equality),
%	Is == g(_X, _Y), writeln(" verified.").
%@ % 532,865 inferences, 1.671 CPU in 1.716 seconds (97% CPU, 318799 Lips)
%@ unify
%@ check_equality
%@  verified.   <=== freeze

% ?- hydra(2, X).
%@ X = h(h(_A, _A), h(_A, _A)) .

% hydra(0, _).
% hydra(N, h(X, X)):- N>0, N0 is N-1, hydra(N0, X).

% ?- hydra(2, X, X).
%@ X = h(_S1, _S1), % where
%@     _S1 = h(h(_S1, _S1), h(_S1, _S1)) 

% hydra(0, A, A).
% hydra(N, h(X, X), A):- N>0, N0 is N-1, hydra(N0, X, A).
```
3

Agree. I thought compare/3 is used for only acyclic terms inside of term_factorized/3.

4

I checked that hydra/2,3 without cut (!) leaves choice point, which must fail immediately. However, as I had corrected my post in this thread, I could not reproduce the freezing on term_factorized/3, and instead I saw it shows amazing robustness for the stress test with the (cut-free) hydra/2,3. As for me, I might have not met any glitch of term_factorized/3. I am not sure on this at this time of moment.

%
hydra(0, _).
hydra(N, h(X, X)):- N>0, N0 is N-1, hydra(N0, X).

% ?- hydra(3, H, A), A=H.
hydra(0, A, A).
hydra(N, h(X, X), A):- N>0, N0 is N-1, hydra(N0, X, A).

% ?- hydra(3, H).
%@ H = h(h(h(_A, _A), h(_A, _A)), h(h(_A, _A), h(_A, _A))) ;
%@ false.
% ?- hydra(3, H, H).
%@ H = h(_S1, _S1), % where
%@     _S1 = h(h(h(_S1, _S1), h(_S1, _S1)), h(h(_S1, _S1), h(_S1, _S1))) ;
%@ false.
7

It’s first time to use the '$factorize_term'/3 on iMac intel 2020, macOS sequoia.
It is astonishing :star_struck:

% ?- time((hydra(10000, _X), hydra(10000, _Y, _Y),
%	'$factorize_term'(g(_X, _Y), _Skel, _Coa), length(_Coa, Len))),
%	writeln(unifying),
%	maplist(unify_pair, _Coa), writeln(unified), _Skel == g(_X, _Y),
%	writeln(verified).
%@ % 40,003 inferences, 0.006 CPU in 0.008 seconds (77% CPU, 6567559 Lips)
%@ unifying
%@ unified
%@ verified
%@ Len = 19999 .
9

I think that is correct. Nice formulation.

As many similar core algorithms in SWI-Prolog, the implementation works by temporarily modifying the term. There is no search involved. In this case (and many others), it uses the garbage collection bits to mark each compound as “seen”. If we hit one we have seen already, we have a case of sharing. Then we need a second scan to remove all marks. One could also store the location of the marks. It is long ago, but AFAIK comparing these two selected re-visiting as generally more efficient. In addition, it does not require a place to store this data, so no allocation issues.

So, it just reveals the actual structure in memory, which is the same as using same_term/2.

11

Not AFAIK. The profiler should give some hint how expensive the re-unify is. If there are many short cycles, moving that into a single predicate is probably a big win. If there are few long cycles, the gain will be small.