[Python-Dev] Dictionary tuning

[Delaney, Timothy C (Timothy)]

> From: Guido van Rossum [mailto:guido@python.org]
>=20
> > I've experimented with about a dozen ways to improve dictionary=20
> > performance and found one that benefits some programs by up to=20
> > 5% without hurting the performance of other programs by more
> > than a single percentage point.
> >=20
> > It entails a one line change to dictobject.c resulting in a new=20
> > schedule of dictionary sizes for a given number of entries:
> >=20
> > Number of           Current size        Proposed size
> > Filled Entries      of dictionary       of dictionary
> > --------------      -------------       -------------
> > [-- 0 to 5 --]            8                   8
> > [-- 6 to 10 --]          16                  32
> > [-- 11 to 21 --]         32                  32
> > [-- 22 to 42 --]         64                 128
> > [-- 43 to 85 --]        128                 128
> > [-- 86 to 170 --]       256                 512
> > [-- 171 to 341 --]      512                 512
>=20
> I suppose there's an "and so on" here, right?  I wonder if for
> *really* large dicts the space sacrifice isn't worth the time saved?

What is the effect on peak memory usage over "average" programs?

This might be a worthwhile speedup on small dicts (up to a TBD number of =
entries) but not worthwhile for large dicts. However, to add this =
capability in would of course add more code to a very common code path =
(additional test for current size to decide what factor to increase by).

> I tried the patch with my new favorite benchmark, startup time for
> Zope (which surely populates a lot of dicts :-).  It did give about
> 0.13 seconds speedup on a total around 3.5 seconds, or almost 4%
> speedup.

Nice (in relative, not absolute terms). Do we have any numbers on memory =
usage during and after that period?

Tim Delaney