On 2021-09-20 05:08:55 -0700, Mostowski Collapse wrote:
> 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.
That's the problem. You think that pointer swizzling is fast because you
are used to languages where this is compiled into a few machine
instructions. (Even there it depends a lot on locality: A random memory
access can take hundreds of clock cycles.)
In Python something like ?a.next = b.next? normally does a dict lookup
on both objects, plus it also has to check for the existence of special
methods on both objects. You can probably copy quite a few contiguous
bytes while this is happening.
Here is a simple demo:
------------------------------------------------------------------------
#!/usr/bin/python3
import time
n = 10000
def build_linked_list(n):
head = [None, None]
tail = head
for i in range(n):
tail[1] = [i, None]
tail = tail[1]
return head
def empty_list(ls):
while ls[1]:
ls[1] = ls[1][1]
t0 = time.monotonic()
ll = build_linked_list(n)
t1 = time.monotonic()
empty_list(ll)
t2 = time.monotonic()
print(n, t1 - t0, t2 - t1)
------------------------------------------------------------------------
#!/usr/bin/python3
import time
n = 10000
def build_list(n):
return list(range(n))
def empty_list(ls):
while ls:
ls.pop(0)
t0 = time.monotonic()
ll = build_list(n)
t1 = time.monotonic()
empty_list(ll)
t2 = time.monotonic()
print(n, t1 - t0, t2 - t1)
------------------------------------------------------------------------
Both scripts create a list of n integers, then repeatedly pop off the
first element until the list is empty. The first uses a linked list
(where each element is a Python list - I guess this is faster than an
object although I haven't timed it) the second a python list. Popping
off the first element is the worst case for a python list since it is
implemented as an array of pointers and n-1 pointers have to be copied
for each operation and the best case for a linked list.
Still, on my laptop with CPython 3.8, the builtin list is faster for
lists of less than 100 elements, they are about on par between 100 and
1000 elements and only for longer lists does the linked list become
faster.
With Pypy 6.0 (yes, I know it's old), the linked list seems to be always
a bit faster although the difference is very small for lists shorter
than 100 elements - GraalVM is probably closer to PyPy than to CPython
in its performance characteristics, but the point is that the dynamic
nature of Python makes some seemingly cheap operations much more costly
than one would expect - a good optimizing compiler may be able to detect
that all that is not needed in a specific case and produce
straightforward code. But unlike for JavaScript (which has a very
similar problem) no company has spent millions of dollars on an
optimizing JIT compiler for Python yet.
hp
--
_ | Peter J. Holzer | Story must make more sense than reality.
|_|_) | |
| | | hjp@hjp.at | -- Charles Stross, "Creative writing
__/ |
http://www.hjp.at/ | challenge!"
