[issue33144] random._randbelow optimization

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:


New changeset ec1622d56c80d15740f7f8459c9a79fd55f5d3c7 by Serhiy Storchaka in 
branch 'master':
bpo-33144: Fix choosing random.Random._randbelow implementation. (GH-6563)
https://github.com/python/cpython/commit/ec1622d56c80d15740f7f8459c9a79fd55f5d3c7


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Raymond Hettinger]

Change by Raymond Hettinger :


--
assignee: rhettinger -> serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

PR 6291 didn't work properly with case 1. Rand2 uses getrandbits() since it is 
overridden in the parent despites the fact that random() is defined later.

PR 6563 fixes this. It walks classes in method resolution order and finds the 
first class that defines random() or getrandbits().

PR 6563 also makes tests not using logging for testing purpose.

--
resolution: fixed -> 
stage: resolved -> patch review
status: closed -> open

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
pull_requests: +6258

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Raymond Hettinger]

Change by Raymond Hettinger :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Possibly, the switch from type checks to identity checks could be considered a 
bugfix that could be backported.  I've always had a lingering worry about that 
part of the code.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Raymond Hettinger]

Raymond Hettinger  added the comment:


New changeset ba3a87aca37cec5b1ee32cf68f4a254fa0bb2bec by Raymond Hettinger 
(Wolfgang Maier) in branch 'master':
bpo-33144: random.Random and subclasses: split _randbelow implementation 
(GH-6291)
https://github.com/python/cpython/commit/ba3a87aca37cec5b1ee32cf68f4a254fa0bb2bec


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Wolfgang Maier]

Wolfgang Maier  added the comment:

ok, I've created issue 33203 to deal with raising ValueError in _randbelow 
consistently.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Wolfgang Maier]

Wolfgang Maier  added the comment:

In addition, I took the opportunity to fix a bug in the original _randbelow in 
that it would only raise the advertised ValueError on n=0 in the 
getrandbits-dependent branch, but ZeroDivisionError in the pure random branch.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Wolfgang Maier]

Wolfgang Maier  added the comment:

So, the PR implements the behaviour suggested by Serhiy as his cases 1 and 2.
Case 2 changes *existing* behaviour because before it was sufficient to have a 
user-defined getrandbits anywhere in the inheritance tree, while with the PR it 
has to be more recent (or be defined within the same class) as the random 
method.
I'm not 100% sold on this particular aspect so if you think the old behaviour 
is better, then that's fine with me. In most real situations it would not make 
a difference anyway (or do people build complex inheritance hierarchies on top 
of random.Random?).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Wolfgang Maier]

Change by Wolfgang Maier :


--
pull_requests: +6015
stage:  -> patch review

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Wolfgang Maier]

Wolfgang Maier  added the comment:

Thanks, Raymond. I'll do that once I've addressed Serhiy's points.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Wolfgang, can you submit this as a PR.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Wolfgang Maier]

Wolfgang Maier  added the comment:

Serhiy:

> I like the idea in general, but have comments about the implementation.
> 
> __init_subclass__ should take **kwargs and pass it to 
> super().__init_subclass__(). type(cls.random) is not the same as 
> type(self.random). I would use the condition `cls.random is 
> _random.Random.random` instead, or check if the method is in cls.__dict__.
> 
> This will break the case when random or getrandbits methods are patched after 
> class creation or per instance, but I think we have no need to support this.
> 

My bad, sorry, and thanks for catching all these issues!

You're absolutely right about the class type checks not being equivalent 
to the original ones at the instance level.
Actually, this is due to the fact that I first moved the checks out of 
_randbelow and into __init__ just as Raymond would have done and tested 
this, but then I realized that __init_subclass__ looked just like the 
right place and moved them again - this time without testing on derived 
classes again.
 From a quick experiment it looks like types.MethodDescriptorType would 
be the correct type to check cls.random against and types.FunctionType 
would need to be checked against cls.getrandbits, but that starts to 
look rather esoteric to me - so you are probably right that something 
with a cls.__dict__ check or the alternative suggestion of `cls.random 
is _random.Random.random` are better solutions, indeed.

> We could support also the following cases:
> 
> 1.
>  class Rand1(Random):
>  def random(self): ...
>  # _randbelow should use random()
> 
>  class Rand2(Rand1):
>  def getrandbits(self): ...
>  # _randbelow should use getrandbits()
>  # this is broken in the current patch
> 

Right, hadn't thought of this situation.

> 2.
>  class Rand1(Random):
>  def getrandbits(self): ...
>  # _randbelow should use getrandbits()
> 
>  class Rand2(Rand1):
>  def random(self): ...
>  # _randbelow should use random()
>  # this is broken in the current code
> 

May be worth fixing, too.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

I think this is excellent application of __init_subclass__. It is common to 
patch an instance method in __init__, but this can create a reference loop if 
patch it by other instance method. In this case the choice doesn't depend on 
arguments of __init__, and can be done at class creation time.

I like the idea in general, but have comments about the implementation.

__init_subclass__ should take **kwargs and pass it to 
super().__init_subclass__(). type(cls.random) is not the same as 
type(self.random). I would use the condition `cls.random is 
_random.Random.random` instead, or check if the method is in cls.__dict__.

This will break the case when random or getrandbits methods are patched after 
class creation or per instance, but I think we have no need to support this.

We could support also the following cases:

1.
class Rand1(Random):
def random(self): ...
# _randbelow should use random()

class Rand2(Rand1):
def getrandbits(self): ...
# _randbelow should use getrandbits()
# this is broken in the current patch

2.
class Rand1(Random):
def getrandbits(self): ...
# _randbelow should use getrandbits()

class Rand2(Rand1):
def random(self): ...
# _randbelow should use random()
# this is broken in the current code

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Tim Peters]

Tim Peters  added the comment:

I'm the wrong guy to ask about that.  Since I worked at Zope Corp, my natural 
inclination is to monkey-patch everything - but knowing full well that will 
offend everyone else ;-)

That said, this optimization seems straightforward to me:  two distinct method 
implementations for two very different approaches that have nothing in common 
besides the method name & signature.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Raymond Hettinger]

Raymond Hettinger  added the comment:

> the optimized `_randbelow()` also avoids populating its locals 
> with 5 unused formal arguments

Yes, that clean-up would be nice as well :-)

Any thoughts on having __init__ set a flag versus using __init__subclass__ to 
backpatch the subclass?  To me, the former looks like plain python and latter 
doesn't seem like something that would normally be done in the standard library.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Tim Peters]

Tim Peters  added the comment:

I don't see anything objectionable about the class optimizing the 
implementation of a private method.

I'll note that there's a speed benefit beyond just removing the two type checks 
in the common case:  the optimized `_randbelow()` also avoids populating its 
locals with 5 unused formal arguments (which are just "a trick" to change what 
would otherwise have been global accesses into local accesses).  So it actually 
makes the method implementation cleaner & clearer too.

But it's really the speed that matters here.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Raymond Hettinger]

Raymond Hettinger  added the comment:

> it could also be done at instantiation time (the attached patch
> uses __init_subclass__ for that purpose 

FWIW, a 10-25% speedup is only possible because the remaining code is already 
somewhat fast.  All that is being proposed is removing couple of lines that 
elsewhere would be considered somewhat thin:

random = self.random
if type(random) is BuiltinMethod \
   or type(getrandbits) is Method:

Overall, the idea of doing the check only once at instantiation time seems 
promising.  That said, I have unspecific general worries about using 
__init_subclass__ and patching the subclass.  Perhaps Serhiy, Tim, or Mark will 
have thoughts on whether this sort of self-patching is something we want to be 
doing in the standard library, whether it would benefit PyPy, and whether it 
has risks to existing code, to debugging and testing, and to future maintenance.

If I were the one to go the route of making a single pre-check, my instinct 
would be to just set a flag in __init__, so that the above code would simplify 
to:

if self._valid_getrandbits:
...

--
assignee:  -> rhettinger
nosy: +mark.dickinson, serhiy.storchaka, tim.peters

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33144] random._randbelow optimization

[Wolfgang Maier]

New submission from Wolfgang Maier :

Given that the random module goes a long way to ensure optimal performance, I 
was wondering why the check for a match between the random and getrandbits 
methods is performed per call of Random._randbelow, when it could also be done 
at instantiation time (the attached patch uses __init_subclass__ for that 
purpose and, in my hands, gives 10-25% speedups for calls to methods relying on 
_randbelow).
Is it really necessary to guard against someone monkey patching the methods 
rather than using inheritance?

--
components: Library (Lib)
files: randbelow.patch
keywords: patch
messages: 314455
nosy: rhettinger, wolma
priority: normal
severity: normal
status: open
title: random._randbelow optimization
type: performance
versions: Python 3.8
Added file: https://bugs.python.org/file47501/randbelow.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com