BINARY_OP_INPLACE_ADD_UNICODE has lots of misses

[sweeneyde]

According to https://github.com/faster-cpython/ideas/blob/main/stats.md:

Name	Count	Self	Cumulative	Miss ratio
BINARY_OP_INPLACE_ADD_UNICODE	325389	0.0%	100.0%	73.7%

I measured individual benchmarks with rm C:\temp\py_stats\*; .\python.bat .\Lib\site-packages\pyperformance\benchmarks\bm_regex_compile.py --fast; .\python.bat .\Tools\scripts\summarize_stats.py:

benchmark	INPLACE_ADD_UNICODE count	Miss ratio
bm_2to3	13816	52.3%
bm_chameleon	32461	7.8%
bm_chaos	2540	40.6%
bm_crypto_pyaes	2672	43.6%
bm_deltablue	2540	40.6%
bm_django_template	7138	68.5%
bm_dulwich_log	55317	3.4%
bm_fannkuch	2540	40.6%
bm_float	2540	40.6%
bm_go	2540	40.6%
bm_hexiom	2540	40.6%
bm_html5lib	2235	65.3%
bm_json_dumps	2540	40.6%
bm_json_loads	2540	40.6%
bm_logging	4689	52.5%
bm_mako	3132	51.9%
bm_meteor_contest	2540	40.6%
bm_nbody	2540	40.6%
bm_nqueens	2540	40.6%
bm_pathlib	26996	0.1%
bm_pickle	2584	41.6%
bm_pidigits	2540	40.6%
bm_pyflate	2586	40.8%
bm_raytrace	2540	40.6%
bm_regex_compile	2584	41.6%
bm_regex_dna	2540	40.6%
bm_regex_effbot	2540	40.6%
bm_regex_v8	2540	40.6%
bm_richards	2540	40.6%
bm_scimark	12132	40.1%
bm_spectral_norm	2540	40.6%
bm_sqlite_synth	2584	41.6%
bm_sympy	35504	80.3%
bm_telco	2564	40.2%
bm_tornado_http	4554	56.9%
bm_unpack_sequence	2540	40.6%
bm_xml_etree	11804	42.8%

This seems to point to something within pyperf/pyperformance doing some string concatenation with +=.

[TeamSpen210]

It seems this specialisation is going to have a lot of misses. When specialising it doesn't check the add op is assigning back to the 1st argument, just that the LHS argument has a refcount of 2. So it'd trigger for a = b + c which would immediately fail. Since we do want the RHS to be any expression though, it'd kinda difficult to backtrack through stack effects to figure out which opcode did the LHS reading. To eliminate misses this probably needs compiler help? One way would be to add duplicate function pointers in the BINARY_OP oparg table, (eg NB_OVERWRITING_ADD) that the specialisation can check. That could be a slowdown though, and would show up in disassembly output etc.

[brandtbucher]

Adding a check for op == NB_INPLACE_ADD at specialization time would be a simple way to protect against this.

It wouldn't work for the a = a + b case anymore... but I'm not sure how common that is. It would be interesting to see if that drops the miss rate without significantly impacting the ratio of BINARY_OP_INPLACE_ADD_UNICODE / BINARY_OP_ADD_UNICODE instructions.

[brandtbucher]

This seems to point to something within pyperf/pyperformance doing some string concatenation with +=.

Yup, the 2540 / 40.6% pairs are suspicious.

I personally like the side-effect of including pyperformance in our stats, though. It's probably the closest thing the current suite has to a real, modern macrobenchmark!

(Also, I think this means pyperformance is doing string concatenation with +, not +=. See my comment above.)

[arhadthedev]

Also, I think this means pyperformance is doing string concatenation with +, not +=.

It looks like it. With (?<var>[a-zA-Z_]+) = \g{var} \+ regex I found three occurences:

• https://github.com/python/pyperformance/blob/034f58b/pyperformance/compile.py#L497
• https://github.com/python/pyperformance/blob/034f58b/pyperformance/data-files/benchmarks/bm_2to3/data/2to3/urlresolvers.py.txt#L350
• https://github.com/python/pyperformance/blob/034f58b/runtests.py#L40

To replace them, I created python/pyperformance#136. Unfortunately, I don't know what command was used to generate original stats.md so I couldn't collect and attach statistics for comparison.

[brandtbucher]

I recommend that you close the PR. It doesn't seem very well-thought-out to me:

• https://github.com/python/pyperformance/blob/034f58b/pyperformance/compile.py#L497

I don't think compile.py is used in the command the above stats were generated from. Even if it is hit, that particular line is probably not "hot" code.

• https://github.com/python/pyperformance/blob/034f58b/pyperformance/data-files/benchmarks/bm_2to3/data/2to3/urlresolvers.py.txt#L350

We definitely shouldn't be modifying the benchmarks to match the assumptions made by our specializations.

• https://github.com/python/pyperformance/blob/034f58b/runtests.py#L40

runtests.py is only used to run pyperformance's own tests. And, that particular line is adding tuples, not strings.

I think our time is better spent fixing CPython's BINARY_OP_INPLACE_ADD_UNICODE logic, rather than trying to hunt down and "fix" the code that found the problem in the first place.

[sweeneyde]

Adding some debugging code, it looks like this method in the re module is a major source of the instability:

https://github.com/python/cpython/blob/f4c03484da59049eb62a9bf7777b963e2267d187/Lib/sre_parse.py#L267-L282

In particular, with some hasty printf debugging

            if (Py_REFCNT(left) != 2) {
                printf("Wrong refcount (%d not 2)! in %s\n", (int)Py_REFCNT(left), PyUnicode_AsUTF8(frame->f_code->co_qualname));
                printf("LHS: %s\n", PyUnicode_AsUTF8(left));
                printf("RHS: %s\n", PyUnicode_AsUTF8(right));
            }
            DEOPT_IF(Py_REFCNT(left) != 2, BINARY_OP);

I got things like this

Wrong refcount (1000000113 not 2)! in Tokenizer.getuntil
LHS:
RHS: d
Wrong refcount (5 not 2)! in Tokenizer.getuntil
LHS: d
RHS: e
Wrong refcount (1000000113 not 2)! in Tokenizer.getuntil
LHS:
RHS: d
Wrong refcount (5 not 2)! in Tokenizer.getuntil
LHS: d
RHS: e
Wrong refcount (1000000113 not 2)! in Tokenizer.getuntil
LHS:
RHS: e
Wrong refcount (5 not 2)! in Tokenizer.getuntil
LHS: e
RHS: x
Wrong refcount (1000000153 not 2)! in Tokenizer.getuntil
LHS:
RHS: W
Wrong refcount (4 not 2)! in Tokenizer.getuntil
LHS: W
RHS: H
Wrong refcount (1000000153 not 2)! in Tokenizer.getuntil
LHS:
RHS: N
Wrong refcount (7 not 2)! in Tokenizer.getuntil
LHS: N
RHS: U
Wrong refcount (1000000153 not 2)! in Tokenizer.getuntil
LHS:
RHS: N
Wrong refcount (7 not 2)! in Tokenizer.getuntil
LHS: N
RHS: A
Wrong refcount (1000000153 not 2)! in Tokenizer.getuntil
LHS:
RHS: P
Wrong refcount (6 not 2)! in Tokenizer.getuntil
LHS: P
RHS: A
Wrong refcount (1000000153 not 2)! in Tokenizer.getuntil
LHS:
RHS: O
Wrong refcount (5 not 2)! in Tokenizer.getuntil
LHS: O
RHS: P
Wrong refcount (1000000153 not 2)! in Tokenizer.getuntil
LHS:
RHS: I

[sweeneyde]

This reminds me, is there a reason single-ascii-character strs aren't static global strings? Wouldn't that make some str iterators faster?

[TeamSpen210]

All simgle-character latin1 strings should be cached, I wonder why they're don't seem to be in this code? Regardless, I wonder if adding a check for "" + str in BINARY_OP_INPLACE_ADD_UNICODE to avoid deoptimising accumulation code like this would be worth it. It'd definitely be code that's usually in a tight loop...

[ericsnowcurrently]

is there a reason single-ascii-character strs aren't static global strings?

We haven't gotten to making them static global yet.

[sweeneyde]

Since this specialization seems rather miss-prone, one solution would be to be more permissive in what is allowed to pass DEOPT_IF checks, and then have a branch in the instruction body to check whether we can operate in place, and to do so if possible, but to create a new str object if not.

In other words, if specialization catches a situation where we can operate in place, we interpret this as meaning that this bytecode only sometimes is able to operate in place.

In fact, PyUnicode_Append(&TOP(), right); already incorporates this logic, checking for unicode_modifiable. So the change would be as simple as removing the line DEOPT_IF(Py_REFCNT(left) != 2, BINARY_OP);.

Too many misses? Eliminate the code that checks for misses ;-)

[sweeneyde]

I opened python/cpython#31318

[sweeneyde]

With this change, all of the (2540, 40.6%) pairs above turn into (4109, 0.0%) pairs.

[sweeneyde]

The result is almost zero misses:

Benchmark	UNICODE_INPLACE_ADD count	Miss ratio
bm_2to3	191862
bm_chameleon	80045
bm_chaos	4109
bm_crypto_pyaes	4109
bm_deltablue	4109
bm_django_template	10545
bm_dulwich_log	108433	0.1%
bm_fannkuch	4109
bm_float	4109
bm_go	4109
bm_hexiom	4109
bm_html5lib	9787
bm_json_dumps	4075
bm_json_loads	4075
bm_logging	15511
bm_mako	6390
bm_meteor_contest	4109
bm_nbody	4109
bm_nqueens	4109
bm_pathlib	52503
bm_pickle	4109
bm_pidigits	4109
bm_pyflate	4157
bm_raytrace	4109
bm_regex_compile	129769
bm_regex_dna	4109
bm_regex_effbot	4120
bm_regex_v8	8993
bm_richards	4109
bm_scimark	19905
bm_spectral_norm	4109
bm_sqlite_synth	4109
bm_sympy	27069
bm_telco	4157
bm_tornado_http	7949
bm_unpack_sequence	4109
bm_xml_etree	18443