summaryrefslogtreecommitdiffstats
path: root/Objects/listobject.c
Commit message (Collapse)AuthorAgeFilesLines
...
* 1. Combined the base and length arrays into a single array of structs.Tim Peters2002-08-101-30/+54
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is friendlier for caches. 2. Cut MIN_GALLOP to 7, but added a per-sort min_gallop vrbl that adapts the "get into galloping mode" threshold higher when galloping isn't paying, and lower when it is. There's no known case where this hurts. It's (of course) neutral for /sort, \sort and =sort. It also happens to be neutral for !sort. It cuts a tiny # of compares in 3sort and +sort. For *sort, it reduces the # of compares to better than what this used to do when MIN_GALLOP was hardcoded to 10 (it did about 0.1% more *sort compares before, but given how close we are to the limit, this is "a lot"!). %sort used to do about 1.5% more compares, and ~sort about 3.6% more. Here are exact counts: i *sort 3sort +sort %sort ~sort !sort 15 449235 33019 33016 51328 188720 65534 before 448885 33016 33007 50426 182083 65534 after 0.08% 0.01% 0.03% 1.79% 3.65% 0.00% %ch from after 16 963714 65824 65809 103409 377634 131070 962991 65821 65808 101667 364341 131070 0.08% 0.00% 0.00% 1.71% 3.65% 0.00% 17 2059092 131413 131362 209130 755476 262142 2057533 131410 131361 206193 728871 262142 0.08% 0.00% 0.00% 1.42% 3.65% 0.00% 18 4380687 262440 262460 421998 1511174 524286 4377402 262437 262459 416347 1457945 524286 0.08% 0.00% 0.00% 1.36% 3.65% 0.00% 19 9285709 524581 524634 848590 3022584 1048574 9278734 524580 524633 837947 2916107 1048574 0.08% 0.00% 0.00% 1.27% 3.65% 0.00% 20 19621118 1048960 1048942 1715806 6045418 2097150 19606028 1048958 1048941 1694896 5832445 2097150 0.08% 0.00% 0.00% 1.23% 3.65% 0.00% 3. Added some key asserts I overlooked before. 4. Updated the doc file.
* PyList_Reverse(): This was leaking a reference to Py_None on every call.Tim Peters2002-08-081-1/+4
| | | | | I believe I introduced this bug when I refactored the reversal code so that the mergesort could use it too. It's not a problem on the 2.2 branch.
* Sped the usual case for sorting by calling PyObject_RichCompareBoolTim Peters2002-08-041-10/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | directly when no comparison function is specified. This saves a layer of function call on every compare then. Measured speedups: i 2**i *sort \sort /sort 3sort +sort %sort ~sort =sort !sort 15 32768 12.5% 0.0% 0.0% 100.0% 0.0% 50.0% 100.0% 100.0% -50.0% 16 65536 8.7% 0.0% 0.0% 0.0% 0.0% 0.0% 12.5% 0.0% 0.0% 17 131072 8.0% 25.0% 0.0% 25.0% 0.0% 14.3% 5.9% 0.0% 0.0% 18 262144 6.3% -10.0% 12.5% 11.1% 0.0% 6.3% 5.6% 12.5% 0.0% 19 524288 5.3% 5.9% 0.0% 5.6% 0.0% 5.9% 5.4% 0.0% 2.9% 20 1048576 5.3% 2.9% 2.9% 5.1% 2.8% 1.3% 5.9% 2.9% 4.2% The best indicators are those that take significant time (larger i), and where sort doesn't do very few compares (so *sort and ~sort benefit most reliably). The large numbers are due to roundoff noise combined with platform variability; e.g., the 14.3% speedup for %sort at i=17 reflects a printed elapsed time of 0.18 seconds falling to 0.17, but a change in the last digit isn't really meaningful (indeed, if it really took 0.175 seconds, one electron having a lazy nanosecond could shift it to either value <wink>). Similarly the 25% at 3sort i=17 was a meaningless change from 0.05 to 0.04. However, almost all the "meaningless changes" were in the same direction, which is good. The before-and-after times for *sort are clearest: before after 0.18 0.16 0.25 0.23 0.54 0.50 1.18 1.11 2.57 2.44 5.58 5.30
* SF bug 590366: Small typo in listsort:ParseTupleTim Peters2002-08-031-1/+1
| | | | The PyArg_ParseTuple() error string still said "msort". Changed to "sort".
* Replaced samplesort with a stable, adaptive mergesort.Tim Peters2002-08-011-406/+772
|
* Fix forMichael W. Hudson2002-07-291-3/+8
| | | | | | [ 587875 ] crash on deleting extended slice The array code got simpler, always a good thing!
* Patch #574867: Correct list.extend docstring.Martin v. Löwis2002-07-281-1/+1
|
* More sort cleanup: Moved the special cases from samplesortslice intoTim Peters2002-07-191-65/+73
| | | | | | | | | | | listsort. If the former calls itself recursively, they're a waste of time, since it's called on a random permutation of a random subset of elements. OTOH, for exactly the same reason, they're an immeasurably small waste of time (the odds of finding exploitable order in a random permutation are ~= 0, so the special-case loops looking for order give up quickly). The point is more for conceptual clarity. Also changed some "assert comments" into real asserts; when this code was first written, Python.h didn't supply assert.h.
* binarysort() cleanup: Documented the key invariants, explained why theyTim Peters2002-07-191-2/+13
| | | | imply this is a stable sort, and added some asserts.
* listreverse(): Don't call the new reverse_slice unless the listTim Peters2002-07-191-1/+2
| | | | has something in it (else ob_item may be a NULL pointer).
* Cleanup yielding a small speed boost: before rich comparisons wereTim Peters2002-07-191-50/+32
| | | | | | | | | | | | | | | | | | introduced, list.sort() was rewritten to use only the "< or not <?" distinction. After rich comparisons were introduced, docompare() was fiddled to translate a Py_LT Boolean result into the old "-1 for <, 0 for ==, 1 for >" flavor of outcome, and the sorting code was left alone. This left things more obscure than they should be, and turns out it also cost measurable cycles. So: The old CMPERROR novelty is gone. docompare() is renamed to islt(), and now has the same return conditinos as PyObject_RichCompareBool. The SETK macro is renamed to ISLT, and is even weirder than before (don't complain unless you want to maintain the sort code <wink>). Overall, this yields a 1-2% speedup in the usual (no explicit function passed to list.sort()) case when sorting arrays of floats (as sortperf.py does). The boost is higher for arrays of ints.
* Trimmed trailing whitespace.Tim Peters2002-07-191-22/+22
|
* Cleanup: Define one internal utility for reversing a list slice, andTim Peters2002-07-191-28/+20
| | | | use that everywhere.
* staticforward bites the dust.Jeremy Hylton2002-07-171-1/+1
| | | | | | | | | | | | | | | The staticforward define was needed to support certain broken C compilers (notably SCO ODT 3.0, perhaps early AIX as well) botched the static keyword when it was used with a forward declaration of a static initialized structure. Standard C allows the forward declaration with static, and we've decided to stop catering to broken C compilers. (In fact, we expect that the compilers are all fixed eight years later.) I'm leaving staticforward and statichere defined in object.h as static. This is only for backwards compatibility with C extensions that might still use it. XXX I haven't updated the documentation.
* Whitespace normalization.Guido van Rossum2002-07-161-66/+66
|
* Make StopIteration a sink state. This is done by clearing out theGuido van Rossum2002-07-161-11/+10
| | | | | | | | | it_seq field when the end of the list is reached. Also remove the next() method -- one is supplied automatically by PyType_Ready() because the tp_iternext slot is set. That's a good thing, because the implementation given here was buggy (it never raised StopIteration).
* Make list_iter() really static.Guido van Rossum2002-07-161-1/+1
|
* docompare(): Another reasonable optimization from Jonathan Hogg for theTim Peters2002-07-151-1/+1
| | | | | | explicit comparison function case: use PyObject_Call instead of PyEval_CallObject. Same thing in context, but gives a 2.4% overall speedup when sorting a list of ints via list.sort(__builtin__.cmp).
* Don't declare a function with staticforward.Jeremy Hylton2002-07-131-2/+2
| | | | | Just declare it static so that lame (BAD_STATIC_FORWARD) compilers don't see a mismatch between the prototype and the function.
* docompare(): Use PyTuple_New instead of Py_BuildValue to build compare'sTim Peters2002-07-111-2/+7
| | | | | | | | | | | | | | | | | | | | | | | arg tuple. This was suggested on c.l.py but afraid I can't find the msg again for proper attribution. For list.sort(cmp) where list is a list of random ints, and cmp is __builtin__.cmp, this yields an overall 50-60% speedup on my Win2K box. Of course this is a best case, because the overhead of calling cmp relative to the cost of actually comparing two ints is at an extreme. Nevertheless it's huge bang for the buck. An additionak 20-30% can be bought by making the arg tuple an immortal static (avoiding all but "the first" PyTuple_New), but that's tricky to make correct since docompare needs to be reentrant. So this picks the cherry and leaves the pits for Fred <wink>. Note that this makes no difference to the list.sort() case; an arg tuple gets built only if the user specifies an explicit sort function.
* Fix the bug described inMichael W. Hudson2002-06-191-5/+9
| | | | | | | | | http://mail.python.org/pipermail/python-dev/2002-June/025461.html with test cases. Also includes extended slice support for arrays, which I thought I'd already checked in but obviously not.
* Missed one use of new PyDoc_STRVAR macroNeal Norwitz2002-06-141-2/+2
|
* SF #561244 Micro optimizationsNeal Norwitz2002-06-131-5/+2
| | | | Convert loops to memset()s.
* Patch #568124: Add doc string macros.Martin v. Löwis2002-06-131-18/+18
|
* Fold remaining long lines.Guido van Rossum2002-06-111-2/+6
|
* This is my nearly two year old patchMichael W. Hudson2002-06-111-1/+187
| | | | | | | | | [ 400998 ] experimental support for extended slicing on lists somewhat spruced up and better tested than it was when I wrote it. Includes docs & tests. The whatsnew section needs expanding, and arrays should support extended slices -- later.
* A bogus assert in the new listiter code prevented starting Python in aTim Peters2002-06-011-10/+12
| | | | | debug build. Repaired that, and rewrote other parts to reduce long-winded casting.
* SF 560736. Optimize list iteration by filling the tp_iter slot.Raymond Hettinger2002-05-311-1/+118
|
* Closes: #556025 seg fault when doing list(xrange(1e9))Neal Norwitz2002-05-221-2/+11
| | | | | | | | | A MemoryError is now raised when the list cannot be created. There is a test, but as the comment says, it really only works for 32 bit systems. I don't know how to improve the test for other systems (ie, 64 bit or systems where the data size != addressable size, e.g. 64 bit data, but 48 bit addressable memory)
* PyObject_GC_Del can now be used as a function designator.Neil Schemenauer2002-04-121-1/+1
|
* This is Neil's fix for SF bug 535905 (Evil Trashcan and GC interaction).Guido van Rossum2002-03-281-1/+1
| | | | | | | | The fix makes it possible to call PyObject_GC_UnTrack() more than once on the same object, and then move the PyObject_GC_UnTrack() call to *before* the trashcan code is invoked. BUGFIX CANDIDATE!
* Fix of SF bug #475877 (Mutable subtype instances are hashable).Guido van Rossum2001-12-031-2/+9
| | | | | | | | | | | | | | | | | Rather than tweaking the inheritance of type object slots (which turns out to be too messy to try), this fix adds a __hash__ to the list and dict types (the only mutable types I'm aware of) that explicitly raises an error. This has the advantage that list.__hash__([]) also raises an error (previously, this would invoke object.__hash__([]), returning the argument's address); ditto for dict.__hash__. The disadvantage for this fix is that 3rd party mutable types aren't automatically fixed. This should be added to the rules for creating subclassable extension types: if you don't want your object to be hashable, add a tp_hash function that raises an exception. Also, it's possible that I've forgotten about other mutable types for which this should be done.
* Enable GC for new-style instances. This touches lots of files, sinceGuido van Rossum2001-10-051-1/+2
| | | | | | | | | | | | | | | | | | | | | | many types were subclassable but had a xxx_dealloc function that called PyObject_DEL(self) directly instead of deferring to self->ob_type->tp_free(self). It is permissible to set tp_free in the type object directly to _PyObject_Del, for non-GC types, or to _PyObject_GC_Del, for GC types. Still, PyObject_DEL was a tad faster, so I'm fearing that our pystone rating is going down again. I'm not sure if doing something like void xxx_dealloc(PyObject *self) { if (PyXxxCheckExact(self)) PyObject_DEL(self); else self->ob_type->tp_free(self); } is any faster than always calling the else branch, so I haven't attempted that -- however those types whose own dealloc is fancier (int, float, unicode) do use this pattern.
* Give the internal immutable list type .extend and .pop methods (theyTim Peters2001-08-301-0/+2
| | | | "should have" been added here when they were added to lists).
* Use new GC API.Neil Schemenauer2001-08-291-15/+10
|
* Patch #427190: Implement and use METH_NOARGS and METH_O.Martin v. Löwis2001-08-161-38/+19
|
* Merge of descr-branch back into trunk.Tim Peters2001-08-021-20/+138
|
* SF bug #439104: Tuple richcompares has code-typo.Tim Peters2001-07-061-1/+1
| | | | | | Symptom: (1, 2, 3) <= (1, 2) returned 1. This was already fixed in CVS for tuples, but an isomorphic error was in the list richcompare code.
* SF bug 433228: repr(list) woes when len(list) big.Tim Peters2001-06-161-13/+55
| | | | | | | | | | | | Gave Python linear-time repr() implementations for dicts, lists, strings. This means, e.g., that repr(range(50000)) is no longer 50x slower than pprint.pprint() in 2.2 <wink>. I don't consider this a bugfix candidate, as it's a performance boost. Added _PyString_Join() to the internal string API. If we want that in the public API, fine, but then it requires runtime error checks instead of asserts.
* Change list.extend() error msgs and NEWS to reflect that list.extend()Tim Peters2001-05-261-2/+2
| | | | | | | now takes any iterable argument, not only sequences. NEEDS DOC CHANGES -- but I don't think we settled on a concise way to say this stuff.
* Cruft cleanup: removed the #ifdef'ery in support of compiling to allowTim Peters2001-05-261-18/+4
| | | | multi-argument list.append(1, 2, 3) (as opposed to .append((1,2,3))).
* roundupsize() and friends: fiddle over-allocation strategy for listTim Peters2001-05-261-8/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | resizing. Accurate timings are impossible on my Win98SE box, but this is obviously faster even on this box for reasonable list.append() cases. I give credit for this not to the resizing strategy but to getting rid of integer multiplication and divsion (in favor of shifting) when computing the rounded-up size. For unreasonable list.append() cases, Win98SE now displays linear behavior for one-at-time appends up to a list with about 35 million elements. Then it dies with a MemoryError, due to fatally fragmented *address space* (there's plenty of VM available, but by this point Win9X has broken user space into many distinct heaps none of which has enough contiguous space left to resize the list, and for whatever reason Win9x isn't coalescing the dead heaps). Before the patch it got a MemoryError for the same reason, but once the list reached about 2 million elements. Haven't yet tried on Win2K but have high hopes extreme list.append() will be much better behaved now (NT & Win2K didn't fragment address space, but suffered obvious quadratic-time behavior before as lists got large). For other systems I'm relying on common sense: replacing integer * and / by << and >> can't plausibly hurt, the number of function calls hasn't changed, and the total operation count for reasonably small lists is about the same (while the operations are cheaper now).
* Fix core dump whenever PyList_Reverse() was called.Guido van Rossum2001-02-121-11/+14
| | | | | | | | | | | This fixes SF bug #132008, reported by Warren J. Hack. The copyright for this patch (and this patch only) belongs to CNRI, as part of the (yet to be issued) 1.6.1 release. This is now checked into the HEAD branch. Tim will check in a test case to check for this specific bug, and an assertion in PyArgs_ParseTuple() to catch similar bugs in the future.
* Convert to rich comparisons:Guido van Rossum2001-01-171-90/+163
| | | | | | | | | | | | | | | | - sort's docompare() calls RichCompare(Py_LT). - list_contains(), list_index(), listcount(), listremove() call RichCompare(Py_EQ). - Get rid of list_compare(), in favor of new list_richcompare(). The latter does some nice shortcuts, like when == or != is requested, it first compares the lengths for trivial accept/reject. Then it goes over the items until it finds an index where the items differe; then it does more shortcut magic to minimize the number of additional comparisons. - Aligned the comments for large struct initializers.
* fix leakJeremy Hylton2001-01-031-1/+3
|
* Use METH_VARARGS instead of "1" in list method table.Tim Peters2000-12-131-9/+9
|
* Rationalize use of limits.h, moving the inclusion to Python.h.Fred Drake2000-09-261-3/+0
| | | | | | | | Add definitions of INT_MAX and LONG_MAX to pyport.h. Remove includes of limits.h and conditional definitions of INT_MAX and LONG_MAX elsewhere. This closes SourceForge patch #101659 and bug #115323.
* REMOVED all CWI, CNRI and BeOpen copyright markings.Guido van Rossum2000-09-011-9/+0
| | | | This should match the situation in the 1.6b1 tree.
* Support for the in-place operations introduced by augmented assignment. OnlyThomas Wouters2000-08-241-18/+88
| | | | | the list object supports this currently, but other candidates are gladly accepted (like arraymodule and such.)
* Added include for limits.hJack Jansen2000-08-221-0/+4
|
generated by cgit v0.12 at 2024-10-20 19:09:41 (GMT)