Integer operations are inefficient for "medium" integers.

[markshannon]

BPO	44946
Nosy	@mdickinson, @vstinner, @markshannon, @xuxinhang
PRs	bpo-44946: Streamline operators and creation of ints for common case of single 'digit'. #27832 bpo-46055: Speed up binary shifting operators #30044

^{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 2021-08-26.15:09:37.280>
created_at = <Date 2021-08-18.10:25:32.126>
labels = ['interpreter-core', 'performance']
title = 'Integer operations are inefficient for "medium" integers.'
updated_at = <Date 2021-12-11.04:39:53.226>
user = 'https://github.com/markshannon'

bugs.python.org fields:

activity = <Date 2021-12-11.04:39:53.226>
actor = 'xuxinhang'
assignee = 'none'
closed = True
closed_date = <Date 2021-08-26.15:09:37.280>
closer = 'Mark.Shannon'
components = ['Interpreter Core']
creation = <Date 2021-08-18.10:25:32.126>
creator = 'Mark.Shannon'
dependencies = []
files = []
hgrepos = []
issue_num = 44946
keywords = ['patch']
message_count = 5.0
messages = ['399832', '399833', '399834', '399838', '400263']
nosy_count = 4.0
nosy_names = ['mark.dickinson', 'vstinner', 'Mark.Shannon', 'xuxinhang']
pr_nums = ['27832', '30044']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue44946'
versions = []

[markshannon]

"Medium" integers are those with a single internal digit or zero.
Medium integers are integers in the range -2**30 to +2**30 on 64 bit machines.
"Small" integers, -5 to 256 are cached, but are represented as medium integers internally.

To a good approximation, all integers are "medium".

However, we make little effort to exploit that fact in the code for binary operations, which are very common operations on integers.

[mdickinson]

We already special-case medium integers in the Objects/longobject.c code, in various places. For example for addition, here:

cpython/Objects/longobject.c

Lines 3070 to 3072 in 3240bc6

	if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
	return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
	}

Are you proposing further changes in longobject.c, or some other mechanism?

[mdickinson]

See also bpo-21955, bpo-10044, and

cpython/Python/ceval.c

Lines 1986 to 1991 in 3240bc6

	/* NOTE(vstinner): Please don't try to micro-optimize int+int on
	CPython using bytecode, it is simply worthless.
	See http://bugs.python.org/issue21955 and
	http://bugs.python.org/issue10044 for the discussion. In short,
	no patch shown any impact on a realistic benchmark, only a minor
	speedup on microbenchmarks. */

[markshannon]

Just changes to longobject.c.

There are still various minor inefficiencies in testing to see whether an int is a medium value, and then throwing away size information before creating result objects.

I'm not expecting this to make much difference, but every little helps.

[markshannon]

New changeset 15d50d7 by Mark Shannon in branch 'main':
bpo-44946: Streamline operators and creation of ints for common case of single 'digit'. (GH-27832)
15d50d7