Everything

php

Home » Project » Newsgroups » php.internals » [RFC] [Under Discussion] Random Extension 4.0 »

[RFC] [Under Discussion] Random Extension 4.0

php.internals

Go Kudo

4 years ago

It's been a while Internals. I'm Go Kudo.

First of all, I would like to apologize for leaving my previous RFC, object
scoped RNG, and the preliminary RFC, split random extension, without any
progress.

The implementation of these RFCs was not sophisticated and failed to be
tested for a long time. In particular, we could not find the time to work
on them on Windows, and they were abandoned.

You may have noticed that my email address has changed. This is because I
have been assigned to work on this RFC and implementation as part of my
company. This has given me the equipment and time to debug in a variety of
environments.

Some people may have a negative impression about this change, but don't
worry. The RFC is still in the form of a feature proposal, and all rights
are reserved by the PHP Group.

Before we get into the RFC, let me explain again how this RFC came to be
proposed.

First, I started to implement an object-level scoped RNG in PHP to solve
the current issue. This is still available in PECL today.

https://pecl.php.net/package/orng
https://github.com/zeriyoshi/php-ext-orng

Later, I found in the PHP Internals ML logs that an implementation of RNG
with object-level scoping had been considered before, and was well received
at the time. However, it seems that the actual implementation was not done
at that time.

https://externals.io/message/98021#98130

After that, I started the first RFC and Vote. The result was a Decline, but
that was mainly due in part to the strange APIs.

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

The refreshed RFC and implementation are available at the following URL:

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

If there are no specific comments, I would like to start voting as soon as
the two-week pre-announcement phase is over.

Regards.
Go Kudo

Tim Düsterhus

4 years ago

Hi

On 2/14/22 12:11, Go Kudo wrote:

> The refreshed RFC and implementation are available at the following URL:
>
> https://wiki.php.net/rfc/rng_extension
> https://github.com/php/php-src/pull/8094
>
> If there are no specific comments, I would like to start voting as soon as
> the two-week pre-announcement phase is over.

1) XorShift128+ has a 128 Bit internal state, but takes an integer seed
within the constructor. Thus only 64 Bits of seed can be provided.

Maybe the seed parameter should be a 16-byte string instead?
Initializing the generator with a completely random seed would then be:

new XorShift128Plus(\random_bytes(16));

instead of the much more complicated:

new XorShift128Plus(\random_int(\PHP_INT_MIN, \PHP_INT_MAX));

Perhaps the following API would be even clearer:

XorShift128Plus::fromSeed(\random_bytes(16));
XorShift128Plus::fromGenerator(new Secure()); // Takes 16 bytes from the
given generator.

2) I would adjust the 'Randomizer' to use the 'Secure' generator as a
safe default. If absolute performance or a reproducible sequence is
required then one can use a custom generator, but the default will be
the secure CSPRNG, making it harder to misuse.

3) The RFC is inconsistent in the example code. Is it 'stringShuffle' or
'shuffleString'?

4) The RFC should document the 'NumberGenerator' interface. Specifically
I'm interested in the return type of the 'generate' method. Does it
return bytes or integers? Is it legal to implement the interface in
userland code?

Best regards
Tim Düsterhus

Go Kudo

4 years ago

2022年2月14日(月) 20:40 Tim Düsterhus <timwolla@bastelstu.be>:

> Hi
>
> On 2/14/22 12:11, Go Kudo wrote:
> > The refreshed RFC and implementation are available at the following URL:
> >
> > https://wiki.php.net/rfc/rng_extension
> > https://github.com/php/php-src/pull/8094
> >
> > If there are no specific comments, I would like to start voting as soon
> as
> > the two-week pre-announcement phase is over.
>
> 1) XorShift128+ has a 128 Bit internal state, but takes an integer seed
> within the constructor. Thus only 64 Bits of seed can be provided.
>
> Maybe the seed parameter should be a 16-byte string instead?
> Initializing the generator with a completely random seed would then be:
>
> new XorShift128Plus(\random_bytes(16));
>
> instead of the much more complicated:
>
> new XorShift128Plus(\random_int(\PHP_INT_MIN, \PHP_INT_MAX));
>
> Perhaps the following API would be even clearer:
>
> XorShift128Plus::fromSeed(\random_bytes(16));
> XorShift128Plus::fromGenerator(new Secure()); // Takes 16 bytes from the
> given generator.
>
> 2) I would adjust the 'Randomizer' to use the 'Secure' generator as a
> safe default. If absolute performance or a reproducible sequence is
> required then one can use a custom generator, but the default will be
> the secure CSPRNG, making it harder to misuse.
>
> 3) The RFC is inconsistent in the example code. Is it 'stringShuffle' or
> 'shuffleString'?
>
> 4) The RFC should document the 'NumberGenerator' interface. Specifically
> I'm interested in the return type of the 'generate' method. Does it
> return bytes or integers? Is it legal to implement the interface in
> userland code?
>
> Best regards
> Tim Düsterhus
>

Hi

> 1) XorShift128+ has a 128 Bit internal state, but takes an integer seed

within the constructor. Thus only 64 Bits of seed can be provided.

This is for convenience. Other software that uses XorShift128+, such as
Chromium (V8), also uses a 64-bit value for the initial seed value.
I think that 128-bit value seeding with strings is unintuitive and not very
good for performance.

https://chromium.googlesource.com/v8/v8/+/refs/heads/main/src/base/utils/random-number-generator.h

> 2) I would adjust the 'Randomizer' to use the 'Secure' generator as a

safe default. If absolute performance or a reproducible sequence is
required then one can use a custom generator, but the default will be the
secure CSPRNG, making it harder to misuse.

Certainly, this may be appropriate. But, in this case, the Randomizer
generated with the default parameters will not be serializable. Is that
acceptable?

Personally, I think this is a good change.

> 3) The RFC is inconsistent in the example code. Is it 'stringShuffle' or

'shuffleString'?

RFC Fixed :)

> 4) The RFC should document the 'NumberGenerator' interface. Specifically

I'm interested in the return type of the 'generate' method. Does it return
bytes or integers? Is it legal to implement the interface in userland code?

It returns an int. Also, as pointed out in GH, the generated value is
implicitly treated as the size equivalent of PHP_INT_SIZE (zend_long) on
the environment. This means that it is not possible to implement the
userland Mersenne twister (32-bit) in a 64-bit environment.

https://github.com/php/php-src/pull/8094#pullrequestreview-881660425

Tim Düsterhus

4 years ago

Hi

On 2/14/22 15:53, Go Kudo wrote:

>> 1) XorShift128+ has a 128 Bit internal state, but takes an integer seed
> within the constructor. Thus only 64 Bits of seed can be provided.
>
> This is for convenience. Other software that uses XorShift128+, such as
> Chromium (V8), also uses a 64-bit value for the initial seed value.
> I think that 128-bit value seeding with strings is unintuitive and not very
> good for performance.
>
> https://chromium.googlesource.com/v8/v8/+/refs/heads/main/src/base/utils/random-number-generator.h

I don't think performance for seeding the RNG matters. That's an
operation you only perform once (or a small number of times). The time
for the actual generation of random numbers most certainly dwarfs the
time used for seeding.

Regarding "unintuitive": I disagree. I find it unintuitive that there
are some RNG sequences that I can't access when providing a seed.

I wouldn't object a convenience constructor that also accepts an
integer, but I believe the default should be a seed that is appropriate
to generate the full state space.

>> 2) I would adjust the 'Randomizer' to use the 'Secure' generator as a
> safe default. If absolute performance or a reproducible sequence is
> required then one can use a custom generator, but the default will be the
> secure CSPRNG, making it harder to misuse.
>
> Certainly, this may be appropriate. But, in this case, the Randomizer
> generated with the default parameters will not be serializable. Is that
> acceptable?

I consider that acceptable. If I want to serialize the randomizer then I
want a reproducible sequence and in that case I should also be forced to
explicitly decide what type of reproducible sequence I want. If I don't
explicitly decide, then newly generated randomizers might use an
entirely different generator if the default changes.,

>> 4) The RFC should document the 'NumberGenerator' interface. Specifically
> I'm interested in the return type of the 'generate' method. Does it return
> bytes or integers? Is it legal to implement the interface in userland code?
>
> It returns an int. Also, as pointed out in GH, the generated value is
> implicitly treated as the size equivalent of PHP_INT_SIZE (zend_long) on
> the environment. This means that it is not possible to implement the
> userland Mersenne twister (32-bit) in a 64-bit environment.

I think the returned value of the generator should be a string
containing raw bytes.

It's very easy to interpret a bytestring as an appropriate integer (e.g.
using unpack()), but if some consumer needs a bytestring then turning
the integer back into a bytestring without accidentally introducing
biases is much harder, because of platform differences and the lack of
unsigned integers in userland.

Unfortunately your PR doesn't compile for me, so I can't test:

make: *** No rule to make target 'php-src/ext/standard/lcg.c', needed by
'ext/standard/lcg.lo'.  Stop.

Best regards
Tim Düsterhus

Tim Düsterhus

4 years ago

Hi

On 2/14/22 16:44, Tim Düsterhus wrote:

> Unfortunately your PR doesn't compile for me, so I can't test:
>
> make: *** No rule to make target 'php-src/ext/standard/lcg.c', needed by
> 'ext/standard/lcg.lo'.  Stop.

I've managed to compile it by cleaning the whole directory and rerunning
of the build steps. Not sure what I missed the first time.

I've now been able to play around with it and have some additional
discussion points:

1) Consider the following script:


<?php

use Random\NumberGenerator\XorShift128Plus;
use Random\Randomizer;

$g1 = new XorShift128Plus(2);
$g2 = clone $g1;

$r1 = new Randomizer($g1);
$r2 = new Randomizer($g2);

var_dump(\bin2hex($r1->getBytes(8)));
var_dump(\bin2hex($r2->getBytes(4)) . \bin2hex($r2->getBytes(4)));

As a user: Would you expect those two 'var_dump' calls to result in the
same output?

Personally I would. For me that implies:

1. generate() should return raw bytes instead of a number (as I
suggested before).
2. The 'Randomizer' object should buffer unused bytes internally and
only call generate() if the internal buffer is drained.

2) Why xorshift instead of xoshiro / xoroshiro?

https://vigna.di.unimi.it/xorshift/ says that:

> Information about my previous xorshift-based generators can be found here, but they have been entirely superseded by the new ones, which are faster and better.

That would imply to me that xorshift should not be used in new developments.

3) Consider the following script:

<?php

use Random\NumberGenerator\XorShift128Plus;

$g1 = new XorShift128Plus(2);

var_dump($g1);

exit;

Should the user be able to see the internal state of the Generator in
the var_dump() output?

4) Both xorshift as well as xoshiro / xoroshiro's reference
implementations include a 'jump()' function that allows one to easily
retrieve generators with distinct sequences, without needing to generate
seeds manually which might or might nor introduce a bias.

Is this something that we should provide as well?

5) As a follow-up to (4): Should the 'generate()' method be called
'next()' or 'step()' instead? Perhaps it should even be '__invoke()'?

Best regards
Tim Düsterhus

Go Kudo

4 years ago

2022年2月15日(火) 1:46 Tim Düsterhus <tim@bastelstu.be>:

> Hi
>
> On 2/14/22 16:44, Tim Düsterhus wrote:
> > Unfortunately your PR doesn't compile for me, so I can't test:
> >
> > make: *** No rule to make target 'php-src/ext/standard/lcg.c', needed by
> > 'ext/standard/lcg.lo'.  Stop.
>
> I've managed to compile it by cleaning the whole directory and rerunning
> of the build steps. Not sure what I missed the first time.
>
> I've now been able to play around with it and have some additional
> discussion points:
>
> 1) Consider the following script:
>
>
>      <?php
>
>      use Random\NumberGenerator\XorShift128Plus;
>      use Random\Randomizer;
>
>      $g1 = new XorShift128Plus(2);
>      $g2 = clone $g1;
>
>      $r1 = new Randomizer($g1);
>      $r2 = new Randomizer($g2);
>
>      var_dump(\bin2hex($r1->getBytes(8)));
>      var_dump(\bin2hex($r2->getBytes(4)) . \bin2hex($r2->getBytes(4)));
>
> As a user: Would you expect those two 'var_dump' calls to result in the
> same output?
>
> Personally I would. For me that implies:
>
>    1. generate() should return raw bytes instead of a number (as I
> suggested before).
>    2. The 'Randomizer' object should buffer unused bytes internally and
> only call generate() if the internal buffer is drained.
>
> 2) Why xorshift instead of xoshiro / xoroshiro?
>
> https://vigna.di.unimi.it/xorshift/ says that:
>
> > Information about my previous xorshift-based generators can be found
> here, but they have been entirely superseded by the new ones, which are
> faster and better.
>
> That would imply to me that xorshift should not be used in new
> developments.
>
> 3) Consider the following script:
>
>      <?php
>
>      use Random\NumberGenerator\XorShift128Plus;
>
>      $g1 = new XorShift128Plus(2);
>
>      var_dump($g1);
>
>      exit;
>
> Should the user be able to see the internal state of the Generator in
> the var_dump() output?
>
> 4) Both xorshift as well as xoshiro / xoroshiro's reference
> implementations include a 'jump()' function that allows one to easily
> retrieve generators with distinct sequences, without needing to generate
> seeds manually which might or might nor introduce a bias.
>
> Is this something that we should provide as well?
>
> 5) As a follow-up to (4): Should the 'generate()' method be called
> 'next()' or 'step()' instead? Perhaps it should even be '__invoke()'?
>
> Best regards
> Tim Düsterhus
>

If there are no objections, I will change the NumberGenerator that
Randomizer uses by default to Secure.

> Regarding "unintuitive": I disagree. I find it unintuitive that there are

some RNG sequences that I can't access when providing a seed.

This is also the case for RNG implementations in many other languages. For
example, Java also uses long (64-bit) as the seed value of the argument for
Math.

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Random.html#%3Cinit%3E(long)

As mentioned above, V8 also uses a 64-bit value as the seed value, and
generating with XorShift128+.

https://github.com/v8/v8/blob/main/src/base/utils/random-number-generator.h

On the other hand, some languages have access to the complete internal
state. Python, for example, accepts bytes or bytearrays.

https://docs.python.org/3/library/random.html#random.seed

However, making strings available in PHP may lead to incorrect usage.

I think we can safely do this by making the seed argument accept both int
and string, and only using it as the internal state if string is specified
and it's 128-bits long.

> I've managed to compile it by cleaning the whole directory and rerunning

of the build steps. Not sure what I missed the first time.

This is probably due to a major change in config.m4. ./buidconf and
./configure need to be rerun properly.

> 1. Would you expect those two 'var_dump' calls to result in the same

output?

Added __debugInfo() magic method supports.

https://github.com/php/php-src/pull/8094/commits/78efd2bd1e0ac5db48c272b364a615a5611e8caa

> generate() should return raw bytes instead of a number (as I suggested

before).

I don't think this is a very good idea.

The RNG is a random number generator and should probably not be generating
strings.
Of course, I am aware that strings represent binary sequences in PHP.
However, this is not user-friendly.

The generation of a binary string is a barrier when trying to implement
some kind of operation using numeric computation.

If you want to deal with the problem of generated size, it would be more
appropriate to define a method such as getGenerateSize() in the interface.
Even in this case, generation widths greater than PHP_INT_SIZE cannot be
supported, but generation widths greater than 64-bit are not very useful in
the first place.

> The 'Randomizer' object should buffer unused bytes internally and only

call generate() if the internal buffer is drained.

Likewise, I think this is not a good idea. Buffering reintroduces the
problem of complex state management, which has been made so easy. The user
will always have to worry about the buffering size of the Randomizer.

> Why xorshift instead of xoshiro / xoroshiro?

The XorShift128Plus algorithm is still in use in major browsers and is dead
in a good way.

Also, in our local testing, SplitMix64 + XorShift128Plus performed well in
terms of performance and random number quality, so I don't think it is
necessary to choose a different algorithm.

If this RFC passes, it will be easier to add algorithms in the future. If a
new algorithm is needed, it can be implemented immediately.

Regards,
Go Kudo

Tim Düsterhus

4 years ago

Hi

On 2/15/22 04:58, Go Kudo wrote:

>> Regarding "unintuitive": I disagree. I find it unintuitive that there are
> some RNG sequences that I can't access when providing a seed.
>
> This is also the case for RNG implementations in many other languages. For
> example, Java also uses long (64-bit) as the seed value of the argument for
> Math.
>
> https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Random.html#%3Cinit%3E(long)

java.util.Random is a LCG with only 48 Bits of state. A single 64-bit
signed long is sufficient to represent the state.

> On the other hand, some languages have access to the complete internal
> state. Python, for example, accepts bytes or bytearrays.
>
> https://docs.python.org/3/library/random.html#random.seed
>
> However, making strings available in PHP may lead to incorrect usage.
>
> I think we can safely do this by making the seed argument accept both int
> and string, and only using it as the internal state if string is specified
> and it's 128-bits long.

That's a solution that would work for me.

>> 1. Would you expect those two 'var_dump' calls to result in the same
> output?
>
> Added __debugInfo() magic method supports.
>
> https://github.com/php/php-src/pull/8094/commits/78efd2bd1e0ac5db48c272b364a615a5611e8caa

Don't forget to update the RFC accordingly. It would probably be helpful
if you would put the full class stubs into the RFC. I find that easier
to understand than a list of methods.

>> generate() should return raw bytes instead of a number (as I suggested
> before).
>
> I don't think this is a very good idea.
>
> The RNG is a random number generator and should probably not be generating
> strings.

I'd say that the 'number' part in RNG is not technically accurate. All
RNGs are effectively generators for a random sequence of bits. The
number part is just an interpretation of those random sequence of bits
(e.g. 64 of them).

> Of course, I am aware that strings represent binary sequences in PHP.
> However, this is not user-friendly.
>
> The generation of a binary string is a barrier when trying to implement
> some kind of operation using numeric computation.

I believe the average user of the RNG API would use the Randomizer
class, instead of the raw generators, thus they would not come in
contact with the raw bytes coming from the generator.

However by getting PHP integers out of the generator it is much harder
for me to process the raw bits and bytes, if that's something I need for
my use case.

As an example if I want to implement the following in userland. Then
with getting raw bytes:
- For Randomizer::getBytes() I can just concatenate the raw bytes.
- For a random uint16BE I can grab 2 bytes and call unpack('n', $bytes)

If I get random 64 Bit integers then:
- For Randomizer::getBytes() I need to use pack and I'm not even sure,
whether I need to use 'q', 'Q', 'J', 'P' to receive an unbiased result.
- For uint16BE I can use "& 0xFFFF", but would waste 48 Bits, unless I
also perform bit shifting to access the other bytes. But then there's
also the same signedness issue.

Interpreting numbers as bytes and vice versa in C / C++ is very easy.
However in PHP userland I believe the bytes -> numbers direction is
easy-ish. The numbers -> bytes direction is full of edge cases.

> If you want to deal with the problem of generated size, it would be more
> appropriate to define a method such as getGenerateSize() in the interface.
> Even in this case, generation widths greater than PHP_INT_SIZE cannot be
> supported, but generation widths greater than 64-bit are not very useful in
> the first place.
>
>> The 'Randomizer' object should buffer unused bytes internally and only
> call generate() if the internal buffer is drained.
>
> Likewise, I think this is not a good idea. Buffering reintroduces the
> problem of complex state management, which has been made so easy. The user
> will always have to worry about the buffering size of the Randomizer.

Unfortunately you did not answer the primary question. The ones you
answered were just follow-up conclusions from the answer I would give:

var_dump(\bin2hex($r1->getBytes(8)));
var_dump(\bin2hex($r2->getBytes(4)) . \bin2hex($r2->getBytes(4)));

As a user: Would you expect those two 'var_dump' calls to result in the
same output?

>> Why xorshift instead of xoshiro / xoroshiro?
>
> The XorShift128Plus algorithm is still in use in major browsers and is dead
> in a good way.

I believe that that the underlying RNG in web browsers is considered an
implementation detail, no?

For PHP this would be part of the API surface and would need to be
maintained indefinitely. Certainly it would make sense to use the latest
and greatest RNG, instead of something that is outdated when its first
shipped, no?

> Also, in our local testing, SplitMix64 + XorShift128Plus performed well in
> terms of performance and random number quality, so I don't think it is
> necessary to choose a different algorithm.
>
> If this RFC passes, it will be easier to add algorithms in the future. If a
> new algorithm is needed, it can be implemented immediately.

Best regards
Tim Düsterhus

Go Kudo

4 years ago

2022年2月15日(火) 19:03 Tim Düsterhus <tim@bastelstu.be>:

> Hi
>
> On 2/15/22 04:58, Go Kudo wrote:
> >> Regarding "unintuitive": I disagree. I find it unintuitive that there
> are
> > some RNG sequences that I can't access when providing a seed.
> >
> > This is also the case for RNG implementations in many other languages.
> For
> > example, Java also uses long (64-bit) as the seed value of the argument
> for
> > Math.
> >
> >
> https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Random.html#%3Cinit%3E(long)
>
> java.util.Random is a LCG with only 48 Bits of state. A single 64-bit
> signed long is sufficient to represent the state.
>
> > On the other hand, some languages have access to the complete internal
> > state. Python, for example, accepts bytes or bytearrays.
> >
> > https://docs.python.org/3/library/random.html#random.seed
> >
> > However, making strings available in PHP may lead to incorrect usage.
> >
> > I think we can safely do this by making the seed argument accept both int
> > and string, and only using it as the internal state if string is
> specified
> > and it's 128-bits long.
>
> That's a solution that would work for me.
>
> >> 1. Would you expect those two 'var_dump' calls to result in the same
> > output?
> >
> > Added __debugInfo() magic method supports.
> >
> >
> https://github.com/php/php-src/pull/8094/commits/78efd2bd1e0ac5db48c272b364a615a5611e8caa
>
> Don't forget to update the RFC accordingly. It would probably be helpful
> if you would put the full class stubs into the RFC. I find that easier
> to understand than a list of methods.
>
> >> generate() should return raw bytes instead of a number (as I suggested
> > before).
> >
> > I don't think this is a very good idea.
> >
> > The RNG is a random number generator and should probably not be
> generating
> > strings.
>
> I'd say that the 'number' part in RNG is not technically accurate. All
> RNGs are effectively generators for a random sequence of bits. The
> number part is just an interpretation of those random sequence of bits
> (e.g. 64 of them).
>
> > Of course, I am aware that strings represent binary sequences in PHP.
> > However, this is not user-friendly.
> >
> > The generation of a binary string is a barrier when trying to implement
> > some kind of operation using numeric computation.
>
> I believe the average user of the RNG API would use the Randomizer
> class, instead of the raw generators, thus they would not come in
> contact with the raw bytes coming from the generator.
>
> However by getting PHP integers out of the generator it is much harder
> for me to process the raw bits and bytes, if that's something I need for
> my use case.
>
> As an example if I want to implement the following in userland. Then
> with getting raw bytes:
> - For Randomizer::getBytes() I can just concatenate the raw bytes.
> - For a random uint16BE I can grab 2 bytes and call unpack('n', $bytes)
>
> If I get random 64 Bit integers then:
> - For Randomizer::getBytes() I need to use pack and I'm not even sure,
> whether I need to use 'q', 'Q', 'J', 'P' to receive an unbiased result.
> - For uint16BE I can use "& 0xFFFF", but would waste 48 Bits, unless I
> also perform bit shifting to access the other bytes. But then there's
> also the same signedness issue.
>
> Interpreting numbers as bytes and vice versa in C / C++ is very easy.
> However in PHP userland I believe the bytes -> numbers direction is
> easy-ish. The numbers -> bytes direction is full of edge cases.
>
> > If you want to deal with the problem of generated size, it would be more
> > appropriate to define a method such as getGenerateSize() in the
> interface.
> > Even in this case, generation widths greater than PHP_INT_SIZE cannot be
> > supported, but generation widths greater than 64-bit are not very useful
> in
> > the first place.
> >
> >> The 'Randomizer' object should buffer unused bytes internally and only
> > call generate() if the internal buffer is drained.
> >
> > Likewise, I think this is not a good idea. Buffering reintroduces the
> > problem of complex state management, which has been made so easy. The
> user
> > will always have to worry about the buffering size of the Randomizer.
>
> Unfortunately you did not answer the primary question. The ones you
> answered were just follow-up conclusions from the answer I would give:
>
>       var_dump(\bin2hex($r1->getBytes(8)));
>       var_dump(\bin2hex($r2->getBytes(4)) . \bin2hex($r2->getBytes(4)));
>
> As a user: Would you expect those two 'var_dump' calls to result in the
> same output?
>
> >> Why xorshift instead of xoshiro / xoroshiro?
> >
> > The XorShift128Plus algorithm is still in use in major browsers and is
> dead
> > in a good way.
>
> I believe that that the underlying RNG in web browsers is considered an
> implementation detail, no?
>
> For PHP this would be part of the API surface and would need to be
> maintained indefinitely. Certainly it would make sense to use the latest
> and greatest RNG, instead of something that is outdated when its first
> shipped, no?
>
> > Also, in our local testing, SplitMix64 + XorShift128Plus performed well
> in
> > terms of performance and random number quality, so I don't think it is
> > necessary to choose a different algorithm.
> >
> > If this RFC passes, it will be easier to add algorithms in the future.
> If a
> > new algorithm is needed, it can be implemented immediately.
>
> Best regards
> Tim Düsterhus
>

> java.util.Random is a LCG with only 48 Bits of state. A single 64-bit

signed long is sufficient to represent the state.

Sorry about that. Java was not affected by this problem.

At first, I updated the RFC to the latest status.

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

I need some time to think about the current issue. I understand its
usefulness, but I feel uncomfortable with the fact that the NumberGenerator
generates a string.

I also wonder about the point of changing RNG to XorShift128Plus. There are
a number of derived implementations, which RNG do you think is more
suitable?

Regards,
Go Kudo

Tim Düsterhus

4 years ago

Hi

On 2/15/22 12:48, Go Kudo wrote:

> At first, I updated the RFC to the latest status.
>
> https://wiki.php.net/rfc/rng_extension

Thank you, the examples are useful.

> I need some time to think about the current issue. I understand its
> usefulness, but I feel uncomfortable with the fact that the NumberGenerator
> generates a string.

Would you feel more comfortable if the interface would be called
\Random\Engine or \Random\Generator (i.e. leaving out the "Number" from
the interface name)?

Engine is the term used by C++:
https://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
Generator is the term used by Java:
https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/RandomGenerator.html

----------

With the 'FixedForUnitTest' example you mentioned in the RFC: While for
that specific implementation it appears pretty obvious that increasing
numbers are generated, in practice:

1. This will result in inconsistent behavior based on the architecture.
I can't test it due to the lack of the necessary architectures, but I
believe the following to be accurate:

$g = new FixedForUnitTest();

$r = new Randomizer($g);

// 0100000000000000 in 64 Bit little endian
// 0100000002000000 in 32 Bit little endian
// 0000000000000001 in 64 Bit big endian
var_dump(bin2hex($r->getBytes(8)));

2. This analogy completely breaks down for the 'shuffle' functions which
call the generator internally an unspecified number of times:

$g = new FixedForUnitTest();

$r = new Randomizer($g);

var_dump($r->shuffleString("abcdefghijklmnopqrstuvwxyz")); //
wosqyrupatvxznmlkjihgfedcb
var_dump($r->shuffleString("abcdefghijklmnopqrstuvwxyz")); //
fwrtjndlsyvpzuhxbqomkigeca

The resulting strings look somewhat ordered, but there is no clear
pattern, despite the underlying generator being completely predictable!

> I also wonder about the point of changing RNG to XorShift128Plus. There are
> a number of derived implementations, which RNG do you think is more
> suitable?
>

I'm not an expert in RNGs, but based off this page:
https://prng.di.unimi.it/ and the linked papers it appears that
xoshiro256** is the overall best choice if memory usage is not a concern.

Best regards
Tim Düsterhus

Go Kudo

4 years ago

2022年2月15日(火) 22:09 Tim Düsterhus <tim@bastelstu.be>:

> Hi
>
> On 2/15/22 12:48, Go Kudo wrote:
> > At first, I updated the RFC to the latest status.
> >
> > https://wiki.php.net/rfc/rng_extension
>
> Thank you, the examples are useful.
>
> > I need some time to think about the current issue. I understand its
> > usefulness, but I feel uncomfortable with the fact that the
> NumberGenerator
> > generates a string.
>
> Would you feel more comfortable if the interface would be called
> \Random\Engine or \Random\Generator (i.e. leaving out the "Number" from
> the interface name)?
>
> Engine is the term used by C++:
> https://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine
> Generator is the term used by Java:
>
> https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/RandomGenerator.html
>
> ----------
>
> With the 'FixedForUnitTest' example you mentioned in the RFC: While for
> that specific implementation it appears pretty obvious that increasing
> numbers are generated, in practice:
>
> 1. This will result in inconsistent behavior based on the architecture.
> I can't test it due to the lack of the necessary architectures, but I
> believe the following to be accurate:
>
>      $g = new FixedForUnitTest();
>
>      $r = new Randomizer($g);
>
>      // 0100000000000000 in 64 Bit little endian
>      // 0100000002000000 in 32 Bit little endian
>      // 0000000000000001 in 64 Bit big endian
>      var_dump(bin2hex($r->getBytes(8)));
>
> 2. This analogy completely breaks down for the 'shuffle' functions which
> call the generator internally an unspecified number of times:
>
>      $g = new FixedForUnitTest();
>
>      $r = new Randomizer($g);
>
>      var_dump($r->shuffleString("abcdefghijklmnopqrstuvwxyz")); //
> wosqyrupatvxznmlkjihgfedcb
>      var_dump($r->shuffleString("abcdefghijklmnopqrstuvwxyz")); //
> fwrtjndlsyvpzuhxbqomkigeca
>
> The resulting strings look somewhat ordered, but there is no clear
> pattern, despite the underlying generator being completely predictable!
>
> > I also wonder about the point of changing RNG to XorShift128Plus. There
> are
> > a number of derived implementations, which RNG do you think is more
> > suitable?
> >
>
> I'm not an expert in RNGs, but based off this page:
> https://prng.di.unimi.it/ and the linked papers it appears that
> xoshiro256** is the overall best choice if memory usage is not a concern.
>
> Best regards
> Tim Düsterhus
>

Hi Tim.

Thanks for the good idea. I changed the NumberGenerator to Engine and
changed generate() to return a string as suggested.

The main changes since last time are as follows:

- The userland implementation can now specify the width of the random
number sequence that can be generated
- Random\Engine::nextByteSize() has been added
- Random\Engine::generate() now returns a string
- Random\Randomizer::getInt() now accepts an empty argument (like mt_rand())

At the same time, I have updated the RFC.

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

I have not yet come to a final conclusion on whether XorShift128Plus should
be switched to another RNG. For example, what about implementing
XorShift128Plus, but adding Xoshiro256** as well?