We should investigate whether we want dicts to compact themselves on del/pop operations.  Currently we have to rely on workarounds to have compactable dict.copy (see issue 31179) etc.

Note: It was recently discussed if "del dict[key]" should keep the insertion order. If I understood correctly: yes, the order must be preserved on deletion.

https://mail.python.org/pipermail/python-dev/2017-November/150142.html

For insert/pop loop, reduce table size aggressively on pop may cause
performance regression.  So reducing size should be conservative.

So my opinion is:

* When dict size become 0, make the dict shared-empty, like dict.clear()
* When (dict size < dk_size/8), call insertion_resize()

I agree that an heuristic is needed to decide when a dict should be compacted.

> * When (dict size < dk_size/8), call insertion_resize()

In bpo-31179, I suggested to Yury to use 2/3 ratio... to avoid integer overflow :-) He first used 80%, but I dislike using the FPU in the dictobject.c. I'm not sure of the cost of switching from integers to floats, and more generally I hate rounding issues, so I prefer to use regular integers ;-)

+           (3) if 'mp' is non-compact ('del' operation does not resize dicts),
+               do fast-copy only if it has at most 1/3 non-used keys.
+
+           The last condition (3) is important to guard against a pathalogical
+           case when a large dict is almost emptied with multiple del/pop
+           operations and copied after that.  In cases like this, we defer to
+           PyDict_Merge, which produces a compacted copy.

By the way, if dict automatically compacts itself automatically, do we still need Yury's test "is the dict compact"?

This issue is a matter of CPU vs memory tradeoff. It reminds me the PEP 393: str type doesn't make tradeoff anymore, CPython guarantee that str always use the most efficient storage (least memory) for characters.

But here the tradeoff is different. A dict is mutable, whereas str is immutable ;-)

> * When dict size become 0, make the dict shared-empty, like dict.clear()

This will cause significant performance regression for `dict[a]=None; del dict[a]` loop.
del/pop shouldn't do clear().

> * When (dict size < dk_size/8), call insertion_resize()

This is bad too.
When ma_used=127 and dk_size=1024, new size will be 1024!
It's because current GROWTH_RATE is used*2 + size/2.

This GROWTH_RATE is set in issue17563.
We should understand it before changing anything.

"This will cause significant performance regression for `dict[a]=None;
del dict[a]` loop. del/pop shouldn't do clear()."

Should we make sure that all dicts have at least MINSIZE entries?

> Should we make sure that all dicts have at least MINSIZE entries?

I don't think so.  I think "allocate on first insert" is good idea for dict.clear()
And I think it's good idea for new dict too:
https://github.com/python/cpython/pull/1080

I think I understand #17563, and I should fix GROWTH_RATE.

Before compact-ordered dict, we can avoid resizing in
"the number of deletions is on a par with the number of insertions."
scenario, by large GROWTH_RATE.
That's because new entry can reuse dummy entries.

But in compact-ordered dict, we can't do that.
We need resizing always, and resize is much faster than legacy dict.

I think GROWTH_RATE should be ma_used*3 for now.