On Sat, Oct 2, 2021 at 7:42 AM Steven D'Aprano <steve@pearwood.info> wrote:

This half-baked idea is inspired by this thread here:

https://mail.python.org/archives/list/python-ideas@python.org/message/5LGWV3...

which in turn was inspired by this Stackoverflow post:

https://stackoverflow.com/questions/56966429/getting-pairs-of-one-item-and-t...

Problem: today, more and more people are using Python to work with Big Data, or at least Biggish Data. For some folks, it is not unusual to have lists with a gigabyte or more or data. So imagine you have a list with a hundred million items, and you need a copy of the entire list. Easy:

alist = [...] # 100 million items blist = alist[:]

And that ought to be pretty efficient too, making the slice is basically just a copy of a bunch of pointers, plus a bit of overhead. A good implementation should have lightning fast list slicing, close to the speed of memcopy in C. Give or take.

No, it would also have to increment the reference count of each item (since blist owns a reference to each). That's what makes this slow.

But now suppose you want a copy of all the items except the item in position (let's say) 1000. Here's a bad way:

blist = alist[:] del blist[1000]

That's inefficient because the list has to shift almost a hundred million items over, and I think they have to be moved one at a time. Which is slowish, even in C.

But this doesn't need to update reference counts (except of the one deleted item) and the move is done using C memmove(), which perhaps isn't as fast as memcpy() but still unbeatably fast.

Here's another way:

blist = alist[:1000] + alist[1001:]

That has to make a slice (copy 1000 items), a second slice (copy another many million items), then make a third copy to concatenate them, then garbage collect the two temporary slices.

Yeah, probably the worst way. And while you might have enough memory for double the original list

(alist and blist) you might not have enough for triple (alist, the two slices, blist).

There are lots of other variants we could come up with, but ultimately we're doing lots of extra work that has to be thrown away, and that costs time or memory or both.

That's always the case when you use Python though. You use it because it's convenient, not because it's particularly efficient.

How about if lists had an in-place method for doing a fast copy of pointers from one list to another? We could do this:

blist = [None]*(len(alist)-1) # Preallocate. blist.copyfrom(alist, index=0, start=0, end=1000) blist.copyfrom(alist, index=1000, start=1001)

No temporary slices are needed.

Here's a pure-Python (and therefore slow) implementation:

def copyfrom(dest, source, index=0, start=0, end=None): if end is None: end = len(source) if len(dest) - index < end - start: raise ValueError('destination too small') for i in range(start, end): dest[index+i-start] = source[i]

In pure Python, copying each item over one by one will save memory but cost a lot of time. Doing it as a method in C should save both memory and time. The implementation could optimize the cases where the source is a list, and fall back on iteration for other sequence types.

Now *personally* I don't work with a lot of Big Data, so this doesn't really scratch any of my personal itches, but I thought I'd throw it out there for others to tell me why it's a dumb idea :-)

At the very least it might lead to a recommendation based on which operation is implemented most efficiently. Though you should just measure it for various N. Are you actually observing that people are doing this with regular lists? Don't people working with Big Data usually use Pandas, which is built on NumPy arrays and custom data structures? -- --Guido van Rossum (python.org/~guido) *Pronouns: he/him **(why is my pronoun here?)* <http://feministing.com/2015/02/03/how-using-they-as-a-singular-pronoun-can-change-the-world/>