Unify duplicate bits_in_digit and bit_length

[niklasf]

BPO	31031
Nosy	@mdickinson, @vstinner, @mlouielu, @niklasf
PRs	bpo-31031: Unify duplicate bits_in_digit and bit_length #2866

^{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 2020-01-16.14:14:39.812>
created_at = <Date 2017-07-25.12:48:04.878>
labels = ['interpreter-core', 'type-feature', '3.7']
title = 'Unify duplicate bits_in_digit and bit_length'
updated_at = <Date 2020-01-16.14:14:39.811>
user = 'https://github.com/niklasf'

bugs.python.org fields:

activity = <Date 2020-01-16.14:14:39.811>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2020-01-16.14:14:39.812>
closer = 'vstinner'
components = ['Interpreter Core']
creation = <Date 2017-07-25.12:48:04.878>
creator = 'niklasf'
dependencies = []
files = []
hgrepos = []
issue_num = 31031
keywords = []
message_count = 4.0
messages = ['299069', '360122', '360123', '360124']
nosy_count = 4.0
nosy_names = ['mark.dickinson', 'vstinner', 'louielu', 'niklasf']
pr_nums = ['2866']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue31031'
versions = ['Python 3.7']

[niklasf]

My previous patch to optimize bits_in_digit was
rejected: http://bugs.python.org/issue29782

This leaves this issue open (mathmodule.c):

/* XXX: This routine does more or less the same thing as

• bits_in_digit() in Objects/longobject.c. Someday it would be nice to
• consolidate them. On BSD, there's a library function called fls()
• that we could use, and GCC provides __builtin_clz().
  */

We could still deal with the code duplication without the
complexity of the optimizations in the previous patch.

[vstinner]

New changeset c5b7900 by Victor Stinner (Niklas Fiekas) in branch 'master':
bpo-31031: Unify duplicate bits_in_digit and bit_length (GH-2866)
c5b7900

[vstinner]

"On BSD, there's a library function called fls() that we could use, and GCC provides __builtin_clz()."

See also rejected bpo-29782 and GH-594.

If someone wants to experiment that, I suggest to add Include/internal/pycore_pymath.h, move _Py_bit_length() there and convert it to a static inline function.

Since the code is now unified, it makes a little bit more sense to add specialized code, *if* the code is not too complex.

I'm still not sure that GH-594 is worth it, since it was not possible to see the speedup on a microbenchmark :-(

[vstinner]

Thanks Niklas Fiekas for merging duplicated code ;-) It should make factorial_partial_product() a little bit more efficient!