But we can also do without term_variables/3 or
term_variable/2. don’ have tries in my system.
But I recently introduced Okasaki tree, but it

turned out that they are totally useless. What
works better in my case was hash+keysort, as
strange as it may sound.

I believe it depends on the grouping factor.
If there is a high grouping factor there is
higher precentage of read from the grouping

datastructure and than write into the
grouping datastructure. So if read is only O(1)
as in hash, you have better preformance than if

read is O(log N) as in tree. And you can also
afford a later keysort. Here is the bagof/3 choker
with hash+keysort compared to tree:

/* Dogelog Player 1.2.5, tree */
?- time(test3).
% Zeit 6073 ms, GC 1 ms, Lips 5182931, Uhr 10.11.2024 00:58
true.

/* Dogelog Player 1.2.5, hash+keysort */
?- time(test4).
% Zeit 3070 ms, GC 2 ms, Lips 9808736, Uhr 10.11.2024 00:58
true.

Quite amazing, if we compare to the traditional bagof/3:

/* Trealla Prolog 2.59.17, keysort */
?- time(test).
% Time elapsed 13.280s, 16158649 Inferences, 1.217 MLips
true.

Mild Shock schrieb:

It all began with the bagof/3 choker:

test :-
   bagof(X, N^(between(1,300,X), between(1,300,N),
      length(_,N)), _), fail; true.

Which makes Prolog system tumble:

/* SWI-Prolog 9.3.14 */
?- time(test).
Action (h for help) ? abort
% 468,739 inferences, 52.016 CPU in 53.069 seconds (98% CPU, 9012 Lips) Execution Aborted

/* Scryer Prolog 0.9.4-201 */
?- time(test).
^C   % CPU time: 110.153s, 145_508_466 inferences
   error('$interrupt_thrown',repl/0).

Its mostlikely the same old problem that was
observed years ago, in that the canonicalization
of variables before the keysort/2 creates long

instantiation chains. It can be solved by adjusting
the unification order. Here is a take in Dogelog Player:

/* Dogelog Player 1.2.5 */
?- time(test).
% Zeit 7405 ms, GC 21 ms, Lips 3962971, Uhr 10.11.2024 00:57
true.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

How did I solve the variant key problem,
which is present in the bagof/3 choker? I
went with numbervars/3 and unnumbervars/3.

But most likely if tries are used for tabling,
they can already do the same. I was looking
a little bit at the trie_insert() C implementation

used in SWI-Prolog distinct/1. It seems distinct/1
can solve the variant key problem by means of
trie_insert/2 alone, since for ordinary

terms it uses a no-op:

trieable(Term, ForTrie) :-
acyclic_term(Term),
term_attvars(Term, []),
!,
ForTrie = t(Term).

Not sure what is needed to enumerate variant key,
turn them back into ordinary terms together
with the associated values. I am also using the

nb_linkarg/3 trick for findall/3 inside bagof/3.
So the values are basically these single linked
lists. The same approach for bagof/3, is also

suitable for aggregate/3.

Mild Shock schrieb:

But we can also do without term_variables/3 or
term_variable/2.  don’ have tries in my system.
But I recently introduced Okasaki tree, but it

turned out that they are totally useless. What
works better in my case was hash+keysort, as
strange as it may sound.

I believe it depends on the grouping factor.
If there is a high grouping factor there is
higher precentage of read from the grouping

datastructure and than write into the
grouping datastructure. So if read is only O(1)
as in hash, you have better preformance than if

read is O(log N) as in tree. And you can also
afford a later keysort. Here is the bagof/3 choker
with hash+keysort compared to tree:

/* Dogelog Player 1.2.5, tree */
?- time(test3).
% Zeit 6073 ms, GC 1 ms, Lips 5182931, Uhr 10.11.2024 00:58
true.

/* Dogelog Player 1.2.5, hash+keysort */
?- time(test4).
% Zeit 3070 ms, GC 2 ms, Lips 9808736, Uhr 10.11.2024 00:58
true.

Quite amazing, if we compare to the traditional bagof/3:

/* Trealla Prolog 2.59.17, keysort */
?- time(test).
% Time elapsed 13.280s, 16158649 Inferences, 1.217 MLips
   true.

Mild Shock schrieb:

It all began with the bagof/3 choker:

test :-
    bagof(X, N^(between(1,300,X), between(1,300,N),
       length(_,N)), _), fail; true.

Which makes Prolog system tumble:

/* SWI-Prolog 9.3.14 */
?- time(test).
Action (h for help) ? abort
% 468,739 inferences, 52.016 CPU in 53.069 seconds (98% CPU, 9012 Lips)
Execution Aborted

/* Scryer Prolog 0.9.4-201 */
?- time(test).
^C   % CPU time: 110.153s, 145_508_466 inferences
    error('$interrupt_thrown',repl/0).

Its mostlikely the same old problem that was
observed years ago, in that the canonicalization
of variables before the keysort/2 creates long

instantiation chains. It can be solved by adjusting
the unification order. Here is a take in Dogelog Player:

/* Dogelog Player 1.2.5 */
?- time(test).
% Zeit 7405 ms, GC 21 ms, Lips 3962971, Uhr 10.11.2024 00:57
true.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)