[RFC] Random Extension 3.0

2 years ago by Go Kudo — view source

unread

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

Regards,
Go Kudo

2 years ago by Larry Garfield — view source

unread

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

Regards,
Go Kudo

This looks pretty nice to my unskilled eye. Two questions.

Why is the number generator a parent class rather than an interface? It seems like an interface target. And either way it needs more clarity about how you'd write one for reals. (It returns an int, so does that mean getBytes() just derives from a series of ints?)
You don't mention the CSPRNG functions at all. Is there any intention to fold those into this model as well, or to leave those as is? Or is the Secure generator implementation intended to replace those? It's unclear here.

--Larry Garfield

2 years ago by Go Kudo — view source

unread

Thank you.

Why is the number generator a parent class rather than an interface?

This is an implementation limitation. I could not find a way to define my
own object handler in interface.
As Nikita pointed out in a previous suggestion, the NumberGenerator now
uses php_random_ng_algo_user to generate random numbers faster than before,
even if it is a userland implementation.

You don't mention the CSPRNG functions at all.

This is a mistake. I have corrected it. Thanks!

I will keep an eye on it throughout the next week, and if there are no
additional responses, I will start voting the week after next.

Regards,
Go Kudo

2021年9月3日(金) 3:26 Larry Garfield larry@garfieldtech.com:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes
the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

Regards,
Go Kudo

This looks pretty nice to my unskilled eye. Two questions.

Why is the number generator a parent class rather than an interface?
It seems like an interface target. And either way it needs more clarity
about how you'd write one for reals. (It returns an int, so does that mean
getBytes() just derives from a series of ints?)

You don't mention the CSPRNG functions at all. Is there any intention
to fold those into this model as well, or to leave those as is? Or is the
Secure generator implementation intended to replace those? It's unclear
here.

--Larry Garfield

--

To unsubscribe, visit: https://www.php.net/unsub.php

2 years ago by Larry Garfield — view source

unread

Thank you.

Why is the number generator a parent class rather than an interface?

This is an implementation limitation. I could not find a way to define my
own object handler in interface.
As Nikita pointed out in a previous suggestion, the NumberGenerator now
uses php_random_ng_algo_user to generate random numbers faster than before,
even if it is a userland implementation.

I'm still unclear how I'd write my own NumberGenerator right now. I mean, I can extend the class, but I don't have a sense for what I'd do with it for non-testing/trivial implementations. You say it's using an internal function to generate numbers, but in user space what would I do with that? And when/why would I?

You don't mention the CSPRNG functions at all.

This is a mistake. I have corrected it. Thanks!

I'm still not clear on the intent here. Is the intent that I should stop using random_int()? And if so, replace it with... what? Do I have to supply a specific non-default generator? That makes the usability worse, and more likely to be gotten wrong.

Also, in future scope you you have this sentence, which makes little sense:

Replace random_bytes() with random_bytes() for random numbers used in shuffle(), str_shuffle(), and array_rand().

--Larry Garfield

2 years ago by Go Kudo — view source

unread

I'm still unclear how I'd write my own NumberGenerator right now. I
mean, I can extend the class, but I don't have a sense for what I'd do with
it for non-testing/trivial implementations. You say it's using an internal
function to generate numbers, but in user space what would I do with that?
And when/why would I?

For example, I will create an application that does a lottery. I need to
estimate the load and test it. If I actually use random numbers to draw the
lots, the test results will be different each time.

It is true that this example can be solved by devising a better
implementation of the userland.

If this is the case, you may be wondering why we implement it this way.

Currently, there are several implementations of random number generators
written in PHP.

https://github.com/savvot/random

Although not in this library, I use an in-house interface that is
completely replaceable with random_int() for load testing in my production
brother.

Also, JIT was implemented in PHP 8.0. which has the potential to make it
possible to write in PHP what would otherwise have to be implemented in C
due to execution speed issues. In fact, the random number generator written
in PHP for my tests shows a significant performance improvement when JIT is
enabled. The ability to have a workable random number implementation in
userland should be useful for future extensions.

Is the intent that I should stop using random_int()?

No, it's not. random_int() is a safe and easy CSPRNG, and is recommended
for future use.
The advantage of using Random\NumberGenerator\Secure is that it can shuffle
strings/arrays using the same random number source as random_int().

Something that is not included in this RFC but that I would like to
deprecate in the future is the mt_srand (srand) function. These have
internal state and are very harmful for extensions such as Swoole:

Also, shuffle() and str_shuffle() are very good functions, but I don't
think they should use the random number source generated by mt_srand. The
user may unintentionally use an unsecured random number.

I apologize for the difficulty in conveying this message. I've revised the
wording.

Changes random source to php_random_int() in shuffle(), str_shuffle(),
and array_rand() .

2021年9月3日(金) 23:04 Larry Garfield larry@garfieldtech.com:

Thank you.

Why is the number generator a parent class rather than an interface?

This is an implementation limitation. I could not find a way to define my
own object handler in interface.
As Nikita pointed out in a previous suggestion, the NumberGenerator now
uses php_random_ng_algo_user to generate random numbers faster than
before,
even if it is a userland implementation.

I'm still unclear how I'd write my own NumberGenerator right now. I mean,
I can extend the class, but I don't have a sense for what I'd do with it
for non-testing/trivial implementations. You say it's using an internal
function to generate numbers, but in user space what would I do with that?
And when/why would I?

You don't mention the CSPRNG functions at all.

This is a mistake. I have corrected it. Thanks!

I'm still not clear on the intent here. Is the intent that I should stop
using random_int()? And if so, replace it with... what? Do I have to
supply a specific non-default generator? That makes the usability worse,
and more likely to be gotten wrong.

Also, in future scope you you have this sentence, which makes little sense:

Replace random_bytes() with random_bytes() for random numbers used in
shuffle(), str_shuffle(), and array_rand().

--Larry Garfield

--

To unsubscribe, visit: https://www.php.net/unsub.php

2 years ago by Go Kudo — view source

unread

My apologies. I had skipped one.

And either way it needs more clarity about how you'd write one for reals.

Added a simple example comparing it to mt_rand. What do you think of this?

2021年9月3日(金) 3:26 Larry Garfield larry@garfieldtech.com:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes
the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

Regards,
Go Kudo

This looks pretty nice to my unskilled eye. Two questions.

Why is the number generator a parent class rather than an interface?
It seems like an interface target. And either way it needs more clarity
about how you'd write one for reals. (It returns an int, so does that mean
getBytes() just derives from a series of ints?)

You don't mention the CSPRNG functions at all. Is there any intention
to fold those into this model as well, or to leave those as is? Or is the
Secure generator implementation intended to replace those? It's unclear
here.

--Larry Garfield

--

To unsubscribe, visit: https://www.php.net/unsub.php

2 years ago by Nikita Popov — view source

unread

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

This looks pretty nice to me. A few bits of feedback:

Unlike the previous versions of the RFC, this one also moves all of the
existing RNG-related functionality from ext/standard to ext/random. Why
does it do this? This doesn't really seem related to the problem this RFC
is solving.
Regarding the abstract class Random\NumberGenerator: You currently need
the abstract class, because php_random_ng is tied to the object. An
alternative design that would allow Random\NumberGenerator to be an
interface would be to make it independent of the object, such that the
structure can be allocated in the Random constructor for userland
implementations. Of course, internal implementations could still embed it
as part of their objects -- just don't make it a requirement.
The future scope mentions: "Changes random source to php_random_int() a
shuffle(), str_shuffle(), and array_rand()". I don't think it makes sense
to switch these functions to use cryptographic randomness by default...

Regards,
Nikita

2 years ago by Go Kudo — view source

unread

Thanks nikita.

ext/standard to ext/random. Why does it do this?

There are several reasons for this.

The random extension name is already used by ext/standard and may
interfere with the build system.
Due to the namespace rules for new extensions, it is inappropriate to
rename an extension.
Due to history, the rand / mt_rand dependency is tricky and I thought it
was time to sort it out.
I don't think it's a good idea to have multiple header files for a single
domain feature.
As stated in the Future Scope, I wanted to be in a position to eliminate
module global random number state in the future.
The existing implementation and the object implementation share most of
the same logic. It was necessary to merge them into one to make them common.

I certainly didn't want to require a workaround for PHP 8.2 or later for
extensions that depended on ext/standard respectively, but I decided that I
had no choice for the above reasons.

just don't make it a requirement.

I would like to modify the design.

I don't think it makes sense to switch these functions to use
cryptographic randomness by default...

While these may not need to be cryptographically secure, I don't think they
need to be state-dependent as well. Probably no one would look at the
function name and think that it depends on the module global state.

php_random_int() doesn't have any state anywhere (except OS) and can
generate the requested random number. I don't see any problem with these
functions using php_random_int() as a random number source.

Regards,
Go Kudo

2021年9月4日(土) 1:02 Nikita Popov nikita.ppv@gmail.com:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

This looks pretty nice to me. A few bits of feedback:

Unlike the previous versions of the RFC, this one also moves all of the
existing RNG-related functionality from ext/standard to ext/random. Why
does it do this? This doesn't really seem related to the problem this RFC
is solving.

Regarding the abstract class Random\NumberGenerator: You currently need
the abstract class, because php_random_ng is tied to the object. An
alternative design that would allow Random\NumberGenerator to be an
interface would be to make it independent of the object, such that the
structure can be allocated in the Random constructor for userland
implementations. Of course, internal implementations could still embed it
as part of their objects -- just don't make it a requirement.

The future scope mentions: "Changes random source to php_random_int() a
shuffle(), str_shuffle(), and array_rand()". I don't think it makes sense
to switch these functions to use cryptographic randomness by default...

Regards,
Nikita

2 years ago by Dan Ackroyd — view source

unread

Nikita wrote:

this one also moves all of the existing RNG-related functionality
from ext/standard to ext/random.

There are several reasons for this.

The random extension name is already used by ext/standard and may
interfere with the build system.

Due to the namespace rules for new extensions, it is inappropriate to
rename an extension.

Due to history, the rand / mt_rand dependency is tricky and I thought it
was time to sort it out.

I don't think it's a good idea to have multiple header files for a single
domain feature.

Have you considered how much work that is going to incur on downstream
projects?

If there's a good reason for moving stuff around then it can be
appropriate, but the RFC phrasing of: "At the same time, the
following internal APIs will also be relocated. If you want to use
them, you can simply include ext/random/random.h." sounds pretty
dismissive of causing possibly unneeded work for downstream projects.

cheers
Dan
Ack

2 years ago by Go Kudo — view source

unread

This may not have been the best way to put it. The point I was trying to
make was that while BC Breaks do occur, they are very easy to solve.

The impact on downstream projects will be significant, and there may be
many extensions affected, since this change concerns a frequently used RNG
feature. However, in other words, it may need to be sorted out as soon as
possible.

However, I also understand the theory that this should be done in
conjunction with a major language change. Perhaps I should have suggested
this for PHP 8.0.

Either way, I'll try to separate these suggestions if necessary, but if we
were to try to provide an OOP API without BC Break, what do you think would
be the ideal form?

Regards,
Go Kudo

2021年9月5日(日) 4:24 Dan Ackroyd Danack@basereality.com:

Nikita wrote:

this one also moves all of the existing RNG-related functionality
from ext/standard to ext/random.

There are several reasons for this.

The random extension name is already used by ext/standard and may
interfere with the build system.

Due to the namespace rules for new extensions, it is inappropriate to
rename an extension.

Due to history, the rand / mt_rand dependency is tricky and I thought
it
was time to sort it out.

I don't think it's a good idea to have multiple header files for a
single
domain feature.

Have you considered how much work that is going to incur on downstream
projects?

If there's a good reason for moving stuff around then it can be
appropriate, but the RFC phrasing of: "At the same time, the
following internal APIs will also be relocated. If you want to use
them, you can simply include ext/random/random.h." sounds pretty
dismissive of causing possibly unneeded work for downstream projects.

cheers
Dan
Ack

2 years ago by Dan Ackroyd — view source

unread

Go Kudo wrote:

Dan Ackroyd wrote:

you can simply include ext/random/random.h." sounds pretty
dismissive of causing possibly unneeded work for downstream projects.

The point I was trying to make was that while BC Breaks do occur, they are very easy to solve.

I've found it useful to think about "value = benefit minus cost".

I was calling out that it seems to be that this is a change you want
to do for aesthetic reasons and are justifying it by trivialising the
work involved. i.e. it has a tiny benefit that only has a positive
value if the cost is also tiny.

Although the change is simple:

Any code base that includes standard/php_rand.h won't compile, and
people will have to find out what changed. Even though the fix may be
easy to implement, each of those people will have to figure it out for
themselves.
quite a few people will have to learn (or relearn) how to use #if to
compare PHP version to include either standard/php_rand.h or
random/php_random.h if they want their code to work on more than 1 PHP
version.
it makes more work for downstream distributors of PHP, as their
patches (including security patches) will need to be moved around.

If there's a good reason to move stuff around, then fine, but avoiding
creating extra work downstream is worth doing. And possibly is a hot
topic right now.

You could probably avoid a lot of downstream work by leaving a stub
file at standard/php_rand.h that includes random/php_random.h.

cheers
Dan
Ack

btw, if you could please avoid top-posting, that would be appreciated:
https://github.com/php/php-src/blob/master/docs/mailinglist-rules.md

"Do not top post. Place your answer underneath anyone you wish to
quote and remove any previous comment that is not relevant to your
post."

2 years ago by Go Kudo — view source

unread

2021年9月23日(木) 2:05 Dan Ackroyd Danack@basereality.com:

Go Kudo wrote:

Dan Ackroyd wrote:

you can simply include ext/random/random.h." sounds pretty
dismissive of causing possibly unneeded work for downstream projects.

The point I was trying to make was that while BC Breaks do occur, they
are very easy to solve.

I've found it useful to think about "value = benefit minus cost".

I was calling out that it seems to be that this is a change you want
to do for aesthetic reasons and are justifying it by trivialising the
work involved. i.e. it has a tiny benefit that only has a positive
value if the cost is also tiny.

Although the change is simple:

Any code base that includes standard/php_rand.h won't compile, and
people will have to find out what changed. Even though the fix may be
easy to implement, each of those people will have to figure it out for
themselves.

quite a few people will have to learn (or relearn) how to use #if to
compare PHP version to include either standard/php_rand.h or
random/php_random.h if they want their code to work on more than 1 PHP
version.

it makes more work for downstream distributors of PHP, as their
patches (including security patches) will need to be moved around.

If there's a good reason to move stuff around, then fine, but avoiding
creating extra work downstream is worth doing. And possibly is a hot
topic right now.

You could probably avoid a lot of downstream work by leaving a stub
file at standard/php_rand.h that includes random/php_random.h.

cheers
Dan
Ack

btw, if you could please avoid top-posting, that would be appreciated:
https://github.com/php/php-src/blob/master/docs/mailinglist-rules.md

"Do not top post. Place your answer underneath anyone you wish to
quote and remove any previous comment that is not relevant to your
post."

I apologize for not knowing the rules of ML.
Is this correct?

It is true that it is better to maintain compatibility that can be
maintained.
However, I think this should be sorted out sometime. Perhaps it will be in
PHP 9.0.

First of all, I would like to change these RFC and implementations.

https://wiki.php.net/rfc/random_ext
https://wiki.php.net/rfc/rng_extension

Thank you.

2 years ago by Ben Ramsey — view source

unread

Go Kudo wrote on 9/2/21 10:10:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

Regards,
Go Kudo

This proposal seems like two different proposals to me:

The first consolidates and cleans up RNG functions for internals
The second exposes an OOP API for working with RNGs

Personally, I don't see the benefit of including this OOP API in the
core. I don't think it provides any benefits over similar abstractions
in userland, and in fact, I think this kind of API is best suited for
iteration in userland.

Cheers,
Ben

2 years ago by Marc — view source

unread

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

For me (user land developer with no voting power) your RFC looks pretty :)

Beside the abstract vs interface question I have some other notes:

On the one hand you define "getBytes()" which returns a string and on
the other hand you define "shuffleString()" - is the first one a binary
string and the other a charset dependent string? I guess here
"shuffleString()" works on byte level and so it should be "shuffleBytes()".

Why are there no default values for min/max on "getInt()" - It seems
unnecessary to me to pass min/max arguments if you are just interested
in a random integer or passing max as well if you are interested in a
positive integer only.

Thanks for the nice RFC!

Regards,
Go Kudo
Marc

2 years ago by Go Kudo — view source

unread

Thanks marc.

"shuffleString()" works on byte level and so it should be
"shuffleBytes()".

Hmm. This may be a difficult problem related to the PHP language
specification. As with str_shuffle(), most people will probably use it to
shuffle strings. People who want to shuffle binaries are likely to
understand that in PHP it is synonymous with shuffleBytes().

Why are there no default values for min/max on "getInt()" - It seems
unnecessary to me to pass min/max arguments

My apologies. I completely forgot that I needed this.
Add this along with a fix for the RNG\NumberGenerator implementation.

Regards,
Go Kudo

2021年9月5日(日) 5:57 Marc marc@mabe.berlin:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes
the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

For me (user land developer with no voting power) your RFC looks pretty :)

Beside the abstract vs interface question I have some other notes:

On the one hand you define "getBytes()" which returns a string and on
the other hand you define "shuffleString()" - is the first one a binary
string and the other a charset dependent string? I guess here
"shuffleString()" works on byte level and so it should be "shuffleBytes()".

Why are there no default values for min/max on "getInt()" - It seems
unnecessary to me to pass min/max arguments if you are just interested
in a random integer or passing max as well if you are interested in a
positive integer only.

Thanks for the nice RFC!

Regards,
Go Kudo
Marc

2 years ago by Nikita Popov — view source

unread

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes
the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

For me (user land developer with no voting power) your RFC looks pretty :)

Beside the abstract vs interface question I have some other notes:

On the one hand you define "getBytes()" which returns a string and on
the other hand you define "shuffleString()" - is the first one a binary
string and the other a charset dependent string? I guess here
"shuffleString()" works on byte level and so it should be "shuffleBytes()".

Why are there no default values for min/max on "getInt()" - It seems
unnecessary to me to pass min/max arguments if you are just interested
in a random integer or passing max as well if you are interested in a
positive integer only.

Because the default range is not obvious. For example mt_rand() without
min/max will actually return only non-negative integers, so someone might
expect $random->getInt() to do the same, even though it makes very little
sense. $random->getInt($n) could be interpreted either as a number in
$n..PHP_INT_MAX (if we just see it as leaving $max at the default value),
or 0..$n-1 (a very common convention for single-argument random integer
functions). Requiring both arguments makes the meaning unambiguous.

Regards,
Nikita

2 years ago by Nikita Popov — view source

unread

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

This RFC currently tries to keep some semblance of compatibility with the
existing mt_rand() algorithm by retaining the same implementation for
mapping the raw random number stream into a range. However, the algorithm
we use for that is not exactly state of the art and requires two full-width
divisions at minimum. There are more efficient scaling algorithms based on
fixed-point multiplication, which are "nearly divisionless" (
https://arxiv.org/pdf/1805.10941.pdf). The variant at
https://github.com/apple/swift/pull/39143 is entirely divisionless.

Doing this would improve performance (though I'm not sure by how much --
maybe once we add up our call overhead, it isn't important anymore?) but it
would provide a different sequence than mt_rand(). Something we might want
to consider.

Regards,
Nikita

2 years ago by Go Kudo — view source

unread

Hi Nikita, sorry for the late reply.

This is a difficult problem. For now, MT19937 is left for compatibility. In
other words, if you don't need compatibility, there is no benefit to using
it.

What about implementing both a new MT and a compatible MT? A compatible MT
would have the following signature


use Random\NumberGenerator\Numbergenerator;

/* for legacy compatibility */
class MT19937 implements NumberGenerator
{
    public function __construct(int $mode = MT_RAND_MT19937, int $seed) {}
}

/* a new implementation */
class MersenneTwister implements NumberGenerator
{
    public function __construct(int $seed) {}
}

I had originally removed the MT_RAND_PHP implementation on the grounds that
legacy implementations should not be retained, but if the regular Mersenne
twister is to be retained for compatibility, I think it should be as well.

Also, maybe we should opt for a more SIMD friendly RNG.

Regards,
Go Kudo

2021年9月7日(火) 17:28 Nikita Popov nikita.ppv@gmail.com:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

This RFC currently tries to keep some semblance of compatibility with the
existing mt_rand() algorithm by retaining the same implementation for
mapping the raw random number stream into a range. However, the algorithm
we use for that is not exactly state of the art and requires two full-width
divisions at minimum. There are more efficient scaling algorithms based on
fixed-point multiplication, which are "nearly divisionless" (
https://arxiv.org/pdf/1805.10941.pdf). The variant at
https://github.com/apple/swift/pull/39143 is entirely divisionless.

Doing this would improve performance (though I'm not sure by how much --
maybe once we add up our call overhead, it isn't important anymore?) but it
would provide a different sequence than mt_rand(). Something we might want
to consider.

Regards,
Nikita

2 years ago by Nikita Popov — view source

unread

Hi Nikita, sorry for the late reply.

This is a difficult problem. For now, MT19937 is left for compatibility.
In other words, if you don't need compatibility, there is no benefit to
using it.

What about implementing both a new MT and a compatible MT? A compatible MT
would have the following signature
use Random\NumberGenerator\Numbergenerator;

/* for legacy compatibility */
class MT19937 implements NumberGenerator
{
    public function __construct(int $mode = MT_RAND_MT19937, int $seed) {}
}

/* a new implementation */
class MersenneTwister implements NumberGenerator
{
    public function __construct(int $seed) {}
}
I had originally removed the MT_RAND_PHP implementation on the grounds
that legacy implementations should not be retained, but if the regular
Mersenne twister is to be retained for compatibility, I think it should be
as well.

Also, maybe we should opt for a more SIMD friendly RNG.

To clarify, what I had in mind here is not the MT generator itself, but the
scaling done in Random::getInt(). This scaling is independent of the used
source. So while the raw numbers generated by
Random\NumberGenerator\MT19937 would be the same as before, the result
produced by Random::getInt() with this source wouldn't be.

Regards,
Nikita

2021年9月7日(火) 17:28 Nikita Popov nikita.ppv@gmail.com:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes
the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

This RFC currently tries to keep some semblance of compatibility with the
existing mt_rand() algorithm by retaining the same implementation for
mapping the raw random number stream into a range. However, the algorithm
we use for that is not exactly state of the art and requires two full-width
divisions at minimum. There are more efficient scaling algorithms based on
fixed-point multiplication, which are "nearly divisionless" (
https://arxiv.org/pdf/1805.10941.pdf). The variant at
https://github.com/apple/swift/pull/39143 is entirely divisionless.

Doing this would improve performance (though I'm not sure by how much --
maybe once we add up our call overhead, it isn't important anymore?) but it
would provide a different sequence than mt_rand(). Something we might want
to consider.

Regards,
Nikita

2 years ago by Go Kudo — view source

unread

I had misunderstood this for a long time. Now I understand.
This is certainly something to think about.

However, I think we also need to consider compatibility. How about
something like the following?

&lt;?php

class MT19973_32
{
    public const SCALE_NORMAL = 0;
    public const SCALE_LEGACY = 1;
    public function __construct(?int $seed, int $flag = self::SCALE_NORMAL)
{}
}

2021年10月4日(月) 19:24 Nikita Popov nikita.ppv@gmail.com:

Hi Nikita, sorry for the late reply.

This is a difficult problem. For now, MT19937 is left for compatibility.
In other words, if you don't need compatibility, there is no benefit to
using it.

What about implementing both a new MT and a compatible MT? A compatible
MT would have the following signature
use Random\NumberGenerator\Numbergenerator;

/* for legacy compatibility */
class MT19937 implements NumberGenerator
{
    public function __construct(int $mode = MT_RAND_MT19937, int $seed) {}
}

/* a new implementation */
class MersenneTwister implements NumberGenerator
{
    public function __construct(int $seed) {}
}
I had originally removed the MT_RAND_PHP implementation on the grounds
that legacy implementations should not be retained, but if the regular
Mersenne twister is to be retained for compatibility, I think it should be
as well.

Also, maybe we should opt for a more SIMD friendly RNG.
To clarify, what I had in mind here is not the MT generator itself, but
the scaling done in Random::getInt(). This scaling is independent of the
used source. So while the raw numbers generated by
Random\NumberGenerator\MT19937 would be the same as before, the result
produced by Random::getInt() with this source wouldn't be.

Regards,
Nikita

2021年9月7日(火) 17:28 Nikita Popov nikita.ppv@gmail.com:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes
the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

This RFC currently tries to keep some semblance of compatibility with
the existing mt_rand() algorithm by retaining the same implementation for
mapping the raw random number stream into a range. However, the algorithm
we use for that is not exactly state of the art and requires two full-width
divisions at minimum. There are more efficient scaling algorithms based on
fixed-point multiplication, which are "nearly divisionless" (
https://arxiv.org/pdf/1805.10941.pdf). The variant at
https://github.com/apple/swift/pull/39143 is entirely divisionless.

Doing this would improve performance (though I'm not sure by how much --
maybe once we add up our call overhead, it isn't important anymore?) but it
would provide a different sequence than mt_rand(). Something we might want
to consider.

Regards,
Nikita

2 years ago by Kamil Tekiela — view source

unread

Please don't add more answers to the class name. There is already going to
be a backlash if we name it "MT19973" instead of "MersenneTwister"

2 years ago by Go Kudo — view source

unread

The RFCs are in limbo, but we are currently thinking of including the
following RNGs in the proposal

XorShift128Plus
MT19937 (for compatibility)
MT19937_64 (for more entropy and wider range)

While it is clear that MT19937 is simply MersenneTwister, it is not
accurate since there is MT19937_64. Also, currently, the constant name that
can be passed to mt_srand() is MT_RAND_MT19937, so I think it is consistent
to use MT19937.

If you mean that it should be MT19937 instead of MT19937_32, then I think
you are right.

Please let me know your opinion.

2021年10月7日(木) 21:56 Kamil Tekiela tekiela246@gmail.com:

Please don't add more answers to the class name. There is already going to
be a backlash if we name it "MT19973" instead of "MersenneTwister"

2 years ago by Kamil Tekiela — view source

unread

Yes, I know the reason why we use MT19937 as the name, but this is not
really very user-friendly name. The actual algorithm could be documented in
the PHP manual but the name could be better. The problem with this name is
that most users simply don't care about the algorithm being used. At least
that is what it was until now. For example
https://phpmanualmasterpieces.tumblr.com/post/65965628369/so-php-such-documented

What I think would be better is to not provide two versions of MT at all
and just call it MersenneTwister. Users who require backwards compatibility
with rand() can do so in userland or keep using rand() for the moment.
Naming is a very minor problem, so I would be ok either way, but I am just
voicing an opinion that having two classes with 32 and 64 at the end, in
this day and age, will be very confusing for users. Better to avoid such
things in PHP.

2 years ago by Go Kudo — view source

unread

Indeed, it may be true that these suggestions should not be made all at
once. If necessary, I would like to propose to organize the RNG
implementation first.

Do we still need an RFC in this case? I'm not sure I'm not fully understand
the criteria for an RFC. Does this internal API change count as a BC Break
that requires an RFC?

Personally, I don't see the benefit of including this OOP API in the core.

On the other hand, can you tell me why you thought it was unnecessary?
Was my example unrealistic?

I'm sorry if my English is not good and my writing seems offensive. I have
no intention to do so.

Regards,
Go Kudo

2021年9月5日(日) 1:12 Ben Ramsey ramsey@php.net:

Go Kudo wrote on 9/2/21 10:10:

Hi Internals.

Expanded from the previous RFC and changed it to an RFC that organizes
the
whole PHP random number generator. Also, the target version has been
changed to 8.2.

https://wiki.php.net/rfc/rng_extension
https://github.com/php/php-src/pull/7453

Hopefully you will get some good responses.

Regards,
Go Kudo

This proposal seems like two different proposals to me:

The first consolidates and cleans up RNG functions for internals

The second exposes an OOP API for working with RNGs

Personally, I don't see the benefit of including this OOP API in the
core. I don't think it provides any benefits over similar abstractions
in userland, and in fact, I think this kind of API is best suited for
iteration in userland.

Cheers,
Ben

2 years ago by Ben Ramsey — view source

unread

Go Kudo wrote on 9/4/21 23:00:

Indeed, it may be true that these suggestions should not be made all at
once. If necessary, I would like to propose to organize the RNG
implementation first.

Do we still need an RFC in this case? I'm not sure I'm not fully understand
the criteria for an RFC. Does this internal API change count as a BC Break
that requires an RFC?

Yes, since re-organizing the RNG implementation is a major language
change that affects extensions and other downstream projects, this
requires an RFC.

Personally, I don't see the benefit of including this OOP API in the core.

On the other hand, can you tell me why you thought it was unnecessary?
Was my example unrealistic?

You also said, in reply to Dan Ackroyd:

Either way, I'll try to separate these suggestions if necessary, but if we
were to try to provide an OOP API without BC Break, what do you think would
be the ideal form?

The OOP API appears to be a wrapper around the RNG functions. The only
thing it gains by being in the core is widespread use, but it loses a
lot of flexibility and maintainability, since the API will be tied to
PHP release cycles.

By doing this as an OOP wrapper in userland code, you're not restricting
yourself to release only when PHP releases, and you can work with the
community (e.g., the PHP-FIG) to develop interfaces that other projects
might use so they can make use of their own RNGs, etc.

Cheers,
Ben

2 years ago by Pierre Joye — view source

unread

Hi Ben,

Go Kudo wrote on 9/4/21 23:00:

Indeed, it may be true that these suggestions should not be made all at
once. If necessary, I would like to propose to organize the RNG
implementation first.

The OOP API appears to be a wrapper around the RNG functions. The only
thing it gains by being in the core is widespread use, but it loses a
lot of flexibility and maintainability, since the API will be tied to
PHP release cycles.

By doing this as an OOP wrapper in userland code, you're not restricting
yourself to release only when PHP releases, and you can work with the
community (e.g., the PHP-FIG) to develop interfaces that other projects
might use so they can make use of their own RNGs, etc.

I tend to agree with you. However, the same logic applies to any non binary
bytes RNG, all of them derivate from there with constraints.

I suppose this is choice PHP has to take. I don't see such APIs changing
too much over time but maybe in the beginning. It could be done in two
phases.

best,
Pierre

2 years ago by Nikita Popov — view source

unread

Go Kudo wrote on 9/4/21 23:00:

Indeed, it may be true that these suggestions should not be made all at
once. If necessary, I would like to propose to organize the RNG
implementation first.

Do we still need an RFC in this case? I'm not sure I'm not fully
understand
the criteria for an RFC. Does this internal API change count as a BC
Break
that requires an RFC?

Yes, since re-organizing the RNG implementation is a major language
change that affects extensions and other downstream projects, this
requires an RFC.

Personally, I don't see the benefit of including this OOP API in the
core.

On the other hand, can you tell me why you thought it was unnecessary?
Was my example unrealistic?

You also said, in reply to Dan Ackroyd:

Either way, I'll try to separate these suggestions if necessary, but if
we
were to try to provide an OOP API without BC Break, what do you think
would
be the ideal form?

The OOP API appears to be a wrapper around the RNG functions. The only
thing it gains by being in the core is widespread use, but it loses a
lot of flexibility and maintainability, since the API will be tied to
PHP release cycles.

By doing this as an OOP wrapper in userland code, you're not restricting
yourself to release only when PHP releases, and you can work with the
community (e.g., the PHP-FIG) to develop interfaces that other projects
might use so they can make use of their own RNGs, etc.

The OO API is not just a wrapper around the RNG functions -- it provides
new functionality that cannot be efficiently implemented in userland code.
This is for two reasons:

It provides independent randomness streams, which means it's not
possible to reuse existing functionality like mt_rand() for this purpose,
which only provides a single global random number stream. You would have to
reimplement the random number generator in userland. While this is
possible, it will generally not be efficient, because PHP does not have
native support for unsigned modular arithmetic, which is what random number
generators generally need.
It allows using functions like shuffle() and array_rand() with an
independent randomness stream. These functions cannot be efficiently
implemented in userland, because userland does not have random access to
arrays. Internals can generate a random number and use it to pick the key
at that position, which is O(1). Userland would have to call array_keys()
first to allow random access on keys, which is O(n).

Which is why I think this is a good addition to php-src. There's three good
reasons to include functionality in php-src (performance, ubiquity and FFI)
and this falls squarely into the first category. And now that we have
fibers and need to worry more about multiple independent execution streams,
we also need to worry about multiple independent randomness streams.

Regards,
Nikita

2 years ago by Ben Ramsey — view source

unread

Nikita Popov wrote on 9/6/21 03:06:

Go Kudo wrote on 9/4/21 23:00:

Indeed, it may be true that these suggestions should not be made all at
once. If necessary, I would like to propose to organize the RNG
implementation first.

Do we still need an RFC in this case? I'm not sure I'm not fully
understand
the criteria for an RFC. Does this internal API change count as a BC
Break
that requires an RFC?

Yes, since re-organizing the RNG implementation is a major language
change that affects extensions and other downstream projects, this
requires an RFC.

Personally, I don't see the benefit of including this OOP API in the
core.

On the other hand, can you tell me why you thought it was unnecessary?
Was my example unrealistic?

You also said, in reply to Dan Ackroyd:

Either way, I'll try to separate these suggestions if necessary, but if
we
were to try to provide an OOP API without BC Break, what do you think
would
be the ideal form?

The OOP API appears to be a wrapper around the RNG functions. The only
thing it gains by being in the core is widespread use, but it loses a
lot of flexibility and maintainability, since the API will be tied to
PHP release cycles.

By doing this as an OOP wrapper in userland code, you're not restricting
yourself to release only when PHP releases, and you can work with the
community (e.g., the PHP-FIG) to develop interfaces that other projects
might use so they can make use of their own RNGs, etc.

The OO API is not just a wrapper around the RNG functions -- it provides
new functionality that cannot be efficiently implemented in userland code.
This is for two reasons:

It provides independent randomness streams, which means it's not
possible to reuse existing functionality like mt_rand() for this purpose,
which only provides a single global random number stream. You would have to
reimplement the random number generator in userland. While this is
possible, it will generally not be efficient, because PHP does not have
native support for unsigned modular arithmetic, which is what random number
generators generally need.

It allows using functions like shuffle() and array_rand() with an
independent randomness stream. These functions cannot be efficiently
implemented in userland, because userland does not have random access to
arrays. Internals can generate a random number and use it to pick the key
at that position, which is O(1). Userland would have to call array_keys()
first to allow random access on keys, which is O(n).

Which is why I think this is a good addition to php-src. There's three good
reasons to include functionality in php-src (performance, ubiquity and FFI)
and this falls squarely into the first category. And now that we have
fibers and need to worry more about multiple independent execution streams,
we also need to worry about multiple independent randomness streams.

Regards,
Nikita

Thanks for the clarification, Nikita.

The RFC says, "The Random class is a utility class that provides
functionality using random numbers." This led me to think it was a
wrapper that did not introduce new functionality.

I can't find any discussion in the RFC on the independent randomness
streams provided by the OOP API. Go Kudo, can you update the RFC with
more information about this functionality?

Cheers,
Ben

2 years ago by Go Kudo — view source

unread

Nikita, Thanks for the clarification.
That's exactly what I intended to do.

can you update the RFC with more information about this functionality?

I understand. Organize them and reconstruct the RFC text.

I've also created an RFC about moving RNG-related functions from
ext/standard to ext/random. I would appreciate it if you could check it out.

https://wiki.php.net/rfc/random_ext

Regards,
Go Kudo

2021年9月7日(火) 2:24 Ben Ramsey ramsey@php.net:

Nikita Popov wrote on 9/6/21 03:06:

Go Kudo wrote on 9/4/21 23:00:

Indeed, it may be true that these suggestions should not be made all at
once. If necessary, I would like to propose to organize the RNG
implementation first.

Do we still need an RFC in this case? I'm not sure I'm not fully
understand
the criteria for an RFC. Does this internal API change count as a BC
Break
that requires an RFC?

Yes, since re-organizing the RNG implementation is a major language
change that affects extensions and other downstream projects, this
requires an RFC.

Personally, I don't see the benefit of including this OOP API in the
core.

On the other hand, can you tell me why you thought it was unnecessary?
Was my example unrealistic?

You also said, in reply to Dan Ackroyd:

Either way, I'll try to separate these suggestions if necessary, but if
we
were to try to provide an OOP API without BC Break, what do you think
would
be the ideal form?

The OOP API appears to be a wrapper around the RNG functions. The only
thing it gains by being in the core is widespread use, but it loses a
lot of flexibility and maintainability, since the API will be tied to
PHP release cycles.

By doing this as an OOP wrapper in userland code, you're not restricting
yourself to release only when PHP releases, and you can work with the
community (e.g., the PHP-FIG) to develop interfaces that other projects
might use so they can make use of their own RNGs, etc.

The OO API is not just a wrapper around the RNG functions -- it provides
new functionality that cannot be efficiently implemented in userland
code.
This is for two reasons:

It provides independent randomness streams, which means it's not
possible to reuse existing functionality like mt_rand() for this purpose,
which only provides a single global random number stream. You would have
to
reimplement the random number generator in userland. While this is
possible, it will generally not be efficient, because PHP does not have
native support for unsigned modular arithmetic, which is what random
number
generators generally need.

It allows using functions like shuffle() and array_rand() with an
independent randomness stream. These functions cannot be efficiently
implemented in userland, because userland does not have random access to
arrays. Internals can generate a random number and use it to pick the key
at that position, which is O(1). Userland would have to call array_keys()
first to allow random access on keys, which is O(n).

Which is why I think this is a good addition to php-src. There's three
good
reasons to include functionality in php-src (performance, ubiquity and
FFI)
and this falls squarely into the first category. And now that we have
fibers and need to worry more about multiple independent execution
streams,
we also need to worry about multiple independent randomness streams.

Regards,
Nikita

Thanks for the clarification, Nikita.

The RFC says, "The Random class is a utility class that provides
functionality using random numbers." This led me to think it was a
wrapper that did not introduce new functionality.

I can't find any discussion in the RFC on the independent randomness
streams provided by the OOP API. Go Kudo, can you update the RFC with
more information about this functionality?

Cheers,
Ben