PEP 509: Add ma_version to PyDictObject

[vstinner]

BPO	26058
Nosy	@malemburg, @brettcannon, @pitrou, @vstinner, @bitdancer, @1st1, @jstasiak
Files	dict_version.patch dict_version-2.patch dict_version-3.patch dict_version-4.patch guard_benchmark.patch guard_benchmark.py dict_version-5.patch dict_version-6.patch dict_version-7.patch dict_version-8.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2016-09-08.20:07:22.991>
created_at = <Date 2016-01-09.09:30:48.408>
labels = ['type-feature']
title = 'PEP 509: Add ma_version to PyDictObject'
updated_at = <Date 2016-09-10.04:52:35.818>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2016-09-10.04:52:35.818>
actor = 'python-dev'
assignee = 'none'
closed = True
closed_date = <Date 2016-09-08.20:07:22.991>
closer = 'vstinner'
components = []
creation = <Date 2016-01-09.09:30:48.408>
creator = 'vstinner'
dependencies = []
files = ['41542', '41547', '41581', '41599', '41604', '41605', '41691', '41701', '42476', '42518']
hgrepos = []
issue_num = 26058
keywords = ['patch']
message_count = 31.0
messages = ['257809', '257810', '257814', '257818', '257819', '257820', '257848', '257875', '257880', '257961', '257992', '258138', '258139', '258151', '258820', '258824', '258826', '258867', '263414', '263525', '263726', '263727', '263728', '263729', '263730', '263731', '263732', '263787', '275132', '275133', '275566']
nosy_count = 8.0
nosy_names = ['lemburg', 'brett.cannon', 'pitrou', 'vstinner', 'r.david.murray', 'python-dev', 'yselivanov', 'jstasiak']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue26058'
versions = ['Python 3.6']

[vstinner]

Attached patch implements the following PEP currently discussed on python-ideas:
https://faster-cpython.readthedocs.org/pep_dict_version.html#pep-dict-version

[vstinner]

Result of pybench on Dict microbenchmarks:

              DictCreation:    44ms    49ms  -10.5%    44ms    49ms  -10.7%
         DictWithFloatKeys:    35ms    35ms   -0.5%    35ms    35ms   -1.0%
       DictWithIntegerKeys:    28ms    28ms   -1.2%    28ms    29ms   -2.3%
        DictWithStringKeys:    26ms    27ms   -3.2%    26ms    28ms   -4.8%
    SimpleDictManipulation:    52ms    53ms   -0.7%    53ms    53ms   -0.4%

Hum, as usuall, pybench doesn't seem reliable at all: I expect worse performance with the patch since it adds "version++" in dict.__setimte__(). I don't really trust pybench, results seem to have a lot of noise :-/

Maybe I'm not using pybench correctly? I used:

$ make distclean; ./configure && make
$ ./python Tools/pybench/pybench.py -f pybench.default
$ patch -p1 < dict_version.patch
$ ./python Tools/pybench/pybench.py -f pybench.dictversion
$ ./python Tools/pybench/pybench.py -s pybench.dictversion -c pybench.default

Full output:

-------------------------------------------------------------------------------
PYBENCH 2.1
-------------------------------------------------------------------------------

• using CPython 3.6.0a0 (default:53271aa4d84c+, Jan 9 2016, 10:27:40) [GCC 5.1.1 20150618 (Red Hat 5.1.1-4)]
• disabled garbage collection
• system check interval set to maximum: 2147483647
• using timer: time.perf_counter
• timer: resolution=1e-09, implementation=clock_gettime(CLOCK_MONOTONIC)

-------------------------------------------------------------------------------
Benchmark: pybench.dictversion
-------------------------------------------------------------------------------

Rounds: 10
Warp:   10
Timer:  time.perf_counter

Machine Details:
   Platform ID:    Linux-4.2.5-300.fc23.x86_64-x86_64-with-fedora-23-Twenty_Three
   Processor:      x86_64

Python:
   Implementation: CPython
   Executable:     /home/haypo/prog/python/default/python
   Version:        3.6.0a0
   Compiler:       GCC 5.1.1 20150618 (Red Hat 5.1.1-4)
   Bits:           64bit
   Build:          Jan  9 2016 10:27:40 (#default:53271aa4d84c+)
   Unicode:        UCS4

-------------------------------------------------------------------------------
Comparing with: pybench.default
-------------------------------------------------------------------------------

Rounds: 10
Warp:   10
Timer:  time.perf_counter

Machine Details:
   Platform ID:    Linux-4.2.5-300.fc23.x86_64-x86_64-with-fedora-23-Twenty_Three
   Processor:      x86_64

Python:
   Implementation: CPython
   Executable:     /home/haypo/prog/python/default/python
   Version:        3.6.0a0
   Compiler:       GCC 5.1.1 20150618 (Red Hat 5.1.1-4)
   Bits:           64bit
   Build:          Jan  9 2016 10:21:57 (#default:53271aa4d84c)
   Unicode:        UCS4

Test minimum run-time average run-time
this other diff this other diff
-------------------------------------------------------------------------------
BuiltinFunctionCalls: 42ms 42ms +0.1% 43ms 43ms -0.9%
BuiltinMethodLookup: 26ms 25ms +5.7% 26ms 25ms +5.1%
CompareFloats: 27ms 27ms -0.9% 27ms 28ms -4.2%
CompareFloatsIntegers: 60ms 63ms -3.3% 61ms 65ms -6.8%
CompareIntegers: 41ms 38ms +7.9% 41ms 38ms +7.2%
CompareInternedStrings: 30ms 28ms +5.7% 30ms 28ms +5.0%
CompareLongs: 24ms 22ms +8.6% 24ms 22ms +8.5%
CompareStrings: 22ms 22ms +0.3% 23ms 24ms -6.6%
ComplexPythonFunctionCalls: 43ms 42ms +1.2% 43ms 45ms -5.2%
ConcatStrings: 29ms 32ms -11.0% 29ms 33ms -13.6%
CreateInstances: 45ms 45ms +0.3% 46ms 46ms -0.4%
CreateNewInstances: 34ms 34ms +0.6% 35ms 34ms +0.7%
CreateStringsWithConcat: 58ms 58ms +0.1% 58ms 58ms -0.1%
DictCreation: 44ms 49ms -10.5% 44ms 49ms -10.7%
DictWithFloatKeys: 35ms 35ms -0.5% 35ms 35ms -1.0%
DictWithIntegerKeys: 28ms 28ms -1.2% 28ms 29ms -2.3%
DictWithStringKeys: 26ms 27ms -3.2% 26ms 28ms -4.8%
ForLoops: 22ms 22ms +0.4% 22ms 22ms +0.6%
IfThenElse: 34ms 34ms +0.9% 34ms 34ms +0.8%
ListSlicing: 34ms 34ms -0.2% 34ms 34ms -0.1%
NestedForLoops: 37ms 36ms +2.1% 37ms 36ms +2.1%
NestedListComprehensions: 36ms 35ms +1.4% 36ms 36ms +1.8%
NormalClassAttribute: 75ms 77ms -2.5% 75ms 77ms -2.3%
NormalInstanceAttribute: 37ms 37ms +2.2% 38ms 37ms +2.5%
PythonFunctionCalls: 37ms 36ms +1.8% 37ms 37ms +1.6%
PythonMethodCalls: 50ms 47ms +5.5% 50ms 48ms +4.5%
Recursion: 61ms 61ms -0.2% 61ms 62ms -0.2%
SecondImport: 35ms 36ms -2.9% 35ms 37ms -3.3%
SecondPackageImport: 37ms 37ms -0.3% 37ms 37ms -0.4%
SecondSubmoduleImport: 89ms 87ms +2.1% 90ms 88ms +1.6%
SimpleComplexArithmetic: 23ms 23ms +0.0% 24ms 24ms -0.1%
SimpleDictManipulation: 52ms 53ms -0.7% 53ms 53ms -0.4%
SimpleFloatArithmetic: 25ms 25ms -1.2% 25ms 25ms -1.0%
SimpleIntFloatArithmetic: 32ms 32ms -0.3% 32ms 32ms -1.1%
SimpleIntegerArithmetic: 32ms 32ms -0.6% 32ms 32ms -0.3%
SimpleListComprehensions: 29ms 28ms +2.3% 30ms 29ms +3.2%
SimpleListManipulation: 27ms 28ms -1.3% 28ms 28ms -1.4%
SimpleLongArithmetic: 22ms 22ms +3.6% 23ms 22ms +4.4%
SmallLists: 38ms 38ms -1.9% 38ms 41ms -7.0%
SmallTuples: 47ms 44ms +7.8% 47ms 44ms +7.5%
SpecialClassAttribute: 75ms 73ms +2.3% 75ms 73ms +2.2%
SpecialInstanceAttribute: 38ms 39ms -1.8% 38ms 39ms -2.1%
StringMappings: 84ms 83ms +0.8% 84ms 84ms +0.5%
StringPredicates: 49ms 49ms -0.6% 49ms 49ms -1.0%
StringSlicing: 42ms 42ms +0.8% 42ms 42ms +0.7%
TryExcept: 25ms 25ms -0.4% 25ms 25ms -0.8%
TryFinally: 31ms 31ms +1.1% 32ms 31ms +1.4%
TryRaiseExcept: 12ms 12ms -0.8% 12ms 12ms -1.4%
TupleSlicing: 43ms 43ms +0.1% 43ms 43ms -0.6%
WithFinally: 49ms 50ms -0.9% 49ms 50ms -0.9%
WithRaiseExcept: 39ms 39ms -0.6% 39ms 40ms -1.6%
-------------------------------------------------------------------------------
Totals: 2011ms 2006ms +0.2% 2025ms 2035ms -0.5%

(this=pybench.dictversion, other=pybench.default)

[vstinner]

Using timeit to microbenchmark dict operations (constructor, __setitem__, __delitem__, clear), I get exactly the same performance or even better performance (???) with the patch.

./python -m timeit 'd={1: 0}; d[2]=0; d[3]=0; d[4]=0; del d[1]; del d[2]; d.clear()'

Original: 318 ns
Patched: 318 ns

./python -m timeit 'd={i:i for i in range(2**16)}' 'for i in range(2**16): d[i]=i-1' 'for i in range(2**16): d[i]=i+1' 'for i in range(2**15): del d[i]' 'd.clear()'

Original: 19.9 ms
Patched: 18.9 ms (5% faster)

[vstinner]

Updated patch, I forgot to include unit tests.

I added a test on integer overflow on the version. The patch adds _testcapi.dict_setversion(dict, version) and _testcapi.PY_SIZE_MAX.

[pitrou]

I don't understand this:

The version 0 is reserved for "missing key"

[vstinner]

I don't understand this:
> The version 0 is reserved for "missing key"

Oh, ignore it, it's an outdated comment :-) Dictionary version is initialized to 0, it's not more "reserved".

FYI I added the comment in my first implementation which also added a version to dictionary *entries*.

[brettcannon]

A better way to benchmark this is to run hg.python.org/benchmarks with a patched interpreter and see if that shows any performance impact.

[vstinner]

Brett:

A better way to benchmark this is to run hg.python.org/benchmarks with a patched interpreter and see if that shows any performance impact.

Ok. Here is the output. Can you please explain me the result? :-) Especially the "significant" value.

$ ./python.orig ../benchmarks/perf.py ./python.orig ./python.patched

INFO:root:Automatically selected timer: perf_counter
INFO:root:Running ./python.patched ../benchmarks/lib3/2to3/2to3 -f all ../benchmarks/lib/2to3
INFO:root:Running ./python.patched ../benchmarks/lib3/2to3/2to3 -f all ../benchmarks/lib/2to3 1 time
INFO:root:Running ./python.orig ../benchmarks/lib3/2to3/2to3 -f all ../benchmarks/lib/2to3
INFO:root:Running ./python.orig ../benchmarks/lib3/2to3/2to3 -f all ../benchmarks/lib/2to3 1 time
INFO:root:Running ./python.patched ../benchmarks/performance/bm_chameleon_v2.py -n 50 --timer perf_counter
INFO:root:Running ./python.orig ../benchmarks/performance/bm_chameleon_v2.py -n 50 --timer perf_counter
INFO:root:Running ./python.patched ../benchmarks/performance/bm_django_v3.py -n 50 --timer perf_counter
INFO:root:Running ./python.orig ../benchmarks/performance/bm_django_v3.py -n 50 --timer perf_counter
INFO:root:Running ./python.patched ../benchmarks/performance/bm_pickle.py -n 50 --timer perf_counter --use_cpickle pickle
INFO:root:Running ./python.orig ../benchmarks/performance/bm_pickle.py -n 50 --timer perf_counter --use_cpickle pickle
INFO:root:Running ./python.patched ../benchmarks/performance/bm_pickle.py -n 50 --timer perf_counter --use_cpickle unpickle
INFO:root:Running ./python.orig ../benchmarks/performance/bm_pickle.py -n 50 --timer perf_counter --use_cpickle unpickle
INFO:root:Running ./python.patched ../benchmarks/performance/bm_json_v2.py -n 50 --timer perf_counter
INFO:root:Running ./python.orig ../benchmarks/performance/bm_json_v2.py -n 50 --timer perf_counter
INFO:root:Running ./python.patched ../benchmarks/performance/bm_json.py -n 50 --timer perf_counter json_load
INFO:root:Running ./python.orig ../benchmarks/performance/bm_json.py -n 50 --timer perf_counter json_load
INFO:root:Running ./python.patched ../benchmarks/performance/bm_nbody.py -n 50 --timer perf_counter
INFO:root:Running ./python.orig ../benchmarks/performance/bm_nbody.py -n 50 --timer perf_counter
INFO:root:Running ./python.patched ../benchmarks/performance/bm_regex_v8.py -n 50 --timer perf_counter
INFO:root:Running ./python.orig ../benchmarks/performance/bm_regex_v8.py -n 50 --timer perf_counter
INFO:root:Running ./python.patched ../benchmarks/performance/bm_tornado_http.py -n 100 --timer perf_counter
INFO:root:Running ./python.orig ../benchmarks/performance/bm_tornado_http.py -n 100 --timer perf_counter
[ 1/10] 2to3...
[ 2/10] chameleon_v2...
[ 3/10] django_v3...
[ 4/10] fastpickle...
[ 5/10] fastunpickle...
[ 6/10] json_dump_v2...
[ 7/10] json_load...
[ 8/10] nbody...
[ 9/10] regex_v8...
[10/10] tornado_http...

Report on Linux smithers 4.2.8-300.fc23.x86_64 #1 SMP Tue Dec 15 16:49:06 UTC 2015 x86_64 x86_64
Total CPU cores: 8

### 2to3 ###
6.825440 -> 6.996616: 1.03x slower

### fastpickle ###
Min: 0.449710 -> 0.458054: 1.02x slower
Avg: 0.451589 -> 0.583100: 1.29x slower
Significant (t=-8.04)
Stddev: 0.00076 -> 0.11568: 152.3886x larger

### fastunpickle ###
Min: 0.549672 -> 0.545734: 1.01x faster
Avg: 0.551284 -> 0.696920: 1.26x slower
Significant (t=-6.65)
Stddev: 0.00118 -> 0.15493: 130.9694x larger

### json_load ###
Min: 0.432500 -> 0.466602: 1.08x slower
Avg: 0.433771 -> 0.471205: 1.09x slower
Significant (t=-10.63)
Stddev: 0.00495 -> 0.02440: 4.9303x larger

### nbody ###
Min: 0.230055 -> 0.234925: 1.02x slower
Avg: 0.230985 -> 0.236441: 1.02x slower
Significant (t=-7.56)
Stddev: 0.00048 -> 0.00508: 10.5095x larger

The following not significant results are hidden, use -v to show them:
chameleon_v2, django_v3, json_dump_v2, regex_v8, tornado_http.

[brettcannon]

So min is the fastest time in a benchmark execution, average is the average across all benchmark executions, and the t-value is some statistics thing. Anything marked insignificant had such a small average difference it isn't worth reporting.

If you want to smooth out the numbers you should do a rigorous run that uses more loops per benchmark to help smooth out outliers. And if you are doing this on Linux there is a flag to measure memory usage as well.

[vstinner]

The PEP is now at python.org: PEP-509.

[vstinner]

Patch version 3 updated for the second version of the PEP-509. Main changes:

• ma_version now has the type PY_UINT64_T
• remove dict.__version__ property: replace with _testcapi.dict_get_version() for tests

[vstinner]

Patch version 4: I forgot to include my patch to update test_sys. Now the full Python test suite pass.

[vstinner]

I'm not a big fan of pybench (it looks unstable and so not reliable), but here are results with dict_version-4.patch.

I used more loops and a lower warp factor to get more reliable tests (I hope):

./python Tools/pybench/pybench.py -f pybench.orig -w 2 -C 100 -n 25
./python.patched Tools/pybench/pybench.py -f pybench.dictver -w 2 -C 100 -n 25
./python Tools/pybench/pybench.py -s pybench.dictver -c pybench.orig

-------------------------------------------------------------------------------
PYBENCH 2.1
-------------------------------------------------------------------------------

• using CPython 3.6.0a0 (default:77d24f51effc+, Jan 13 2016, 11:27:53) [GCC 5.3.1 20151207 (Red Hat 5.3.1-2)]
• disabled garbage collection
• system check interval set to maximum: 2147483647
• using timer: time.perf_counter
• timer: resolution=1e-09, implementation=clock_gettime(CLOCK_MONOTONIC)

-------------------------------------------------------------------------------
Benchmark: pybench.dictver
-------------------------------------------------------------------------------

Rounds: 25
Warp:   2
Timer:  time.perf_counter

Machine Details:
   Platform ID:    Linux-4.2.8-300.fc23.x86_64-x86_64-with-fedora-23-Twenty_Three
   Processor:      x86_64

Python:
   Implementation: CPython
   Executable:     /home/haypo/prog/python/default/python
   Version:        3.6.0a0
   Compiler:       GCC 5.3.1 20151207 (Red Hat 5.3.1-2)
   Bits:           64bit
   Build:          Jan 13 2016 11:27:53 (#default:77d24f51effc+)
   Unicode:        UCS4

-------------------------------------------------------------------------------
Comparing with: pybench.orig
-------------------------------------------------------------------------------

Rounds: 25
Warp:   2
Timer:  time.perf_counter

Machine Details:
   Platform ID:    Linux-4.2.8-300.fc23.x86_64-x86_64-with-fedora-23-Twenty_Three
   Processor:      x86_64

Python:
   Implementation: CPython
   Executable:     /home/haypo/prog/python/default/python
   Version:        3.6.0a0
   Compiler:       GCC 5.3.1 20151207 (Red Hat 5.3.1-2)
   Bits:           64bit
   Build:          Jan 13 2016 11:14:50 (#default:77d24f51effc)
   Unicode:        UCS4

Test minimum run-time average run-time
this other diff this other diff
-------------------------------------------------------------------------------
BuiltinFunctionCalls: 230ms 229ms +0.4% 241ms 230ms +5.1%
BuiltinMethodLookup: 130ms 132ms -1.2% 135ms 134ms +0.4%
CompareFloats: 147ms 149ms -1.4% 151ms 149ms +1.2%
CompareFloatsIntegers: 330ms 333ms -0.8% 347ms 335ms +3.6%
CompareIntegers: 214ms 209ms +2.5% 223ms 209ms +6.5%
CompareInternedStrings: 160ms 145ms +10.8% 170ms 145ms +16.9%
CompareLongs: 121ms 120ms +0.2% 124ms 120ms +3.4%
CompareStrings: 132ms 131ms +0.7% 138ms 132ms +4.8%
ComplexPythonFunctionCalls: 233ms 235ms -0.7% 241ms 238ms +1.1%
ConcatStrings: 166ms 165ms +0.3% 177ms 167ms +6.0%
CreateInstances: 240ms 247ms -3.1% 253ms 249ms +1.5%
CreateNewInstances: 178ms 186ms -4.2% 188ms 188ms +0.1%
CreateStringsWithConcat: 315ms 316ms -0.5% 331ms 318ms +4.3%
DictCreation: 254ms 236ms +7.8% 262ms 237ms +10.5%
DictWithFloatKeys: 211ms 199ms +6.1% 219ms 201ms +8.9%
DictWithIntegerKeys: 171ms 163ms +5.4% 180ms 166ms +9.0%
DictWithStringKeys: 163ms 142ms +14.5% 170ms 144ms +17.7%
ForLoops: 121ms 121ms -0.3% 125ms 124ms +0.9%
IfThenElse: 179ms 178ms +0.7% 185ms 178ms +3.6%
ListSlicing: 194ms 193ms +0.4% 198ms 194ms +2.2%
NestedForLoops: 212ms 210ms +1.2% 220ms 210ms +4.6%
NestedListComprehensions: 205ms 212ms -3.3% 218ms 215ms +1.5%
NormalClassAttribute: 429ms 407ms +5.5% 446ms 408ms +9.3%
NormalInstanceAttribute: 212ms 206ms +2.8% 226ms 209ms +8.0%
PythonFunctionCalls: 208ms 210ms -1.4% 215ms 212ms +1.2%
PythonMethodCalls: 275ms 253ms +8.7% 293ms 255ms +14.9%
Recursion: 333ms 328ms +1.4% 366ms 329ms +11.0%
SecondImport: 190ms 188ms +0.8% 201ms 188ms +6.7%
SecondPackageImport: 195ms 192ms +1.8% 214ms 192ms +11.7%
SecondSubmoduleImport: 472ms 447ms +5.7% 502ms 455ms +10.3%
SimpleComplexArithmetic: 141ms 138ms +2.1% 146ms 139ms +5.2%
SimpleDictManipulation: 287ms 288ms -0.3% 313ms 290ms +8.0%
SimpleFloatArithmetic: 138ms 137ms +0.7% 151ms 140ms +7.9%
SimpleIntFloatArithmetic: 172ms 180ms -4.3% 182ms 181ms +0.4%
SimpleIntegerArithmetic: 172ms 169ms +1.9% 184ms 170ms +8.1%
SimpleListComprehensions: 166ms 167ms -0.7% 179ms 173ms +3.3%
SimpleListManipulation: 159ms 153ms +3.9% 166ms 155ms +7.6%
SimpleLongArithmetic: 118ms 117ms +1.2% 123ms 118ms +4.3%
SmallLists: 210ms 204ms +2.8% 221ms 205ms +7.3%
SmallTuples: 244ms 252ms -3.1% 255ms 256ms -0.2%
SpecialClassAttribute: 424ms 416ms +1.8% 442ms 419ms +5.5%
SpecialInstanceAttribute: 214ms 211ms +1.3% 223ms 214ms +4.5%
StringMappings: 442ms 446ms -0.8% 460ms 447ms +2.9%
StringPredicates: 259ms 258ms +0.2% 281ms 260ms +8.2%
StringSlicing: 218ms 220ms -1.2% 228ms 221ms +3.3%
TryExcept: 130ms 135ms -3.9% 134ms 136ms -1.4%
TryFinally: 173ms 171ms +0.9% 180ms 172ms +4.4%
TryRaiseExcept: 62ms 63ms -1.2% 63ms 63ms +0.9%
TupleSlicing: 223ms 224ms -0.3% 251ms 232ms +8.0%
WithFinally: 263ms 264ms -0.4% 280ms 265ms +5.4%
WithRaiseExcept: 205ms 203ms +0.7% 215ms 204ms +5.5%
-------------------------------------------------------------------------------
Totals: 11040ms 10900ms +1.3% 11635ms 10991ms +5.9%

(this=pybench.dictver, other=pybench.orig)