Issue 13903: New shared-keys dictionary implementation

Jim.Jewett

Include/dictobject.h ==================== Reducing PyDict_MINSIZE from 8 to 4: I suspect this is probably a good ...

1 year, 3 months ago #2

Include/dictobject.h
====================

Reducing PyDict_MINSIZE from 8 to 4:

I suspect this is probably a good change, but it is worth mentioning in the
changes, and worth measuring.  How many dicts really have only 2 (or now 3?)
values, vs the cost of an extra resize?


Renaming PyDictEntry to PyDictKeyEntry:

Why?  

Personally, I consider its structure to be an internal detail, and would like to
see it removed from the header (or at least put in a more private header, like
dictobjectimpl.h).  But if it is being kept, it might make sense to keep the
name as well; the combined dicts use is as a full entry, and the split dicts go
out of their way to fill it in as if it were a regular entry.

dict_lookup_func should probably also be moved to a more private location.  Even
if it is moved (and especially if it isn't), you should not assume that the
current list is exhaustive.  Keeping it public suggests that 3rd party
extensions will be supplying their own *internal-format* lookup funcs; they
might, and there are use cases, but I think they should know that they are
messing with internals when they do.

_dictkeysobject should probably also be in a more private location; the only
external usage I found (in object.h) was just a pointer, and didn't need to know
what the structure looked like.


Lib/Test/test_pprint.py
=======================
I agree that the format of set(range(3)) is problematic, but the printing of the
empty sets is clearly a valid test.

For the other tests, I think it is wrong to just stop running them.  At a
minimum, the test should be copied to another with a @skip decorator. 
Personally, I would prefer that pprint do the same thing with sets that it
already does with dicts, and just order the keys if it can.  (Since it can for
these tests, that would solve the issue.)


Objects/dictnotes.txt
=====================

Please leave the note about builtins being all interned strings; just update the
size to 133 as 3.2, or something newer.

The notes about cache line counts for larger dicts and Cache Locality
Experiments still apply to combined dicts, and to the keys table.  Go ahead and
reword it, but please don't delete it.

It is worth noting here that PyDict_MINSIZE was 8 prior to python 3.3, so that
people realize it is a recent change.  

Particularly leave the discussion of why flipping the last bit might be OK, but
linear probing isn't.  The outcome of the hash randomization *might* make it
easier to change to iteration order in the future.

Objects/dictobject.c
====================
Line numbers are based on
https://bitbucket.org/markshannon/cpython_new_dict/compare/..mirror/cpython --
not sure if that is the same version as this patch.

Why the removals around line 28-31 and 144-190?  These are still useful
comments, and the #undef is still a useful compile-time flag.

Around 180, you're reinventing ref-counting; just making the keys a PyObject
costs only a single pointer (for type), except when debugging is turned	on and
you might want the extra information.  Note that this would also take care of
using the GC trashcan macros for you.


At 186, I think this can be worded a bit more clearly. Maybe:

/* USABLE_FRACTION must obey the following:
 *     (0 < USABLE_FRACTION(n) < n) for all n >= PyDict_MINSIZE
 *
 * USABLE_FRACTION should be very quick to calculate.
 * Fractions around 5/8 to 2/3 seem to work well in practice.
 */


I'm also pretty sure that the previous code (multiplying both sides, to avoid
adding or dividing) was tuned for speed; don't give that up with without
measurements.

Using two multiplies also has the advantage of leaving dk_free with a more
intuitive meaning.  (count of free slots, rather than count of still-usable
slots.)


Line 206 -- Why is lookdict (the generic, might not even be a string key) not
deletable?



Line 246 -- Why not just memset the whole thing to 0?
Line 308-309 why not just memset the values to NULL?



Line 312-316 -- Why was this deleted?  The removal suggests that it no longer
returns the place where a key would be inserted.

Line 397-406 -- why remove these comments?  Particularly	since you're still
insisting on PyUnicode_CheckExact?


	Line 604 (old 466):  What if the lookdict is something custom from a subclass? 
I think it would be safer to check for the functions that you do expect.


Line 674 (old 528):  Why remove the register declaration?
Line 746 (old 572):  Why remove the register declaration?
Line 997 (old 793):  Why remove the register declaration?
Line 999-1000 (old 795-797):  Why remove the register declaration?
Line 1025-1027 (old 841-843):  Why remove the register declaration?
(just make it a global comment)


Line 832-833:  Why null the memory out if it is just being deallocated? 
Addresses shouldn't be particularly sensitive even if it were going all the way
to the OS.

Line 860 seems redundant, given lines 857 and 859.

old lines 818-832:  The info about growth rate (and possible	shrinkage) is worth
documenting, though I suppose it should move nearer the actual (current)
calculation.

Line 1082:  Where is empty_values INCREFed?

Global -- what makes a keytable immutable?  Is that something user python code
(or extension code) should be able to do?  To undo?

What exactly happens if a shared keytable needs to be resized up?  I think
you've answered that in email, but I didn't really find clear comments about it
in the code.

-jJ

Sign in to reply to this message.

Benjamin Peterson

I mostly have endless stylistic complaints. http://bugs.python.org/review/13903/diff/4567/16188 File Include/dictobject.h (right): http://bugs.python.org/review/13903/diff/4567/16188#newcode109 Include/dictobject.h:109: int _PyObjectDict_SetItem(PyTypeObject *tp, ...

1 year, 1 month ago #3

Mark.Shannon

All fixed. I've mostly followed Benjamin's recommendations with a few minor stylistic differences which I've ...

1 year ago #4

All fixed. I've mostly followed Benjamin's recommendations
with a few minor stylistic differences which I've explained.

http://bugs.python.org/review/13903/diff/4567/16189
File Include/object.h (right):

http://bugs.python.org/review/13903/diff/4567/16189#newcode452
Include/object.h:452: struct _dictkeysobject *ht_cached_keys;
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Why not say "PyDictKeysObject"?

To avoid object.h depending on dictobject.h

http://bugs.python.org/review/13903/diff/4567/16191
File Lib/test/test_pprint.py (right):

http://bugs.python.org/review/13903/diff/4567/16191#newcode252
Lib/test/test_pprint.py:252: return
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> It'd be better to use an expectedFailure.

Done.

http://bugs.python.org/review/13903/diff/4567/16193
File Objects/dictnotes.txt (right):

http://bugs.python.org/review/13903/diff/4567/16193#newcode23
Objects/dictnotes.txt:23: Size 147 interned strings (as of Py3.3a0).
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> We're past alpha 0 now.

Done.

http://bugs.python.org/review/13903/diff/4567/16193#newcode62
Objects/dictnotes.txt:62:
----------------------------------------------------------------
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Adjust this.

Done.

http://bugs.python.org/review/13903/diff/4567/16193#newcode88
Objects/dictnotes.txt:88: Currently set to 2/3.
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Wrap next line into this.

Done.

http://bugs.python.org/review/13903/diff/4567/16194
File Objects/dictobject.c (right):

http://bugs.python.org/review/13903/diff/4567/16194#newcode12
Objects/dictobject.c:12: There are four kinds of slots in the table:
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> It might be nice to make predicate macros for these various states like
> SLOT_PENDING/ACTIVE/DUMMY/UNUSED. Then, below, where you are checking
> invariants, you could use them. It would be more clear what you check for in
the
> assertions below.

Most of the assertions are checking other things, so I don't think the macros
would be worthwhile.

http://bugs.python.org/review/13903/diff/4567/16194#newcode76
Objects/dictobject.c:76: PyObject *_me_value; /* This field is only meaningful
for combined tables */
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Why the underscore prefix?

I removed the prefix. I had used it previously as PyDictKeyEntry was originally
declared in dictobject.h
and I wanted to make it extra clear that this field should
not be accessed by other code.

http://bugs.python.org/review/13903/diff/4567/16194#newcode236
Objects/dictobject.c:236: static int
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> This might as well be on one line.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode291
Objects/dictobject.c:291: #define ENSURE_ALLOWS_DELETIONS(d) \
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Can this be a static function?

It could be, but as it should always be inlined its probably better as a macro.

http://bugs.python.org/review/13903/diff/4567/16194#newcode313
Objects/dictobject.c:313: static PyDictKeysObject *new_keys_object(Py_ssize_t
size) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Function name on separate line and brace on its own line like other functions.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode320
Objects/dictobject.c:320: dk = PyMem_Malloc(sizeof(PyDictKeysObject) +
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> It's usually preferable to use the macros version: PyMem_MALLOC

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode349
Objects/dictobject.c:349: PyMem_DEL(keys);
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> This is deprecate in favor of PyMem_FREE.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode352
Objects/dictobject.c:352: #define new_values(size) PyMem_New(PyObject *, size)
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> PyMem_NEW

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode354
Objects/dictobject.c:354: #define free_values(values) PyMem_DEL(values)
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Same comment about PyMem_DEL being deprecated applies.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode383
Objects/dictobject.c:383: new_dict_with_shared_keys(PyDictKeysObject *keys) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Brace on next line.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode393
Objects/dictobject.c:393: for (i = 0; i < size; i++) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Why not memset?

Because memset is only faster for large or unaligned memory. For small aligned
memory (and shared-keys dict are small) the loop is faster, unless the compiler
is smart enough to perform the substitution itself. Many aren't.

http://bugs.python.org/review/13903/diff/4567/16194#newcode400
Objects/dictobject.c:400: PyDict_New(void) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Brace on next line?

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode436
Objects/dictobject.c:436: register size_t mask = (size_t)mp->ma_keys->dk_size-1;
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Do you want to use the DK_SIZE macro?

I've added a DK_MASK macro and used that throughout.

http://bugs.python.org/review/13903/diff/4567/16194#newcode610
Objects/dictobject.c:610: if (ep->me_hash == hash && unicode_eq(ep->me_key,
key)) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> This and the last if can be folded together.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode622
Objects/dictobject.c:622: if (ep->me_hash == hash && unicode_eq(ep->me_key,
key)) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> This if can be folded with the last one.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode637
Objects/dictobject.c:637: Py_hash_t hash, PyObject ***value_addr)
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Fix alignment.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode646
Objects/dictobject.c:646: return lookdict(mp, key, hash, value_addr);
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Need to set the lookdict pointer on keys, too?

No. mp->ma_keys->dk_lookup <=> _PyDict_HasSplitTable(mp)
For a split table, only the lookdict_split will work and
lookdict_split requires a split table. I've added a comment.

http://bugs.python.org/review/13903/diff/4567/16194#newcode655
Objects/dictobject.c:655: if (ep->me_hash == hash && unicode_eq(ep->me_key,
key)) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Fold ifs.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode667
Objects/dictobject.c:667: if (ep->me_hash == hash && unicode_eq(ep->me_key,
key)) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Same comment about folding condition.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode791
Objects/dictobject.c:791: if (mp->ma_values != NULL) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> This whole chain of ifs can be in one condition.

I've put the first two together as they form the test,
whereas the third is the action (the test is to check for an error)

http://bugs.python.org/review/13903/diff/4567/16194#newcode898
Objects/dictobject.c:898: Py_ssize_t i, size;
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> The name "oldsize" might be better.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode913
Objects/dictobject.c:913: if (oldkeys->dk_lookup == lookdict)
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Do this after checking that mp->ma_keys is not NULL.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode923
Objects/dictobject.c:923: assert(oldkeys = Py_EMPTY_KEYS);
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> I think you meant ==.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode983
Objects/dictobject.c:983: } else if (mp->ma_keys->dk_lookup == lookdict_unicode)
{
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> 2 lines.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode985
Objects/dictobject.c:985: if (dictresize(mp, DK_SIZE(mp->ma_keys)))
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Fold into above condition.

I prefer not to as the second "condition" is really an action, the test is for
an exception.

http://bugs.python.org/review/13903/diff/4567/16194#newcode992
Objects/dictobject.c:992: if (values == NULL)
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Need to set memory error.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode994
Objects/dictobject.c:994: size = DK_SIZE(mp->ma_keys);
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Set size before 991 and then use it there.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode1014
Objects/dictobject.c:1014: return new_dict(new_keys_object(newsize), NULL);
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> What if new_keys_object fails?

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode1110
Objects/dictobject.c:1110: _PyDict_LoadGlobal(PyDictObject *globals,
PyDictObject* builtins, PyObject *key)
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Fix PyDictObject* start.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode1402
Objects/dictobject.c:1402: /* Prevent repr from deleting value during key
format. */
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> "deleting value" -> "deleting key and value"

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode2309
Objects/dictobject.c:2309: if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Fold with if on last line.

Same argument as before, dictresize is an action, not a condition.

http://bugs.python.org/review/13903/diff/4567/16194#newcode2403
Objects/dictobject.c:2403: return PyFloat_FromDouble(res);
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Hmm, I'm not so sure about this. Is returning a float useful?

I'm not sure about this either. But how do we divide up the shared keys if
returning an int?

http://bugs.python.org/review/13903/diff/4567/16194#newcode3599
Objects/dictobject.c:3599: PyObject *key, PyObject *value) {
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Put brace on next line.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode3614
Objects/dictobject.c:3614: *dictptr = dict;
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> There's no point in doing this if you didn't just create a dict.

Done.

http://bugs.python.org/review/13903/diff/4567/16194#newcode3626
Objects/dictobject.c:3626: CACHED_KEYS(tp) = make_keys_shared(dict);
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> What if this fails?

Done.

http://bugs.python.org/review/13903/diff/4567/16196
File Objects/typeobject.c (right):

http://bugs.python.org/review/13903/diff/4567/16196#newcode2310
Objects/typeobject.c:2310: et->ht_cached_keys = _PyDict_NewKeysForClass();
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Check for failure?

et->ht_cached_keys == NULL is a valid state.
I've altered _PyDict_NewKeysForClass so as not set an error.

http://bugs.python.org/review/13903/diff/4567/16196#newcode2418
Objects/typeobject.c:2418: res->ht_cached_keys = _PyDict_NewKeysForClass();
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> And here?

Ditto

http://bugs.python.org/review/13903/diff/4567/16196#newcode2776
Objects/typeobject.c:2776: extern void
On 2012/04/20 04:33:19, Benjamin Peterson wrote:
> Shouldn't this be in dictobject.h instead?

_PyDictKeys_DecRef is not a public function. This is the only use of it. 

An alternative might be to move the dictobject structs and macros into a
dictobject_impl.h and include that in this file.

Sign in to reply to this message.

Mark.Shannon

1 year ago #5

Worthwhile addition. I've made a couple of comments.

http://bugs.python.org/review/13903/diff/4766/16903
File Objects/dictobject.c (right):

http://bugs.python.org/review/13903/diff/4766/16903#newcode265
Objects/dictobject.c:265: #define DK_DEBUG_DECREF _Py_DEC_REFTOTAL
_Py_REF_DEBUG_COMMA
I don't think we should use _Py_INC_REFTOTAL as the keys are not PyObjects.
Could you add a DK_RefTotal value, or does that make checking for leaks awkard?

http://bugs.python.org/review/13903/diff/4766/16903#newcode1269
Objects/dictobject.c:1269: DK_DECREF(oldkeys);
Could you replace the  free_keys_object() call with a macro that would include
the assert and DK_DEBUG_DECREF?
I would like to keep the assertion as (keys->dk_refcnt == 1)
for combined tables is an important invariant.

http://bugs.python.org/review/13903/diff/4766/16903#newcode1378
Objects/dictobject.c:1378: DK_DECREF(keys);
Ditto.

Sign in to reply to this message.

#13903: New shared-keys dictionary implementation

Patch Set 1 #

Patch Set 2 #

Patch Set 3 #

Patch Set 4 #

Patch Set 5 #

Patch Set 6 #

Patch Set 7 #

Patch Set 8 #

Patch Set 9 #

Patch Set 10 #

Patch Set 11 #

Patch Set 12 #

Patch Set 13 #

Patch Set 14 #

Patch Set 15 #

Patch Set 16 #

Patch Set 17 #

Patch Set 18 #

Messages