diff options
| -rw-r--r-- | Include/patchlevel.h | 8 | ||||
| -rw-r--r-- | Lib/collections/__init__.py | 12 | ||||
| -rw-r--r-- | Lib/test/test_collections.py | 7 | ||||
| -rw-r--r-- | Lib/test/test_dictviews.py | 22 | ||||
| -rw-r--r-- | Misc/NEWS | 15 | ||||
| -rw-r--r-- | Objects/setobject.c | 145 |
6 files changed, 162 insertions, 47 deletions
diff --git a/Include/patchlevel.h b/Include/patchlevel.h index b5cac68813..246eba8c97 100644 --- a/Include/patchlevel.h +++ b/Include/patchlevel.h @@ -17,13 +17,13 @@ /* Version parsed out into numeric values */ /*--start constants--*/ #define PY_MAJOR_VERSION 3 -#define PY_MINOR_VERSION 5 +#define PY_MINOR_VERSION 6 #define PY_MICRO_VERSION 0 -#define PY_RELEASE_LEVEL PY_RELEASE_LEVEL_BETA -#define PY_RELEASE_SERIAL 1 +#define PY_RELEASE_LEVEL PY_RELEASE_LEVEL_ALPHA +#define PY_RELEASE_SERIAL 0 /* Version as a string */ -#define PY_VERSION "3.5.0b1+" +#define PY_VERSION "3.6.0a0" /*--end constants--*/ /* Version as a single 4-byte hex number, e.g. 0x010502B2 == 1.5.2b2. diff --git a/Lib/collections/__init__.py b/Lib/collections/__init__.py index fc60e13daa..9c22d86d79 100644 --- a/Lib/collections/__init__.py +++ b/Lib/collections/__init__.py @@ -736,14 +736,22 @@ class Counter(dict): def __pos__(self): 'Adds an empty counter, effectively stripping negative and zero counts' - return self + Counter() + result = Counter() + for elem, count in self.items(): + if count > 0: + result[elem] = count + return result def __neg__(self): '''Subtracts from an empty counter. Strips positive and zero counts, and flips the sign on negative counts. ''' - return Counter() - self + result = Counter() + for elem, count in self.items(): + if count < 0: + result[elem] = 0 - count + return result def _keep_positive(self): '''Internal method to strip elements with a negative or zero count''' diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py index ec86466779..ac7b9af2f4 100644 --- a/Lib/test/test_collections.py +++ b/Lib/test/test_collections.py @@ -1867,6 +1867,13 @@ class TestOrderedDict(unittest.TestCase): od = OrderedDict(**d) self.assertGreater(sys.getsizeof(od), sys.getsizeof(d)) + def test_views(self): + # See http://bugs.python.org/issue24286 + s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split() + od = OrderedDict.fromkeys(s) + self.assertEqual(od.keys(), dict(od).keys()) + self.assertEqual(od.items(), dict(od).items()) + def test_override_update(self): # Verify that subclasses can override update() without breaking __init__() class MyOD(OrderedDict): diff --git a/Lib/test/test_dictviews.py b/Lib/test/test_dictviews.py index 280353a3a2..d96832e576 100644 --- a/Lib/test/test_dictviews.py +++ b/Lib/test/test_dictviews.py @@ -1,3 +1,4 @@ +import collections import unittest class DictSetTest(unittest.TestCase): @@ -197,6 +198,27 @@ class DictSetTest(unittest.TestCase): d[42] = d.values() self.assertRaises(RuntimeError, repr, d) + def test_abc_registry(self): + d = dict(a=1) + + self.assertIsInstance(d.keys(), collections.KeysView) + self.assertIsInstance(d.keys(), collections.MappingView) + self.assertIsInstance(d.keys(), collections.Set) + self.assertIsInstance(d.keys(), collections.Sized) + self.assertIsInstance(d.keys(), collections.Iterable) + self.assertIsInstance(d.keys(), collections.Container) + + self.assertIsInstance(d.values(), collections.ValuesView) + self.assertIsInstance(d.values(), collections.MappingView) + self.assertIsInstance(d.values(), collections.Sized) + + self.assertIsInstance(d.items(), collections.ItemsView) + self.assertIsInstance(d.items(), collections.MappingView) + self.assertIsInstance(d.items(), collections.Set) + self.assertIsInstance(d.items(), collections.Sized) + self.assertIsInstance(d.items(), collections.Iterable) + self.assertIsInstance(d.items(), collections.Container) + if __name__ == "__main__": unittest.main() @@ -2,6 +2,18 @@ Python News +++++++++++ +What's New in Python 3.6.0 alpha 1? +=================================== + +Release date: XXXX-XX-XX + +Core and Builtins +----------------- + +Library +------- + + What's New in Python 3.5.0 beta 2? ================================== @@ -30,6 +42,9 @@ Core and Builtins - Issue #24268: PEP 489: Multi-phase extension module initialization. Patch by Petr Viktorin. +- Issue #23359: Optimize set object internals by specializing the + hash table search into a lookup function and an insert function. + - Issue #23955: Add pyvenv.cfg option to suppress registry/environment lookup for generating sys.path on Windows. diff --git a/Objects/setobject.c b/Objects/setobject.c index 1805debba1..e1aa4176ba 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -52,7 +52,6 @@ static setentry * set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) { setentry *table = so->table; - setentry *freeslot = NULL; setentry *entry; size_t perturb = hash; size_t mask = so->mask; @@ -86,14 +85,12 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) return entry; mask = so->mask; /* help avoid a register spill */ } - if (entry->hash == -1 && freeslot == NULL) - freeslot = entry; if (i + LINEAR_PROBES <= mask) { for (j = 0 ; j < LINEAR_PROBES ; j++) { entry++; - if (entry->key == NULL) - goto found_null; + if (entry->hash == 0 && entry->key == NULL) + return entry; if (entry->hash == hash) { PyObject *startkey = entry->key; assert(startkey != dummy); @@ -114,6 +111,89 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) return entry; mask = so->mask; } + } + } + + perturb >>= PERTURB_SHIFT; + i = (i * 5 + 1 + perturb) & mask; + + entry = &table[i]; + if (entry->hash == 0 && entry->key == NULL) + return entry; + } +} + +/* +Internal routine to insert a new key into the table. +Used by the public insert routine. +Eats a reference to key. +*/ +static int +set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) +{ + setentry *table = so->table; + setentry *freeslot = NULL; + setentry *entry; + size_t perturb = hash; + size_t mask = so->mask; + size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */ + size_t j; + int cmp; + + entry = &table[i]; + if (entry->key == NULL) + goto found_null; + + while (1) { + if (entry->hash == hash) { + PyObject *startkey = entry->key; + /* startkey cannot be a dummy because the dummy hash field is -1 */ + assert(startkey != dummy); + if (startkey == key) + goto found_active; + if (PyUnicode_CheckExact(startkey) + && PyUnicode_CheckExact(key) + && unicode_eq(startkey, key)) + goto found_active; + Py_INCREF(startkey); + cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) /* unlikely */ + return -1; + if (table != so->table || entry->key != startkey) /* unlikely */ + return set_insert_key(so, key, hash); + if (cmp > 0) /* likely */ + goto found_active; + mask = so->mask; /* help avoid a register spill */ + } + if (entry->hash == -1 && freeslot == NULL) + freeslot = entry; + + if (i + LINEAR_PROBES <= mask) { + for (j = 0 ; j < LINEAR_PROBES ; j++) { + entry++; + if (entry->hash == 0 && entry->key == NULL) + goto found_null; + if (entry->hash == hash) { + PyObject *startkey = entry->key; + assert(startkey != dummy); + if (startkey == key) + goto found_active; + if (PyUnicode_CheckExact(startkey) + && PyUnicode_CheckExact(key) + && unicode_eq(startkey, key)) + goto found_active; + Py_INCREF(startkey); + cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) + return -1; + if (table != so->table || entry->key != startkey) + return set_insert_key(so, key, hash); + if (cmp > 0) + goto found_active; + mask = so->mask; + } if (entry->hash == -1 && freeslot == NULL) freeslot = entry; } @@ -123,11 +203,26 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) i = (i * 5 + 1 + perturb) & mask; entry = &table[i]; - if (entry->key == NULL) + if (entry->hash == 0 && entry->key == NULL) goto found_null; } + found_null: - return freeslot == NULL ? entry : freeslot; + if (freeslot == NULL) { + /* UNUSED */ + so->fill++; + } else { + /* DUMMY */ + entry = freeslot; + } + so->used++; + entry->key = key; + entry->hash = hash; + return 0; + + found_active: + Py_DECREF(key); + return 0; } /* @@ -172,38 +267,6 @@ set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash) /* ======== End logic for probing the hash table ========================== */ /* ======================================================================== */ - -/* -Internal routine to insert a new key into the table. -Used by the public insert routine. -Eats a reference to key. -*/ -static int -set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) -{ - setentry *entry; - - entry = set_lookkey(so, key, hash); - if (entry == NULL) - return -1; - if (entry->key == NULL) { - /* UNUSED */ - entry->key = key; - entry->hash = hash; - so->fill++; - so->used++; - } else if (entry->key == dummy) { - /* DUMMY */ - entry->key = key; - entry->hash = hash; - so->used++; - } else { - /* ACTIVE */ - Py_DECREF(key); - } - return 0; -} - /* Restructure the table by allocating a new table and reinserting all keys again. When entries have been deleted, the new table may @@ -345,7 +408,7 @@ set_discard_entry(PySetObject *so, setentry *oldentry) entry = set_lookkey(so, oldentry->key, oldentry->hash); if (entry == NULL) return -1; - if (entry->key == NULL || entry->key == dummy) + if (entry->key == NULL) return DISCARD_NOTFOUND; old_key = entry->key; entry->key = dummy; @@ -623,7 +686,7 @@ set_contains_entry(PySetObject *so, setentry *entry) if (lu_entry == NULL) return -1; key = lu_entry->key; - return key != NULL && key != dummy; + return key != NULL; } static int |