[Patches] [ python-Patches-425242 ] Patch which "inlines" small dictionaries

[noreply@sourceforge.net]

Patches item #425242, was updated on 2001-05-18 10:15
You can respond by visiting: 
http://sourceforge.net/tracker/?func=detail&atid=305470&aid=425242&group_id=5470

Category: core (C code)
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: M.-A. Lemburg (lemburg)
Assigned to: Jeremy Hylton (jhylton)
>Summary: Patch which "inlines" small dictionaries

Initial Comment:
As discussed on python-dev, this patch inlines small
dictionary tables directly in the dictionary object.

----------------------------------------------------------------------

>Comment By: M.-A. Lemburg (lemburg)
Date: 2001-05-21 01:25

Message:
Logged In: YES 
user_id=38388

Hmm, timdict2.patch seems to be a completly different
solution. What I am missing in that patch is the ability to
tune the implementation... what happens if I want to bump
MINSIZE to some higher value ? I think the patch should at
least include an explanation of how this can be done.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2001-05-20 15:31

Message:
Logged In: YES 
user_id=31435

Just deleted my first patch.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2001-05-20 15:30

Message:
Logged In: YES 
user_id=31435

timdict2.patch is more aggressive about iterating until 
we've seen fill non-virgin entries go by rather than the 
table size.  This is never slower but is sometimes a 
surprising win!  For example, dicts keyed by a contiguous 
range of small integers tend to fill a solid initial 
segment of the dict.  When resizing or copying, after the 
patch it's common for the loop to get out, e.g., after ~170 
iterations instead of (the current, and always) 256.

Also added some desperately needed comments about what the 
GF(2^n-{0}) business means in pragmatic terms; + a few 
assorted cleanups.

I think this is ready for prime time, but do have concerns 
about the increased memory use (embedding an 8-slot table 
in every dict object means every dict bites another 8*3*4 
== 96 bytes on a 32-bit box; OTOH, dicts with up to and 
including 5 entries never need more space than that, and 
dicts with 3, 4 or 5 entries were actually larger before 
due to the malloc overhead tagging along with their 
dynamically allocated 8-slot table).

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2001-05-19 20:40

Message:
Logged In: YES 
user_id=31435

Assigned to Jeremy since he's been timing stuff lately 
too:  care to give it a try?

timdict.patch is in some ways more aggressive than MAL's 
patch, taking advantage of that we always have *some* 
memory to point to now, thus allowing to get rid of a bunch 
of table==NULL? tests and associated gotos and labels.

The newer patch passes all the tests I've thrown at it, in 
debug and release builds.  It was a major bitch to get 
working correctly, due to an excruciating interaction among 
PyDict_Clear() and garbage collection and module 
finalization and the special treatment of __builtins__ (who 
would have guessed that allocating a tuple could cause a 
module to finalize!?).

I never figured out why MAL's patch died, and after 
spending 10 hours figuring out why mine did, don't intend 
to waste the rest of the weekend trying <wink>.


----------------------------------------------------------------------

Comment By: M.-A. Lemburg (lemburg)
Date: 2001-05-18 10:21

Message:
Logged In: YES 
user_id=38388

This is just a quick update of the original patch which I
prepared for Python 1.5 some years ago. Since the dictionary
implementation has evolved somewhat since then, I'm not sure
whether it still works as robust as it does for Python 1.5
(I've been using this for years without any problem).

Running the test suite, their appears to be a hanger due to
some endless loop which occurrs for test_popen2. I'm not
sure where Python hangs, but it could well be that the
resize routines have to adapted a little for the current
dict implementation.



----------------------------------------------------------------------

You can respond by visiting: 
http://sourceforge.net/tracker/?func=detail&atid=305470&aid=425242&group_id=5470