summaryrefslogtreecommitdiffstats
path: root/Objects/setobject.c
Commit message (Collapse)AuthorAgeFilesLines
* Fix typo in comment.Eric V. Smith2014-01-141-1/+1
|
* Add comments to frozenset_hash().Raymond Hettinger2014-01-051-1/+14
| | | | Also, provide a minor hint to the compiler on how to group the xors.
* Minor code clean-up. Keep the C-API all in one section.Raymond Hettinger2013-12-151-3/+3
|
* Note that LINEAR_PROBES can be set to zero.Raymond Hettinger2013-09-221-1/+1
|
* Minor beautification. Put updates and declarations in a more logical order.Raymond Hettinger2013-09-211-2/+2
|
* When LINEAR_PROBES=0, let the compiler remove the dead code on its own.Raymond Hettinger2013-09-211-12/+0
|
* Make the linear probe sequence clearer.Raymond Hettinger2013-09-211-8/+4
|
* Issue 18771: Make it possible to set the number linear probes at compile-time.Raymond Hettinger2013-09-151-5/+19
|
* Put the defines in the logical section and fix indentation.Raymond Hettinger2013-09-081-8/+8
|
* Minor code beautification.Raymond Hettinger2013-09-081-6/+5
|
* Improve code clarity by removing two unattractive macros.Raymond Hettinger2013-09-081-16/+18
|
* Remove the freelist scheme for setobjects.Raymond Hettinger2013-09-081-47/+8
| | | | | | | | | The setobject freelist was consuming memory but not providing much value. Even when a freelisted setobject was available, most of the setobject fields still needed to be initialized and the small table still required a memset(). This meant that the custom freelisting scheme for sets was providing almost no incremental benefit over the default Python freelist scheme used by _PyObject_Malloc() in Objects/obmalloc.c.
* Small rearrangement to bring together the three functions for probing the ↵Raymond Hettinger2013-09-081-32/+39
| | | | hash table.
* Move the overview comment to the top of the file.Raymond Hettinger2013-09-071-22/+20
|
* Minor touchups.Raymond Hettinger2013-09-021-4/+6
|
* Factor-out the common code for setting a KeyError.Raymond Hettinger2013-09-021-15/+1
|
* Instead of XORed indicies, switch to a hybrid of linear probing and open ↵Raymond Hettinger2013-09-021-91/+68
| | | | | | | | | | | | | | | addressing. Modern processors tend to make consecutive memory accesses cheaper than random probes into memory. Small sets can fit into L1 cache, so they get less benefit. But they do come out ahead because the consecutive probes don't probe the same key more than once and because the randomization step occurs less frequently (or not at all). For the open addressing step, putting the perturb shift before the index calculation gets the upper bits into play sooner.
* Update copyright.Raymond Hettinger2013-09-011-1/+1
|
* Further reduce the cost of hash collisions by inspecting an additional ↵Raymond Hettinger2013-09-011-4/+39
| | | | nearby entry.
* Tighten-up the lookkey() logic and beautify the code a bit.Raymond Hettinger2013-08-291-88/+43
| | | | | | | Use less code by moving many of the steps from the initial lookup into the main search loop. Beautify the code but keep the overall logic unchanged.
* Issue #18772: fix the gdb plugin after the set implementation changesAntoine Pitrou2013-08-241-8/+2
|
* Add the same dummy type that is used in dictionaries.Raymond Hettinger2013-08-231-15/+49
|
* Issue 18797: Remove unneeded refcount adjustments for dummy objects.Raymond Hettinger2013-08-221-16/+6
| | | | It suffices to keep just one reference when the object is created.
* Hoist the global dummy lookup out of the inner loop for set_merge().Raymond Hettinger2013-08-211-1/+3
|
* Remove a redundant hash table probe (this was artifact from an earlier draft ↵Raymond Hettinger2013-08-211-11/+0
| | | | of the patch).
* Issue 18772: Restore set dummy object back to unicode and restore the ↵Raymond Hettinger2013-08-211-4/+4
| | | | | | | | | | | | | identity checks in lookkey(). The Gdb prettyprint plugin depended on the dummy object being displayable. Other solutions besides a unicode object are possible. For now, get it back up and running. The identity checks in lookkey() need to be there to prevent the dummy object from leaking through Py_RichCompareBool() into user code in the rare circumstance where the dummy's hash value exactly matches the hash value of the actual key being looked up.
* Issue18771: Reduce the cost of hash collisions for set objects.Raymond Hettinger2013-08-191-20/+86
|
* Remove the else-clause because the conditions are no longer mutually exclusive.Raymond Hettinger2013-08-171-1/+1
|
* Use a known unique object for the dummy entry.Raymond Hettinger2013-08-171-25/+20
| | | | | This lets us run PyObject_RichCompareBool() without first needing to check whether the entry is a dummy.
* Hoist the global "dummy" lookup outside of the reinsertion loop.Raymond Hettinger2013-08-151-1/+3
|
* Issue #18722: Remove uses of the "register" keyword in C code.Antoine Pitrou2013-08-131-37/+37
|
* Replace outdated optimization with clearer code that compiles better.Raymond Hettinger2013-08-061-3/+3
| | | | | | | | | | | | | | | | | | | | | Letting the compiler decide how to optimize the multiply by five gives it the freedom to make better choices for the best technique for a given target machine. For example, GCC on x86_64 produces a little bit better code: Old-way (3 steps with a data dependency between each step): shrq $5, %r13 leaq 1(%rbx,%r13), %rax leaq (%rax,%rbx,4), %rbx New-way (3 steps with no dependency between the first two steps which can be run in parallel): leaq (%rbx,%rbx,4), %rax # i*5 shrq $5, %r13 # perturb >>= PERTURB_SHIFT leaq 1(%r13,%rax), %rbx # 1 + perturb + i*5
* Fix compilation warning with gcc 4.8 (unused typedef)Antoine Pitrou2013-06-181-1/+0
|
* Fix the internals of our hash functions to used unsigned values during hashGregory P. Smith2012-12-111-6/+6
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | computation as the overflow behavior of signed integers is undefined. NOTE: This change is smaller compared to 3.2 as much of this cleanup had already been done. I added the comment that my change in 3.2 added so that the code would match up. Otherwise this just adds or synchronizes appropriate UL designations on some constants to be pedantic. In practice we require compiling everything with -fwrapv which forces overflow to be defined as twos compliment but this keeps the code cleaner for checkers or in the case where someone has compiled it without -fwrapv or their compiler's equivalent. Found by Clang trunk's Undefined Behavior Sanitizer (UBSan). Cleanup only - no functionality or hash values change.
| * Fix the internals of our hash functions to used unsigned values during hashGregory P. Smith2012-12-111-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | computation as the overflow behavior of signed integers is undefined. In practice we require compiling everything with -fwrapv which forces overflow to be defined as twos compliment but this keeps the code cleaner for checkers or in the case where someone has compiled it without -fwrapv or their compiler's equivalent. Found by Clang trunk's Undefined Behavior Sanitizer (UBSan). Cleanup only - no functionality or hash values change.
* | Fix typo.Ezio Melotti2012-09-281-2/+2
| |
* | Issue #14785: Add sys._debugmallocstats() to help debug low-level memory ↵David Malcolm2012-06-221-0/+10
| | | | | | | | allocation issues
* | Rename _PyIter_GetBuiltin to _PyObject_GetBuiltin, and do not include it in ↵Antoine Pitrou2012-04-041-1/+1
| | | | | | | | the stable ABI.
* | Issue #14288: Serialization support for builtin iterators.Kristján Valur Jónsson2012-04-031-2/+43
| |
* | Issue #6695: Full garbage collection runs now clear the freelist of set objects.Antoine Pitrou2011-12-161-2/+10
| | | | | | | | Initial patch by Matthias Troffaes.
* | merge 3.2Benjamin Peterson2011-10-301-1/+1
|\ \ | |/
| * remove unused variableBenjamin Peterson2011-10-301-1/+1
| |
* | Fix the return value of set_discard (issue #10519)Petri Lehtinen2011-10-301-2/+3
|\ \ | |/
| * Fix the return value of set_discard (issue #10519)Petri Lehtinen2011-10-301-2/+3
| |
* | Avoid unnecessary recursive function calls (#closes #10519)Petri Lehtinen2011-10-301-2/+2
|\ \ | |/
| * Avoid unnecessary recursive function calls (closes #10519)Petri Lehtinen2011-10-301-2/+2
| |
* | Rename _Py_identifier to _Py_IDENTIFIER.Martin v. Löwis2011-10-141-1/+1
| |
* | Use identifier API for PyObject_GetAttrString.Martin v. Löwis2011-10-101-1/+2
| |
* | Implement PEP 393.Martin v. Löwis2011-09-281-25/+15
| |
* | Issue #1621: Fix undefined behaviour in bytes.__hash__, str.__hash__, ↵Mark Dickinson2011-09-241-10/+10
| | | | | | | | tuple.__hash__, frozenset.__hash__ and set indexing operations.
generated by cgit v0.12 at 2024-11-26 17:11:44 (GMT)