[Tim Peters] > Dicts can be larger after the > patch, but never > smaller, so there's nothing opposing the "can be larger" > part: on average, allocated address space must be strictly larger than before. I think of the resize intervals as steps on a staircase. My patch eliminates the even numbered stairs. The average logarithmic slope of the staircase doesn't change, there are just fewer discrete steps. Also, the height of the staircase doesn't change unless the top stair was even, in which case, another half step is added. [Tim Peters] > Resizing a large dict is an expensive operation too. Not only are there fewer resizes, but the cost of the operation becomes cheaper because it takes less time to load a sparse dictionary than one that is more dense. [Tim Peters] > Whether that *matters* on average to the average user is something > we can answer > rigorously just as soon as we find an average user with an > average program > <wink>. I'm not inclined to worry much about it. Me either, I suspect that it is rare to find a stable application that is functioning just fine and consuming nearly all memory. Sooner or later, some change in data, hardware, os, or script would push it over the edge. [Timothy Delaney] > That's what I was getting at. I know that (for example) most > classes I create have less that 16 entries in their __dict__. > With this change, each class instance would take (approx) twice > as much memory for its __dict__. I suspect that class instance > __dict__ is the most common dictionary I use. Those dicts would also be the ones benefitting from the patch. Their density would be halved; resulting in fewer collisions, improved search times, and better cache performance. [Timothy Delaney] > Perhaps we need to add some internal profiling, so that > "quickly-growing" dictionaries get larger reallocations ;) I came up with this patch a couple of months ago and have since tried every tweak I could think of (apply to this size dict but not that one, etc) but found nothing that survived a battery of application benchmarks. Have you guys tried out the patch? I'm very interested in getting results from different benchmarks, processors, cache sizes, and various operating systems. sparse-is-better-than-dense-ly yours, Raymond (currently, the only one. unlike two Tims, two Bretts, two Jacks and a Fredrik distinct from Fred) ################################################################# ################################################################# ################################################################# ##### ##### ##### ################################################################# ################################################################# #################################################################
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4