Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.math > #639381

Backtracking Branching Association List (Was: The End of Deutsch-Schorr-Waite [cycle_detection.rs])

Show all headers | View raw

Hi,

So the 115 ms by Dogelog Player are faster than the
0.130s by Scryer Prolog. Quite amazing! From
Dogelog Player library(math):

/**
  * acyclic_term(T): [TC2 8.3.11]
  * The predicate succeeds when the Prolog term T is an acyclic term,
  * otherwise the predicate fails.
  */
% acyclic_term(+Term)
acyclic_term(X) :- sys_cyclic_term(X, []), !, fail.
acyclic_term(_).

% sys_cyclic_term(+Term, +List)
sys_cyclic_term(X, S) :- compound(X),
    member(Y, S),
    same_term(X, Y), !.
sys_cyclic_term(X, S) :- compound(X),
    X =.. [_|L],
    member(Y, L),
    sys_cyclic_term(Y, [X|S]).

Algorithms that implicitly detect sharing cannot
do much? Since we only need to find a first cycle?
Also a challenge to bring the association list to
native and lets say turn it into a hash table,

don't know yet when and how even somebody would
attempt that. Big advantage of anything not using
Deutsch-Schorr-Waite , no write operation into the
given term. Write operation are sometimes

poison for the CPU and the RAM.

Bye

Mild Shock schrieb:
> Hi,
> 
> Assume that we live in a world where we
> have excess memory. So we can afford stacks!
> And then make the crucial observation,
> 
> we can use the stack of the Prolog engine,
> no need to create an artificial stack in C,
> or use the native stack of C.
> 
> I guess SWI-Prolog has already groked the
> first we can "afford stacks". But did anybody
> already grok the "100% Prolog" idea?
> 
> Well we are not yet there 100% Prolog
> has still an overhead. Here is a little
> test acyclic_term/2:
> 
> /* SWI-Prolog 9.3.26, C Stacks and/or Agendas */
> ?- time((between(1,30,_), acyclic2, fail; true)).
> % 330,150 inferences, 0.016 CPU in 0.023 seconds
> (69% CPU, 21129600 Lips)
> true.
> 
> /* Trealla Prolog 2.79.6, ?? */
> ?- time((between(1,30,_), acyclic2, fail; true)).
> % Time elapsed 0.063s, 643413 Inferences, 10.166 MLips
>     true.
> 
> /* Dogelog Player 1.3.5, 100% Prolog */
> ?- time((between(1,30,_), acyclic2, fail; true)).
> % Zeit 115 ms, GC 0 ms, Lips 11803904, Uhr 28.07.2025 10:03
> true.
> 
> /* Scryer Prolog 0.9.4-417, Deutsch-Schorr-Waite  */
> ?- time((between(1,30,_), acyclic2, fail; true)).
> % CPU time: 0.130s, 626_829 inferences
> true.
> 
> Bye

Back to sci.math | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Novacore goes Bisimulation: Scryer Prolog is Slow! Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:30 +0200
  Is Mild Shock going rogue? (Re: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:32 +0200
    Is Mostowski Collapse a professional mathematician (Re: Is Mild Shock going rogue?) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:32 +0200
      New Project Name: NovaCore becomes VibeCore (Re: Is Mostowski Collapse a professional mathematician) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:43 +0200
  The End of Deutsch-Schorr-Waite [cycle_detection.rs] (Re: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-28 10:51 +0200
    Backtracking Branching Association List (Was: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-07-28 10:57 +0200
      Do it like in acyclic_decompose/3 (Was: Backtracking Branching Association List) Mild Shock <janburse@fastmail.fm> - 2025-07-28 11:39 +0200
        Cache-Trashing vs Cache-Friendly [Code Example] (Re: Do it like in acyclic_decompose/3) Mild Shock <janburse@fastmail.fm> - 2025-07-28 17:27 +0200
    Re: The End of Deutsch-Schorr-Waite [cycle_detection.rs] (Re: Novacore goes Bisimulation: Scryer Prolog is Slow!) Jordon Molokovsky <ovm@lorr.ru> - 2025-07-28 12:56 +0000
      I guess your brain was "overheating" (Re: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-07-28 17:17 +0200
        Re: I guess your brain was "overheating" (Re: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Alton Grammatakakis <kl@aaasi.gr> - 2025-07-28 16:09 +0000
          The difference is only in one letter "t" or "d" (Was: I guess your brain was "overheating") Mild Shock <janburse@fastmail.fm> - 2025-07-28 21:17 +0200
          Re: You literally wrote "overheat" (Re: I guess your brain was "overheating" (Re: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Neury Valetov <ntt@uovrav.ru> - 2025-07-28 19:44 +0000
            Don't put large memory in your computer it might "overheat" (Re: You literally wrote "overheat") Mild Shock <janburse@fastmail.fm> - 2025-07-29 15:57 +0200
            Re: Don't put large memory in your computer it might "overheat" (Was: You literally wrote "overheat") Mizraim Zelenenkov <iall@zm.ru> - 2025-07-29 16:00 +0000
              Why Russ Bots Again: Micro Penis? (Was: Don't put large memory in your computer it might "overheat" ) Mild Shock <janburse@fastmail.fm> - 2025-07-29 23:16 +0200
      Re: I guess your brain was "overheating" (Re: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Emile Paduchev <mcc@clleeeme.ru> - 2025-07-28 15:53 +0000
        You literally wrote "overheat" (Was: I guess your brain was "overheating") Mild Shock <janburse@fastmail.fm> - 2025-07-28 21:19 +0200
    Entering the Age of Rational Trees (2025) (Re: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-08-16 13:05 +0200
  The pairs are nasty, otherwise not always slow! (Re: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-30 14:44 +0200
  It was painful for my GC, but fixed now (Was: The pairs are nasty, otherwise not always slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-30 14:49 +0200

csiph-web