summaryrefslogtreecommitdiffstats
path: root/Objects/dictobject.c
Commit message (Collapse)AuthorAgeFilesLines
* Make the new dictionary iterators transparent with respect to length.Raymond Hettinger2004-03-181-4/+20
| | | | | | This gives another 30% speedup for operations such as map(func, d.iteritems()) or list(d.iteritems()) which can both take advantage of length information when provided.
* Optimize dictionary iterators.Raymond Hettinger2004-03-181-57/+202
| | | | | | | | | | | | | | | | | | * Split into three separate types that share everything except the code for iternext. Saves run time decision making and allows each iternext function to be specialized. * Inlined PyDict_Next(). In addition to saving a function call, this allows a redundant test to be eliminated and further specialization of the code for the unique needs of each iterator type. * Created a reusable result tuple for iteritems(). Saves the malloc time for tuples when the previous result was not kept by client code (this is the typical use case for iteritems). If the client code does keep the reference, then a new tuple is created. Results in a 20% to 30% speedup depending on the size and sparsity of the dictionary.
* Dictionary optimizations:Raymond Hettinger2004-03-171-24/+61
| | | | | | | | | | | | * Factored constant structure references out of the inner loops for PyDict_Next(), dict_keys(), dict_values(), and dict_items(). Gave measurable speedups to each (the improvement varies depending on the sparseness of the dictionary being measured). * Added a freelist scheme styled after that for tuples. Saves around 80% of the calls to malloc and free. About 10% of the time, the previous dictionary was completely empty; in those cases, the dictionary initialization with memset() can be skipped.
* Factor out code common to PyDict_Copy() and PyDict_Merge().Raymond Hettinger2004-03-081-20/+6
|
* SF #904720: dict.update should take a 2-tuple sequence like dict.__init_Raymond Hettinger2004-03-041-18/+24
| | | | | | | | (Championed by Bob Ippolito.) The update() method for mappings now accepts all the same argument forms as the dict() constructor. This includes item lists and/or keyword arguments.
* Oops. Return -1 to distinguish error from empty dict.Jeremy Hylton2004-02-171-1/+1
| | | | | This change probably isn't work a bug fix. It's unlikely that anyone was calling this method without passing it a real dict.
* Simplify previous checkin -- a new function was not needed.Raymond Hettinger2003-12-131-26/+1
|
* * Added a new method flag, METH_COEXIST.Raymond Hettinger2003-12-131-0/+34
| | | | | * Used the flag to optimize set.__contains__(), dict.__contains__(), dict.__getitem__(), and list.__getitem__().
* Expose dict_contains() and PyDict_Contains() with is about 10% fasterRaymond Hettinger2003-11-251-3/+4
| | | | | | | than PySequence_Contains() and more clearly applicable to dicts. Apply the new function in setobject.c where __contains__ checking is ubiquitous.
* SF patch #798467: Update docstring of has_key for bool changesRaymond Hettinger2003-09-011-1/+1
| | | | (Contributed by George Yoshida.)
* SF patch #729395: Dictionary tuningRaymond Hettinger2003-05-071-2/+2
| | | | | Adjust resize argument for dict.update() and dict.copy(). Extends the previous change to dict.__setitem__().
* SF patch #729395: Dictionary tuningRaymond Hettinger2003-05-051-10/+16
| | | | | | | | | | * Increase dictionary growth rate resulting in more sparse dictionaries, fewer lookup collisions, increased memory use, and better cache performance. For dicts with over 50k entries, keep the current growth rate in case an application is suffering from tight memory constraints. * Set the most common case (no resize) to fall-through the test.
* Add a reference to dictnotes.txt. It does no good if you don't know it'sRaymond Hettinger2003-05-031-0/+6
| | | | there or where to find it.
* 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-8/+1
| | | | Factors out the common case of returning self.
* SF patch #693753: fix for bug 639806: default for dict.popRaymond Hettinger2003-03-061-3/+15
| | | | (contributed by Michael Stone.)
* Add closing ) in commentNeal Norwitz2003-02-151-1/+1
|
* cPickle.c, load_build(): Taught cPickle how to pick apartTim Peters2003-02-151-1/+11
| | | | | | | | | | | | | | | | | | the optional proto 2 slot state. pickle.py, load_build(): CAUTION: Noted that cPickle's load_build and pickle's load_build really don't do the same things with the state, and didn't before this patch either. cPickle never tries to do .update(), and has no backoff if instance.__dict__ can't be retrieved. There are no tests that can tell the difference, and part of what cPickle's load_build() did looked accidental to me, so I don't know what the true intent is here. pickletester.py, test_pickle.py: Got rid of the hack for exempting cPickle from running some of the proto 2 tests. dictobject.c, PyDict_Next(): documented intended use.
* SF patch #659536: Use PyArg_UnpackTuple where possible.Raymond Hettinger2002-12-291-4/+4
| | | | | | | 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.
* Constify char* API. Fixes #651363. 2.2 candidate.Martin v. Löwis2002-12-111-3/+3
|
* SF 548651: Fix the METH_CLASS implementation.Tim Peters2002-12-091-3/+2
| | | | | | | Most of these patches are from Thomas Heller, with long lines folded by Tim. The change to test_descr.py is from Guido. See the bug report. Not a bugfix candidate -- METH_CLASS is new in 2.3.
* Remove assumption that cls is a subclass of dict.Raymond Hettinger2002-12-071-7/+1
| | | | Simplifies the code and gets Just van Rossum's example to work.
* Replace BadInternalCall with TypeError. Add a test case. Fix whitespace.Raymond Hettinger2002-12-041-2/+3
| | | | | | | Just van Rossum showed a weird, but clever way for pure python code to trigger the BadInternalCall. The C code had assumed that calling a class constructor would return an instance of that class; however, classes that abuse __new__ can invalidate that assumption.
* Add missing decrefNeal Norwitz2002-11-271-0/+1
|
* SF Patch 643443. Added dict.fromkeys(iterable, value=None), a classRaymond Hettinger2002-11-271-0/+56
| | | | method for constructing new dictionaries from sequences of keys.
* Patch #642500 with slight modifications: allow keyword arguments inJust van Rossum2002-11-231-5/+7
| | | | | | | dict() constructor. Example: >>> dict(a=1, b=2) {'a': 1, 'b': 2} >>>
* In doc strings, use 'k in D' rather than D.has_key(k).Guido van Rossum2002-09-041-2/+2
|
* SF patch 576101, by Oren Tirosh: alternative implementation ofGuido van Rossum2002-08-191-9/+3
| | | | | | | | interning. I modified Oren's patch significantly, but the basic idea and most of the implementation is unchanged. Interned strings created with PyString_InternInPlace() are now mortal, and you must keep a reference to the resulting string around; use the new function PyString_InternImmortal() to create immortal interned strings.
* 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.
* Make StopIteration a sink state. This is done by clearing out theGuido van Rossum2002-07-161-28/+11
| | | | | | | | | | di_dict field when the end of the list is reached. Also make the error ("dictionary changed size during iteration") a sticky state. 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).
* Patch #568124: Add doc string macros.Martin v. Löwis2002-06-131-30/+30
|
* Add Raymond Hettinger's d.pop(). See SF patch 539949.Guido van Rossum2002-04-121-0/+38
|
* PyObject_GC_Del and PyObject_Del can now be used as a functionNeil Schemenauer2002-04-121-3/+3
| | | | | | designators. Remove PyMalloc_New.
* Add the 'bool' type and its values 'False' and 'True', as described inGuido van Rossum2002-04-031-1/+1
| | | | | | | | | | | | | PEP 285. Everything described in the PEP is here, and there is even some documentation. I had to fix 12 unit tests; all but one of these were printing Boolean outcomes that changed from 0/1 to False/True. (The exception is test_unicode.py, which did a type(x) == type(y) style comparison. I could've fixed that with a single line using issubtype(x, type(y)), but instead chose to be explicit about those places where a bool is expected. Still to do: perhaps more documentation; change standard library modules to return False/True from predicates.
* Remove the CACHE_HASH and INTERN_STRINGS preprocessor symbols.Tim Peters2002-03-291-34/+8
|
* 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!
* Use pymalloc if it's enabled.Neil Schemenauer2002-03-221-2/+2
|
* SF bug #491415 PyDict_UpdateFromSeq2() unusedTim Peters2001-12-111-8/+2
| | | | | | | PyDict_UpdateFromSeq2(): removed it. PyDict_MergeFromSeq2(): made it public and documented it. PyDict_Merge() docs: updated to reveal <wink> that the second argument can be any mapping object.
* Fix of SF bug #475877 (Mutable subtype instances are hashable).Guido van Rossum2001-12-031-1/+8
| | | | | | | | | | | | | | | | | 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.
* Rename "dictionary" (type and constructor) to "dict".Tim Peters2001-10-291-5/+5
|
* dictionary() constructor:Tim Peters2001-10-271-7/+5
| | | | | | + Change keyword arg name from "x" to "items". People passing a mapping object can stretch their imaginations <wink>. + Simplify the docstring text.
* Generalize dictionary() to accept a sequence of 2-sequences. At theTim Peters2001-10-261-16/+102
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | outer level, the iterator protocol is used for memory-efficiency (the outer sequence may be very large if fully materialized); at the inner level, PySequence_Fast() is used for time-efficiency (these should always be sequences of length 2). dictobject.c, new functions PyDict_{Merge,Update}FromSeq2. These are wholly analogous to PyDict_{Merge,Update}, but process a sequence-of-2- sequences argument instead of a mapping object. For now, I left these functions file static, so no corresponding doc changes. It's tempting to change dict.update() to allow a sequence-of-2-seqs argument too. Also changed the name of dictionary's keyword argument from "mapping" to "x". Got a better name? "mapping_or_sequence_of_pairs" isn't attractive, although more so than "mosop" <wink>. abstract.h, abstract.tex: Added new PySequence_Fast_GET_SIZE function, much faster than going thru the all-purpose PySequence_Size. libfuncs.tex: - Document dictionary(). - Fiddle tuple() and list() to admit that their argument is optional. - The long-winded repetitions of "a sequence, a container that supports iteration, or an iterator object" is getting to be a PITA. Many months ago I suggested factoring this out into "iterable object", where the definition of that could include being explicit about generators too (as is, I'm not sure a reader outside of PythonLabs could guess that "an iterator object" includes a generator call). - Please check my curly braces -- I'm going blind <0.9 wink>. abstract.c, PySequence_Tuple(): When PyObject_GetIter() fails, leave its error msg alone now (the msg it produces has improved since PySequence_Tuple was generalized to accept iterable objects, and PySequence_Tuple was also stomping on the msg in cases it shouldn't have even before PyObject_GetIter grew a better msg).
* 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.
* Changed the dict implementation to take "string shortcuts" only whenTim Peters2001-09-141-13/+16
| | | | | | | | | | | | | | | | keys are true strings -- no subclasses need apply. This may be debatable. The problem is that a str subclass may very well want to override __eq__ and/or __hash__ (see the new example of case-insensitive strings in test_descr), but go-fast shortcuts for strings are ubiquitous in our dicts (and subclass overrides aren't even looked for then). Another go-fast reason for the change is that PyCheck_StringExact() is a quicker test than PyCheck_String(), and we make such a test on virtually every access to every dict. OTOH, a str subclass may also be perfectly happy using the base str eq and hash, and this change slows them a lot. But those cases are still hypothetical, while Python's own reliance on true-string dicts is not.
* Repair typo in comment.Tim Peters2001-09-021-1/+1
|
* Make dictionary() a real constructor. Accepts at most one argument, "aTim Peters2001-09-021-2/+29
| | | | | | | | | | | | mapping object", in the same sense dict.update(x) requires of x (that x has a keys() method and a getitem). Questionable: The other type constructors accept a keyword argument, so I did that here too (e.g., dictionary(mapping={1:2}) works). But type_call doesn't pass the keyword args to the tp_new slot (it passes NULL), it only passes them to the tp_init slot, so getting at them required adding a tp_init slot to dicts. Looks like that makes the normal case (i.e., no args at all) a little slower (the time it takes to call dict.tp_init and have it figure out there's nothing to do).
* Use new GC API.Neil Schemenauer2001-08-291-7/+6
|
* Patch #427190: Implement and use METH_NOARGS and METH_O.Martin v. Löwis2001-08-161-50/+25
|
* Add PyDict_Merge(a, b, override):Guido van Rossum2001-08-101-2/+18
| | | | | | PyDict_Merge(a, b, 1) is the same as PyDict_Update(a, b). PyDict_Merge(a, b, 0) does something similar but leaves existing items unchanged.
* Merge of descr-branch back into trunk.Tim Peters2001-08-021-123/+107
|