Improving PRNG implementation. View as Markdown

Thanks. I have edited the RFC based on your question.

Method names: you don't need to emulate the conventions from non-OOP
code, e.g. string_shuffle() --> strShuffle and array_rand() -->
arrayRand(). Use a more naturally readable convention like shuffleString().

As mentioned in the RFC, it is intended for interoperability. However, you
may be right that we should forget the past and aim for a better
implementation.

Do you have evidence of widespread demand for this functionality? Usage
statistics for the userland implementation you mentioned[3] don't look that
hot.

A difficult problem. At least for PHP, which is a web-oriented language,
there may be little demand for it.

In my opinion, an object-scoped implementation will be needed in the
future. For example, there are currently proposed implementations of Fiber,
which will certainly make global state unpredictable. Swoole extension is
also a concern, although I am not familiar with this.

Regards,
Go Kudo

2020年12月20日(日) 23:09 Max Semenik maxsem.wiki@gmail.com:

Thanks cmb. I have created a first draft of an RFC. I think I've covered
all the necessary requirements, but I'd like to know if there are any
problems.
https://wiki.php.net/rfc/object_scope_prng

A few IMHO comments:

• Namespaces are controversial. There were multiple discussions and RFCs
  about introducing them for new functionality but nothing came out of it.
  Still probably worth adding an option for \PHP\PRNG to the vote, or
  something like that.
• The "Which set of PRNGs should be provided as standard?" vote seems
  vague to me. Are you proposing to add only one algorithm? Why? Also, the
  adding just interfaces option makes no sense because there's Composer for
  things that don't require a C implementation.
• "One possible solution is to implement the PRNG in pure PHP. There is
  actually a userland library [1], but it is not fast enough for PHP at the
  moment. (However, this may be improved by JIT)" - this definitely needs a
  comparison because implementation in C is only needed for performance
  reasons.
• Method names: you don't need to emulate the conventions from non-OOP
  code, e.g. string_shuffle() --> strShuffle and array_rand() -->
  arrayRand(). Use a more naturally readable convention like shuffleString().
• The return value in "function shuffle(array &$array): bool" means that
  if something goes wrong, callers will have no idea what it is. Just throw
  an exception.
• If the classes are namespaced, don't prefix their names,
  e.g. PRNGInterface --> RandomGenerator (yay, so many opportunities for
  bikeshedding!)
• Perhaps it's worth mentioning other languages using this pattern, e.g.
  Java[1] and C#[2].
• Do you have evidence of widespread demand for this functionality? Usage
  statistics for the userland implementation you mentioned[3] don't look that
  hot.

---

[1] https://docs.oracle.com/javase/8/docs/api/java/util/Random.html
[2] https://docs.microsoft.com/en-us/dotnet/api/system.random?view=net-5.0
[3] https://packagist.org/packages/savvot/random

Hi Marc, and sorry for the late reply. Email has been marked as spam...

I would expect the Random number generator to implement from Iterator
using an integer for current() value
and providing utility functions (simple functions or methods of another
class) for shuffle, random array entry like this:

Thank you very much. This suggestion makes sense and looks very structured.

However, I feel that in the PHP world, this structuring is a bit too much.
Ease of use is very important in PHP.

Nevertheless, I am satisfied with this proposal. I'd like to hear from
someone who is more familiar with the PHP context about the form of the
implementation.

But, it may be faster to actually hold a vote to ask this question. I'm not
sure how much support this proposal has at this point, but do you think
it's worth a try?

2020年12月29日(火) 18:26 Marc marc@mabe.berlin:

Hi zeriyoshi,

Thanks tyson.

This would also make it easier to use those generators in brand new

algorithms that weren't in the initial RFC.

(or in algorithms written by users in PHP)

This suggestion seems to make sense. Maybe the RNG should only focus on
generating random numbers and not anything else.
However, the fact that array and string manipulation functions are no
longer native to C may have a speed disadvantage.

So I came up with the idea of minimizing the interface definition as RNG.

interface PRNGInterface
{
    public function nextInt(?int $min = null, ?int $max = null): int;
    public function nextDouble(): double; // maybe, non-needed.
    public function nextByte(int $length): string;
}

The methods for array and string operations are defined separately as
interfaces that inherit from the interface.

interface RandomInterface extends PRNGInterface
{
    public function shuffle(array &$array): bool;
    public function arrayRand(array $array, int $num = 1): int|string|array;
    public function strShuffle(string $string): string;
}

This can be overly structured, but it will serve all purposes.

Personally I feel the interfaces still looking a bit off to me.

I would expect the Random number generator to implement from Iterator
using an integer for current() value

and providing utility functions (simple functions or methods of another
class) for shuffle, random array entry like this:

interface RNG extends Iterator {
    public function `rewind()`;
    public function `next()`;
    public function `current()`: int;
    public function `key()`: int;
    public function valid();
}


interface PRNG extends RNG {
    public function __current(int $seed);
    public function getSeed(): int;
}

class RNGUtil {
    public static function shuffleArray(int $randomNumber, array $arr): array;
    public static function randomArrayElement(int $randomNumber, array $arr): mixed;
    public static function between(int $randomNumber, int $min = PHP_INT_MIN, int $max = PHP_INT_MAX): int;
    public static function bytes(RNG $rng, int $length): string;
}

Regards,
Go Kudo

2020年12月23日(水) 0:40 tyson andre tysonandre775@hotmail.com tysonandre775@hotmail.com:

Hi Go Kudo,

A possible alternative that is widely used in other programming
languages is to limit the interface API to only generating bytes/integers,
and to provide global functions that would use generic random number
generator objects (from internal or user-provided code) in their algorithms.

This would also make it easier to use those generators in brand new
algorithms that weren't in the initial RFC.
(or in algorithms written by users in PHP)

This alternative is similar to Javahttps://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#shuffle(java.util.List,%20java.util.Random)
and https://docs.oracle.com/javase/7/docs/api/java/util/Random.html
and C++ https://www.cplusplus.com/reference/algorithm/shuffle/
where the algorithms accept a random number generator conforming to some
interface
and Python https://docs.python.org/3/library/random.html#random.shuffle

interface PRNGInterface {
    public function random[Signed]Int(): int;  // between `PHP_INT_MIN` and
`PHP_INT_MAX` (4 bytes or 8 bytes)
    public function randomBytes(int $length): string // $length bytes of
raw data
    // possibly randomByte(): int // between 0 and 255
    // public function randomIntInRange(int $min, int $max)
    // __serialize(), __unserialize() may be provided, but may be
counterproductive for classes that wrap /dev/urandom or `random_bytes()`?
}
// possibly provide a trait that provides defaults based on abstract
function randomInt

function whateverprefixornamespace_rand(PRNGInterface $rng, [int $min, int
$max]): int {}
// If this is intended to be secure, whateverprefix_array_rand may need to
avoid the optimizations used by array_rand for sparse arrays
function whateverprefixornamespace_array_rand(PRNGInterface $rng, array
$array, ...): int {}
function whateverprefixornamespace_shuffle(PRNGInterface $rng, array
&$array): bool;
// alternately might be possible by extending existing global functions
with an optional parameter

Thanks,

• Tyson

Hello Nikita.

In addition to the functions you already list, I'd add
function rng_bytes(RNGInterface $rng, int $length): string;
function rng_between(RNGInterface $rng, int $min, int $max): int;
Certainly these are useful. I've added this to the RFC in TypeC.

Just to share another possibility, we could also modify existing
functions to optionally accept RNGInterface, like
shuffle(array &$array, ?RNGInterface $rng = null): bool;
This approach may be appropriate. This way, the user is implicitly aware
that he is using a global state RNG.

What do you mean by "use unintended instances" here?
For example, if you write the following code, the user will receive an
unintended result.

$rng1 = new \RNG\XorShift128Plus(1234);
$rng2 = new \RNG\MT19937(1234);

$arr1 = range(1, 100);
$arr2 = range(1, 100);
rng_shuffle($rng1, $arr1);
rng_shuffle($rng1, $arr2); // oops, this case uses $rng1 RNG instance.

I believe that if these features are provided by class methods, such
mistakes can be avoided.
However, it is a matter of likelihood and similar mistakes can happen
anyway.

Regarding implementation complexity, yes, this version is a bit more
involved if we want to allow userland implementations of RNGInterface. To
be honest I don't particularly care about supporting userland (we could
also only allow it to be implemented internally), but I think it shouldn't
be too hard either.
Yes, it's probably possible. I need to understand the PHP implementation
more deeply :)
If you know of any implementations that might be helpful, I would like to
know about them.

As for the implementation of userland, I don't put that much emphasis on it
either. I just use classes for clarity, and I'm fine only provided by the
core or extensions.

This is generally the part I'm least sure about. I agree that it would be
good to leverage 64-bit numbers on systems that support them. On the other
hand, I also think that having a consistent random number stream between
32-bit and 64-bit systems may be important. For example, if you use this
functionality for predictable "randomness" in unit tests, then it would be
a problem if your library could only be tested on 32-bit or only on 64-bit.

Certainly, this seems to be a problem. However, the 32bit architecture
environment is very limited, and a 64bit RNG can be useful for applications
and libraries that are designed to run on 64bit architecture.

Also, some of the new RNGs that we are trying to implement, such as
XorShift128+, have an internal state of uint64_t. The random numbers they
generate are always 64bit, and rounding them to 32bit may prevent their
intended use.
For these reasons, I think that we should provide a next64() method.

However, care must be taken in serializing the instance. We are trying to
implement 32bit environment-safe serialization in the current PR, but it is
not smart to say the least.
https://github.com/php/php-src/pull/6568/files#diff-0f1c13e606f11fb5da8dc091109852a6dec328e5aea2389091ff839510cf23faR275

Based on the above discussion, I have added TypeC2 to the RFC.
How about this?

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

Regards,
Go Kudo

2021年1月6日(水) 19:50 Nikita Popov nikita.ppv@gmail.com:

Thanks Nikita.

Thanks for the input. This looks like a very smart solution.
I've edited the RFC and added a new proposal as TypeC.

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

In addition to the functions you already list, I'd add

function rng_bytes(RNGInterface $rng, int $length): string;
function rng_between(RNGInterface $rng, int $min, int $max): int;

Similar to your type B proposal.

Just to share another possibility, we could also modify existing functions
to optionally accept RNGInterface, like

shuffle(array &$array, ?RNGInterface $rng = null): bool;

However, I'm not sure this is better than adding a separate family of
functions.

However, I have a couple of concerns. The first is that users will have
to be careful with RNG instances (for better or worse, TypeA will not allow
users to use unintended instances), and the second is that it will
complicate the implementation of PHP functions.

What do you mean by "use unintended instances" here?

Regarding implementation complexity, yes, this version is a bit more
involved if we want to allow userland implementations of RNGInterface. To
be honest I don't particularly care about supporting userland (we could
also only allow it to be implemented internally), but I think it shouldn't
be too hard either.

Also, given the current environment in which PHP runs, I think that
random number generation in the 64bit range should be supported.
How about including the next64() method in the interface?

This is generally the part I'm least sure about. I agree that it would be
good to leverage 64-bit numbers on systems that support them. On the other
hand, I also think that having a consistent random number stream between
32-bit and 64-bit systems may be important. For example, if you use this
functionality for predictable "randomness" in unit tests, then it would be
a problem if your library could only be tested on 32-bit or only on 64-bit.

As long as an API like rng_between($rng, $min, $max) is used, we can
always assemble two 32-bit values into a random number that is larger than
32-bit. But of course, fetching a single 64-bit number is more efficient...

Nikita

2021年1月5日(火) 23:53 Nikita Popov nikita.ppv@gmail.com:

I updated the RFC draft and changed it to a proposal to bifurcate the
interface.

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

At the same time, I was looking into the RNG problem in Swoole and found
out that the problem was actually occurring.

https://www.easyswoole.com/En/Other/random.html

The above problem with Swoole is only for child processes and can be
fixed
by the user, but as mentioned above, I think it will become more
serious as
PHP becomes more complex in the future.
I hadn't thought of this before, but we might want to consider
deprecating
existing state-dependent RNG functions.

I am seeking feedback on this proposal in order to take the RFC to the
next
step.
Thank you in advance.

Regards,
Go Kudo

I think the general direction of your second proposal (B) is the right
one, but I'm concerned about some of the details.

First and foremost, I don't think that RNG should extend Iterator. Just
having a single "next()" method or similar is sufficient. The Iterator
interface provides many additional things that don't really make sense in
this context and only complicate the implementation. We should clearly
specify the value range of next() though. I assume that for portability
reasons (ensure same sequence on 32-bit and 64-bit) this would have to be a
sign-extended 32-bit value.

The type B proposal distinguishes between a RNG and a PRNG interface. Is
this really useful? I don't think the value of the "getSeed()" method is
high enough to justify the split interface.

The RNGUtil class has methods like:

public static function shuffleArray(int $randomNumber, array $arr):

array;

This doesn't make sense to me, as a single random number is not enough
to shuffle a whole array :) Instead this should be accepting the RNG and
perform an internal call to next() (of course, with a fast by-pass
mechanism if the RNG is implemented internally):

public static function shuffleArray(RNG $rng, array $arr): array;

I'm also wondering why this is a static class rather than a set of
free-standing functions. Why RNGUtil::shuffleArray() rather than
rng_shuffle_array()?

Regards,
Nikita

2020年12月16日(水) 23:46 zeriyoshi zeriyoshi@gmail.com:

Nice to meet you, internals.

PHP 8.0 has been released. With the inclusion of JIT, PHP is about to
be
extended beyond the web.

So I'd like to make a few suggestions.

First , PHP has the historical Mersenne Twister PRNG. However, this
implementation keeps its state in a global and cannot be handled as an
object like other languages (e.g. Java).

So, I created a PHP Extension and proposed it to PECL.

https://marc.info/?l=pecl-dev&m=160795415604102&w=2
https://github.com/zeriyoshi/php-ext-orng

But, Then I looked at the mailing list archives and noticed that a
similar
proposal had been made before.

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

I feel that this suggestion is needed now to expand PHP beyond the
web.

Second suggestion is to stop using the Combined LCG as the default
seed
value for each function.

PHP's Combined LCG only uses PID (or ZTS Thread ID) and time as
entropy.
https://github.com/php/php-src/blob/master/ext/standard/lcg.c#L72

With the development of container technology, this problem seems to be
getting more serious. So I think we should use the random numbers
provided
by the OS (getrandom on Linux) if available.

I would like to hear your opinions.

Regards
Go Kudo <zeriyoshi@gmail.com