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

Groups > comp.lang.prolog > #14805

The End of Debray Allocator (Was: The End of Deutsch-Schorr-Waite [cycle_detection.rs])

Show all headers | View raw

Hi,

While I had an allocator that was reusing
slots. But for release 1.3.6 I rejected it,
and went back to a different solution.

The new solution is more interesting, since
it allows to have exec_unify() and exec_build()
to be commutative with itself and each other,

they do not have to be called in input order
anymore. The generated code shows a trait of
relocatability consisting of blocks that can

be executed in varying order. The following
things went out of the window:

- Old Take: 3 variable instructions,
   1 intruction for annonymous variable,
   1 instruction for first variable,
   1 instruction for non-first variable.
   The first variable instruction did the
   slot reuse via an overwrite.

- New Take: 2 variable instructions,
   1 instruction for annonymous variable
   1 instruction for non-annonymous variable.
   The non-annonymous variable is clever, uses the
   state of the slot to dynamically figure out whether
   it is first or not. We loose slot overwriting.

That we cannnot overwrite slots anymore makes
the var displays bigger. But unlike in the Debray Allocator
for the WAM. The display is not WAM registers,

it is more volatile. Only used during neck optimized
built-ins and when creating the clause rest.
The bigger displays causes a small performance

penality, they have to be also initialized
particularly to make the algorithm work. But
the host programming language allocators do

that for us. The extra effort is compensated
that we are now more flexible in code generation,
and also more flexible in the builtin implementation.

As a first result, we removed the '$EVAL'/2 cludge,
to compile is/2. Possibly more things are to come.
Especially in the domain of static variable shunting.

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 comp.lang.prolog | 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 13:51 +0200
  Is Mild Shock going rogue? (Was: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:07 +0200
    Is Mostowski Collapse a professional mathematician (Was: Is Mild Shock going rogue?) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:16 +0200
      New Project Name: NovaCore becomes VibeCore (Re: Is Mostowski Collapse a professional mathematician) Mild Shock <janburse@fastmail.fm> - 2025-07-25 14:42 +0200
  Nice Printing Error Scryer Prolog (Was: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-26 21:33 +0200
    Dynamic unify_with_occurs_check/2 speed-up (Was: Nice Printing Error Scryer Prolog) Mild Shock <janburse@fastmail.fm> - 2025-07-26 21:37 +0200
  The End of Deutsch-Schorr-Waite [cycle_detection.rs] (Was: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-28 10:50 +0200
    Backtracking Branching Association List (Re: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-07-28 11:02 +0200
      Do it like in acyclic_decompose/3 (Re: Backtracking Branching Association List) Mild Shock <janburse@fastmail.fm> - 2025-07-28 11:38 +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
    Entering the Age of Rational Trees (2025) (Was: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-08-16 13:02 +0200
    The End of Debray Allocator (Was: The End of Deutsch-Schorr-Waite [cycle_detection.rs]) Mild Shock <janburse@fastmail.fm> - 2025-08-24 14:44 +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:45 +0200
    It was painful for my GC, but fixed now (Re: The pairs are nasty, otherwise not always slow!) Mild Shock <janburse@fastmail.fm> - 2025-07-30 14:51 +0200
  Scryer Prolog has the most useless max_depth (Re: Novacore goes Bisimulation: Scryer Prolog is Slow!) Mild Shock <janburse@fastmail.fm> - 2025-08-02 13:43 +0200
    Novacore goes native (=)/2 and (==)/2 bisimulation (Was: Scryer Prolog has the most useless max_depth) Mild Shock <janburse@fastmail.fm> - 2025-08-02 14:45 +0200

csiph-web