summaryrefslogtreecommitdiffstats
path: root/Objects/listobject.c
Commit message (Collapse)AuthorAgeFilesLines
* Optimize inner loops for subscript, repeat, and concat.Raymond Hettinger2004-03-091-27/+39
|
* Optimize slice assignments.Raymond Hettinger2004-03-091-16/+17
| | | | | | | | | | | | | * Replace sprintf message with a constant message string -- this error message ran on every invocation except straight deletions but it was only needed when the rhs was not iterable. The message was also out-of-date and did not reflect that iterable arguments were allowed. * For inner loops that do not make ref count adjustments, use memmove() for fast copying and better readability. * For inner loops that do make ref count adjustments, speed them up by factoring out the constant structure reference and using vitem[] instead.
* Optimize tuple_slice() and make further improvements to list_slice()Raymond Hettinger2004-03-081-14/+16
| | | | | | and list.extend(). Factoring the inner loops to remove the constant structure references and fixed offsets gives speedups ranging from 20% to 30%.
* Small optimizations for list_slice() and list_extend_internal().Raymond Hettinger2004-03-081-9/+20
| | | | | | | | * Using addition instead of substraction on array indices allows the compiler to use a fast addressing mode. Saves about 10%. * Using PyTuple_GET_ITEM and PyList_SET_ITEM is about 7% faster than PySequenceFast_GET_ITEM which has to make a list check on every pass.
* Keep the list.pop() optimization while restoring the many possibilityRaymond Hettinger2004-02-191-4/+2
| | | | | for types other than PyInt being accepted for the optional argument. (Spotted by Neal Norwitz.)
* Double the speed of list.pop() which was spending most of its time parsingRaymond Hettinger2004-02-171-2/+11
| | | | arguments.
* Refactor list_extend() and list_fill() for gains in code size, memoryRaymond Hettinger2004-02-151-84/+71
| | | | | | | | | | | | | | | | | | | | | | | | utilization, and speed: * Moved the responsibility for emptying the previous list from list_fill to list_init. * Replaced the code in list_extend with the superior code from list_fill. * Eliminated list_fill. Results: * list.extend() no longer creates an intermediate tuple except to handle the special case of x.extend(x). The saves memory and time. * list.extend(x) runs 5 to 10% faster when x is a list or tuple 15% faster when x is an iterable not defining __len__ twice as fast when x is an iterable defining __len__ * the code is about 15 lines shorter and no longer duplicates functionality.
* Fine tune the speed/space trade-off for overallocating small lists.Raymond Hettinger2004-02-141-8/+3
| | | | | | | | | | | | | | The Py2.3 approach overallocated small lists by up to 8 elements. The last checkin would limited this to one but slowed down (by 20 to 30%) the creation of small lists between 3 to 8 elements. This tune-up balances the two, limiting overallocation to 3 elements (significantly reducing space consumption from Py2.3) and running faster than the previous checkin. The first part of the growth pattern (0, 4, 8, 16) neatly meshes with allocators that trigger data movement only when crossing a power of two boundary. Also, then even numbers mesh well with common data alignments.
* Fix missing return value. Spotted by Neal NorwitzRaymond Hettinger2004-02-141-0/+1
|
* Optimize list.pop() for the common special case of popping off the end.Raymond Hettinger2004-02-131-0/+5
| | | | More than doubles its speed.
* * Optimized list appends and pops by making fewer calls the underlying systemRaymond Hettinger2004-02-131-89/+68
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | realloc(). This is achieved by tracking the overallocation size in a new field and using that information to skip calls to realloc() whenever possible. * Simplified and tightened the amount of overallocation. For larger lists, this overallocates by 1/8th (compared to the previous scheme which ranged between 1/4th to 1/32nd over-allocation). For smaller lists (n<6), the maximum overallocation is one byte (formerly it could be upto eight bytes). This saves memory in applications with large numbers of small lists. * Eliminated the NRESIZE macro in favor of a new, static list_resize function that encapsulates the resizing logic. Coverting this back to macro would give a small (under 1%) speed-up. This was too small to warrant the loss of readability, maintainability, and de-coupling. * Some functions using NRESIZE had grown unnecessarily complex in their efforts to bend to the macro's calling pattern. With the new list_resize function in place, those other functions could be simplified. That is being saved for a separate patch. * The ob_item==NULL check could be eliminated from the new list_resize function. This would entail finding each piece of code that sets ob_item to NULL and adding a new line to invalidate the overallocation tracking field. Rather than impose a new requirement on other pieces of list code, it was preferred to leave the NULL check in place and retain the benefits of decoupling, maintainability and information hiding (only PyList_New() and list_sort() need to know about the new field). This approach also reduces the odds of breaking an extension module. (Collaborative effort by Raymond Hettinger, Hye-Shik Chang, Tim Peters, and Armin Rigo.)
* Revert change accidentally checked in as part of a whitespace normalizationTim Peters2004-01-181-9/+5
| | | | patch.
* Whitespace normalization.Tim Peters2004-01-181-5/+9
|
* Apply tuple/list pre-sizing optimization to a broader class of objects.Raymond Hettinger2004-01-041-8/+4
| | | | | | | | Formerly, length data fetched from sequence objects. Now, any object that reports its length can benefit from pre-sizing. On one sample timing, it gave a threefold speedup for list(s) where s was a set object.
* complete backout of listobject.c v2.171Andrew MacIntyre2003-12-281-4/+0
|
* Revert previous two checkins to repair test failure.Jeremy Hylton2003-12-261-24/+6
| | | | | | The special-case code that was removed could return a value indicating success but leave an exception set. test_fileinput failed in a debug build as a result.
* use the correct macro to access list sizeAndrew MacIntyre2003-12-261-1/+1
|
* Performance of list([]) in 2.3 came up in a thread on comp.lang.python,Andrew MacIntyre2003-12-251-6/+28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | which can be reviewed via http://coding.derkeiler.com/Archive/Python/comp.lang.python/2003-12/1011.html Duncan Booth investigated, and discovered that an "optimisation" was in fact a pessimisation for small numbers of elements in a source list, compared to not having the optimisation, although with large numbers of elements in the source list the optimisation was quite beneficial. He posted his change to comp.lang.python (but not to SF). Further research has confirmed his assessment that the optimisation only becomes a net win when the source list has more than 100 elements. I also found that the optimisation could apply to tuples as well, but the gains only arrive with source tuples larger than about 320 elements and are nowhere near as significant as the gains with lists, (~95% gain @ 10000 elements for lists, ~20% gain @ 10000 elements for tuples) so I haven't proceeded with this. The code as it was applied the optimisation to list subclasses as well, and this also appears to be a net loss for all reasonable sized sources (~80-100% for up to 100 elements, ~20% for more than 500 elements; I tested up to 10000 elements). Duncan also suggested special casing empty lists, which I've extended to all empty sequences. On the basis that list_fill() is only ever called with a list for the result argument, testing for the source being the destination has now happens before testing source types.
* Guido grants a Christmas wish:Raymond Hettinger2003-12-171-37/+0
| | | | sorted() becomes a regular function instead of a classmethod.
* * Added a new method flag, METH_COEXIST.Raymond Hettinger2003-12-131-0/+5
| | | | | * Used the flag to optimize set.__contains__(), dict.__contains__(), dict.__getitem__(), and list.__getitem__().
* Fix memory error treatment correctly. Going to dsu_fail causesHye-Shik Chang2003-12-101-1/+1
| | | | | deallocating garbage pointers; saved_ob_item and empty_ob_item. (Reviewed by Raymond Hettinger)
* Fixes and tests for various "holding pointers when arbitrary Python codeMichael W. Hudson2003-12-041-35/+46
| | | | | | can run" bugs as discussed in [ 848856 ] couple of new list.sort bugs
* Make sure the list.sort's decorate step unwinds itself before returningRaymond Hettinger2003-11-281-2/+9
| | | | | an exception raised by the key function. (Suggested by Michael Hudson.)
* Improve the reverse list iterator to free memory as soon as the iteratorRaymond Hettinger2003-11-081-1/+4
| | | | is exhausted.
* Minor code fixup. Make sure that len reflects the current list size.Raymond Hettinger2003-11-081-0/+1
|
* Optimize reversed(list) using a custom iterator.Raymond Hettinger2003-11-071-2/+96
|
* Fix compiler warning about possible use of n without assignment.Jeremy Hylton2003-11-031-5/+6
| | | | Also fix use of n for two different variables in two different blocks.
* Add list.sorted() classmethod.Raymond Hettinger2003-10-291-0/+37
|
* Fix typo found by Neal Norwitz.Raymond Hettinger2003-10-161-1/+1
|
* * list.sort() now supports three keyword arguments: cmp, key, and reverse.Raymond Hettinger2003-10-161-5/+228
| | | | | | | key provides C support for the decorate-sort-undecorate pattern. reverse provide a stable sort of the list with the comparisions reversed. * Amended the docs to guarantee sort stability.
* My last fix left n used unitialized in tha a==b case.Michael W. Hudson2003-08-151-1/+1
| | | | | | Fix, by not using n at all in that case. Needs to be applied to release23-maint, too.
* Fix reference leak noted in test_types:Michael W. Hudson2003-08-141-9/+9
| | | | | | Check for a[:] = a _before_ calling PySequence_Fast on a. release23-maint candidate Reference leak doesn't happen with head of release22-maint.
* Use _PyEval_SliceIndex to handle list.index() calls withWalter Dörwald2003-06-171-1/+3
| | | | huge start and stop arguments. Add tests.
* Fix sloppy index() implementation:Guido van Rossum2003-06-171-2/+12
| | | | | - don't use min() and max() - interpret negative start/stop argument like negative slice indices
* SF #754014: list.index() should accept optional start, end argumentsRaymond Hettinger2003-06-171-5/+10
| | | | Also, modified UserList.index() to match and expanded the related tests.
* SF bug #604716: faster [None]*n or []*nRaymond Hettinger2003-05-211-0/+12
| | | | Fulfilled request to special case repetitions of lists of length 0 or 1.
* SF bug #730296: Unexpected Changes in list IteratorRaymond Hettinger2003-05-071-2/+0
| | | | | | | | | | | | Reverted a Py2.3b1 change to iterator in subclasses of list and tuple. They had been changed to use __getitem__ whenever it had been overriden in the subclass. This caused some usabilty and performance problems. Also, it was inconsistent with the rest of python where many container methods access the underlying object directly without first checking for an overridden getter. Users needing a change in iterator behavior should override it directly.
* Patch #708604: Check more function results. Will backport to 2.2.Martin v. Löwis2003-05-031-1/+8
|
* Squashed new compiler wngs about trying to compare pointers toTim Peters2003-04-241-1/+1
| | | | functions with different signatures.
* SF bug 665835: filter() treatment of str and tuple inconsistentRaymond Hettinger2003-04-241-0/+2
| | | | | | | | As a side issue on this bug, it was noted that list and tuple iterators used macros to directly access containers and would not recognize __getitem__ overrides. If the method is overridden, the patch returns a generic sequence iterator which calls the __getitem__ method; otherwise, it returns a high custom iterator with direct access to container elements.
* - list.insert(i, x) now interprets negative i as it would beGuido van Rossum2003-04-141-2/+5
| | | | | | interpreted by slicing, so negative values count from the end of the list. This was the only place where such an interpretation was not placed on a list index.
* Renamed PyObject_GenericGetIter to PyObject_SelfIterRaymond Hettinger2003-03-171-1/+1
| | | | | | to more accurately describe what the function does. Suggested by Thomas Wouters.
* Created PyObject_GenericGetIter().Raymond Hettinger2003-03-171-9/+1
| | | | Factors out the common case of returning self.
* Allow list sort's comparison function to explicitly be None. See SF patchSkip Montanaro2003-01-021-1/+4
| | | | 661092.
* SF patch #659536: Use PyArg_UnpackTuple where possible.Raymond Hettinger2002-12-291-1/+1
| | | | | | | Obtain cleaner coding and a system wide performance boost by using the fast, pre-parsed PyArg_Unpack function instead of PyArg_ParseTuple function which is driven by a format string.
* SF Bug 645777: list.extend() works with any iterable and is no longerRaymond Hettinger2002-12-291-1/+1
| | | | experimental.
* The final tweaks before closingMichael W. Hudson2002-12-051-20/+23
| | | | | | [ 633152 ] list slice ass ignores subtypes of list Allow arbitrary sequences on the RHS of extended slices.
* SF patch 637176: list.sort crasherTim Peters2002-11-121-96/+29
| | | | | | | | | | | Armin Rigo's Draconian but effective fix for SF bug 453523: list.sort crasher slightly fiddled to catch more cases of list mutation. The dreaded internal "immutable list type" is gone! OTOH, if you look at a list *while* it's being sorted now, it will appear to be empty. Better than a core dump.
* Use PyOS_snprintf() instead of sprintf and wrap the long lineNeal Norwitz2002-11-051-2/+4
|
* This is Alex Martelli's patchMichael W. Hudson2002-11-051-9/+12
| | | | | | [ 633870 ] allow any seq assignment to a list slice plus a very silly little test case of my own.
generated by cgit v0.12 at 2024-12-04 09:01:11 (GMT)