[Patches] [ python-Patches-916251 ] Create a freelist for dictionaries

[SourceForge.net]

Patches item #916251, was opened at 2004-03-14 20:48
Message generated for change (Comment added) made by nnorwitz
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=916251&group_id=5470

Category: Core (C code)
Group: Python 2.4
Status: Open
Resolution: None
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Neal Norwitz (nnorwitz)
Summary: Create a freelist for dictionaries

Initial Comment:
Neal, here is a simple implementation of freelists for 
dictionaries.

I've not yet measured it across multiple applications 
and have no basis for knowing what a good maximum 
size should be (it's currently set at 100 which costs 
about 6K of memory when full).

Right now, it only saves malloc time.  It would great to 
also save some on the other initialization steps.  The 
trick would be finding a way for delloc() to a little more 
work to save correspondingly more in PyDict_New().

Any review, ideas, independent timings, or creative 
thinking are welcome.

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

>Comment By: Neal Norwitz (nnorwitz)
Date: 2004-03-15 22:15

Message:
Logged In: YES 
user_id=33168

Thanks Tim.  I saw it late last night and didn't re-read
today.  Too much PSF work, not enough coding. :-(

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

Comment By: Tim Peters (tim_one)
Date: 2004-03-15 22:12

Message:
Logged In: YES 
user_id=31435

Neal, study the comment following that code.  Sick code 
could have reduced the size of the dict as a side effect of 
calling PyObject_RichCompareBool(); that would make 
ma_mask smaller than it was at the start of the loop.  Nothing 
about a dict can be assumed invariant across anything that 
may release the GIL or call back into Python (except for the 
address of the dict object). 

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

Comment By: Neal Norwitz (nnorwitz)
Date: 2004-03-15 22:05

Message:
Logged In: YES 
user_id=33168

Looking at the patch now, but I noticed a seemingly useless
comparison in characterize around line 1328 (not related to
your work):

 if (cmp > 0 ||
     i > a->ma_mask ||
     a->ma_table[i].me_value == NULL)

I see no way for i > a->ma_mask based off the for loop (i <=
a->ma_mask).  Am I missing something?

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

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-03-15 20:15

Message:
Logged In: YES 
user_id=80475

Added a revised patch that can save even more work.

If the previously freed dictionary has mp->mp_fill==0, then 
the memset() initialization can be skipped.

Instrumenting this (against several different apps and the 
test suite) shows that 4 out of 5 mallocs are saved and the 1 
in 10 memsets are saved.  The counts fall off by about a 
quarter if the size of the freelist is cut in half (suggesting 
that 60 to 100 freedicts is plenty).


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

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-03-15 03:47

Message:
Logged In: YES 
user_id=80475

>> There could be a problem in that the element's are freed.

Sure they are.  The dict isn't put on the freelist until
*after* all the 
elements are freed by dealloc() and the ma_table is freed. 
All that is left is the shell that includes the ma_smalltable. 


>> would be better to free older dict refs

No, no refs are kept.  The shells are empty and
undifferentiated, so age doesn't matter (just like the
freelist scheme for tuples and   frames).

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

Comment By: Neal Norwitz (nnorwitz)
Date: 2004-03-14 23:30

Message:
Logged In: YES 
user_id=33168

There could be a problem in that the elements aren't freed.

d = {}
k, v = 1, 2
# create weakref to k and/or v
d[k] = v
del d

The weakref callback wouldn't be called in this case, right?
What are your thoughts on memory reclaimation in general?
I don't know anything about the internals of dict, but if
it's resized very large, should the entries be reduced?

Doing more thinking out loud...I wonder if it would be better to
free older dict refs when the table became full?  I think
the answer
may also depend on size, memory locations (pages used), etc.

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

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