list.pop(0) vs. collections.dequeue
in [Python]
|
From: Steve Howell on 22 Jan 2010 17:38 On Jan 22, 1:29 pm, Christian Heimes <li...(a)cheimes.de> wrote: > Steve Howell wrote: > > I disagree that Python code rarely pops elements off the top of a > > list. There are perfectly valid use cases for wanting a list over a > > dequeue without having to pay O(N) for pop(0). Maybe we are just > > quibbling over the meaning of "rarely." > > I was speaking from my own point of view. I've written several tenths of > thousands of lines of Python code in the last seven years, mostly > related to data manipulation, web applications and operating system > interaction but also GUI stuff and scientific code. I can't recall any > performance critical or prominent code that modifies the head of a list > a lot. > That maybe would be an argument for just striking the paragraph from the tutorial. If it's rare that people pop the head off the list in code that is performance critical or prominent, why bother to even mention it in the tutorial? > Of course there a use cases where you may want to use list.pop(). Unless > you need a FILO structure you can always replace a LILO with a FIFO -- > instead of list.insert(0, value) and list.pop(0) use list.append(value) > and list.pop(). It's not possible to optimize a data structure for all > use cases. > > > I am not proposing a linked list of pointers. I am wondering about > > something like this: > > > p = &p[1]; > > (and then reclaim p[0] as free memory, I already said I understood > > that was the tricky bit) > > > The pointer arithmetic for accessing each element would still work in O > > (1), right? > > You mean it's an impossible trick unless you come up with your own > memory management system. Realloc(), the standard function to change the > size of chunk of allocated memory in C, doesn't support your desired > operation. > Impossible is a strong word. You could be lazy about giving the memory back, and just wait till the whole list is garbage collected. I don't think there's anything in Python's contract that says memory has to be freed the exact moment you stop using it, especially since we're talking about doing an O(N) memmove just to free up one pointer's worth of memory. I know the Python programmer could simply iterate through the list rather than popping off unused elements, but that just means that you not only tie up the memory for the pointers just as long, but you also prevent the objects themselves from being garbage collected. In my case I'm not really concerned about giving the memory back right away, it's more about keeping my code simple. Once I'm done with an element, I do just want to pop it off and keep all the simplicity of the lists, but I am just concerned enough speed that for a 1000 element list, I don't want to be doing 1000 memmoves for an average of 500 pointers, which effectively moves about a million bytes around for no reason. I suppose the solution is to either give up the sugar of lists, or try to wrap something like deque or list-with-offset into a sequence.
From: Steve Howell on 22 Jan 2010 17:52 On Jan 22, 1:32 pm, Terry Reedy <tjre...(a)udel.edu> wrote: > On 1/22/2010 2:14 PM, Steve Howell wrote: > > > The v2.6.4 version of the tutorial says this: > > Is that really true in CPython? It seems like you could advance the > > pointer instead of shifting all the elements. It would create some > > nuances with respect to reclaiming the memory, but it seems like an > > easy way to make lists perform better under a pretty reasonable use > > case. > > Something like this was one proposed (ie, leave space at both ends of a > list) but was rejected as over-complicating the list implementation for > *relatively* rare use cases. I believe deque was written subsequently to > address such other use cases. Bummer. I guess I get to do my own over-complicating of code, being in that unfortunate minority.
From: Dave Angel on 22 Jan 2010 17:54 Steve Howell wrote: > On Jan 22, 12:40 pm, Christian Heimes <li...(a)cheimes.de> wrote: > >> Steve Howell wrote: >> >>> Is that really true in CPython? It seems like you could advance the >>> pointer instead of shifting all the elements. It would create some >>> nuances with respect to reclaiming the memory, but it seems like an >>> easy way to make lists perform better under a pretty reasonable use >>> case. >>> >>> Does anybody know off the top of their head if the "have-to-be-shifted- >>> by-one" warning is actually valid? >>> >> Why do you think the documentation has such obvious errors? >> > > I wasn't making any assumptions, hence the question mark. The Python > docs are very good, but even the best of projects make advances that > aren't reflected in the docs. > > >> CPython's list type uses an array of pointers to store its members. The >> type is optimized for the most common list operations in Python: >> iteration and appending. Python code rarely changes the head or middle >> of a list. The dequeue type is an optimized data structure for popping >> and inserting data at both ends. >> >> > > I disagree that Python code rarely pops elements off the top of a > list. There are perfectly valid use cases for wanting a list over a > dequeue without having to pay O(N) for pop(0). Maybe we are just > quibbling over the meaning of "rarely." > > >> When you list.pop() or list.insert() the pointers in the internal array >> must be shifted. appending is much faster because the internal array is >> overallocated meaning it contains free slots at the tail of the data >> structure. A linked list of pointers requires more memory and iteration >> is slower since since it can't utilize the CPU's cache as good as an array. >> >> > > I am not proposing a linked list of pointers. I am wondering about > something like this: > > p =p[1]; > (and then reclaim p[0] as free memory, I already said I understood > that was the tricky bit) > > The pointer arithmetic for accessing each element would still work in O > (1), right? > > I think it was Dijkstr (sp?) who said you can accomplish anything with just one more level of indirection. Clearly each attribute (variable) that has a binding to a given list must point to a fixed piece of memory, that cannot safely be moved, because there's no efficient way to find all the attributes. That fixed piece is the list object, and I expect it's 16 or 20 bytes, on a 32bit implementation. It must in turn point to the actual malloc'ed block that contains pointers to all the elements of the list. So that block will be 4*n where n is the number of reserved cells, at least as large as len(). This is the block where copying takes place when you insert or delete from the beginning. The list object must contain a pointer to the beginning of this block, or it wouldn't be able to free() it later. So you'd be suggesting a second pointer that actually points to the current 0th pointer. And a pop would simply increment this second pointer. Such an approach might be worthwhile if you expect lots of pops and pushes, with a minimal net change. But of course each time you did a pop, you'd have to decide whether it was time to normalize/compact the block. As you say, reclaiming the 0th element of this block to the memory pool would be tricky. Doubly so, because 1) the C memory allocator has no such notion as resizing the beginning of a block. and 2) it would have nothing useful to do with the 4 bytes freed. The minimum allocated block in Python is probably 16 bytes of actual address space. I'd guess that's 4 bytes for malloc's overhead, and 8 bytes for the minimum object header, and 4 bytes for data. To check me, try: >>> a = 5.3 >>> b = 49.6 >>> id(a), id(b) (11074136, 11074152) Anyway, this could be done, where once the two pointers get some distance apart, you do a realloc, and copy everything. But of course you'd want to build some hysteresis into it, to avoid thrashing. There wouldn't be much of a performance hit, but it would increase every list size by 4 bytes minimum. So I doubt it would be a list replacement. This'd be an interesting project.to do as an addon module. DaveA
From: Dave Angel on 22 Jan 2010 17:57 Arnaud Delobelle wrote: > Steve Howell <showell30(a)yahoo.com> writes: > > >> On Jan 22, 12:14 pm, Chris Rebert <c...(a)rebertia.com> wrote: >> >> <snip> > I made the comment you quoted. In CPython, it is O(n) to delete/insert > an element at the start of the list - I know it because I looked at the > implementation a while ago. This is why collections.deque exists I > guess. I don't know how they are implemented but insertion/deletion at > either end are O(1) and so is random access. So they are the data > structure that you want. > > Not according to the 2.6 docs. Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead. That sounds to me like a doubly-linked list implementation. <snip>
From: Christian Heimes on 22 Jan 2010 18:17
Steve Howell wrote: > That maybe would be an argument for just striking the paragraph from > the tutorial. If it's rare that people pop the head off the list in > code that is performance critical or prominent, why bother to even > mention it in the tutorial? How else are you going to teach new Python developers that they should favor append() and pop() in place of insert() and pop(0)? :) > Impossible is a strong word. You could be lazy about giving the > memory back, and just wait till the whole list is garbage collected. > I don't think there's anything in Python's contract that says memory > has to be freed the exact moment you stop using it, especially since > we're talking about doing an O(N) memmove just to free up one > pointer's worth of memory. Your proposal would increase the size of every list object of sizeof(ptr) or ssize_t (32 or 64bits) in order to store the information where the first element is. It would also unnecessarily complicate the code and possible slow down a lot of list operations. > I know the Python programmer could simply iterate through the list > rather than popping off unused elements, but that just means that you > not only tie up the memory for the pointers just as long, but you also > prevent the objects themselves from being garbage collected. > > In my case I'm not really concerned about giving the memory back right > away, it's more about keeping my code simple. Once I'm done with an > element, I do just want to pop it off and keep all the simplicity of > the lists, but I am just concerned enough speed that for a 1000 > element list, I don't want to be doing 1000 memmoves for an average of > 500 pointers, which effectively moves about a million bytes around for > no reason. The simplicity of Python is gained with some performance drawbacks. You have to learn to use Python algorithms. You can't simply re implement a fast C algorithm and expect it to be fast in Python, too. Christian |