Issue916251
This issue tracker has been migrated to GitHub,
and is currently read-only.
For more information,
see the GitHub FAQs in the Python's Developer Guide.
Created on 2004-03-15 01:48 by rhettinger, last changed 2022-04-11 14:56 by admin. This issue is now closed.
Files | ||||
---|---|---|---|---|
File name | Uploaded | Description | Edit | |
dict.diff | rhettinger, 2004-03-15 01:48 | Simplest possible freelist implementation | ||
dict3.diff | rhettinger, 2004-03-16 01:15 | Add ability to bypass memset() |
Messages (10) | |||
---|---|---|---|
msg45565 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2004-03-15 01:48 | |
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. |
|||
msg45566 - (view) | Author: Neal Norwitz (nnorwitz) * | Date: 2004-03-15 04:30 | |
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. |
|||
msg45567 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2004-03-15 08:47 | |
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). |
|||
msg45568 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2004-03-16 01:15 | |
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). |
|||
msg45569 - (view) | Author: Neal Norwitz (nnorwitz) * | Date: 2004-03-16 03:05 | |
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? |
|||
msg45570 - (view) | Author: Tim Peters (tim.peters) * | Date: 2004-03-16 03:12 | |
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). |
|||
msg45571 - (view) | Author: Neal Norwitz (nnorwitz) * | Date: 2004-03-16 03:15 | |
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. :-( |
|||
msg45572 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2004-03-17 06:25 | |
Logged In: YES user_id=80475 Hye-Shik, can you give this a second review? |
|||
msg45573 - (view) | Author: Hyeshik Chang (hyeshik.chang) * | Date: 2004-03-17 09:46 | |
Logged In: YES user_id=55188 The code looks solid and fine for me. And it runs perfectly. BTW, it doesn't seem to accellate over-all speed much according to pystone and pybench on non-debug build while it absolutely accellates about 3~5% in debug build on my machine. |
|||
msg45574 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2004-03-17 22:19 | |
Logged In: YES user_id=80475 Thanks. Applying along with some other inner loop other optimizations. PyStone only measures a very narrow subset of python. PyBench is broader, but measures only a few specific actions. Also, in this case, I didn't expect a huge speedup -- dictionary creation is much less significant than the cost of using them. Also, dict creation doesn't occur nearly as often as tuple creation. Still, when it kicks in (which is most of the time), it almost always saves cycles. |
History | |||
---|---|---|---|
Date | User | Action | Args |
2022-04-11 14:56:03 | admin | set | github: 40033 |
2004-03-15 01:48:44 | rhettinger | create |