Hi All, My new dictionary implementation has been further updated in light of various comments and questions. The code is here: https://bitbucket.org/markshannon/cpython_new_dict The resizing code has been streamlined. This means that resizing by doubling does not suffer any real performance penalty versus quadrupling. Doubling uses less memory for most benchmarks (it never uses more memory). Michael Foord wrote:
2to3, which seems to be the only "realistic" benchmark that runs on Py3, shows no change in speed and uses 10% less memory. In your first version 2to3 used 28% less memory. Do you know why it's worse in this version?
The answer is that the second version used quadrupling rather than doubling for resizing. All tests pass. test_sys has been altered to allow for the different size of the dictionary. One test in test_pprint has been disabled. This test is broken anyway, see http://bugs.python.org/issue13907. In general, for the new dictionary implementation, with doubling at a resize, speed is unchanged and memory usage is reduced. On "average": ~1% slow down, ~10% reduction in memory use. Full set of benchmarks for new dict with doubling and quadrupling attached. Unfortunately the benchmarking program introduces systematic errors for timings, but it's the best we have at the moment. Note that the json benchmark is unstable and should be ignored. The GC benchmark might be unstable as well, I haven't experimented. The memory usage numbers seems to be more reliable. Revised PEP to follow. Cheers, Mark. Report on Linux vespasian 2.6.24-30-generic #1 SMP i686 Total CPU cores: 1 New dict (doubling) vs. CPython =============================== Speed ----- ### call_simple ### Min: 1.131625 -> 1.216112: 1.07x slower Avg: 1.143615 -> 1.223153: 1.07x slower Significant (t=-95.62) Stddev: 0.00694 -> 0.00745: 1.0734x larger Timeline: b'http://tinyurl.com/7ey5unc' ### fastpickle ### Min: 2.365578 -> 2.315522: 1.02x faster Avg: 2.379824 -> 2.326625: 1.02x faster Significant (t=28.84) Stddev: 0.00984 -> 0.00857: 1.1479x smaller Timeline: b'http://tinyurl.com/75nk6fg' ### fastunpickle ### Min: 2.043093 -> 2.083532: 1.02x slower Avg: 2.056331 -> 2.103432: 1.02x slower Significant (t=-31.72) Stddev: 0.00667 -> 0.00811: 1.2144x larger Timeline: b'http://tinyurl.com/7r24oyr' ### float ### Min: 0.256634 -> 0.242119: 1.06x faster Avg: 0.281768 -> 0.252510: 1.12x faster Significant (t=34.46) Stddev: 0.00985 -> 0.00911: 1.0811x smaller Timeline: b'http://tinyurl.com/72cy3ap' ### formatted_logging ### Min: 1.801701 -> 1.886665: 1.05x slower Avg: 1.825188 -> 1.907127: 1.04x slower Significant (t=-31.16) Stddev: 0.01431 -> 0.01188: 1.2046x smaller Timeline: b'http://tinyurl.com/7yjstcs' ### iterative_count ### Min: 0.531924 -> 0.570944: 1.07x slower Avg: 0.549278 -> 0.586633: 1.07x slower Significant (t=-17.09) Stddev: 0.01287 -> 0.00856: 1.5042x smaller Timeline: b'http://tinyurl.com/7afe77x' ### json_dump ### Min: 1.807933 -> 2.361769: 1.31x slower Avg: 1.833581 -> 2.375774: 1.30x slower Significant (t=-249.39) Stddev: 0.01165 -> 0.01003: 1.1623x smaller Timeline: b'http://tinyurl.com/7nkvfdf' ### json_load ### Min: 1.494502 -> 1.733510: 1.16x slower Avg: 1.513454 -> 1.780639: 1.18x slower Significant (t=-50.91) Stddev: 0.01285 -> 0.03481: 2.7088x larger Timeline: b'http://tinyurl.com/78uex2v' ### nbody ### Min: 1.195176 -> 1.111036: 1.08x faster Avg: 1.205988 -> 1.117919: 1.08x faster Significant (t=64.16) Stddev: 0.00770 -> 0.00591: 1.3028x smaller Timeline: b'http://tinyurl.com/88ylc46' ### nqueens ### Min: 1.205363 -> 1.270263: 1.05x slower Avg: 1.219677 -> 1.286260: 1.05x slower Significant (t=-34.55) Stddev: 0.00992 -> 0.00934: 1.0626x smaller Timeline: b'http://tinyurl.com/6nbjq6y' ### regex_compile ### Min: 2.139500 -> 2.410691: 1.13x slower Avg: 2.150651 -> 2.429258: 1.13x slower Significant (t=-168.69) Stddev: 0.00736 -> 0.00907: 1.2333x larger Timeline: b'http://tinyurl.com/88xr386' ### regex_effbot ### Min: 0.194415 -> 0.200979: 1.03x slower Avg: 0.199182 -> 0.206103: 1.03x slower Significant (t=-4.83) Stddev: 0.00715 -> 0.00717: 1.0028x larger Timeline: b'http://tinyurl.com/6ll7pdv' ### regex_v8 ### Min: 0.233819 -> 0.219033: 1.07x faster Avg: 0.249771 -> 0.227338: 1.10x faster Significant (t=7.69) Stddev: 0.01553 -> 0.01358: 1.1440x smaller Timeline: b'http://tinyurl.com/74dqdsy' ### richards ### Min: 0.698549 -> 0.727000: 1.04x slower Avg: 0.717596 -> 0.750720: 1.05x slower Significant (t=-16.90) Stddev: 0.00896 -> 0.01058: 1.1812x larger Timeline: b'http://tinyurl.com/76cvgyj' ### silent_logging ### Min: 0.282622 -> 0.302598: 1.07x slower Avg: 0.291308 -> 0.313256: 1.08x slower Significant (t=-13.24) Stddev: 0.00791 -> 0.00865: 1.0937x larger Timeline: b'http://tinyurl.com/6vovnav' ### simple_logging ### Min: 1.622786 -> 1.796359: 1.11x slower Avg: 1.660321 -> 1.821784: 1.10x slower Significant (t=-38.86) Stddev: 0.02772 -> 0.00974: 2.8450x smaller Timeline: b'http://tinyurl.com/777y27t' ### threaded_count ### Min: 0.501266 -> 0.532309: 1.06x slower Avg: 0.521384 -> 0.549346: 1.05x slower Significant (t=-13.74) Stddev: 0.01074 -> 0.00957: 1.1228x smaller Timeline: b'http://tinyurl.com/889qegb' ### unpack_sequence ### Min: 0.000212 -> 0.000212: no change Avg: 0.000232 -> 0.000242: 1.04x slower Significant (t=-6.07) Stddev: 0.00026 -> 0.00026: 1.0096x larger Timeline: b'http://tinyurl.com/8yzsnmo' ### 2to3 ### 36.702294 -> 37.234327: 1.01x slower ### mako ### Min: 0.982504 -> 0.887246: 1.11x faster Avg: 1.008269 -> 0.934528: 1.08x faster Significant (t=57.62) Stddev: 0.01178 -> 0.01645: 1.3970x larger Timeline: b'http://tinyurl.com/7p2j9s2' ### mako ### Min: 0.753596 -> 0.874137: 1.16x slower Avg: 0.793711 -> 0.915435: 1.15x slower Significant (t=-85.92) Stddev: 0.01607 -> 0.01561: 1.0293x smaller Timeline: b'http://tinyurl.com/8xu5nh9' The following not significant results are hidden, use -v to show them: call_method, call_method_slots, call_method_unknown, normal_startup, pidigits, startup_nosite. Memory ------ ### call_method ### Mem max: 4164.000 -> 4032.000: 1.0327x smaller Usage over time: b'http://tinyurl.com/7saraes' ### call_method_slots ### Mem max: 4164.000 -> 4028.000: 1.0338x smaller Usage over time: b'http://tinyurl.com/722jr7s' ### call_method_unknown ### Mem max: 4464.000 -> 4068.000: 1.0973x smaller Usage over time: b'http://tinyurl.com/6oayz7q' ### call_simple ### Mem max: 4148.000 -> 4008.000: 1.0349x smaller Usage over time: b'http://tinyurl.com/75v3szx' ### fastpickle ### Mem max: 5108.000 -> 4876.000: 1.0476x smaller Usage over time: b'http://tinyurl.com/6s3q7pt' ### fastunpickle ### Mem max: 5132.000 -> 4896.000: 1.0482x smaller Usage over time: b'http://tinyurl.com/7fjhljq' ### float ### Mem max: 8592.000 -> 6772.000: 1.2688x smaller Usage over time: b'http://tinyurl.com/7ke4acp' ### formatted_logging ### Mem max: 10732.000 -> 10892.000: 1.0149x larger Usage over time: b'http://tinyurl.com/83z4f2a' ### iterative_count ### Mem max: 4200.000 -> 4068.000: 1.0324x smaller Usage over time: b'http://tinyurl.com/77ph38p' ### json_dump ### Mem max: 4944.000 -> 4600.000: 1.0748x smaller Usage over time: b'http://tinyurl.com/896y5he' ### json_load ### Mem max: 4940.000 -> 4596.000: 1.0748x smaller Usage over time: b'http://tinyurl.com/77mw6wz' ### nbody ### Mem max: 4172.000 -> 4024.000: 1.0368x smaller Usage over time: b'http://tinyurl.com/7h2795d' ### normal_startup ### Mem max: 3772.000 -> 3632.000: 1.0385x smaller Usage over time: b'http://tinyurl.com/84nwxz7' ### nqueens ### Mem max: 4272.000 -> 4132.000: 1.0339x smaller Usage over time: b'http://tinyurl.com/7sshb2v' ### pidigits ### Mem max: 4248.000 -> 4108.000: 1.0341x smaller Usage over time: b'http://tinyurl.com/82urnw2' ### regex_compile ### Mem max: 8572.000 -> 8904.000: 1.0387x larger Usage over time: b'http://tinyurl.com/6nukmpu' ### regex_effbot ### Mem max: 4864.000 -> 4736.000: 1.0270x smaller Usage over time: b'http://tinyurl.com/767ge37' ### regex_v8 ### Mem max: 7508.000 -> 7860.000: 1.0469x larger Usage over time: b'http://tinyurl.com/72lxz75' ### richards ### Mem max: 4464.000 -> 4356.000: 1.0248x smaller Usage over time: b'http://tinyurl.com/7794rv7' ### silent_logging ### Mem max: 4844.000 -> 4496.000: 1.0774x smaller Usage over time: b'http://tinyurl.com/8332w2a' ### simple_logging ### Mem max: 6952.000 -> 5352.000: 1.2990x smaller Usage over time: b'http://tinyurl.com/8yk7svt' ### startup_nosite ### Mem max: 2872.000 -> 2748.000: 1.0451x smaller Usage over time: b'http://tinyurl.com/72bbdnp' ### threaded_count ### Mem max: 4232.000 -> 4084.000: 1.0362x smaller Usage over time: b'http://tinyurl.com/8yrshqh' ### unpack_sequence ### Mem max: 5688.000 -> 5416.000: 1.0502x smaller Usage over time: b'http://tinyurl.com/7jy6dpl' ### mako ### Mem max: 9012.000 -> 8580.000: 1.0503x smaller Usage over time: b'http://tinyurl.com/82qzfvo' ### 2to3 ### Mem max: 32684.000 -> 22356.000: 1.4620x smaller Usage over time: b'http://tinyurl.com/77hbok6' ### gc ### Mem max: 92600.000 -> 49000.000: 1.8898x smaller Usage over time: b'http://tinyurl.com/86vswmt' New dict (quadrupling) vs. CPython ================================== Speed ----- ### call_simple ### Min: 1.217095 -> 1.269468: 1.04x slower Avg: 1.228556 -> 1.282715: 1.04x slower Significant (t=-55.48) Stddev: 0.00826 -> 0.00864: 1.0459x larger Timeline: b'http://tinyurl.com/7qtz7hk' ### fastpickle ### Min: 2.421091 -> 2.333122: 1.04x faster Avg: 2.447303 -> 2.348845: 1.04x faster Significant (t=41.67) Stddev: 0.01290 -> 0.01062: 1.2142x smaller Timeline: b'http://tinyurl.com/8634dn3' ### fastunpickle ### Min: 2.069723 -> 2.024058: 1.02x faster Avg: 2.082294 -> 2.039120: 1.02x faster Significant (t=17.92) Stddev: 0.00775 -> 0.01517: 1.9572x larger Timeline: b'http://tinyurl.com/73t6ldd' ### formatted_logging ### Min: 1.839560 -> 1.950483: 1.06x slower Avg: 1.868685 -> 1.973164: 1.06x slower Significant (t=-36.79) Stddev: 0.01822 -> 0.00843: 2.1607x smaller Timeline: b'http://tinyurl.com/6pej9zy' ### iterative_count ### Min: 0.482927 -> 0.564538: 1.17x slower Avg: 0.496796 -> 0.575018: 1.16x slower Significant (t=-41.67) Stddev: 0.00982 -> 0.00893: 1.1002x smaller Timeline: b'http://tinyurl.com/735skdg' ### json_dump ### Min: 1.863940 -> 2.130464: 1.14x slower Avg: 1.905174 -> 2.158846: 1.13x slower Significant (t=-44.83) Stddev: 0.03699 -> 0.01525: 2.4253x smaller Timeline: b'http://tinyurl.com/8yx7oso' ### json_load ### Min: 1.586767 -> 1.761993: 1.11x slower Avg: 1.610569 -> 1.793440: 1.11x slower Significant (t=-80.38) Stddev: 0.01279 -> 0.00976: 1.3097x smaller Timeline: b'http://tinyurl.com/6ny4qr5' ### regex_compile ### Min: 2.163662 -> 2.332177: 1.08x slower Avg: 2.174792 -> 2.349151: 1.08x slower Significant (t=-89.97) Stddev: 0.00824 -> 0.01095: 1.3287x larger Timeline: b'http://tinyurl.com/7htwu63' ### regex_effbot ### Min: 0.203670 -> 0.197273: 1.03x faster Avg: 0.208266 -> 0.202605: 1.03x faster Significant (t=3.74) Stddev: 0.00752 -> 0.00763: 1.0143x larger Timeline: b'http://tinyurl.com/7znmo3r' ### regex_v8 ### Min: 0.226723 -> 0.221915: 1.02x faster Avg: 0.239020 -> 0.230629: 1.04x faster Significant (t=3.22) Stddev: 0.01280 -> 0.01325: 1.0349x larger Timeline: b'http://tinyurl.com/7m99e3s' ### richards ### Min: 0.708626 -> 0.727219: 1.03x slower Avg: 0.729989 -> 0.747773: 1.02x slower Significant (t=-8.71) Stddev: 0.01022 -> 0.01020: 1.0020x smaller Timeline: b'http://tinyurl.com/6ueszbh' ### silent_logging ### Min: 0.272886 -> 0.306478: 1.12x slower Avg: 0.281103 -> 0.314645: 1.12x slower Significant (t=-19.17) Stddev: 0.00832 -> 0.00916: 1.1002x larger Timeline: b'http://tinyurl.com/79koy5q' ### threaded_count ### Min: 0.492332 -> 0.540116: 1.10x slower Avg: 0.518163 -> 0.571137: 1.10x slower Significant (t=-20.88) Stddev: 0.01135 -> 0.01390: 1.2242x larger Timeline: b'http://tinyurl.com/6lsbcvf' ### unpack_sequence ### Min: 0.000208 -> 0.000212: 1.02x slower Avg: 0.000230 -> 0.000243: 1.06x slower Significant (t=-7.71) Stddev: 0.00026 -> 0.00026: 1.0039x larger Timeline: b'http://tinyurl.com/74oeotm' ### mako ### Min: 0.874489 -> 0.823223: 1.06x faster Avg: 0.910595 -> 0.867006: 1.05x faster Significant (t=39.33) Stddev: 0.01187 -> 0.01289: 1.0862x larger Timeline: b'http://tinyurl.com/7zrms7f' ### 2to3 ### 35.266204 -> 35.746234: 1.01x slower ### gc ### 81.385087 -> 72.084505: 1.13x faster The following not significant results are hidden, use -v to show them: call_method, call_method_slots, call_method_unknown, float, nbody, normal_startup, nqueens, pidigits, simple_logging, startup_nosite. Memory ------ ### call_method ### Mem max: 4160.000 -> 4148.000: 1.0029x smaller Usage over time: b'http://tinyurl.com/7vefebw' ### call_method_slots ### Mem max: 4160.000 -> 4144.000: 1.0039x smaller Usage over time: b'http://tinyurl.com/792cyef' ### call_method_unknown ### Mem max: 4460.000 -> 4192.000: 1.0639x smaller Usage over time: b'http://tinyurl.com/6qy28zv' ### call_simple ### Mem max: 4152.000 -> 4124.000: 1.0068x smaller Usage over time: b'http://tinyurl.com/85fjkcd' ### fastpickle ### Mem max: 5112.000 -> 5208.000: 1.0188x larger Usage over time: b'http://tinyurl.com/79fbjo7' ### fastunpickle ### Mem max: 5172.000 -> 5216.000: 1.0085x larger Usage over time: b'http://tinyurl.com/78ux4wb' ### float ### Mem max: 8596.000 -> 6892.000: 1.2472x smaller Usage over time: b'http://tinyurl.com/7m97d7r' ### formatted_logging ### Mem max: 11228.000 -> 11504.000: 1.0246x larger Usage over time: b'http://tinyurl.com/8y8mb64' ### iterative_count ### Mem max: 4208.000 -> 4228.000: 1.0048x larger Usage over time: b'http://tinyurl.com/8834pgs' ### json_dump ### Mem max: 4972.000 -> 4956.000: 1.0032x smaller Usage over time: b'http://tinyurl.com/7y5jlcr' ### json_load ### Mem max: 4984.000 -> 4952.000: 1.0065x smaller Usage over time: b'http://tinyurl.com/87mashx' ### nbody ### Mem max: 4172.000 -> 4160.000: 1.0029x smaller Usage over time: b'http://tinyurl.com/6nlpgr6' ### normal_startup ### Mem max: 3772.000 -> 3744.000: 1.0075x smaller Usage over time: b'http://tinyurl.com/76lbp3j' ### nqueens ### Mem max: 4284.000 -> 4256.000: 1.0066x smaller Usage over time: b'http://tinyurl.com/6lmo2wh' ### pidigits ### Mem max: 4252.000 -> 4236.000: 1.0038x smaller Usage over time: b'http://tinyurl.com/75u5x94' ### regex_compile ### Mem max: 9188.000 -> 8924.000: 1.0296x smaller Usage over time: b'http://tinyurl.com/7zegqhq' ### regex_effbot ### Mem max: 4888.000 -> 4856.000: 1.0066x smaller Usage over time: b'http://tinyurl.com/6trs6gc' ### regex_v8 ### Mem max: 7700.000 -> 8008.000: 1.0400x larger Usage over time: b'http://tinyurl.com/82eole9' ### richards ### Mem max: 4464.000 -> 4492.000: 1.0063x larger Usage over time: b'http://tinyurl.com/6vnhcbo' ### silent_logging ### Mem max: 4844.000 -> 4804.000: 1.0083x smaller Usage over time: b'http://tinyurl.com/7k6l8ty' ### simple_logging ### Mem max: 6860.000 -> 6828.000: 1.0047x smaller Usage over time: b'http://tinyurl.com/7ybn594' ### startup_nosite ### Mem max: 2872.000 -> 2856.000: 1.0056x smaller Usage over time: b'http://tinyurl.com/7z7h3pf' ### threaded_count ### Mem max: 4228.000 -> 4236.000: 1.0019x larger Usage over time: b'http://tinyurl.com/6tdq2mq' ### unpack_sequence ### Mem max: 5704.000 -> 5856.000: 1.0266x larger Usage over time: b'http://tinyurl.com/75sboe3' ### mako ### Mem max: 8796.000 -> 8760.000: 1.0041x smaller Usage over time: b'http://tinyurl.com/6qyt8wm' ### 2to3 ### Mem max: 32676.000 -> 29472.000: 1.1087x smaller Usage over time: b'http://tinyurl.com/7ze4nrv' ### gc ### Mem max: 92460.000 -> 49144.000: 1.8814x smaller Usage over time: b'http://tinyurl.com/7wa9zwg'