From 13a9828719bc15daee08a1ed1be1b43156cd5289 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Martin=20v=2E=20L=C3=B6wis?= Date: Thu, 15 Feb 2007 09:51:35 +0000 Subject: [PATCH] Patch #1397848: add the reasoning behind no-resize-on-shrinkage. --- Objects/dictnotes.txt | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/Objects/dictnotes.txt b/Objects/dictnotes.txt index 3b63197e79..d3aa77401c 100644 --- a/Objects/dictnotes.txt +++ b/Objects/dictnotes.txt @@ -98,6 +98,17 @@ Tunable Dictionary Parameters depending on the size of the dictionary. Setting to *4 eliminates every other resize step. +* Maximum sparseness (minimum dictionary load). What percentage + of entries can be unused before the dictionary shrinks to + free up memory and speed up iteration? (The current CPython + code does not represent this parameter directly.) + +* Shrinkage rate upon exceeding maximum sparseness. The current + CPython code never even checks sparseness when deleting a + key. When a new key is added, it resizes based on the number + of active keys, so that the addition may trigger shrinkage + rather than growth. + Tune-ups should be measured across a broad range of applications and use cases. A change to any parameter will help in some situations and hurt in others. The key is to find settings that help the most common @@ -115,6 +126,15 @@ __iter__(), iterkeys(), iteritems(), itervalues(), and update(). Also, every dictionary iterates at least twice, once for the memset() when it is created and once by dealloc(). +Dictionary operations involving only a single key can be O(1) unless +resizing is possible. By checking for a resize only when the +dictionary can grow (and may *require* resizing), other operations +remain O(1), and the odds of resize thrashing or memory fragmentation +are reduced. In particular, an algorithm that empties a dictionary +by repeatedly invoking .pop will see no resizing, which might +not be necessary at all because the dictionary is eventually +discarded entirely. + Results of Cache Locality Experiments ------------------------------------- -- 2.50.1