Curiously, some time ago Ethan Furman discussed on Python Ideas the introduction of a method in Enum that check if the Enum has a member without raising and exception. He said that it was a question asked a lot on StackOverflow. Guido van Rossum asked about the SO questions, Ethan linked them and nobody had raised some doubts about the widespread of the necessity.
Anyway, I’ve done a little experiment. I implemented a naive version of sort() for dict(). I have not yet implemented a mergesort for dict, so the speedup is not extraordinary, but also not negligible:
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ sudo pyperf system tune
[sudo] password for marco:
Tune the system configuration to run benchmarks
Actions
=======
CPU Frequency: Minimum frequency of CPU 0-3 set to the maximum frequency
System state
============
CPU: use 4 logical CPUs: 0-3
Perf event: Maximum sample rate: 1 per second
ASLR: Full randomization
Linux scheduler: No CPU is isolated
CPU Frequency: 0-3=min=max=2600 MHz
CPU scaling governor (intel_pstate): performance
Turbo Boost (intel_pstate): Turbo Boost disabled
IRQ affinity: irqbalance service: inactive
IRQ affinity: Default IRQ affinity: CPU 0-3
IRQ affinity: IRQ affinity: IRQ 0-17,51,67,120-131=CPU 0-3
Power supply: the power cable is plugged
Advices
=======
Linux scheduler: Use isolcpus=<cpu list> kernel parameter to isolate CPUs
Linux scheduler: Use rcu_nocbs=<cpu list> kernel parameter (with isolcpus) to not schedule RCU on isolated CPUs
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ pyperf timeit --rigorous -s "d = {k:k for k in range(16)}" "dict(sorted(d.items()))"
.........................................
Mean +- std dev: 1.85 us +- 0.03 us
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ pyperf timeit --rigorous -s "d = {k:k for k in range(16)}" "d.sort()"
.........................................
Mean +- std dev: 1.10 us +- 0.01 us
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ pyperf timeit --rigorous -s "d = {k:k for k in range(1000)}" "dict(sorted(d.items()))"
.........................................
Mean +- std dev: 86.0 us +- 0.6 us
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ pyperf timeit --rigorous -s "d = {k:k for k in range(1000)}" "d.sort()"
.........................................
Mean +- std dev: 80.7 us +- 1.0 us
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ pyperf timeit --rigorous -s "d = {k:k for k in range(16, -1, -1)}" "dict(sorted(d.items()))"
.........................................
Mean +- std dev: 1.92 us +- 0.02 us
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ pyperf timeit --rigorous -s "d = {k:k for k in range(16, -1, -1)}" "d.sort()"
.........................................
Mean +- std dev: 1.17 us +- 0.01 us
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ pyperf timeit --rigorous -s "d = {k:k for k in range(1000, -1, -1)}" "dict(sorted(d.items()))"
.........................................
Mean +- std dev: 86.4 us +- 0.9 us
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ pyperf timeit --rigorous -s "d = {k:k for k in range(1000, -1, -1)}" "d.sort()"
.........................................
Mean +- std dev: 81.0 us +- 1.1 us
(venv) marco@buzz:~/sources/cpython_new_build_optimized$ python
Python 3.11.0a0 (heads/dict_sort-dirty:fa106a685c, Jun 5 2021, 19:59:25) [GCC 7.5.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> d = {k:k for k in range(16, -1, -1)}
>>> d
{16: 16, 15: 15, 14: 14, 13: 13, 12: 12, 11: 11, 10: 10, 9: 9, 8: 8, 7: 7, 6: 6, 5: 5, 4: 4, 3: 3, 2: 2, 1: 1, 0: 0}
>>> d.sort()
>>> d
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10, 11: 11, 12: 12, 13: 13, 14: 14, 15: 15, 16: 16}
>>>
The testing build was an optimized one. Notice that:
- the keywords does not work for now.
dictis only sorted from lowest to highest without any key function applied, and the sort is done on keys only - the current implementation takes not into account shared
dicts or holes indict - no success/sanity check is done for things like PyList_New
Anyway, I think this is promising. If I’ll be able to copy the mergesort of list and adapt it to dict, I suppose the speedup will be higher.