I've been working on this idea for a couple of days. Tim Peters has being helping me out and I think it has come far enough to get some more feedback. It is not yet a good replacement for the current address_in_range() test. However, performance wise, it is very close. Tim figures we are not done optimizing it yet so maybe it will get better.
Code is available on my github branch:
https://github.com/nascheme/cpython/tree/obmalloc_radix_tree
Tim's "obmalloc-big-pools" is what I have been comparing it to. It seems 8 KB pools are faster than 4 KB. I applied Tim's arena trashing fix (bpo-37257) to both branches. Some rough (--fast) pyperformance benchmark results are below.
+-------------------------+---------------------+-----------------------------+ | Benchmark | obmalloc-big-pools | obmalloc_radix | +=========================+=====================+=============================+ | crypto_pyaes | 168 ms | 170 ms: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+ | hexiom | 13.7 ms | 13.6 ms: 1.01x faster (-1%) | +-------------------------+---------------------+-----------------------------+ | json_dumps | 15.9 ms | 15.6 ms: 1.02x faster (-2%) | +-------------------------+---------------------+-----------------------------+ | json_loads | 36.9 us | 37.1 us: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+ | meteor_contest | 141 ms | 139 ms: 1.02x faster (-2%) | +-------------------------+---------------------+-----------------------------+ | nqueens | 137 ms | 140 ms: 1.02x slower (+2%) | +-------------------------+---------------------+-----------------------------+ | pickle_dict | 26.2 us | 25.9 us: 1.01x faster (-1%) | +-------------------------+---------------------+-----------------------------+ | pickle_list | 3.91 us | 3.94 us: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+ | python_startup_no_site | 8.00 ms | 7.78 ms: 1.03x faster (-3%) | +-------------------------+---------------------+-----------------------------+ | regex_dna | 246 ms | 241 ms: 1.02x faster (-2%) | +-------------------------+---------------------+-----------------------------+ | regex_v8 | 29.6 ms | 30.0 ms: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+ | richards | 93.9 ms | 92.7 ms: 1.01x faster (-1%) | +-------------------------+---------------------+-----------------------------+ | scimark_fft | 525 ms | 531 ms: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+ | scimark_sparse_mat_mult | 6.32 ms | 6.24 ms: 1.01x faster (-1%) | +-------------------------+---------------------+-----------------------------+ | spectral_norm | 195 ms | 198 ms: 1.02x slower (+2%) | +-------------------------+---------------------+-----------------------------+ | sqlalchemy_imperative | 49.5 ms | 50.5 ms: 1.02x slower (+2%) | +-------------------------+---------------------+-----------------------------+ | sympy_expand | 691 ms | 695 ms: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+ | unpickle_list | 5.09 us | 5.32 us: 1.04x slower (+4%) | +-------------------------+---------------------+-----------------------------+ | xml_etree_parse | 213 ms | 215 ms: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+ | xml_etree_generate | 134 ms | 136 ms: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+ | xml_etree_process | 103 ms | 104 ms: 1.01x slower (+1%) | +-------------------------+---------------------+-----------------------------+
Not significant (34): 2to3; chameleon; chaos; deltablue; django_template; dulwich_log; fannkuch; float; go; html5lib; logging_format; logging_silent; logging_simple; mako; nbody; pathlib; pickle; pidigits; python_startup; raytrace; regex_compile; regex_effbot; scimark_lu; scimark_monte_carlo; scimark_sor; sqlalchemy_declarative; sqlite_synth; sympy_integrate; sympy_sum; sympy_str; telco; unpack_sequence; unpickle; xml_etree_iterparse