Merge BINARY_SUBSCR_LIST_INT with BINARY_SUBSCR_LIST_TUPLE

@eendebakpt

BPO	47251
Nosy	@eendebakpt
PRs	gh-91407: Merge BINARY_SUBSCR_LIST_INT with BINARY_SUBSCR_TUPLE_INT #32404

^{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 = None
created_at = <Date 2022-04-07.19:10:15.380>
labels = ['interpreter-core', '3.11']
title = 'Merge BINARY_SUBSCR_LIST_INT with BINARY_SUBSCR_LIST_TUPLE'
updated_at = <Date 2022-04-07.19:12:32.413>
user = 'https://github.com/eendebakpt'

bugs.python.org fields:

activity = <Date 2022-04-07.19:12:32.413>
actor = 'pieter.eendebak'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2022-04-07.19:10:15.380>
creator = 'pieter.eendebak'
dependencies = []
files = []
hgrepos = []
issue_num = 47251
keywords = ['patch']
message_count = 1.0
messages = ['416937']
nosy_count = 1.0
nosy_names = ['pieter.eendebak']
pr_nums = ['32404']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = None
url = 'https://bugs.python.org/issue47251'
versions = ['Python 3.11']

The implementations of BINARY_SUBSCR_LIST_INT and BINARY_SUBSCR_TUPLE_INT are almost identical. They can be merged, so there is one opcode less and the code is shared.

The code is very similar, but they deal with different underlying objects, so one calls PyList_GET_SIZE() vs PyTuple_GET_SIZE(). Surely they are similar enough to do some refactoring of shared code, but wouldn't there still need to be two different opcodes?

        TARGET(BINARY_SUBSCR_LIST_INT) {
            assert(cframe.use_tracing == 0);
            PyObject *sub = TOP();
            PyObject *list = SECOND();
            DEOPT_IF(!PyLong_CheckExact(sub), BINARY_SUBSCR);
            DEOPT_IF(!PyList_CheckExact(list), BINARY_SUBSCR);

            // Deopt unless 0 <= sub < PyList_Size(list)
            Py_ssize_t signed_magnitude = Py_SIZE(sub);
            DEOPT_IF(((size_t)signed_magnitude) > 1, BINARY_SUBSCR);
            assert(((PyLongObject *)_PyLong_GetZero())->ob_digit[0] == 0);
            Py_ssize_t index = ((PyLongObject*)sub)->ob_digit[0];
            DEOPT_IF(index >= PyList_GET_SIZE(list), BINARY_SUBSCR);
            STAT_INC(BINARY_SUBSCR, hit);
            PyObject *res = PyList_GET_ITEM(list, index);
            assert(res != NULL);
            Py_INCREF(res);
            STACK_SHRINK(1);
            Py_DECREF(sub);
            SET_TOP(res);
            Py_DECREF(list);
            JUMPBY(INLINE_CACHE_ENTRIES_BINARY_SUBSCR);
            NOTRACE_DISPATCH();
        }

        TARGET(BINARY_SUBSCR_TUPLE_INT) {
            assert(cframe.use_tracing == 0);
            PyObject *sub = TOP();
            PyObject *tuple = SECOND();
            DEOPT_IF(!PyLong_CheckExact(sub), BINARY_SUBSCR);
            DEOPT_IF(!PyTuple_CheckExact(tuple), BINARY_SUBSCR);

            // Deopt unless 0 <= sub < PyTuple_Size(list)
            Py_ssize_t signed_magnitude = Py_SIZE(sub);
            DEOPT_IF(((size_t)signed_magnitude) > 1, BINARY_SUBSCR);
            assert(((PyLongObject *)_PyLong_GetZero())->ob_digit[0] == 0);
            Py_ssize_t index = ((PyLongObject*)sub)->ob_digit[0];
            DEOPT_IF(index >= PyTuple_GET_SIZE(tuple), BINARY_SUBSCR);
            STAT_INC(BINARY_SUBSCR, hit);
            PyObject *res = PyTuple_GET_ITEM(tuple, index);
            assert(res != NULL);
            Py_INCREF(res);
            STACK_SHRINK(1);
            Py_DECREF(sub);
            SET_TOP(res);
            Py_DECREF(tuple);
            JUMPBY(INLINE_CACHE_ENTRIES_BINARY_SUBSCR);
            NOTRACE_DISPATCH();
        }

cpython/Python/ceval.c

Line 2105 in 98ff4a6

TARGET(BINARY_SUBSCR_LIST_INT) {

cpython/Include/opcode.h

Line 129 in 2bde682

#define BINARY_SUBSCR_LIST_INT 20

Also, there's a typo in the issue title, it should be BINARY_SUBSCR_TUPLE_INT, not BINARY_SUBSCR_LIST_TUPLE, but I'm not sure how easy it is to change that since this issue was part of the migration.

@kevin-chau

@kevin-chau @markshannon Thanks for the feedback on the PR. Merging the two opcodes does not seem a good idea at this moment. Factoring out common code is possible (see item 4. below), but I would like to know whether this is worth the effort.

Although the two opcodes can be combined into a single opcode, this introduces branching which can hurt performance. This is in the lines

            if (is_list)
              res = PyList_GET_ITEM(sequence, index);
            else
               res = PyTuple_GET_ITEM(sequence, index);

The list object stores the elements in PyObject **ob_item;, whereas the tuple has PyObject *ob_item[1];. I see no method to access these two different structures without some kind of branching.

A performance gain because the two opcodes are actually merged can only happen for strange constructions like

a=[ [1,2,3,4], (1,2,None)] * 100
for seq in a:
	value = seq[1]

I doubt this is common in real code.

To reduce branching I tested combining DOPTS statements, e.g. replace

            DEOPT_IF(!PyLong_CheckExact(sub), BINARY_SUBSCR);
            DEOPT_IF(!PyList_CheckExact(list), BINARY_SUBSCR);

with

DEOPT_IF(!PyLong_CheckExact(sub) || !PyList_CheckExact(list), BINARY_SUBSCR);

(several other variations have been tried as well). This showed no performance improvements

I tried Mark's suggestion to factor out common code of BINARY_SUBSCR_LIST_INT and BINARY_SUBSCR_LIST_TUPLE. The result is in main...eendebakpt:combine_list_tuple_opcode_v3. Factoring out the code is possible, without any performance loss or gain.

Is the factoring out worthwhile to make a new PR for?

Performance benchmarks for 4.

Microbenchmark

import pyperf
runner = pyperf.Runner()

setup='l=[1,2,None,4,5,6,7,8,9,10]; t=(1,None,3,4)'

runner.timeit(name=f"list", stmt=f"x=l[3]",setup=setup)
runner.timeit(name=f"tuple", stmt=f"x=t[2]",setup=setup)
code="""
for ii in range(400):
	idx=ii%4
	a=l[idx]
	b=t[idx]	
"""
runner.timeit(name=f"mixed", stmt=code,setup=setup)

code="""
a=[ [1,2,3,4], (1,2,None)] * 100
for seq in a:
	value = seq[1]
"""
runner.timeit(name=f"mixed_same_opcode", stmt=code,setup=setup)

results in Geometric mean: 1.00x slower

Pyperformance

chaos: Mean +- std dev: [base] 87.8 ms +- 0.8 ms -> [patch] 88.4 ms +- 1.3 ms: 1.01x slower
fannkuch: Mean +- std dev: [base] 514 ms +- 15 ms -> [patch] 524 ms +- 2 ms: 1.02x slower
float: Mean +- std dev: [base] 103 ms +- 2 ms -> [patch] 104 ms +- 1 ms: 1.01x slower
go: Mean +- std dev: [base] 163 ms +- 1 ms -> [patch] 167 ms +- 2 ms: 1.02x slower
hexiom: Mean +- std dev: [base] 7.66 ms +- 0.04 ms -> [patch] 8.05 ms +- 0.06 ms: 1.05x slower
json_dumps: Mean +- std dev: [base] 15.1 ms +- 0.5 ms -> [patch] 15.0 ms +- 0.2 ms: 1.01x faster
logging_silent: Mean +- std dev: [base] 133 ns +- 1 ns -> [patch] 133 ns +- 0 ns: 1.00x slower
nbody: Mean +- std dev: [base] 111 ms +- 2 ms -> [patch] 113 ms +- 1 ms: 1.02x slower
nqueens: Mean +- std dev: [base] 106 ms +- 1 ms -> [patch] 110 ms +- 1 ms: 1.04x slower
pickle_dict: Mean +- std dev: [base] 30.9 us +- 0.2 us -> [patch] 31.2 us +- 1.0 us: 1.01x slower
pickle_list: Mean +- std dev: [base] 4.41 us +- 0.04 us -> [patch] 4.35 us +- 0.04 us: 1.01x faster
pyflate: Mean +- std dev: [base] 532 ms +- 8 ms -> [patch] 557 ms +- 5 ms: 1.05x slower
python_startup: Mean +- std dev: [base] 10.9 ms +- 0.5 ms -> [patch] 10.7 ms +- 0.4 ms: 1.01x faster
raytrace: Mean +- std dev: [base] 381 ms +- 3 ms -> [patch] 378 ms +- 4 ms: 1.01x faster
regex_compile: Mean +- std dev: [base] 163 ms +- 1 ms -> [patch] 167 ms +- 1 ms: 1.03x slower
regex_dna: Mean +- std dev: [base] 238 ms +- 2 ms -> [patch] 240 ms +- 3 ms: 1.01x slower
richards: Mean +- std dev: [base] 57.4 ms +- 1.5 ms -> [patch] 58.0 ms +- 0.8 ms: 1.01x slower
scimark_fft: Mean +- std dev: [base] 447 ms +- 10 ms -> [patch] 443 ms +- 4 ms: 1.01x faster
scimark_lu: Mean +- std dev: [base] 142 ms +- 2 ms -> [patch] 145 ms +- 2 ms: 1.03x slower
scimark_sparse_mat_mult: Mean +- std dev: [base] 6.18 ms +- 0.11 ms -> [patch] 5.87 ms +- 0.09 ms: 1.05x faster
spectral_norm: Mean +- std dev: [base] 150 ms +- 7 ms -> [patch] 146 ms +- 3 ms: 1.02x faster
unpack_sequence: Mean +- std dev: [base] 52.6 ns +- 1.0 ns -> [patch] 53.3 ns +- 1.1 ns: 1.01x slower
unpickle: Mean +- std dev: [base] 15.0 us +- 0.3 us -> [patch] 14.7 us +- 0.2 us: 1.02x faster
unpickle_pure_python: Mean +- std dev: [base] 301 us +- 2 us -> [patch] 303 us +- 2 us: 1.01x slower
xml_etree_parse: Mean +- std dev: [base] 176 ms +- 3 ms -> [patch] 175 ms +- 3 ms: 1.01x faster
xml_etree_process: Mean +- std dev: [base] 71.3 ms +- 0.7 ms -> [patch] 71.8 ms +- 0.6 ms: 1.01x slower

Benchmark hidden because not significant (20): 2to3, deltablue, json_loads, logging_format, logging_simple, meteor_contest, pathlib, pickle, pickle_pure_python, pidigits, python_startup_no_site, regex_effbot, regex_v8, scimark_monte_carlo, scimark_sor, sqlite_synth, telco, unpickle_list, xml_etree_iterparse, xml_etree_generate

Geometric mean: 1.00x slower

@markshannon

@markshannon The issue can be closed afaik. I am not allowed (maybe because it was opened by the mannequin?)

Navigation Menu

Repository navigation

Merge BINARY_SUBSCR_LIST_INT with BINARY_SUBSCR_LIST_TUPLE #91407

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Merge BINARY_SUBSCR_LIST_INT with BINARY_SUBSCR_LIST_TUPLE #91407

Description

Activity

eendebakpt commented on Apr 7, 2022

kevin-chau commented on Apr 11, 2022

eendebakpt commented on Apr 15, 2022

eendebakpt commented on Apr 25, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions