I haven't had much of a chance to comb through all the code it detail, but there are least a few places that loop over the whole entry table (size is dk_nentries) when fewer iterations would suffice (stop once mp->ma_used entries have been seen).  Since the table is usually dense packed to the left, this will give fewer loops and fewer memory accesses.

I'm wondering why new dict implementation don't keep the array of items compact? Original Raymond's implementation did not preserve the order after deletions, but saved items in an array without gaps. This could simplify and speed up an iteration (no need to check values for NULL, and needed to iterate fewer elements), and could get rid of reallocations in often mutated dicts. I haven't found clear explanation of this.

> I'm wondering why new dict implementation don't keep the array of items compact? Original Raymond's implementation did not preserve the order after deletions, but saved items in an array without gaps. This could simplify and speed up an iteration (no need to check values for NULL, and needed to iterate fewer elements), and could get rid of reallocations in often mutated dicts. I haven't found clear explanation of this.

As far as I remember, I choose it because:

1. easy to explain, easy to discussion.

"keep insertion order" is easier than "keep insertion order unless deletion".

I want to start discussion based on most simple behavior.
But my patch was reviewed by core developers in sprint, when right before 3.6b1.

2. I want to share same implementation with OrderedDict, like PyPy.

3. Make patch compact.

If we compact dk_entries when deletion, we need another dk_indices compaction.
Before sprint, my patch wasn't reviewed for months.  I was afraid that my patch wasn't reviewed by 3.6b1.


For now, "namespace dict keeps insertion order" is language spec.
`del` shouldn't break insertion order.

patch LGTM.

> Since the table is usually dense packed to the left, this will give fewer loops and fewer memory accesses.

Since dk_nentries is "right end of active entries", this patch doesn't
affect for "dence packed to the left" dict.
But it can affect when dk_entries is sparce, and there are many deleted entries on the right end.

While this isn't bugfix, I'm +1 to commit this to 3.6 branch to reduce
future maintenance cost.

In general the idea LGTM. It it is slightly dangerous if dict structure is broken. j is incremented only when value != NULL, and if ma_used is not correct, this can cause reading out of the end of an array. Of course this should never happen. But if there is a chance to add some assertions or additional checks in debug mode, it would be nice. Unless this complicate the code to much.

The i counter is not used in some loops. It can be eliminated.

Do you mind to create a pull request Raymond?

This doesn't meet our criteria for backports.

I can convert this to a pull request if there is still interest in the change.

> I can convert this to a pull request if there is still interest in the change.

Yes, please do.

New changeset f66e336f455b5a6bb0ca857d61c43be410d0df13 by Inada Naoki (Cheryl Sabella) in branch 'master':
bpo-29202: improve dict iteration (GH-11900)
https://github.com/python/cpython/commit/f66e336f455b5a6bb0ca857d61c43be410d0df13