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!"
--
https://mail.python.org/mailman/listinfo/python-list
