Fast Term Factorization via Paige-Tarjan: Bypassing ==/2 and compare/2

General
1

I am experimenting with an alternative approach to term factorization based on the Paige-Tarjan minimization method. From a theoretical standpoint, I doubt the current implementation of term_factorized/3—which relies on compare/2 and ==/2—has a strict theoretical basis for evaluating cyclic term equivalence, and it inherently risks structural traversal overhead.

To address this, I implemented the initial extraction phase in C using the Foreign Language Interface. This completely bypasses Prolog-level structural checks and ==/2. Instead, it uses PL_compare to enforce strict O(1) physical memory address identity. It safely flattens cyclic structures into a minimal coalgebra vector, which is then passed back to Prolog for Paige-Tarjan minimization.

While this is “hot tested” and not yet exhaustively verified, the performance on massive cyclic structures is promising. Here is a test using a deeply nested cyclic graph (hydra/3):

% ?- 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).

pt_term_min_coa(Xs, Is, Mvec) :-
    c_extract_coa(Xs, Js, Tvec),
    pt_min_coa(Tvec, Mvec, Qmap),
    apply_quotient_map(Js, Qmap, Is).

On iMac intell 2020 macOS Tahoe 26.62
SWI-Prolog version 10.1.11 for x86_64-darwin

% ?- time((hydra(2000, _H, _A), _A=_H,  pt_term_min_coa([_H], Is, Mvec))).
%@ % 4,079 inferences, 0.011 CPU in 0.011 seconds (99% CPU, 376778 Lips)
%@ Is = [1],
%@ Mvec = u(h(1, 1)) .

% ?- time((hydra(10000, _H, _A), _A=_H,  pt_term_min_coa([_H], Is, Mvec))).
%@ % 20,078 inferences, 0.267 CPU in 0.268 seconds (100% CPU, 75065 Lips)
%@ Is = [1],
%@ Mvec = u(h(1, 1)) .

The C-level extraction isolates the physical pointers efficiently before applying the quotient map, completely avoiding infinite traversal or stack overflows without relying on ==/2.

2

Interesting indeed! But, PL_compare() is even more expensive than ==/2 as it walks both terms depth-first like ==/2, but when it finds a difference it must decide on the order rather than simply failing. There is also PL_same_compound() that compares two terms by address rather than content.

Anyway, a faster and more reliable term factorization is surely welcome, so please keep working on it.

3

Thanks for comment, Jan

Replacing ‘PL_compare’ with PL_same_compound, and adding some hashing,
It gets roughly 3 times faster, though not sure whether my hydra is suitable for benchmark test.
they always shrink drastically into one.

% ?- time((hydra(10000, _H, _A), _A=_H,  pt_term_coa([_H], Is, Mvec))).
%@ % 20,005 inferences, 0.106 CPU in 0.172 seconds (61% CPU, 189244 Lips)
%@ Is = [1],
%@ Mvec = u(h(1, 1)) .

% ?- time((generate_hydras(1000, _Xs), pt_term_coa(_Xs, Is, _Mvec))).
%@ % 1,006,003 inferences, 0.293 CPU in 0.401 seconds (73% CPU, 3436213 Lips)
%@ Is = [1, 1, 1, 1, 1, 1, 1, 1, 1|…] .

pt_term_coa(Xs, Is, Mvec) :-
    c_extract_coa(Xs, Js, Tvec),
    c_paige_tarjan(Tvec, Mvec, Qmap),
    apply_quotient_map(Js, Qmap, Is).

% ?- 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).

generate_hydras(0, []) :- !.
generate_hydras(N, [H|Rest]) :-
    N > 0,
    hydra(N, H, A), A=H,
    N1 is N - 1,
    generate_hydras(N1, Rest).