[Raymond]

...

...

None of those can compete with my proposed C implementation which pre-allocates around 50 cells at a time and does it's read/writes through array lookups. It avoids all the expensive resizing of list and uses C ints instead of PyInts.

Josiah Carlson <jcarlson@uci.edu> writes:

...

That's pretty crazy. If I had a say, I'd be +1 just because I've seen so many people using their own {append, pop(0)} queues before.

[Zack]

As a user of Python, I am +1 on making there be a *really really fast* queue data structure somewhere, but -0 on its being something other than the existing Queue class. Can't we just optimize the one we've got? Ideally without losing the thread safety guarantees (but making it usable in an unthreaded program would be nice)?

You miss one thing -- the Queue class exists *specifically* for thread communication. It has very different semantics than I'd want for a generic queue. E.g. with Queue, if you try to get something out of an empty queue, your thread *blocks*. That's only appropriate for applications that expect this. (Imagine the newbie questions to c.l.py. :-) My own ideal solution would be a subtle hack to the list implementation to make pop(0) and insert(0, x) go a lot faster -- this can be done by adding one or two extra fields to the list head and allowing empty space at the front of the list as well as at the end. --Guido van Rossum (home page: http://www.python.org/~guido/)

[Guido]

...

My own ideal solution would be a subtle hack to the list implementation to make pop(0) and insert(0, x) go a lot faster -- this can be done by adding one or two extra fields to the list head and allowing empty space at the front of the list as well as at the end.

[Josiah Carlson]

I'm sure you know this, but just for sake of argument, how many extra fields? A couple? A few? 20? 30?

As Guido said, "one or two" would be enough. I think you're talking about different things, though: Guido is talking about the number of new named struct members that would have to be added to Python's list object header. I think you're talking about how many array slots to leave unused on both ends. Just as now, on a reallocation the number of free slots asked for has to be proportional to the total number of slots, so that growth via a huge number of one-at-a-time appends takes (amortized) constant-time per append. Picking any fixed number of free slots leads to overall quadratic-time (in the number of appends) behavior.

[Guido]

You misunderstood -- the *fields* I was talking about are counters or pointers that keep track of the overallocation, and 1 or at most 2 is enough.

One would be enough. To avoid breaking huge mounds of code all over the place, I think the existing ob_item should "float", to point always to the current element "at index 0". So ob_item would change when inserting or deleting "at the left end". The only new thing you need then is a field recording the number of unused slots "left-side" slots, between the start of the memory actually allocated and the slot ob_item points at; that field would have to be added or subtracted to/from ob_item in the obvious ways when allocating or deallocating the raw memory, but *most* of listobject.c could ignore it, and none of the PyList macros would need to change (in particular, the speed of indexed access wouldn't change). The overallocation strategy gets more complicated, though, and less effective for prepending. If you run out of room when prepending, it's not enough just to ask realloc() for more memory, you also have to memmove() the entire vector, to "make room at the left end". In previous lives I've found that "appending at the right" is as efficient as it is in practice largely because most non-trivial C realloc() calls end up extending the vector in-place, not needing to copy anything. The O() behavior is the same if each boost in size has to move everything that already existed, but the constant factor goes up more than just measurably <wink>.

[Kurt B. Kaiser]

Aren't array-based implementations of queue usually based on circular buffers?

Yes, but those are generally bounded queues.

Head and tail pointers plus a count are sufficient. Then a push is: check count (resize if necessary), write, adjust head pointer, adjust count.

By analogy to a real-life queue (of, say, people), pushing is usually viewed as adding to the tail (when you get in line for movie tickets, you're likely to get punched if you add yourself to the head of the queue). I have to insist on using that terminology, just because it ties my head in knots to swap the usual meanings.

A pull is similar, using the tail pointer. Constant time.

So is the speculative Python list gimmick we're talking about, until it runs out of room. We use mildly exponential overallocation when growing a list to ensure amortized O(1) behavior regardless.

The resize is a little tricky because the gap between the tail and head pointers is what needs to grow.

Resizing is easier with the speculative Python list gimmick, and 0-based indexing (where list[0] is the current head) is identical to the list-indexing implementation Python already has. The latter is important because it's fast. Needing to "wrap around" an index to account for circularity would introduce new test+branch expense into indexing.

The current implementation of Queue (with what appears to me to be a listpop(v, 0) for get() ) involves an internal shift of the whole pointer vector, O(n), for every read of the queue. The Cookbook examples mentioned alleviate this but still with excess copying or unbounded memory usage. IMHO it's better done in listobject.

Queue.py and the speculative Python list gimmick are different issues. The overhead of mucking with locks, and Python-level method calls, in Queue.py surely overwhelms whatever savings you could get over the two-list queue implementation Josiah put in his Cookbook comment. The only "extra" expense there over a straight push-and-pop-both-at-the-right-end Python list is that each element added to the queue is involved in (no more than) one C-level pointer swap (due to the reverse() call, when the input list is turned into the output list). If the speculative Python list gimmick were implemented, Queue.py could, of course, change to use it.

I'm not up to speed on the reasons why ob_item needs to float

So that indexing a Python list is as fast as it is today, and so that a mountain of C code continues to work (all C code mucking with Python lists now believes that a list contains ob_size elements, starting at ob_items and ending at ob_items+ob_size-1).

but perhaps there is a straightforward indirect relationship to the head pointer.

ob_item would *be* the head pointer (for my meaning for "head"), whenever the list is non-empty.

Why not have listobject grow deque functionality using circular buffer techniques?

As above, I don't see much to recommend that over the speculative Python list gimmick: indexing is slower and more complicated, resizing is more complicated, and all the listobject.c internals would get more complicated by needing to deal with that the list contents are no longer necessarily in a contiguous slice of a C vector (from the C POV, the list contents could be in two disjoint contiguous slices). It would have the advantage that resizing is never needed until you're wholly out of room, but that seems minor compared to the drawbacks.

Kurt B. Kaiser wrote:

With a circular buffer approach, the headpointer and tailpointer will walk down the block and when the end is reached the tailpointer will wrap around and "appended" items will be stored at the low end of the block. The process continues without any copying.

I think you two are talking about completely different things. Tim is talking about a modification to the builtin list type. You are talking about a new data type for queues. You are both right: Changing the list type to leave space in the front would make it more efficient for implementing queues than the current list type, especially if people use the standard idiom. Using a new type would be even more efficient if the queue is bounded. I'm still opposed to adding a new queue type, because it complicates the library, and it does not give any benefit to existing code - one actually has to change the existing implementations of queues. People don't want to change their code, especially if they need to support old Python versions. So changing the list type looks more promising to me. Not taking any action might be acceptable as well. Regards, Martin

Kurt B. Kaiser wrote:

I am talking about a modification to listobject.c, also.

So you suggest that the list type become circular??? That will cause a major ABI incompatibility, as all modules that use PyList_GET_SIZE need to be recompiled. In addition, it causes a slow-down for the standard use of lists. So you would make the general case slower, just to support a special case. Why are you proposing that? Regards, Martin

"Martin v. Loewis" <martin@v.loewis.de> writes:

That will cause a major ABI incompatibility, as all modules that use PyList_GET_SIZE need to be recompiled. In addition, it causes a slow-down for the standard use of lists. So you would make the general case slower, just to support a special case. Why are you proposing that?

I'm not proposing it, I'd have to provide an implementaton to do that :-) I just asked the question, "Why not a circular buffer implementation?" Tim has been patient enough to get my education on that subject started. ob_size should continue to be the number of pointers to objects. The GET_ITEM/SET_ITEM macros are more problematic in terms of overhead because an additional memory access would be required to get the current size of the block containing the pointer vector. As Tim said, other methods under consideration could also change the ABI. If the overall slowdown of lists to get fast queues was 5%, that would no doubt be unacceptable. If it was 0.5%, I imagine it would be acceptable? Note that if no pop(0)'s are ever done on the list there is no wrap around and the slowdown is limited to the access of blocksize plus a test; no modulo arithmetic is necessary. This is also the case if the list doesn't grow and items are only removed, including list[0]. And in the latter case, the memmoves associated with internal deletions will dominate the performance in all implementations. -- KBK

...

Note that if no pop(0)'s are ever done on the list there is no wrap around and the slowdown is limited to the access of blocksize plus a test; no modulo arithmetic is necessary. This is also the case if

[Kurt B. Kaiser] the

...

list doesn't grow and items are only removed, including list[0]. And in the latter case, the memmoves associated with internal deletions will dominate the performance in all implementations.

[Timbot]

Neither case holds for a queue; the question that started this was whether to provide a fancy queue implementation in C, and (of course) Guido would rather see Python lists efficiently usable for that purpose too. I suspected that might not be a realistic hope, and now I'm starting to *think* it too <wink>.

It needn't be especially fancy. Here is what I had in mind: n = 50 class fifo(object): def __init__(self): # block[0:n] is for data and block[n] is a link field self.head = self.tail = [None] * (n+1) self.headptr = self.tailptr = 0 def push(self, x): if self.headptr == n: newblock = [None] * (n+1) self.head[n] = newblock self.head = newblock self.headptr = 0 self.head[self.headptr] = x self.headptr += 1 def pop(self): if self.tail is self.head and self.tailptr >= self.headptr: raise IndexError if self.tailptr == n: self.tail = self.tail[n] self.tailptr = 0 x = self.tail[self.tailptr] self.tailptr += 1 return x The memory manager is called once every for 50 queue insertions and memory is freed after every 50 pops. Outside of that, every push and pop just a fast array access and pointer increment. Long queues incur about a 15-20% space overhead as compared to a straight-list implementation. Speedwise, this beats the socks off of the current approach. Raymond Hettinger ################################################################# ################################################################# ################################################################# ##### ##### ##### ################################################################# ################################################################# ################################################################# ################################################################# ################################################################# ################################################################# ##### ##### ##### ################################################################# ################################################################# #################################################################

...

The memory manager is called once every for 50 queue insertions and memory is freed after every 50 pops. Outside of that, every push and pop just a fast array access and pointer increment. Long queues incur about a 15-20% space overhead as compared to a straight-list implementation. Speedwise, this beats the socks off of the current approach.

Meaning pairing append() and pop(0)? Sure -- it would be hard not to beat that <wink>.

I've never needed a queue in Python where "the standard" two-list

No, I meant that it is *much* faster to do an indexed write to a pre-allocated list than to use anything relying on PyList_Append() or ins1(). All of those individual calls to realloc are expensive. The 50 to 1 dilution of that expense is how it beats Knuth's two stack trick. Guess which of these two statements is faster and by how much: list(itertools.repeat(None, 5000)) list(tuple(itertools.repeat(None, 5000))) The answer is important because it points the way to faster list comprehensions and other list building applications. trick

(as shown in Josiah's Cookbook comment) wasn't more than good enough, so my interest in this is really limited to whether Python's native list type can (realistically) be made efficient for general deque operation.

And my interest is in a collections module which should probably published elsewhere (too much negativity on the subject here). I am frankly surprised that so many here think that a collections module would be bad for the language. Go figure. It's not like these are new, untried ideas -- the goal was supposed be improving productivity by providing higher level tools. A fast underlying implementation was just icing on the cake. Raymond Hettinger ################################################################# ################################################################# ################################################################# ##### ##### ##### ################################################################# ################################################################# #################################################################

[Raymond Hettinger]

No, I meant that it is *much* faster to do an indexed write to a pre-allocated list than to use anything relying on PyList_Append() or ins1(). All of those individual calls to realloc are expensive. The 50 to 1 dilution of that expense is how it beats Knuth's two stack trick.

That's fine. As I said before, I've never had a use for a queue in Python where the two-stack trick (coded in Python, even) wasn't more than fast enough for me. If I did, there are a universe of possibilities, including Marc-Andre's mxQueue. That doesn't use Python lists; doesn't call realloc on every queue put (only when it's out of room, which is "never" when a queue reaches steady state); and, when it does realloc, overallocates by a much larger amount than Python's list type.

Guess which of these two statements is faster and by how much:

list(itertools.repeat(None, 5000)) list(tuple(itertools.repeat(None, 5000)))

I did guess, and was correct to 6 significant decimal digits <wink>.

The answer is important because it points the way to faster list comprehensions and other list building applications.

That Python's builtin list calls realloc() on every append is pretty gross, but it's also a tradeoff, saving the bytes in the list header that would be required to remember how many allocated-but-unused slots exist. If you've got a million tiny lists (and some apps do), burning an additional 8MB for something your app doesn't really need isn't attractive (on a 32-bit box today, the list header is 16 bytes; pymalloc aligns to 8-byte boundaries, so the next possible size is 24 bytes). list's very small overallocation (in the ballpark of 5%) is also aimed at minimizing memory burden. Speed isn't everything, tradeoffs are hard, and something loses when something else is favored. (BTW, I never would have considered implementing a resizable list type *without* keeping a field to record the amount of overallocation, so this isn't the tradeoff I would have made <wink>.)

... And my interest is in a collections module which should probably published elsewhere (too much negativity on the subject here).

A collections *package* is a fine idea. I say "package" instead of "module" because there are literally hundreds of container types, and queues and bags are a tiny corner of that space. An example dear to my heart is BTrees (I maintain Zope's BTree implementation), which is a wonderful way to get an associative mapping sorted by key value. BTrees have a large API all by themselves, so it wouldn't make sense to try to squash them into a module along with 50 other container types.

I am frankly surprised that so many here think that a collections module would be bad for the language.

I was more of the impression that bags didn't have fans <wink>.

Go figure. It's not like these are new, untried ideas -- the goal was supposed be improving productivity by providing higher level tools. A fast underlying implementation was just icing on the cake.

I'm strongly in favor of a collections package.

[Guido]

Just in case nobody had thought of it before, couldn't the realloc() call be avoided when roundupsize(oldsize) == roundupsize(newsize)???

I had thought of it before, but never acted on it <wink>. roundupsize() has gotten more expensive over the years too, and it may vary across boxes whether it's cheaper to call that a second time than it is to make the system realloc deduce that nothing needs to be done. roundupsize() is certainly cheaper than Microsoft's realloc() in the do-nothing case. Note that there's an endcase glitch here when oldsize==0 and newsize==1. roundupsize() returns 8 for both, but it doesn't follow that ob_item isn't NULL. realloc(p, n) special-cases the snot out of p==NULL to avoid crashing then. Note in passing that roundupsize() is expensive *because* lists don't remember the amount of overallocated space too: roundupsize() has to arrange to deliver the same result for many consecutive inputs, to prevent asking the platform for non-trivial reallocs() ("trivial realloc" == "do-nothing realloc" == realloc(p, n) called with fixed p and n multiple successive times). If we knew the point at which the "excess" slots were exhausted, then, e.g., doing realloc(oldsize + (oldsize >> 4)) at that point would give similar behavior with a much cheaper "new size" function (if we only computed a new size when a new size was actually needed, the "new size" function wouldn't have to arrange to remain constant over (eventually) unboundedly long stretches of consecutive inputs).

[Guido]

...

Just in case nobody had thought of it before, couldn't the realloc() call be avoided when roundupsize(oldsize) == roundupsize(newsize)???

[Tim]

Followup: it's not quite that easy, because (at least) PyList_New(int size) can create a list whose allocated size hasn't been rounded up.

If I "fix" that, then it's possible to get away with just one roundupsize() call on most list.insert() calls (including list.append()), while avoiding the realloc() call too. Patch attached.

I timed it like so:

def punchit(): from time import clock as now a = [] push = a.append start = now() for i in xrange(1000000): push(i) finish = now() return finish - start

for i in range(10): print punchit()

and got these elapsed times (this is Windows, so this is elapsed wall-clock time):

before after ------------- -------------- 1.05227710823 1.02203188119 1.05532442716 0.569660068053 1.05461539751 0.568627533147 1.0564449622 0.569336562799 1.05964146231 0.573247959235 1.05679528655 0.568503494862 1.05569402772 0.569745553898 1.05383177727 0.569499991619 1.05528000805 0.569163914916 1.05636618113 0.570356526258

So pretty consistent here, apart from the glitch on the first "after" run, and about an 80% speedup.

Yawn <wink>.

If someone wants to run with this, be my guest. There may be other holes (c.f. PyList_New above), and it could sure use a comment about why it's correct (if it in fact is <0.9 wink>).

Awesome! We need timing results on some other platforms (Linux, FreeBSD, MacOSX). Volunteers? --Guido van Rossum (home page: http://www.python.org/~guido/)

[John Williams]

Tim's optimization seems to help even more on Linux than Windows. On my box each iteration of the test program takes 0.80s without the patch and 0.27 with it.

Wow! That's better than I had hoped for. I'll note one subtlety: the call to realloc() probably endures mutex locking overhead to keep it threadsafe, even if the realloc() is (in the end) a nop. It certainly does under Microsoft's realloc(), but the native locking gimmicks on Windows are very fast (Windows loves threads).

[Jeff Epler]

To repeat findings on a Linux machine (redhat9, x86, 2.4GHz): Old New 0.74 0.22 0.74 0.22 0.74 0.22 0.74 0.22 0.72 0.21 0.76 0.22 0.74 0.22 0.77 0.22 0.75 0.22 0.74 0.22

I also got the same (?) failure as tim described: test_list make: *** [test] Segmentation fault

Yup, that's the one. This line in listsort(): self->ob_item = empty_ob_item = PyMem_NEW(PyObject *, 0); violates the new assumption too; it can be replaced with, e.g., self->ob_item = empty_ob_item = PyMem_NEW(PyObject *, roundupsize(0) * sizeof(PyObject*)); although that should really be checked for a NULL return too.

Guido van Rossum <guido@python.org> writes:

Awesome! We need timing results on some other platforms (Linux, FreeBSD, MacOSX).

OpenBSD 3.3, i386 2.4Ghz P4 Celeron, 256MB, 128kB cache before after ------ ----- 1.2 0.64 1.15 0.60 1.16 0.60 1.16 0.60 1.16 0.61 1.15 0.60 1.13 0.61 1.15 0.59 1.14 0.62 1.15 0.60 before: 15773 pystones, 29.9 mPB after: 12690 pystones, 31.4 mPB Switch back to CVS: 19531, 19379, 19531, 19379, 19305, 19084 pystones, 31.4 mPB Switch back to Tim's patch: 15015, 15480, 14588 pystones should not need, but: make clean && make (just make on previous, only listobject.c being recompiled) Still patched: 13158, 14006, 13193; restart python; 15923, 16722, 16023 restart python; 12953, 13698, 12953, 13513 Well, pystones are all over the map on this box. But the improvement is there for punchit and the parrotbench benchmark is solid across the change. -- KBK

Guido van Rossum <guido@python.org> writes:

...

before: 15773 pystones, 29.9 mPB after: 12690 pystones, 31.4 mPB

What's the mPB number? If its the time to complete parrotbench, this is actually a slowdown, just as for pystone.

...

Switch back to CVS:

19531, 19379, 19531, 19379, 19305, 19084 pystones, 31.4 mPB

Switch back to Tim's patch:

15015, 15480, 14588 pystones

should not need, but: make clean && make (just make on previous, only listobject.c being recompiled)

Still patched: 13158, 14006, 13193; restart python; 15923, 16722, 16023 restart python; 12953, 13698, 12953, 13513

Well, pystones are all over the map on this box. But the improvement is there for punchit and the parrotbench benchmark is solid across the change.

Unclear. Please clarify mPB.

milliParrotBenches/sec. 1000/(time to complete Parrotbench [sec]) In a few years we'll be spec'ing kPB :-) So the data so far is 29.9 mPB unpatched 31.4 mPB patched 31.4 mPB unpatched This morning: 30.7, 30.4, 30.1, 32.1, 32.2, 31.9 mPB patched (using make time) rm Objects/listobject.c && cvs up Objects/listobject.c make clean && make 30.1, 30.2, 30.3, 32.1, 29.6, 29.9, 28.2 mPB unpatched Average unpatched: 30.2 mPB Average patched: 31.3 mPB So a 3 - 4% improvement, maybe. Needs more data. I reported the equivalent of 31.1 mPB on 2Jan04, which was the best of several trials. The 'best of 3' pystones at that time was 17182. Pystone ------- My impression is that Pystone isn't a good benchmark for this box unless run many times over a long period with python restarts, perhaps a cron at night. It may be the 128kB cache, but the results are very variable. This morning, with patched listobject.c, it's 15015, 15060, 14881; restart python; 16891, 17182, 17361 restart python; 14925, 14970, 14925, 14492, 14662, 14836, 15060, 15106, 15060 append sys.path and import a module: 13889, 13927, 14084 do some stuff, then: 14662, 14368, 14577 restart python; 14836, 14881, 14836 restart python; 15337, 15337, 15337, 15773, 15873, 15674, 15479, 15432, 14792 Following the switch back to unpatched mentioned above: 18182, 18050, 18248, 18450, 18248, 18181 restart python; 14881, 14970, 14705, 14836, 14749, 14970 restart python; 16835, 16835, 16778, 17064, 17182, 16892 restart python; append sys.path, import module; 20000, 20408, 20080, 20808, 19763, 20000 do some stuff; 19305, 19762, 19607, 19084, 19455, 19455 restart python; 17605, 17731, 17482, 17544, 17544, 17483 On these two sets: Average unpatched: 17865 pystones Average patched: 15136 pystones A 15% reduction with the patch. This *may* be significant, but requires a lot more data here and investigation by others. On this box the pystone rating jumps between python restarts. I haven't calculated any more advanced statistics; IMHO with small data sets, especially jumpy, ragged ones like these, you can often get a better feel by just eyeballing it. The downside being, you tend to see what you want to see.... -- KBK

Here are the parrotbench results, using the "user" field from "make time" output. There's a clear speedup of nearly 1 second in the -listopt version. During parts of these tests my system was also running nice'd distcc jobs, but since user time was measured this shouldn't matter much. "real" times were slower for python-listopt (0.56 seconds difference of median values) and more scattered (1.52 std dev vs 0.32 std dev) for this reason. Python-cvs Python-listopt 18.32 18.39 18.44 18.39 18.83 17.53 18.75 17.38 18.63 17.37 18.91 17.36 18.55 17.63 18.66 18.06 18.68 17.38 18.74 17.92 Minimum 18.32 17.36 Maximum 18.91 18.39 Median 18.67 17.58 Average 18.65 17.74 Std.Dev 0.18 0.42 T-test 0.00% =ttest(b2:b11; c2:c11; 2; 3) Difference of median values -0.91

On Jan 13, 2004, at 12:14 PM, Guido van Rossum wrote:

...

[Guido]

...

Just in case nobody had thought of it before, couldn't the realloc() call be avoided when roundupsize(oldsize) == roundupsize(newsize)???

[Tim]

...

Followup: it's not quite that easy, because (at least) PyList_New(int size) can create a list whose allocated size hasn't been rounded up.

If I "fix" that, then it's possible to get away with just one roundupsize() call on most list.insert() calls (including list.append()), while avoiding the realloc() call too. Patch attached.

I timed it like so:

def punchit(): from time import clock as now a = [] push = a.append start = now() for i in xrange(1000000): push(i) finish = now() return finish - start

for i in range(10): print punchit()

and got these elapsed times (this is Windows, so this is elapsed wall-clock time):

before after ------------- -------------- 1.05227710823 1.02203188119 1.05532442716 0.569660068053 1.05461539751 0.568627533147 1.0564449622 0.569336562799 1.05964146231 0.573247959235 1.05679528655 0.568503494862 1.05569402772 0.569745553898 1.05383177727 0.569499991619 1.05528000805 0.569163914916 1.05636618113 0.570356526258

So pretty consistent here, apart from the glitch on the first "after" run, and about an 80% speedup.

Yawn <wink>.

If someone wants to run with this, be my guest. There may be other holes (c.f. PyList_New above), and it could sure use a comment about why it's correct (if it in fact is <0.9 wink>).

Awesome! We need timing results on some other platforms (Linux, FreeBSD, MacOSX).

Volunteers?

Mac OS X 10.3.2, gcc (GCC) 3.3 20030304 (Apple Computer, Inc. build 1495), dual g5 2ghz w/ 1gb ram, ./configure --disable-framework before after 0.38 0.29 0.36 0.26 0.36 0.26 0.36 0.27 0.36 0.26 0.36 0.26 0.36 0.26 0.36 0.26 0.36 0.27 0.36 0.26 Mac OS X 10.3.2, gcc (GCC) 3.3 20030304 (Apple Computer, Inc. build 1495), dvi titanium powerbook g4 1ghz w/ 1gb ram, ./configure --disable-framework before after 0.78 0.57 0.74 0.53 0.73 0.53 0.74 0.52 0.73 0.52 0.76 0.53 0.73 0.53 0.75 0.53 0.75 0.53 0.75 0.52 So it seems that the 2ghz g5 is about twice as fast as the 1ghz g4 for Python (when running TIm's test), and that either way you save about 25% with Tim's patch. -bob

[Raymond Hettinger]

I'll look at the this this weekend.

The improvement is awesome. Hope it has doesn't muck-up anything else.

It probably does. It introduces a deep assumption that a list is *never* allocated, or resized, to hold ob_size slots, but always to hold (at lesat) roundupsize(ob_size) slots. If that's ever wrong, the "after" code may not call realloc() when a realloc is needed (for example, leave out the part that patched PyList_New(), and watch Python crash all over the place). One of the standard tests crashed, but I didn't have time to figure out why. It seemed odd because it died in some sorting test. A note about why it "should be" correct: for all i >= 0 roundupsize(i) > i [1] is true. So, calling ob_size "n" for brevity, if we ever reach a point where roundupsize(n) == n+1 then since roundupsize(n+1) > n+1 (by #1, letting i = n+1) it follows that roundupsize(n+1) > n+1 == roundupsize(n) Or, IOW, when roundupsize(n)==n+1, we're exactly at a boundary where roundupsize(n+1) grows, so that's a point at which adding a new element requires calling realloc. Otherwise roundupsize(n) > n+1 (since roundupsize(n) > n by #1, it's not possible that roundupsize(n) < n+1), so there's room enough already for an additional element, and realloc() doesn't need to be called.

It needn't be especially fancy. Here is what I had in mind:

n = 50 class fifo(object):

def __init__(self): # block[0:n] is for data and block[n] is a link field self.head = self.tail = [None] * (n+1) self.headptr = self.tailptr = 0 ...etc...

I've got a few of the standard FIFO implementations sitting here, and I thought I would give them a run against each other. Testing methods are as follows: Initially create a FIFO of n elements. Alternate between pushing and popping 2n elements from the FIFO. Empty the FIFO. Timing each block, we get the following: Create Steady Empty n = 10000: Fifo 0.047 0.328 0.141 Fifo_list 0.171 0.485 0.14 fast_list_fifo 0.0 0.297 0.157 doublelistfifo 0.0 0.359 0.172 fifo_raymond 0.109 0.422 0.172 n = 20000: Fifo 0.093 0.657 0.297 Fifo_list 0.375 0.984 0.266 fast_list_fifo 0.0 0.594 0.312 doublelistfifo 0.0 0.719 0.344 fifo_raymond 0.203 0.859 0.329 n = 30000: Fifo 0.157 0.984 0.437 Fifo_list 0.563 1.453 0.422 fast_list_fifo 0.0 0.89 0.469 doublelistfifo 0.016 1.078 0.515 fifo_raymond 0.297 1.297 0.5 n = 40000: Fifo 0.203 1.328 0.594 Fifo_list 0.984 1.953 0.594 fast_list_fifo 0.015 1.188 0.625 doublelistfifo 0.0 1.437 0.687 fifo_raymond 0.438 1.734 0.656 Fifo: dictionary used as a fifo fifo_list: [cur, [next, [...]]] fast_list_fifo: push appends, pop increments a pointer, but never removes element doublelistfifo: self explanatory fifo_raymond: the fifo described by raymond. Initialization for Raymond's fifo can be ignored, it is merely inserting objects one at a time (I am short on time this evening). Interpret the rest of the numbers as is reasonable, but consider that there is likely a few percent margin of error on each number, unless something always beats another. I must be going to bed now, the wife is yelling at me. - Josiah

[Tim]

...

... We use mildly exponential overallocation when growing a list to ensure amortized O(1) behavior regardless.

[Kurt B. Kaiser]

The whole game lies in what happens when you resize: how much data are you going to copy?

We currently don't copy anything when we resize, although the platform realloc() may. To "make room at the left end" we would have to do a memmove() on a contiguous vector of len(list) pointers. I don't agree that's "the whole game", though -- it's a small piece of the game (the point of using exponential overallaction is to ensure that). As I said in the first msg, though, the overallocation gimmick we use now is less effective if a list can grow and shrink at both ends.

... If I understand the gimmick, as the queue is used

If a list is used as a queue, yes.

the ob_item/headpointer will walk down the block and items will be appended at the tail until the tail collides with the end of the block. At that point the gimmick approach will memmove the queue to place ob_item at the beginning of the block.

Possibly -- nobody has given enough detail to say. I'd be inclined to continue doing what we do now when an append runs out of room, which is to ask for more room, overallocating by a small percentage of the current list size. If there's free room "at the left end", though, it may or may not be more efficient to memmove the guts left. Those are important details that haven't gotten beyond the hand-wavy stage.

Since the block is only a little longer than the queue, that's quite a bit of copying, unless I'm missing something.

The amount of copying in *any* case where the speculative gimmick copies is proportional to the number of elements currenty in the list. When a list contains a million items, it's expensive. If a list contains a few dozen items, it's cheap. The current scheme overallocates proportional to the number of elements in the list, so "a little longer" is "a little" in a relative sense rather than in an absolute sense (e.g., it's millions of elements longer if the list contains hundreds of millions of elements -- then you can go through millions of appends after a resize before needing to do anything fancy again).

With a circular buffer approach, the headpointer and tailpointer will walk down the block and when the end is reached the tailpointer will wrap around and "appended" items will be stored at the low end of the block. The process continues without any copying.

So long as it doesn't run out of room. Eventually it will, and then it has to move stuff too. At that level the schemes are the same. Given specific common queue access patterns, a queue in steady state will "run out of room" more often under the contiguous gimmick than the circular one (I gave a simple example of that before, which in fact is probably a best case for the circular implementation and a worst case for the other one).

The position of the pointers is calculated modulo the blocksize, so no test/branch is involved.

Integer mod is much worse than test/branch -- Python runs on boxes where an integer divide takes more than 100 cycles. So I was assuming the cheaper way to implement this ("if (physical_pointer >= fence) physical_pointer -= block_size;"; test-and-conditionally-add/subtract instead of integer mod; and don't suggest that allocated sizes be restricted to powers of 2 just to make integer mod efficient (we can't afford that much memory waste)).

If there is some space at the beginning of the block which has been freed up by pop(0), the list will automatically wrap around to fill it, even when the pop(0) has been done in a non-queue context.

You can trust that my objection isn't that I don't understand how to implement a circular queue <wink>.

With a circular buffer, upon resize the gap between tail and head is widened by the amount added to the block. With a queue, that would on average amount to copying half the data, but with a known stride.

I don't know what "known stride" means in this context. Regardless of whether a circular implementation is used, a Python list is a contiguous vector of C pointers, and they're all the same size. Only these pointers are moved. With a reasonably careful circular implementation, needing to move half the pointers would be the worst case; assuming that the head and tail are equally likely to bump into each other at each possible position, the average number of pointer moves would be len/4.

One could take a conservative approach and rotate the buffer every resize so that ob_item is at the beginning of the block, but doing that seems to be unnecessary.

Also unhelpful -- every line of C code mucking with lists would still have to cater to the possibility that the list is spread across two disjoint memory slices. ...

...

As above, I don't see much to recommend that over the speculative Python list gimmick: indexing is slower and more complicated,

pointer arithmetic is cheap compared to memory access.

Let's inject some common sense here. Indexed list access is an extremely frequent operation, and cache-friendly sequential indexed list access is also extremely frequent. Moving memory around is a rare operation, and neither scheme can avoid it: the overwhelmingly most common kind of growing list will continue to be append-at-the-end, where the circular scheme buys nothing, but slows down all list operations. Growing lists are in turn rare compared to fixed-size lists, where the circular implementation is pure loss, in both time and space. The speculative gimmick is a loss in space there too, but doesn't slow it.

...

resizing is more complicated,

I'm not sure that's the case.

Neither am I, really <wink>.

And the gimmick approach has a 'complication' when the tail hits the end of the block even when the queue lenth is constant.

That appears to be its only drawback.

...

and all the listobject.c internals would get more complicated by needing to deal with that the list contents are no longer necessarily in a contiguous slice of a C vector (from the C POV, the list contents could be in two disjoint contiguous slices).

Not if modulo pointer arithmetic is used.

Sorry, but I consider this one too unrealistic to continue talking about. Start here: #define PyList_GET_ITEM(op, i) (((PyListObject *)(op))->ob_item[i]) #define PyList_SET_ITEM(op, i, v) \ (((PyListObject *)(op))->ob_item[i] = (v)) What are you going to replace those with? They must be fast, and they're expanded in over 100 places in the core. Then move on to here (the simplest function in listobject.c that actually does something <wink>): /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */ static void reverse_slice(PyObject **lo, PyObject **hi) { assert(lo && hi); --hi; while (lo < hi) { PyObject *t = *lo; *lo = *hi; *hi = t; ++lo; --hi; } } How are you going to rewrite that? For that matter, how are you going to change the function *signature* when "a slice of a Python list" can no longer be represented by a low and high pointer? When you're done with that, do this one: /* Merge the na elements starting at pa with the nb elements starting at pb * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the * merge, and should have na <= nb. See listsort.txt for more info. * Return 0 if successful, -1 if error. */ static int merge_lo(MergeState *ms, PyObject **pa, int na, PyObject **pb, int nb) { int k; PyObject *compare; PyObject **dest; int result = -1; /* guilty until proved innocent */ int min_gallop = ms->min_gallop; assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); if (MERGE_GETMEM(ms, na) < 0) return -1; memcpy(ms->a, pa, na * sizeof(PyObject*)); dest = pa; pa = ms->a; *dest++ = *pb++; --nb; if (nb == 0) goto Succeed; if (na == 1) goto CopyB; compare = ms->compare; for (;;) { int acount = 0; /* # of times A won in a row */ int bcount = 0; /* # of times B won in a row */ /* Do the straightforward thing until (if ever) one run * appears to win consistently. */ for (;;) { assert(na > 1 && nb > 0); k = ISLT(*pb, *pa, compare); if (k) { if (k < 0) goto Fail; *dest++ = *pb++; ++bcount; acount = 0; --nb; if (nb == 0) goto Succeed; if (bcount >= min_gallop) break; } else { *dest++ = *pa++; ++acount; bcount = 0; --na; if (na == 1) goto CopyB; if (acount >= min_gallop) break; } } /* One run is winning so consistently that galloping may * be a huge win. So try that, and continue galloping until * (if ever) neither run appears to be winning consistently * anymore. */ ++min_gallop; do { assert(na > 1 && nb > 0); min_gallop -= min_gallop > 1; ms->min_gallop = min_gallop; k = gallop_right(*pb, pa, na, 0, compare); acount = k; if (k) { if (k < 0) goto Fail; memcpy(dest, pa, k * sizeof(PyObject *)); dest += k; pa += k; na -= k; if (na == 1) goto CopyB; /* na==0 is impossible now if the comparison * function is consistent, but we can't assume * that it is. */ if (na == 0) goto Succeed; } *dest++ = *pb++; --nb; if (nb == 0) goto Succeed; k = gallop_left(*pa, pb, nb, 0, compare); bcount = k; if (k) { if (k < 0) goto Fail; memmove(dest, pb, k * sizeof(PyObject *)); dest += k; pb += k; nb -= k; if (nb == 0) goto Succeed; } *dest++ = *pa++; --na; if (na == 1) goto CopyB; } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); ++min_gallop; /* penalize it for leaving galloping mode */ ms->min_gallop = min_gallop; } Succeed: result = 0; Fail: if (na) memcpy(dest, pa, na * sizeof(PyObject*)); return result; CopyB: assert(na == 1 && nb > 0); /* The last element of pa belongs at the end of the merge. */ memmove(dest, pb, nb * sizeof(PyObject *)); dest[nb] = *pa; return 0; } There are thousands of additional lines that assume a list is one contiguous vector of pointers, and that the dead-simple and killer-fast ordinary contiguous-vector C idioms work.

...

It would have the advantage that resizing is never needed until you're wholly out of room, but that seems minor compared to the drawbacks.

Just thought I'd repeat that <wink>.

[Terry Reedy]

On enhancing list object: queue vs. deque.

My general impression is that queues, while less common than stacks, are used enough in enough different algorithms that adding one implementation field to list headers so that pop(0) is an O(1) pointer move might be an overall win for Python. The current O(n) move everything every time behavior is certainly a nuisance when queues are needed.

See the other msgs in this thread today -- I'm not convinced that queue-like behavior can be supported that efficiently.

Deques, on the other hand, seem to be more a theoretical construct. Algorithm books include them for completeness in describing possible list disciplines, but generally ignore them thereafter. I am hard put to remember an algorithm that actually needs them. They are certainly much rarer than queues. So I do not think trying to make prepends O(1) should be considered further.

I expect that if queue-like behavior *can* be supported efficiently using an always-contiguous vector, efficient dequeue-like behavior will fall out for free.

My possibly naive thought is that before reallocating, look at the ratio of left free to total.

I don't know what that means (neither the "left free" part nor what exactly "total" is counting). The devil is in the details here.

If memmove would result in as much, or perhaps nearly as much, over-allocation as realloc,

memmove() leaves the total number of unused slots unchanged. realloc can do that too, or increase it by any amount, or decrease it by any amount. I just don't know what you're trying to say ... explain how it works, step by step, in the q = [incoming() for i in range(1000)] while True: q.append(incoming()) consume(q.pop(0)) example.

then just do that. Certainly if the ratio is small (like say .1), don't bother with memmove. The exact cutoff is a tuning matter.

Separate issue: for best performance, one would like to be able trade space for time and preallocate a large enough block so that most append faults result in a memmove back to the left. Does the current builtin shrinkage discipline would allow this. Or does "q=[0]*1000; q[:]=[]" shrink the space for q back to nearly nothing?

Python *offers* to give 992 slots back; whether the platform realloc() accepts the offer is up to it. In the "details are everything" department, Python *also* creates a temp vector of length 1000, and copies all of q[:] into it before it deletes any of q: emptying a list is a linear-time operation, not constant-time. That's because it's not safe to decref anything in a list while tearing it down (e.g., the list may be visible to a __del__ method, which must not be allowed to see NULL pointers, or reclaimed objects, in the list).

(One might also want to do same for stack. And yes, I remember: 'user tuning' is a 'bad idea'. But....)

Tim Peters wrote:

The overallocation strategy gets more complicated, though, and less effective for prepending. If you run out of room when prepending, it's not enough just to ask realloc() for more memory, you also have to memmove() the entire vector, to "make room at the left end". In previous lives I've found that "appending at the right" is as efficient as it is in practice largely because most non-trivial C realloc() calls end up extending the vector in-place, not needing to copy anything. The O() behavior is the same if each boost in size has to move everything that already existed, but the constant factor goes up more than just measurably <wink>.

Shouldn't you malloc() in the case of prepending, and do the copying yourself? realloc can only avoid copying if it can append a free block. For the list, we know a) realloc is unlikely to find a new block, anyway, as it is pymalloc, which never extends a small block. b) even if realloc would be able to extend the block, we still would have to copy the data. I don't know whether the overallocation would make similar-sized room at both ends, or whether it would take the current operation into account. For the specific case of queues, we may find that doing *just* the copying might be sufficient, with no need to go to the allocator. Regards, Martin

...

I don't know whether the overallocation would make similar-sized room at both ends, or whether it would take the current operation into account. For the specific case of queues, we may find that doing *just* the copying might be sufficient, with no need to go to the allocator.

Hm. An idea: don't bother overallocating when inserting in the front, but do keep the free space in the front if possible. Then recommend that queus are implemented using append(x) and pop(0), rather than using insert(0, x) and pop().

That is a reasonable approach and probably not difficult to implement. Since external code (outside listobject.c) may already be relying on ob_item, the approach should just change that field to always point to the start of valid data. A new field would have to keep a pointer to the actual allocated block. Raymond Hettinger ################################################################# ################################################################# ################################################################# ##### ##### ##### ################################################################# ################################################################# #################################################################

Tim Peters wrote:

...

Hm. An idea: don't bother overallocating when inserting in the front, but do keep the free space in the front if possible.

I'm not clear on what that means, and the devil's in the details.

I interpret it as: when doing an insert in the middle or at the beginning, continue doing what we do today. I.e. never overallocate extra space in the front, unless the extra space is already there (so realloc would just copy it/leave it as-is). When appending, you would then first check whether there is space at the beginning, and move items if there is. Otherwise reallocate, with the overallocation-to-the-right formula.

...

Then recommend that queues are implemented using append(x) and pop(0), rather than using insert(0, x) and pop().

Given the way realloc() works, I expect that add-at-the-right will always be favored.

Indeed, I would always implement lists as .append/.pop(0) - it would not have occurred to my mind to write them as insert(0, x)/.pop(), as I consider .insert on a list unintuitive. Regards, Martin