On Fri, Sep 17, 2021 at 7:17 AM Mostowski Collapse <janburse@fastmail.fm> wrote:
>
> About Exceptions: Thats just building ISO core
> standard Prolog error terms.
>
> About Garbage Collection: Thats just Prolog
> garbage collection, which does shrink some
> single linked lists, which ordinary
> programmig language GC cannot do,
>

Okay, so.... you're building your own garbage collection on top of
Python's, and you're wondering why it's slow?

Change your code to not try to implement one language inside another,
and you'll see a massive performance improvement.

ChrisA

On 16/09/21 2:56 pm, Mostowski Collapse wrote:
> I can access the functor of a compound via:
>
> obj.functor
>
> but when I flatten Compound into arrays, it would become:
>
> obj[0]
>
> Should I declare a constant FUNCTOR = 0?

You could, but keep in mind that access to a global in Python
is somewhat expensive, since it requires a dictionary lookup.

There's always a tradeoff between clarity and efficiency.
In this case, I think obj[0] is clear enough -- the reader
will be well aware that the first item of a term is the
functor. Especially if you use a name that makes it clear
what kind of object it is, rather than a generic name such
as "obj".

--
Greg

On 16/09/21 6:56 am, Mostowski Collapse wrote:
> What could be slow, repeatedly requesting the "args"
> field. Maybe I should do:
>
> help = term.args
> i = 0
> while i < len(help) - 1:
> ____mark_term(help[i])
> ____i += 1
> term = help[i]

Yes, that will certainly help.

But you're still evaluating len(help) - 1 every time around
the loop, so this is even better:

help = term.args
n = len(help) - 1
i = 0
while i < n:
mark_term(help[i])
i += 1
term = help[i]

Some general principles to be aware of:

* Almost nothing is free -- Python very literally does what
you tell it to do, even if it looks dumb.

* Access to attributes and global variables is expensive
(requires at least one dict lookup, often more in the case
of attributes).

* Access to *local* variables, on the other hand, is very
cheap (essentially an array lookup).

* Function calls are expensive -- both to look up the name, if
it's global, which it usually is, and the machinery of the
call itself.

* Creating objects is expensive. Creating instances of
user-defined objects is more expensive than built-in ones.

--
Greg

Thanks for your response, will have a look.
Ok, dis() is all that is need to disassemble.

Very cool!

A long term goal could be indeed to have
a Prolog interpreter produce 20MLips, like
SWI-Prolog, but tightly integrated into

Python. So that it directly makes use of
the Python objects and the Python garbage
collection like Dogelog Runtime.

Although Dogelog Runtime has its own
garbage collection, its only used to help
the native Python garbage collection.

The result is that you can enjoy bi-directly
calling Python. For example the Prolog
adding of two numbers is realized as:

###
# +(A, B, C): [ISO 9.1.7]
# The predicate succeeds in C with the sum of A and B.
##
def eval_add(alpha, beta):
check_number(alpha)
check_number(beta)
try:
return alpha + beta
except OverflowError:
raise make_error(Compound("evaluation_error", ["float_overflow"]))

And then register it:

add("+", 3, make_dispatch(eval_add, MASK_MACH_FUNC))

Could also map the exception to a Prolog term later.
Thats not so much an issue for speed. The sunshine
case is straight forward.

But I might try dis() on eval_add(). Are exceptions
blocks in Python cheap or expensive? Are they like
in Java, some code annotation, or like in Go

programming language pushing some panic handler?

Greg Ewing schrieb:
> On 16/09/21 4:23 am, Mostowski Collapse wrote:
>> I really wonder why my Python implementation
>> is a factor 40 slower than my JavaScript implementation.
>
> There are Javascript implementations around nowadays that are
> blazingly fast. Partly that's because a lot of effort has been
> put into them, but it's also because Javascript is a different
> language. There are many dynamic aspects to Python that make
> fast implementations difficult.
>
>> I use in Python:
>>
>>    temp = [NotImplemented] * code[pos]
>>    pos += 1
>>
>> is the the idiom [_] * _ slow?
>
> No, on the contrary it's probably the fastest way to do it
> in Python. You could improve it a bit by precomputing
> [NotImplemented]:
>
> # once at the module level
> NotImplementedList = [NotImplemented]
>
> # whenever you want a new list
> temp = NotImplementedList * code[pos]
>
> That's probably at least as fast as built-in function for
> creating lists would be.
>
>> does it really first create an
>> array of size 1 and then enlarge it?
>
> It does:
>
> >>> def f(code, pos):
> ...  return [NotImplemented] * code[pos]
> ...
> >>> from dis import dis
> >>> dis(f)
>   2           0 LOAD_GLOBAL              0 (NotImplemented)
>               2 BUILD_LIST               1
>               4 LOAD_FAST                0 (code)
>               6 LOAD_FAST                1 (pos)
>               8 BINARY_SUBSCR
>              10 BINARY_MULTIPLY
>              12 RETURN_VALUE
>
> BTW, the Python terminology is "list", not "array".
> (There *is* something in the stdlib called an array, but
> it's rarely used or needed.)
>

No its cooperative. Usually objects do get
garbage collected by the native garbage collector
of the host language in Dogelog runtime.

The Prolog garbage collection is only to help
the host language garbage collector when you have
a deep recursion in Prolog.

You can then reclaim intermediate variables.
A simple example to test the slightly idio-
syncratic Prolog garbage collection is:

fibo(0, 1) :- !.
fibo(1, 1) :- !.
fibo(N, X) :-
M is N-1, fibo(M, Y),
L is M-1, fibo(L, Z),
X is Y+Z.

When running fibo(30,X) SWI-Prolog does around
800 garbage collections to keep the environment
small. But SWI-Prolog allocates all its objects

only very seldom on the heap. It uses its own
stack. On the other hand Dogelog runtime creates
everything on the heap. And completely relies on

the host language garbage collection. It only
helps the host language garbage collection it
that it performs from time to time this movement:

Before:

-->[ A ]-->[ B ]-->[ C ]-->

After:

-->[ A ]---------->[ C ]-->

A,B,C are objects of type Variable. The above
movement only happens for objects of type Variables
from time to time. For objects of type Compound

no modifications are done during Prolog garbage
collection. The Prolog garbage collection aggressively
nulls the Variable object B, and the host language

later will garbage collect what the Variable object B
was pointing to. But the Variable object B might
nevertheless have point to something shared with

some other Variable object or a local or a global
Python variable, or a Compound. This is then all
courtesy of the host language to decide reachability.

Chris Angelico schrieb:
> On Fri, Sep 17, 2021 at 7:17 AM Mostowski Collapse <janburse@fastmail.fm> wrote:
>>
>> About Exceptions: Thats just building ISO core
>> standard Prolog error terms.
>>
>> About Garbage Collection: Thats just Prolog
>> garbage collection, which does shrink some
>> single linked lists, which ordinary
>> programmig language GC cannot do,
>>
>
> Okay, so.... you're building your own garbage collection on top of
> Python's, and you're wondering why it's slow?
>
> Change your code to not try to implement one language inside another,
> and you'll see a massive performance improvement.
>
> ChrisA
>

The Prolog garbage collection that does
the movement on the variable trail is only
a very small fraction of the runtime.

The garbage collection time is measured.
Some measurements with version 0.9.5
took the following values:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Standard Python Version, Warm Run
% ?- time(fibo(23,X)).
% % Wall 3865 ms, gc 94 ms, 71991 lips
% X = 46368.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% GraalVM Python Version, Warm Warm Run
% ?- time(fibo(23,X)).
% % Wall 695 ms, gc 14 ms, 400356 lips
% X = 46368.

The "gc" timing measures Prolog garbage
collection. So you get the following percentage
of time spent in Prolog garbage collection:

Standard Python: 94 / 3865 = 2.4%

GraalVM Python: 14 / 695 = 2.0%

I consider this a good result. The Prolog
garbage collection is not utterly expensive.
The detecting the movement and performing

the variable movement on the trail, doesn't
take so much time. Currently the garbage collection
in Dogelog runtime is configured towards

synchronization with 60FPS, it does around
60-120 garbage collections per second. This
is less than what SWI-Prolog does.

SWI-Prolog has a much higher GC rate.

But I did not yet measure new version 0.9.6.

Mostowski Collapse schrieb:
> No its cooperative. Usually objects do get
> garbage collected by the native garbage collector
> of the host language in Dogelog runtime.
>
> The Prolog garbage collection is only to help
> the host language garbage collector when you have
> a deep recursion in Prolog.
>
> You can then reclaim intermediate variables.
> A simple example to test the slightly idio-
> syncratic Prolog garbage collection is:
>
> fibo(0, 1) :- !.
> fibo(1, 1) :- !.
> fibo(N, X) :-
>    M is N-1, fibo(M, Y),
>    L is M-1, fibo(L, Z),
>    X is Y+Z.
>
> When running fibo(30,X) SWI-Prolog does around
> 800 garbage collections to keep the environment
> small. But SWI-Prolog allocates all its objects
>
> only very seldom on the heap. It uses its own
> stack. On the other hand Dogelog runtime creates
> everything on the heap. And completely relies on
>
> the host language garbage collection. It only
> helps the host language garbage collection it
> that it performs from time to time this movement:
>
> Before:
>
>     -->[ A ]-->[ B ]-->[ C ]-->
>
> After:
>
>     -->[ A ]---------->[ C ]-->
>
> A,B,C are objects of type Variable. The above
> movement only happens for objects of type Variables
> from time to time. For objects of type Compound
>
> no modifications are done during Prolog garbage
> collection. The Prolog garbage collection aggressively
> nulls the Variable object B, and the host language
>
> later will garbage collect what the Variable object B
> was pointing to. But the Variable object B might
> nevertheless have point to something shared with
>
> some other Variable object or a local or a global
> Python variable, or a Compound. This is then all
> courtesy of the host language to decide reachability.
>
> Chris Angelico schrieb:
>> On Fri, Sep 17, 2021 at 7:17 AM Mostowski Collapse
>> <janburse@fastmail.fm> wrote:
>>>
>>> About Exceptions: Thats just building ISO core
>>> standard Prolog error terms.
>>>
>>> About Garbage Collection: Thats just Prolog
>>> garbage collection, which does shrink some
>>> single linked lists, which ordinary
>>> programmig language GC cannot do,
>>>
>>
>> Okay, so.... you're building your own garbage collection on top of
>> Python's, and you're wondering why it's slow?
>>
>> Change your code to not try to implement one language inside another,
>> and you'll see a massive performance improvement.
>>
>> ChrisA
>>
>

Concerning garbage collection, did a long term
measurement for the first time. I measured
LIPS for fibonacci numbers, i.e. time(fibo(23,X)).

Doing the same thing 16 times, how long does it take?
Here is a depiction how the LIPS relatively differ in each run:
https://gist.github.com/jburse/c85297e97091caf22d306dd8c8be12fe#gistcomment-3896343

I can also calculate the mean and standard deviation.
From this we see that Python has a 5% deviation, whereas
GraalVM has a 1% deviation. So the GraalVM garbage

collector works more evenly? Disclaimer, I measured
different time spans, the GraalVM is now 7x times
faster than Standard Python, so this is inconclusive.

Mostowski Collapse schrieb am Freitag, 17. September 2021 um 10:58:57 UTC+2:
> The Prolog garbage collection that does
> the movement on the variable trail is only
> a very small fraction of the runtime.
>
> The garbage collection time is measured.
> Some measurements with version 0.9.5
> took the following values:
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> % Standard Python Version, Warm Run
> % ?- time(fibo(23,X)).
> % % Wall 3865 ms, gc 94 ms, 71991 lips
> % X = 46368.
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> % GraalVM Python Version, Warm Warm Run
> % ?- time(fibo(23,X)).
> % % Wall 695 ms, gc 14 ms, 400356 lips
> % X = 46368.
>
> The "gc" timing measures Prolog garbage
> collection. So you get the following percentage
> of time spent in Prolog garbage collection:
>
> Standard Python: 94 / 3865 = 2.4%
>
> GraalVM Python: 14 / 695 = 2.0%
>
> I consider this a good result. The Prolog
> garbage collection is not utterly expensive.
> The detecting the movement and performing
>
> the variable movement on the trail, doesn't
> take so much time. Currently the garbage collection
> in Dogelog runtime is configured towards
>
> synchronization with 60FPS, it does around
> 60-120 garbage collections per second. This
> is less than what SWI-Prolog does.
>
> SWI-Prolog has a much higher GC rate.
>
> But I did not yet measure new version 0.9.6.
>
> Mostowski Collapse schrieb:
> > No its cooperative. Usually objects do get
> > garbage collected by the native garbage collector
> > of the host language in Dogelog runtime.
> >
> > The Prolog garbage collection is only to help
> > the host language garbage collector when you have
> > a deep recursion in Prolog.
> >
> > You can then reclaim intermediate variables.
> > A simple example to test the slightly idio-
> > syncratic Prolog garbage collection is:
> >
> > fibo(0, 1) :- !.
> > fibo(1, 1) :- !.
> > fibo(N, X) :-
> > M is N-1, fibo(M, Y),
> > L is M-1, fibo(L, Z),
> > X is Y+Z.
> >
> > When running fibo(30,X) SWI-Prolog does around
> > 800 garbage collections to keep the environment
> > small. But SWI-Prolog allocates all its objects
> >
> > only very seldom on the heap. It uses its own
> > stack. On the other hand Dogelog runtime creates
> > everything on the heap. And completely relies on
> >
> > the host language garbage collection. It only
> > helps the host language garbage collection it
> > that it performs from time to time this movement:
> >
> > Before:
> >
> > -->[ A ]-->[ B ]-->[ C ]-->
> >
> > After:
> >
> > -->[ A ]---------->[ C ]-->
> >
> > A,B,C are objects of type Variable. The above
> > movement only happens for objects of type Variables
> > from time to time. For objects of type Compound
> >
> > no modifications are done during Prolog garbage
> > collection. The Prolog garbage collection aggressively
> > nulls the Variable object B, and the host language
> >
> > later will garbage collect what the Variable object B
> > was pointing to. But the Variable object B might
> > nevertheless have point to something shared with
> >
> > some other Variable object or a local or a global
> > Python variable, or a Compound. This is then all
> > courtesy of the host language to decide reachability.
> >
> > Chris Angelico schrieb:
> >> On Fri, Sep 17, 2021 at 7:17 AM Mostowski Collapse
> >> <janb...@fastmail.fm> wrote:
> >>>
> >>> About Exceptions: Thats just building ISO core
> >>> standard Prolog error terms.
> >>>
> >>> About Garbage Collection: Thats just Prolog
> >>> garbage collection, which does shrink some
> >>> single linked lists, which ordinary
> >>> programmig language GC cannot do,
> >>>
> >>
> >> Okay, so.... you're building your own garbage collection on top of
> >> Python's, and you're wondering why it's slow?
> >>
> >> Change your code to not try to implement one language inside another,
> >> and you'll see a massive performance improvement.
> >>
> >> ChrisA
> >>
> >

On 17/09/21 7:56 am, Mostowski Collapse wrote:
> The trail in Dogelog
> Runtime is a single linked list:
>
>     -->[ A ]-->[ B ]-->[ C ]-->
>
> Now if B becomes unused, you need to rewire
> the trail, it should then look like:
>
>     -->[ A ]---------->[ C ]-->

Python has a way of creating weak references (see the weakref
module). You could set the trail up like this:

-->[*]-->[*]-->[*]-->
| | |
v v v
[w] [w] [w]
: : :
v v v
[A] [B] [C]

where [w] is a weak reference object. Then you could periodically
scan the trail looking for dead weakref objects and remove the
corresponding [*] node from the list.

You can also attach callbacks to weakref objects that are triggered
when the referenced object dies. You might be able to make use of
that to remove items from the trail instead of the periodic scanning.

--
Greg

On 16/09/21 6:13 am, Mostowski Collapse wrote:
> So in Python I now do the following:
>
> peek = kb.get(functor, NotImplemented)
> if peek is not NotImplemented:

If you're able to use None instead of NotImplemented, you
could simplify that to

peek = kb.get(functor)
if peek:
...

> But if get() in Python is implemented under the hood with
> exception handling. ... then Python get() will probably be quite slow.

No, it doesn't use exceptions as far as I know. It should
be fairly fast.

--
Greg

On 17/09/21 8:41 pm, Mostowski Collapse wrote:
> Are exceptions
> blocks in Python cheap or expensive? Are they like
> in Java, some code annotation, or like in Go
> programming language pushing some panic handler?

They're not free, but they're not hugely expensive either.
Don't be afraid to use them when it makes sense to do so.

I'm not sure what you mean by "some code annotations",
so I don't know how to answer that question. I suspect
that the way exceptions are implemented in the JVM is
similar to the way CPython does it, but I don't know
a lot about the JVM.

--
Greg

Yeah, it seems weak references could indeed spare
me mark_term(). But then I am stil left with sweep_trail().
I did not yet measure what takes more time mark_term()
or sweep_trail(). The displayed "gc" is the sum of both.

From what I have seen, very large trail practically reduced
to a zero trail during Prolog GC, I am assuming that
mark_term() is not the working horse. Usually mark_term()
only marks what is not-Garbage, and sweep_trail()

has to deal with Garbage and not-Garbage. And there
is usually a lot of Garbage, much more than not-Garbage.
Finding the objects that survive, is like finding the needle
in the haystack, except we do not have to scan the

haystack, the needles are on the goal list. But afterwards,
the second pass, scanning the trail is the work of Heracles
cleaning the Augeas stables. This scan is trowing away the
hay and keeping the needles.

Greg Ewing schrieb am Samstag, 18. September 2021 um 05:49:37 UTC+2:
> On 17/09/21 7:56 am, Mostowski Collapse wrote:
> > The trail in Dogelog
> > Runtime is a single linked list:
> >
> > -->[ A ]-->[ B ]-->[ C ]-->
> >
> > Now if B becomes unused, you need to rewire
> > the trail, it should then look like:
> >
> > -->[ A ]---------->[ C ]-->
> Python has a way of creating weak references (see the weakref
> module). You could set the trail up like this:
>
> -->[*]-->[*]-->[*]-->
> | | |
> v v v
> [w] [w] [w]
> : : :
> v v v
> [A] [B] [C]
>
> where [w] is a weak reference object. Then you could periodically
> scan the trail looking for dead weakref objects and remove the
> corresponding [*] node from the list.
>
> You can also attach callbacks to weakref objects that are triggered
> when the referenced object dies. You might be able to make use of
> that to remove items from the trail instead of the periodic scanning.
>
> --
> Greg

On Sun, Sep 19, 2021 at 11:46 AM Mostowski Collapse <bursejan@gmail.com> wrote:
>
> Yeah, it seems weak references could indeed spare
> me mark_term(). But then I am stil left with sweep_trail().
> I did not yet measure what takes more time mark_term()
> or sweep_trail(). The displayed "gc" is the sum of both.
>
> From what I have seen, very large trail practically reduced
> to a zero trail during Prolog GC, I am assuming that
> mark_term() is not the working horse. Usually mark_term()
> only marks what is not-Garbage, and sweep_trail()
>
> has to deal with Garbage and not-Garbage. And there
> is usually a lot of Garbage, much more than not-Garbage.
> Finding the objects that survive, is like finding the needle
> in the haystack, except we do not have to scan the

If you stop referring to something, it is garbage. Python will dispose of it.

You literally need to do nothing at all, and let the language take
care of things.

ChrisA

I am refering to:

Greg Ewing schrieb:
> where [w] is a weak reference object. Then you could periodically
> scan the trail looking for dead weakref objects and remove the
> corresponding [*] node from the list.
>
> You can also attach callbacks to weakref objects that are triggered
> when the referenced object dies. You might be able to make use of
> that to remove items from the trail instead of the periodic scanning.

Question to Chris Angelico: If I stay with my
sweep_trail(), which is the periodically scanning,
I can use a single linked list.

On the other hand if I would use the trigger
from Python, I possibly would need a double linked
list, to remove an element.

Chris Angelico, is there a third option, that I have
overlooked? Single linked list uses less space
than double linked list, this why I go with scan.

Chris Angelico schrieb:
> On Sun, Sep 19, 2021 at 11:46 AM Mostowski Collapse <bursejan@gmail.com> wrote:
>>
>> Yeah, it seems weak references could indeed spare
>> me mark_term(). But then I am stil left with sweep_trail().
>> I did not yet measure what takes more time mark_term()
>> or sweep_trail(). The displayed "gc" is the sum of both.
>>
>> From what I have seen, very large trail practically reduced
>> to a zero trail during Prolog GC, I am assuming that
>> mark_term() is not the working horse. Usually mark_term()
>> only marks what is not-Garbage, and sweep_trail()
>>
>> has to deal with Garbage and not-Garbage. And there
>> is usually a lot of Garbage, much more than not-Garbage.
>> Finding the objects that survive, is like finding the needle
>> in the haystack, except we do not have to scan the
>
> If you stop referring to something, it is garbage. Python will dispose of it.
>
> You literally need to do nothing at all, and let the language take
> care of things.
>
> ChrisA
>

The trail itself can possibly not be eliminated. Its like a
database logfile. The trail is used during backtracking to
undo variable bindings. Which is like a database rollback.

Here is an example where a tail is used:

/* X equals 1 or X equals 2 */
?- X=1; X=2.
X = 1;
X = 2.

In the first answer the trail will have recorded that X
was bound to 1. When the second answer is requested,
the trail is used to unbind X, so that it can be bound to 2.

The Prolog garbage collection is a compactification
of the trail. Maybe databases can do the same with their
logfiles, for example if a logfile contains an insert and

then a delete of the same row, then these two logentries
can be merged. The only difference here is that Prolog
garbage collection primarily compactes towards trail

entries that have become irrelevant. This is part of
intelligent bracktracking, and backjumping over multiple
goal invocations, that didn't record a choice point.

The Prolog garbage collection can compact the trail
before backjumping happens. So that Prolog search
has more space available.

Mostowski Collapse schrieb am Sonntag, 19. September 2021 um 10:51:03 UTC+2:
> I am refering to:
>
> Greg Ewing schrieb:
> > where [w] is a weak reference object. Then you could periodically
> > scan the trail looking for dead weakref objects and remove the
> > corresponding [*] node from the list.
> >
> > You can also attach callbacks to weakref objects that are triggered
> > when the referenced object dies. You might be able to make use of
> > that to remove items from the trail instead of the periodic scanning.
> Question to Chris Angelico: If I stay with my
> sweep_trail(), which is the periodically scanning,
> I can use a single linked list.
>
> On the other hand if I would use the trigger
> from Python, I possibly would need a double linked
> list, to remove an element.
>
> Chris Angelico, is there a third option, that I have
> overlooked? Single linked list uses less space
> than double linked list, this why I go with scan.
>
> Chris Angelico schrieb:
> > On Sun, Sep 19, 2021 at 11:46 AM Mostowski Collapse <burs...@gmail.com> wrote:
> >>
> >> Yeah, it seems weak references could indeed spare
> >> me mark_term(). But then I am stil left with sweep_trail().
> >> I did not yet measure what takes more time mark_term()
> >> or sweep_trail(). The displayed "gc" is the sum of both.
> >>
> >> From what I have seen, very large trail practically reduced
> >> to a zero trail during Prolog GC, I am assuming that
> >> mark_term() is not the working horse. Usually mark_term()
> >> only marks what is not-Garbage, and sweep_trail()
> >>
> >> has to deal with Garbage and not-Garbage. And there
> >> is usually a lot of Garbage, much more than not-Garbage.
> >> Finding the objects that survive, is like finding the needle
> >> in the haystack, except we do not have to scan the
> >
> > If you stop referring to something, it is garbage. Python will dispose of it.
> >
> > You literally need to do nothing at all, and let the language take
> > care of things.
> >
> > ChrisA
> >

On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janburse@fastmail.fm> wrote:
>
> I am refering to:
>
> Greg Ewing schrieb:
> > where [w] is a weak reference object. Then you could periodically
> > scan the trail looking for dead weakref objects and remove the
> > corresponding [*] node from the list.
> >
> > You can also attach callbacks to weakref objects that are triggered
> > when the referenced object dies. You might be able to make use of
> > that to remove items from the trail instead of the periodic scanning.
>
> Question to Chris Angelico: If I stay with my
> sweep_trail(), which is the periodically scanning,
> I can use a single linked list.
>
> On the other hand if I would use the trigger
> from Python, I possibly would need a double linked
> list, to remove an element.
>
> Chris Angelico, is there a third option, that I have
> overlooked? Single linked list uses less space
> than double linked list, this why I go with scan.
>

I don't know. I don't understand your code well enough to offer advice
like that, because *your code is too complicated* and not nearly clear
enough.

But however it is that you're doing things, the best way is almost
always to directly refer to objects. Don't fiddle around with creating
your own concept of a doubly-linked list and a set of objects; just
refer directly to the objects. Let Python be Python, don't try to
build your own language on top of it.

ChrisA

sympy also builds a language on top of Python.
pandas also builds a language on top of Python.

Is there some pope that says this wouldn't be
allowed, I dont think so, otherwise sympy, pandas, etc..

wouldn't exist. I dont understand your argument.

Chris Angelico schrieb:
> On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janburse@fastmail.fm> wrote:
>>
>> I am refering to:
>>
>> Greg Ewing schrieb:
>> > where [w] is a weak reference object. Then you could periodically
>> > scan the trail looking for dead weakref objects and remove the
>> > corresponding [*] node from the list.
>> >
>> > You can also attach callbacks to weakref objects that are triggered
>> > when the referenced object dies. You might be able to make use of
>> > that to remove items from the trail instead of the periodic scanning.
>>
>> Question to Chris Angelico: If I stay with my
>> sweep_trail(), which is the periodically scanning,
>> I can use a single linked list.
>>
>> On the other hand if I would use the trigger
>> from Python, I possibly would need a double linked
>> list, to remove an element.
>>
>> Chris Angelico, is there a third option, that I have
>> overlooked? Single linked list uses less space
>> than double linked list, this why I go with scan.
>>
>
> I don't know. I don't understand your code well enough to offer advice
> like that, because *your code is too complicated* and not nearly clear
> enough.
>
> But however it is that you're doing things, the best way is almost
> always to directly refer to objects. Don't fiddle around with creating
> your own concept of a doubly-linked list and a set of objects; just
> refer directly to the objects. Let Python be Python, don't try to
> build your own language on top of it.
>
> ChrisA
>

Also I nowhere wrote that I would use doubly-linked list or
a set of objects. The trail is neither, its a single linked list. I
also refer directly to objects, I do not need the trail to refer

to objects. The Prolog trail is only a logbook. The Prolog trail
has similarity to a database log:

transaction journal, database log, binary log or audit **trail**
https://en.wikipedia.org/wiki/Transaction_log

Do you say Python should not be used to implement
such things? In my opinion, Python has a high potential
to implement Prolog, because it has also ast.parse()

and compile(). But I do not yet have a showcase that uses
these features of Python to compile Prolog. I dont work 24/7
and I cannot clone myself. Currently the Prolog code is interpreted.

I have a prototype where Prolog code is compiled into JavaScript,
but I did not yet try this approach with Python. Here you see how
JavaScript closures are generated, a first prototype:

const alt4 = make_defined([new Clause(1, [0, 0], function(
display, actual, cont) {return(new Compound(".", [new Compound(
"==", [deref(actual.args[0]), "end_of_file"]), new Compound(
".", [new Compound("$CUT", [deref(display[0])]), cont
])]))}, 0, undefined), new Clause(1, [0, 0], function(
display, actual, cont) {return(new Compound(".", [new Compound(
"expand_include", [deref(actual.args[0]), deref(actual.args[1]
), display[0] = new Variable()]), new Compound(".",
[new Compound("handle_term", [deref(display[0])]), new Compound(
".", ["fail", cont])])]))}, -1, undefined)]);

add("next_term", 1, new Clause(2, [0], function(display, actual,
cont) {return(new Compound(".", [new Compound("read_term",
[deref(actual.args[0]), display[0] = new Variable(),
new Compound(".", [new Compound("variable_names", [
display[1] = new Variable()]), "[]"])]), new Compound(
".", [new Compound(alt4, [deref(display[0]), deref(
display[1])]), cont])]))}, -1, undefined));

https://github.com/jburse/dogelog-moon/issues/184

Will do the same for Python in the next weeks. Then later this approach
will be combined with a few planned optimizations. So far got a 25%
speed increase for JavaScript with this new compilation scheme, but

there is no official release out yet, that features this approach. And
there should be much more in it, also for Python.

Mostowski Collapse schrieb am Sonntag, 19. September 2021 um 21:46:20 UTC+2:
> sympy also builds a language on top of Python.
> pandas also builds a language on top of Python.
>
> Is there some pope that says this wouldn't be
> allowed, I dont think so, otherwise sympy, pandas, etc..
>
> wouldn't exist. I dont understand your argument.
>
> Chris Angelico schrieb:
> > On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janb...@fastmail.fm> wrote:
> >>
> >> I am refering to:
> >>
> >> Greg Ewing schrieb:
> >> > where [w] is a weak reference object. Then you could periodically
> >> > scan the trail looking for dead weakref objects and remove the
> >> > corresponding [*] node from the list.
> >> >
> >> > You can also attach callbacks to weakref objects that are triggered
> >> > when the referenced object dies. You might be able to make use of
> >> > that to remove items from the trail instead of the periodic scanning.
> >>
> >> Question to Chris Angelico: If I stay with my
> >> sweep_trail(), which is the periodically scanning,
> >> I can use a single linked list.
> >>
> >> On the other hand if I would use the trigger
> >> from Python, I possibly would need a double linked
> >> list, to remove an element.
> >>
> >> Chris Angelico, is there a third option, that I have
> >> overlooked? Single linked list uses less space
> >> than double linked list, this why I go with scan.
> >>
> >
> > I don't know. I don't understand your code well enough to offer advice
> > like that, because *your code is too complicated* and not nearly clear
> > enough.
> >
> > But however it is that you're doing things, the best way is almost
> > always to directly refer to objects. Don't fiddle around with creating
> > your own concept of a doubly-linked list and a set of objects; just
> > refer directly to the objects. Let Python be Python, don't try to
> > build your own language on top of it.
> >
> > ChrisA
> >

Please be patient. A big problem with development can be
burnout. So I am trying to slow down things at the moment.
The ideas are easy to sketch, but implementation can take

weeks. Here is the idea again in a nutshell: use ast.parse()
and compile(). Or build directly an AST, not using the string
detour as in ast.parse(). How long will it take to have a

working solution? 11 years ago there was:

Pyrolog: Prolog written in Python using PyPy's RPython tool chain
https://www.reddit.com/r/prolog/comments/fbuz1/pyrolog_prolog_written_in_python_using_pypys/

RPython is a framework for implementing interpreters and virtual
machines for programming languages, especially dynamic languages.
https://rpython.readthedocs.io/en/latest/faq.html

Currently I am not planning to use RPython, want to to use
standard Python AST and compile(). Might have a look at
RPython or similar stuff later.

Mostowski Collapse schrieb am Sonntag, 19. September 2021 um 22:02:41 UTC+2:
> Also I nowhere wrote that I would use doubly-linked list or
> a set of objects. The trail is neither, its a single linked list. I
> also refer directly to objects, I do not need the trail to refer
>
> to objects. The Prolog trail is only a logbook. The Prolog trail
> has similarity to a database log:
>
> transaction journal, database log, binary log or audit **trail**
> https://en.wikipedia.org/wiki/Transaction_log
>
> Do you say Python should not be used to implement
> such things? In my opinion, Python has a high potential
> to implement Prolog, because it has also ast.parse()
>
> and compile(). But I do not yet have a showcase that uses
> these features of Python to compile Prolog. I dont work 24/7
> and I cannot clone myself. Currently the Prolog code is interpreted.
>
> I have a prototype where Prolog code is compiled into JavaScript,
> but I did not yet try this approach with Python. Here you see how
> JavaScript closures are generated, a first prototype:
>
> const alt4 = make_defined([new Clause(1, [0, 0], function(
> display, actual, cont) {return(new Compound(".", [new Compound(
> "==", [deref(actual.args[0]), "end_of_file"]), new Compound(
> ".", [new Compound("$CUT", [deref(display[0])]), cont
> ])]))}, 0, undefined), new Clause(1, [0, 0], function(
> display, actual, cont) {return(new Compound(".", [new Compound(
> "expand_include", [deref(actual.args[0]), deref(actual.args[1]
> ), display[0] = new Variable()]), new Compound(".",
> [new Compound("handle_term", [deref(display[0])]), new Compound(
> ".", ["fail", cont])])]))}, -1, undefined)]);
>
> add("next_term", 1, new Clause(2, [0], function(display, actual,
> cont) {return(new Compound(".", [new Compound("read_term",
> [deref(actual.args[0]), display[0] = new Variable(),
> new Compound(".", [new Compound("variable_names", [
> display[1] = new Variable()]), "[]"])]), new Compound(
> ".", [new Compound(alt4, [deref(display[0]), deref(
> display[1])]), cont])]))}, -1, undefined));
>
> https://github.com/jburse/dogelog-moon/issues/184
>
> Will do the same for Python in the next weeks. Then later this approach
> will be combined with a few planned optimizations. So far got a 25%
> speed increase for JavaScript with this new compilation scheme, but
>
> there is no official release out yet, that features this approach. And
> there should be much more in it, also for Python.
> Mostowski Collapse schrieb am Sonntag, 19. September 2021 um 21:46:20 UTC+2:
> > sympy also builds a language on top of Python.
> > pandas also builds a language on top of Python.
> >
> > Is there some pope that says this wouldn't be
> > allowed, I dont think so, otherwise sympy, pandas, etc..
> >
> > wouldn't exist. I dont understand your argument.
> >
> > Chris Angelico schrieb:
> > > On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janb...@fastmail.fm> wrote:
> > >>
> > >> I am refering to:
> > >>
> > >> Greg Ewing schrieb:
> > >> > where [w] is a weak reference object. Then you could periodically
> > >> > scan the trail looking for dead weakref objects and remove the
> > >> > corresponding [*] node from the list.
> > >> >
> > >> > You can also attach callbacks to weakref objects that are triggered
> > >> > when the referenced object dies. You might be able to make use of
> > >> > that to remove items from the trail instead of the periodic scanning.
> > >>
> > >> Question to Chris Angelico: If I stay with my
> > >> sweep_trail(), which is the periodically scanning,
> > >> I can use a single linked list.
> > >>
> > >> On the other hand if I would use the trigger
> > >> from Python, I possibly would need a double linked
> > >> list, to remove an element.
> > >>
> > >> Chris Angelico, is there a third option, that I have
> > >> overlooked? Single linked list uses less space
> > >> than double linked list, this why I go with scan.
> > >>
> > >
> > > I don't know. I don't understand your code well enough to offer advice
> > > like that, because *your code is too complicated* and not nearly clear
> > > enough.
> > >
> > > But however it is that you're doing things, the best way is almost
> > > always to directly refer to objects. Don't fiddle around with creating
> > > your own concept of a doubly-linked list and a set of objects; just
> > > refer directly to the objects. Let Python be Python, don't try to
> > > build your own language on top of it.
> > >
> > > ChrisA
> > >

> On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janburse@fastmail.fm> wrote:
>>
>> On the other hand if I would use the trigger
>> from Python, I possibly would need a double linked
>> list, to remove an element.

Here's another idea: Put weak references in the trail, but
don't bother with the scanning -- just skip over dead ones
during backtracking.

Seems to me you would be doing about the same amount of
work either way, just doing it at different times.

--
Greg

This strategy works if you use failure driven loops.
It doesn't work you program recursive loops that go
on forever. Like Erlang processes.

foo(X) :-
bar(X,Y), foo(Y).

Typically Y is a fresh variable. A good Prolog system
with good Garbage Collection can run such a process
for days and months.

If you don't clean up the trail, you exhaust the
memory after a few minutes or seconds.

Greg Ewing schrieb:
>> On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse
>> <janburse@fastmail.fm> wrote:
>>>
>>> On the other hand if I would use the trigger
>>> from Python, I possibly would need a double linked
>>> list, to remove an element.
>
> Here's another idea: Put weak references in the trail, but
> don't bother with the scanning -- just skip over dead ones
> during backtracking.
>
> Seems to me you would be doing about the same amount of
> work either way, just doing it at different times.
>

But I dont see any utility in investing too much time with
the Prolog garbage collection of Dogelog runtime. It is
only a small share of the execution time:

Mostowski Collapse schrieb am Freitag, 17. September 2021 um 10:58:57 UTC+2:
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> % Standard Python Version, Warm Run
> % ?- time(fibo(23,X)).
> % % Wall 3865 ms, gc 94 ms, 71991 lips
> % X = 46368.
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> % GraalVM Python Version, Warm Warm Run
> % ?- time(fibo(23,X)).
> % % Wall 695 ms, gc 14 ms, 400356 lips
> % X = 46368.
>
> The "gc" timing measures Prolog garbage
> collection. So you get the following percentage
> of time spent in Prolog garbage collection:
>
> Standard Python: 94 / 3865 = 2.4%
>
> GraalVM Python: 14 / 695 = 2.0%

If you spare these 2-3% it will not speed-up Dogelog runtime.
The Prolog garbage collection is there to allow Erlang
processes. And its also there to allow more Prolog search

without exhausting the memory. But it cost you only 2-3%
judging from the Fibonnacci Numbers example. Need to
check with other examples whether its higher.

But since the ratio between Garbage and non-Garbage is
usually high, and non-Garbage is easily identified, and
the Garbage is also easily removed, the time will

possibly not exceed much more than the same 2-3% for
other examples. So in conclusion I am least worried
about the Prolog garbage collection. You guys are only

worried because its something new. But its nothing that
does any harm and costs a lot, it only does good and
is very cheap in terms of extra runtime effort.

Mostowski Collapse schrieb am Montag, 20. September 2021 um 08:44:49 UTC+2:
> This strategy works if you use failure driven loops.
> It doesn't work you program recursive loops that go
> on forever. Like Erlang processes.
>
> foo(X) :-
> bar(X,Y), foo(Y).
>
> Typically Y is a fresh variable. A good Prolog system
> with good Garbage Collection can run such a process
> for days and months.
>
> If you don't clean up the trail, you exhaust the
> memory after a few minutes or seconds.
>
> Greg Ewing schrieb:
> >> On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse
> >> <janb...@fastmail.fm> wrote:
> >>>
> >>> On the other hand if I would use the trigger
> >>> from Python, I possibly would need a double linked
> >>> list, to remove an element.
> >
> > Here's another idea: Put weak references in the trail, but
> > don't bother with the scanning -- just skip over dead ones
> > during backtracking.
> >
> > Seems to me you would be doing about the same amount of
> > work either way, just doing it at different times.
> >

On 2021-09-20 04:33:39 +1000, Chris Angelico wrote:
> On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janburse@fastmail.fm> wrote:
> > Question to Chris Angelico: If I stay with my
> > sweep_trail(), which is the periodically scanning,
> > I can use a single linked list.
> >
> > On the other hand if I would use the trigger
> > from Python, I possibly would need a double linked
> > list, to remove an element.
> >
> > Chris Angelico, is there a third option, that I have
> > overlooked? Single linked list uses less space
> > than double linked list, this why I go with scan.
> >
>
> I don't know. I don't understand your code well enough to offer advice
> like that, because *your code is too complicated* and not nearly clear
> enough.
>
> But however it is that you're doing things, the best way is almost
> always to directly refer to objects. Don't fiddle around with creating
> your own concept of a doubly-linked list and a set of objects; just
> refer directly to the objects.

And almost certainly: Just use the builtin list type if you need a list.
Don't build one yourself.

> Let Python be Python, don't try to build your own language on top of
> it.

Well, he's writing a Prolog interpreter, so building his own language on
top of Python is sort of the point. I think a better way to put it is
"Don't try to write Python as if it was C". A C operation may be
compiled to a single machine instruction which is executed in a fraction
of a nanosecond. A Python instruction (in CPython) always includes at
least the interpreter overhead and often several method lookups and method
calls. You want to amortize that overhead over as much work as possible.

hp

--
_ | Peter J. Holzer | Story must make more sense than reality.
|_|_) | |
| | | hjp@hjp.at | -- Charles Stross, "Creative writing
__/ | http://www.hjp.at/ | challenge!"

I read the following, and you should also know:

> Python's [] is implemented as an array, not a linked list.
> Although resizing is O(n), appending to it is amortized O(1),
> because resizes happen very rarely.
https://stackoverflow.com/a/5932364/502187

The list type doesn't have an O(1) operation to remove
an element during sweep. The list type, not like its name
would suggest, in Python is an array.

These arrays are not so expensive when you append()
an element. Because they are allocated with some excess
capacity. And they grow exponentially.

So amortisized you can append() a lot of elements to
a Python list, which is an array. But you cannot poke so
cheaply holes into it. So if you have this scenario:

Before:
- [ A1, .., An , B, C1, .., Cm ]

After:
- [ A1, .., An , C1, .., Cm ]

You have to copy C1,..,Cm one position down. On the other
hand, when scanning the single list, removing the
element is just pointer swizzling.

The code is here, the positive if-then-else branch keeps
the element, the negative if-then-else branch drops the
element. Thats quite standard algorithm for linked lists:

/* pointer swizzling */
while temp is not None:
term = temp
temp = term.tail
if (term.flags & MASK_VAR_MARK) != 0:
term.flags &= ~MASK_VAR_MARK
if back is not None:
back.tail = term
else:
trail = term
back = term
else:
term.instantiated = NotImplemented
term.tail = None
count -= 1

https://github.com/jburse/dogelog-moon/blob/main/devel/runtimepy/drawer/machine.py#L163

There is nothing wrong with implementing a single list
in Python. Only you never saw that one maybe. If you would
indeed use Python lists which are arrays, you would

maybe get a much slower sweep_trail() and this would
be seen. But currently its not seen. It happens that 1000000
of elements are sweeped, if you would do this with copy

inside a Python list which are arrays, it would get much
more expensive, and the extremly cheap Prolog garbage
collection, as it stands now, wouldn't be that cheap anymore.

You can try yourself. My sweep_trail() needs frequent resize,
which would be O(n) each, so that sweep_trail becomes O(n^2).
Which the current implementation its only O(n).

Peter J. Holzer schrieb am Montag, 20. September 2021 um 13:49:49 UTC+2:
> On 2021-09-20 04:33:39 +1000, Chris Angelico wrote:
> > On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janb...@fastmail.fm> wrote:
> > > Question to Chris Angelico: If I stay with my
> > > sweep_trail(), which is the periodically scanning,
> > > I can use a single linked list.
> > >
> > > On the other hand if I would use the trigger
> > > from Python, I possibly would need a double linked
> > > list, to remove an element.
> > >
> > > Chris Angelico, is there a third option, that I have
> > > overlooked? Single linked list uses less space
> > > than double linked list, this why I go with scan.
> > >
> >
> > I don't know. I don't understand your code well enough to offer advice
> > like that, because *your code is too complicated* and not nearly clear
> > enough.
> >
> > But however it is that you're doing things, the best way is almost
> > always to directly refer to objects. Don't fiddle around with creating
> > your own concept of a doubly-linked list and a set of objects; just
> > refer directly to the objects.
> And almost certainly: Just use the builtin list type if you need a list.
> Don't build one yourself.
> > Let Python be Python, don't try to build your own language on top of
> > it.
> Well, he's writing a Prolog interpreter, so building his own language on
> top of Python is sort of the point. I think a better way to put it is
> "Don't try to write Python as if it was C". A C operation may be
> compiled to a single machine instruction which is executed in a fraction
> of a nanosecond. A Python instruction (in CPython) always includes at
> least the interpreter overhead and often several method lookups and method
> calls. You want to amortize that overhead over as much work as possible.
>
> hp
>
> --
> _ | Peter J. Holzer | Story must make more sense than reality.
> |_|_) | |
> | | | h...@hjp.at | -- Charles Stross, "Creative writing
> __/ | http://www.hjp.at/ | challenge!"

What would be maybe possible, is to
scan the trail from the other side, and
use a first pass to determine the new

size, and use a second pass to fill a new
array with the remaining elments. This would
be two times O(n), so it would be linear

and not quadratic O(n^2) as when you scan
from the top and poke holes. But then something
else doesn't work so easily. Namely:

def adjust_mark(temp):
while temp is not None:
if (temp.flags & MASK_VAR_MARK) != 0:
return temp
else:
temp = temp.tail
return temp

https://github.com/jburse/dogelog-moon/blob/main/devel/runtimepy/drawer/machine.py#L151

This is needed to adjust the choice points.
If you have an array instead of a linked
listed as I have now, you would need

to adjust array indexes instead pointers
into linked list elements. I havent come
up with an array solution yet for the trail,

since I dont see any utility in investing too
much time with the Prolog garbage collection of
Dogelog runtime. It is only a small share

of the execution time:

Mostowski Collapse schrieb am Freitag, 17. September 2021 um 10:58:57 UTC+2:
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> % Standard Python Version, Warm Run
> % ?- time(fibo(23,X)).
> % % Wall 3865 ms, gc 94 ms, 71991 lips
> % X = 46368.
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> % GraalVM Python Version, Warm Warm Run
> % ?- time(fibo(23,X)).
> % % Wall 695 ms, gc 14 ms, 400356 lips
> % X = 46368.

Mostowski Collapse wrote:
> I read the following, and you should also know:
>
>> Python's [] is implemented as an array, not a linked list.
>> Although resizing is O(n), appending to it is amortized O(1),
>> because resizes happen very rarely.
> https://stackoverflow.com/a/5932364/502187
>
> The list type doesn't have an O(1) operation to remove
> an element during sweep. The list type, not like its name
> would suggest, in Python is an array.
>
> These arrays are not so expensive when you append()
> an element. Because they are allocated with some excess
> capacity. And they grow exponentially.
>
> So amortisized you can append() a lot of elements to
> a Python list, which is an array. But you cannot poke so
> cheaply holes into it. So if you have this scenario:
>
> Before:
> - [ A1, .., An , B, C1, .., Cm ]
>
> After:
> - [ A1, .., An , C1, .., Cm ]
>
> You have to copy C1,..,Cm one position down. On the other
> hand, when scanning the single list, removing the
> element is just pointer swizzling.
>
> The code is here, the positive if-then-else branch keeps
> the element, the negative if-then-else branch drops the
> element. Thats quite standard algorithm for linked lists:
>
> /* pointer swizzling */
> while temp is not None:
> term = temp
> temp = term.tail
> if (term.flags & MASK_VAR_MARK) != 0:
> term.flags &= ~MASK_VAR_MARK
> if back is not None:
> back.tail = term
> else:
> trail = term
> back = term
> else:
> term.instantiated = NotImplemented
> term.tail = None
> count -= 1
>
> https://github.com/jburse/dogelog-moon/blob/main/devel/runtimepy/drawer/machine.py#L163
>
> There is nothing wrong with implementing a single list
> in Python. Only you never saw that one maybe. If you would
> indeed use Python lists which are arrays, you would
>
> maybe get a much slower sweep_trail() and this would
> be seen. But currently its not seen. It happens that 1000000
> of elements are sweeped, if you would do this with copy
>
> inside a Python list which are arrays, it would get much
> more expensive, and the extremly cheap Prolog garbage
> collection, as it stands now, wouldn't be that cheap anymore.
>
> You can try yourself. My sweep_trail() needs frequent resize,
> which would be O(n) each, so that sweep_trail becomes O(n^2).
> Which the current implementation its only O(n).
>
> Peter J. Holzer schrieb am Montag, 20. September 2021 um 13:49:49 UTC+2:
>> On 2021-09-20 04:33:39 +1000, Chris Angelico wrote:
>>> On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janb...@fastmail.fm> wrote:
>>>> Question to Chris Angelico: If I stay with my
>>>> sweep_trail(), which is the periodically scanning,
>>>> I can use a single linked list.
>>>>
>>>> On the other hand if I would use the trigger
>>>> from Python, I possibly would need a double linked
>>>> list, to remove an element.
>>>>
>>>> Chris Angelico, is there a third option, that I have
>>>> overlooked? Single linked list uses less space
>>>> than double linked list, this why I go with scan.
>>>>
>>>
>>> I don't know. I don't understand your code well enough to offer advice
>>> like that, because *your code is too complicated* and not nearly clear
>>> enough.
>>>
>>> But however it is that you're doing things, the best way is almost
>>> always to directly refer to objects. Don't fiddle around with creating
>>> your own concept of a doubly-linked list and a set of objects; just
>>> refer directly to the objects.
>> And almost certainly: Just use the builtin list type if you need a list.
>> Don't build one yourself.
>>> Let Python be Python, don't try to build your own language on top of
>>> it.
>> Well, he's writing a Prolog interpreter, so building his own language on
>> top of Python is sort of the point. I think a better way to put it is
>> "Don't try to write Python as if it was C". A C operation may be
>> compiled to a single machine instruction which is executed in a fraction
>> of a nanosecond. A Python instruction (in CPython) always includes at
>> least the interpreter overhead and often several method lookups and method
>> calls. You want to amortize that overhead over as much work as possible.
>>
>> hp
>>
>> --
>> _ | Peter J. Holzer | Story must make more sense than reality.
>> |_|_) | |
>> | | | h...@hjp.at | -- Charles Stross, "Creative writing
>> __/ | http://www.hjp.at/ | challenge!"

In general the algorithm I am using is from
a paper by Matts Carlson from SICStus Prolog.
Its this paper here:

Garbage Collection for Prolog Based on WAM
January 1986
Karen Appleby, Mats Carlsson, Seif Haridi, Dan Sahlin
https://www.researchgate.net/publication/279463524

But since you guys are so facinated with
the Prolog garbage collection aspect, which
is not the locus where you can do a lot

of optimizations, feel free to investigate
and come up with a solution. It will not
change the performance of Dogelog runtime,

but it could be an academic experiment
neverthless. There is nothing wrong with the
simgle linked list as it stands, since

it has O(n) sweep_trail(). It uses a litte
more storage than an array would do.

Mostowski Collapse wrote:
> What would be maybe possible, is to
> scan the trail from the other side, and
> use a first pass to determine the new
>
> size, and use a second pass to fill a new
> array with the remaining elments. This would
> be two times O(n), so it would be linear
>
> and not quadratic O(n^2) as when you scan
> from the top and poke holes. But then something
> else doesn't work so easily. Namely:
>
>    def adjust_mark(temp):
>        while temp is not None:
>         if (temp.flags & MASK_VAR_MARK) != 0:
>             return temp
>         else:
>             temp = temp.tail
>     return temp
>
> https://github.com/jburse/dogelog-moon/blob/main/devel/runtimepy/drawer/machine.py#L151
>
>
> This is needed to adjust the choice points.
> If you have an array instead of a linked
> listed as I have now, you would need
>
> to adjust array indexes instead pointers
> into linked list elements. I havent come
> up with an array solution yet for the trail,
>
> since I dont see any utility in investing too
> much time with the Prolog garbage collection of
> Dogelog runtime. It is only a small share
>
> of the execution time:
>
> Mostowski Collapse schrieb am Freitag, 17. September 2021 um 10:58:57
> UTC+2:
> > %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> > % Standard Python Version, Warm Run
> > % ?- time(fibo(23,X)).
> > % % Wall 3865 ms, gc 94 ms, 71991 lips
> > % X = 46368.
> >
> > %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> > % GraalVM Python Version, Warm Warm Run
> > % ?- time(fibo(23,X)).
> > % % Wall 695 ms, gc 14 ms, 400356 lips
> > % X = 46368.
>
> Mostowski Collapse wrote:
>> I read the following, and you should also know:
>>
>>> Python's [] is implemented as an array, not a linked list.
>>> Although resizing is O(n), appending to it is amortized O(1),
>>> because resizes happen very rarely.
>> https://stackoverflow.com/a/5932364/502187
>>
>> The list type doesn't have an O(1) operation to remove
>> an element during sweep. The list type, not like its name
>> would suggest, in Python is an array.
>>
>> These arrays are not so expensive when you append()
>> an element. Because they are allocated with some excess
>> capacity. And they grow exponentially.
>>
>> So amortisized you can append() a lot of elements to
>> a Python list, which is an array. But you cannot poke so
>> cheaply holes into it. So if you have this scenario:
>>
>> Before:
>>       - [ A1, .., An , B, C1, .., Cm ]
>>
>> After:
>>       - [ A1, .., An , C1, .., Cm ]
>> You have to copy C1,..,Cm one position down. On the other
>> hand, when scanning the single list, removing the
>> element is just pointer swizzling.
>>
>> The code is here, the positive if-then-else branch keeps
>> the element, the negative if-then-else branch drops the
>> element. Thats quite standard algorithm for linked lists:
>>
>>       /* pointer swizzling */
>>      while temp is not None:
>>          term = temp
>>          temp = term.tail
>>          if (term.flags & MASK_VAR_MARK) != 0:
>>              term.flags &= ~MASK_VAR_MARK
>>              if back is not None:
>>                  back.tail = term
>>              else:
>>                  trail = term
>>              back = term
>>          else:
>>              term.instantiated = NotImplemented
>>              term.tail = None
>>              count -= 1
>>
>> https://github.com/jburse/dogelog-moon/blob/main/devel/runtimepy/drawer/machine.py#L163
>>
>>
>> There is nothing wrong with implementing a single list
>> in Python. Only you never saw that one maybe. If you would
>> indeed use Python lists which are arrays, you would
>>
>> maybe get a much slower sweep_trail() and this would
>> be seen. But currently its not seen. It happens that 1000000
>> of elements are sweeped, if you would do this with copy
>>
>> inside a Python list which are arrays, it would get much
>> more expensive, and the extremly cheap Prolog garbage
>> collection, as it stands now, wouldn't be that cheap anymore.
>>
>> You can try yourself. My sweep_trail() needs frequent resize,
>> which would be O(n) each, so that sweep_trail becomes O(n^2).
>> Which the current implementation its only O(n).
>>
>> Peter J. Holzer schrieb am Montag, 20. September 2021 um 13:49:49 UTC+2:
>>> On 2021-09-20 04:33:39 +1000, Chris Angelico wrote:
>>>> On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse
>>>> <janb...@fastmail.fm> wrote:
>>>>> Question to Chris Angelico: If I stay with my
>>>>> sweep_trail(), which is the periodically scanning,
>>>>> I can use a single linked list.
>>>>>
>>>>> On the other hand if I would use the trigger
>>>>> from Python, I possibly would need a double linked
>>>>> list, to remove an element.
>>>>>
>>>>> Chris Angelico, is there a third option, that I have
>>>>> overlooked? Single linked list uses less space
>>>>> than double linked list, this why I go with scan.
>>>>>
>>>>
>>>> I don't know. I don't understand your code well enough to offer advice
>>>> like that, because *your code is too complicated* and not nearly clear
>>>> enough.
>>>>
>>>> But however it is that you're doing things, the best way is almost
>>>> always to directly refer to objects. Don't fiddle around with creating
>>>> your own concept of a doubly-linked list and a set of objects; just
>>>> refer directly to the objects.
>>> And almost certainly: Just use the builtin list type if you need a list.
>>> Don't build one yourself.
>>>> Let Python be Python, don't try to build your own language on top of
>>>> it.
>>> Well, he's writing a Prolog interpreter, so building his own language on
>>> top of Python is sort of the point. I think a better way to put it is
>>> "Don't try to write Python as if it was C". A C operation may be
>>> compiled to a single machine instruction which is executed in a fraction
>>> of a nanosecond. A Python instruction (in CPython) always includes at
>>> least the interpreter overhead and often several method lookups and
>>> method
>>> calls. You want to amortize that overhead over as much work as possible.
>>>
>>> hp
>>>
>>> --
>>> _ | Peter J. Holzer | Story must make more sense than reality.
>>> |_|_) | |
>>> | | | h...@hjp.at | -- Charles Stross, "Creative writing
>>> __/ | http://www.hjp.at/ | challenge!"
>