[Python-Dev] Re: Is anyone using 15-bit PyLong digits (PYLONG_BITS_IN_DIGIT=15)?
>> The reason for digits being a multiple of 5 bits should be revisited vs >> its original intent > I added that. The only intent was to make it easier to implement > bigint exponentiation easily ... That said, I see the comments in longintrepr.h note a stronger constraint: """ the marshal code currently expects that PyLong_SHIFT is a multiple of 15 """ But that's doubtless also shallow. ___ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/YSNDNGB2QUBS3ZX2JZNFZCDITRTDGBEM/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-Dev] Re: Is anyone using 15-bit PyLong digits (PYLONG_BITS_IN_DIGIT=15)?
[Gregory P. Smith ]
> The reason for digits being a multiple of 5 bits should be revisited vs
> its original intent
I added that. The only intent was to make it easier to implement
bigint exponentiation easily while viewing the exponent as being in
base 32 (so as to chew up 5 bits at a time).. Since the number of
digit bits _was_ 15 at the time, and it was 'obvious enough" that 30
bits would work fine when 64-bit boxes became important enough to care
about, it was easy to settle on "multiple of 5" as a quick, pragmatic
tradeoff. The number controls how much space and time is needed to
precompute a lookup table for a "large" (many bits) power - and powers
can be very large indeed in the modular exponentiation case.
I doubt Python will move beyond 30-bit digits. While 64-bit support
became increasingly and steadily more widespread (both SW and HW) in
the 32-bit world. I see very much less enthusiasm to move beyond 64
bits. Yes, 64x64 -> 128 multiply is spreading, but that's about it.
Some applications can make very good use of that, but, in the grand
scheme of things, they remain niche. Whole universes of apps are
getting real benefit by moving from 32 to 64 bits. That's needed just
to get integers big enough to represent physical memory addresses in
many consumer desktops now. But we'll likely never need to go beyond
64 bits for that.
In any case, "multiple of 5" is a shallow constraint. and getting rid
of it shouldn't require more than rewriting longobject.c's
long_pow()'s
for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
loop in a more convoluted way to cross digit boundaries when trying to
suck up "the next" 5 bits.
In fact, there are good reasons to make that loop more convoluted
anyway, but I never got around to it (it "should" instead be aiming to
find "the next" 5-bit slice that ends with a 1-bit, which would allow
cutting the aforementioned precomputed table in half).
___
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/CP3EH5EWVDJKN63XAOMDCOL4OTWUF2JY/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-Dev] Re: Is anyone using 15-bit PyLong digits (PYLONG_BITS_IN_DIGIT=15)?
On Thu, Dec 30, 2021 at 12:42 PM Gregory P. Smith wrote: > > On Thu, Dec 30, 2021 at 4:47 AM Mark Dickinson wrote: > >> tl;dr: I'd like to deprecate and eventually remove the option to use >> 15-bit digits in the PyLong implementation. Before doing so, I'd like to >> find out whether there's anyone still using 15-bit PyLong digits, and if >> so, why they're doing so. >> >> History: the use of 30-bit digits in PyLong was introduced for Python 3.1 >> and Python 2.7, to improve performance of int (Python 3) / long (Python 2) >> arithmetic. At that time, we retained the option to use 15-bit digits, for >> two reasons: >> >> - (1) use of 30-bit digits required C99 features (uint64_t and friends) >> at a time when we hadn't yet committed to requiring C99 >> - (2) it wasn't clear whether 30-bit digits would be a performance win on >> 32-bit operating systems >> >> Twelve years later, reason (1) no longer applies, and I suspect that: >> >> - No-one is deliberately using the 15-bit digit option. >> - There are few machines where using 15-bit digits is faster than using >> 30-bit digits. >> >> But I don't have solid data on either of these suspicions, hence this >> post. >> >> Removing the 15-bit digit option would simplify the code (there's >> significant mental effort required to ensure we don't break things for >> 15-bit builds when modifying Objects/longobject.c, and 15-bit builds don't >> appear to be exercised by the buildbots), remove a hidden compatibility >> trap (see b.p.o. issue 35037), widen the applicability of the various fast >> paths for arithmetic operations, and allow for some minor fast-path >> small-integer optimisations based on the fact that we'd be able to assume >> that presence of *two* extra bits in the C integer type rather than just >> one. As an example of the latter: if `a` and `b` are PyLongs that fit in a >> single digit, then with 15-bit digits and a 16-bit `digit` and `sdigit` >> type, `a + b` can't currently safely (i.e., without undefined behaviour >> from overflow) be computed with the C type `sdigit`. With 30-bit digits and >> a 32-bit `digit` and `sdigit` type, `a + b` is safe. >> >> Mark >> > > tying the thread together: this is https://bugs.python.org/issue45569 > > Check 32-bit builds. When I pushed for the 30-bit digit implementation, I > wanted it for all builds but if I recall correctly it *might* have > changed the minimum structure size for PyLong which could've been an ABI > issue? double check that. 32-bit is still important. Raspbian. rpi, rpi > zero, and first rev rpi2 are 32-bit arm architectures so even with 64-bit > raspbian on the horizon, that won't be the norm. and for those, memory > matters so a 32-bit userspace on 64-bit capable hardware is still preferred > for small pointer sizes on the majority which have <=4GiB ram. > > I believe performance was the other concern, 30-bit happens to perform > great on 32-bit x86 as it has 32*32->64 multiply hardware. Most 32-bit > architectures do not AFAIK, making 30 bit digit multiplies less efficient. > And 32-bit x86 was clearly on its way out by the time we adopted 30-bit so > it was simpler to just not do it on that dying snowflake of a platform. > (test it on raspbian - it's the one that matters) > > Regardless of possible issues to work out, I'd love us to have a simpler > 30-bit only implementation. > > Granted, modern 64-bit hardware often has 64*64->128 bit multiply hardware > so you can imagine going beyond 30 and winding up in complexity land > again. at least the extra bits would be >=2 at that point. The reason for > digits being a multiple of 5 bits should be revisited vs its original > intent and current state of the art "bignum optimized for mostly small > numbers" at some point as well. > > -gps > > Historical context of adding the 30-bit support (also driven primarily by Mark, no surprise!) in late 2008 early 2009: https://bugs.python.org/issue4258 (and https://codereview.appspot.com/14105) -gps ___ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/PRL7TJWUDYAMBQKVDLAIKD2OS2VOQPMQ/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-Dev] Re: Is anyone using 15-bit PyLong digits (PYLONG_BITS_IN_DIGIT=15)?
On Thu, Dec 30, 2021 at 4:47 AM Mark Dickinson wrote: > tl;dr: I'd like to deprecate and eventually remove the option to use > 15-bit digits in the PyLong implementation. Before doing so, I'd like to > find out whether there's anyone still using 15-bit PyLong digits, and if > so, why they're doing so. > > History: the use of 30-bit digits in PyLong was introduced for Python 3.1 > and Python 2.7, to improve performance of int (Python 3) / long (Python 2) > arithmetic. At that time, we retained the option to use 15-bit digits, for > two reasons: > > - (1) use of 30-bit digits required C99 features (uint64_t and friends) at > a time when we hadn't yet committed to requiring C99 > - (2) it wasn't clear whether 30-bit digits would be a performance win on > 32-bit operating systems > > Twelve years later, reason (1) no longer applies, and I suspect that: > > - No-one is deliberately using the 15-bit digit option. > - There are few machines where using 15-bit digits is faster than using > 30-bit digits. > > But I don't have solid data on either of these suspicions, hence this post. > > Removing the 15-bit digit option would simplify the code (there's > significant mental effort required to ensure we don't break things for > 15-bit builds when modifying Objects/longobject.c, and 15-bit builds don't > appear to be exercised by the buildbots), remove a hidden compatibility > trap (see b.p.o. issue 35037), widen the applicability of the various fast > paths for arithmetic operations, and allow for some minor fast-path > small-integer optimisations based on the fact that we'd be able to assume > that presence of *two* extra bits in the C integer type rather than just > one. As an example of the latter: if `a` and `b` are PyLongs that fit in a > single digit, then with 15-bit digits and a 16-bit `digit` and `sdigit` > type, `a + b` can't currently safely (i.e., without undefined behaviour > from overflow) be computed with the C type `sdigit`. With 30-bit digits and > a 32-bit `digit` and `sdigit` type, `a + b` is safe. > > Mark > tying the thread together: this is https://bugs.python.org/issue45569 Check 32-bit builds. When I pushed for the 30-bit digit implementation, I wanted it for all builds but if I recall correctly it *might* have changed the minimum structure size for PyLong which could've been an ABI issue? double check that. 32-bit is still important. Raspbian. rpi, rpi zero, and first rev rpi2 are 32-bit arm architectures so even with 64-bit raspbian on the horizon, that won't be the norm. and for those, memory matters so a 32-bit userspace on 64-bit capable hardware is still preferred for small pointer sizes on the majority which have <=4GiB ram. I believe performance was the other concern, 30-bit happens to perform great on 32-bit x86 as it has 32*32->64 multiply hardware. Most 32-bit architectures do not AFAIK, making 30 bit digit multiplies less efficient. And 32-bit x86 was clearly on its way out by the time we adopted 30-bit so it was simpler to just not do it on that dying snowflake of a platform. (test it on raspbian - it's the one that matters) Regardless of possible issues to work out, I'd love us to have a simpler 30-bit only implementation. Granted, modern 64-bit hardware often has 64*64->128 bit multiply hardware so you can imagine going beyond 30 and winding up in complexity land again. at least the extra bits would be >=2 at that point. The reason for digits being a multiple of 5 bits should be revisited vs its original intent and current state of the art "bignum optimized for mostly small numbers" at some point as well. -gps > > > *References* > > Related b.p.o. issue: https://bugs.python.org/issue45569 > MinGW compatibility issue: https://bugs.python.org/issue35037 > Introduction of 30-bit digits: https://bugs.python.org/issue4258 > ___ > Python-Dev mailing list -- python-dev@python.org > To unsubscribe send an email to python-dev-le...@python.org > https://mail.python.org/mailman3/lists/python-dev.python.org/ > Message archived at > https://mail.python.org/archives/list/python-dev@python.org/message/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/ > Code of Conduct: http://python.org/psf/codeofconduct/ > ___ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/WS5WHRCRHO4DOQPRW7EZYG3PRF4UIKAW/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-Dev] Is anyone using 15-bit PyLong digits (PYLONG_BITS_IN_DIGIT=15)?
tl;dr: I'd like to deprecate and eventually remove the option to use 15-bit digits in the PyLong implementation. Before doing so, I'd like to find out whether there's anyone still using 15-bit PyLong digits, and if so, why they're doing so. History: the use of 30-bit digits in PyLong was introduced for Python 3.1 and Python 2.7, to improve performance of int (Python 3) / long (Python 2) arithmetic. At that time, we retained the option to use 15-bit digits, for two reasons: - (1) use of 30-bit digits required C99 features (uint64_t and friends) at a time when we hadn't yet committed to requiring C99 - (2) it wasn't clear whether 30-bit digits would be a performance win on 32-bit operating systems Twelve years later, reason (1) no longer applies, and I suspect that: - No-one is deliberately using the 15-bit digit option. - There are few machines where using 15-bit digits is faster than using 30-bit digits. But I don't have solid data on either of these suspicions, hence this post. Removing the 15-bit digit option would simplify the code (there's significant mental effort required to ensure we don't break things for 15-bit builds when modifying Objects/longobject.c, and 15-bit builds don't appear to be exercised by the buildbots), remove a hidden compatibility trap (see b.p.o. issue 35037), widen the applicability of the various fast paths for arithmetic operations, and allow for some minor fast-path small-integer optimisations based on the fact that we'd be able to assume that presence of *two* extra bits in the C integer type rather than just one. As an example of the latter: if `a` and `b` are PyLongs that fit in a single digit, then with 15-bit digits and a 16-bit `digit` and `sdigit` type, `a + b` can't currently safely (i.e., without undefined behaviour from overflow) be computed with the C type `sdigit`. With 30-bit digits and a 32-bit `digit` and `sdigit` type, `a + b` is safe. Mark *References* Related b.p.o. issue: https://bugs.python.org/issue45569 MinGW compatibility issue: https://bugs.python.org/issue35037 Introduction of 30-bit digits: https://bugs.python.org/issue4258 ___ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/ Code of Conduct: http://python.org/psf/codeofconduct/
