rfc:object_scope_prng
Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
rfc:object_scope_prng [2021/01/18 12:28] zeriyoshi fix patches and test and vote |
rfc:object_scope_prng [2021/04/14 14:38] (current) zeriyoshi status update |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== PHP RFC: Object scoped RNG Implementations. ====== | ====== PHP RFC: Object scoped RNG Implementations. ====== | ||
- | * Version: 1.2 | + | * Version: 2.1 (Implementation: 1.3) |
- | * Date: 2021-01-18 | + | * Date: 2020-12-20 |
* Author: Go Kudo < | * Author: Go Kudo < | ||
- | * Status: | + | * Status: |
* Implementation: | * Implementation: | ||
* First Published at: https:// | * First Published at: https:// | ||
===== Introduction ===== | ===== Introduction ===== | ||
- | + | PHP currently | |
- | PHP currently | + | |
- | However, since these functions keep their state in global space, unintended function calls may cause inconsistency even for the same seed value. | + | |
<code php> | <code php> | ||
- | mt_srand(1234); | + | \mt_srand(1234); |
- | foo(); | + | \mt_rand(); // Generate random number. |
- | mt_rand() === 411284887; // false | + | |
- | + | ||
- | function foo() { | + | |
- | | + | |
- | } | + | |
</ | </ | ||
- | This is inappropriate for applications that require consistency in the generated values | + | The shuffle(), str_shuffle(), and array_rand() functions are also available. |
- | These global states | + | |
- | In other languages, RNGs are implemented as objects, so this problem doesn't exists. [3] [4] | + | <code php> |
+ | $array = [0 => ' | ||
+ | \shuffle($array); | ||
+ | \str_shuffle(' | ||
+ | \array_rand($array, | ||
+ | </ | ||
- | The global state of MT is also used by other functions that use random numbers, and this problem is further exacerbated when the consistency | + | However, the current implementation |
<code php> | <code php> | ||
- | mt_srand(1234); | + | \mt_srand(1234); |
- | $arr = [1, 2, 3, 4, 5]; | + | \str_shuffle(' |
- | shuffle($arr); | + | |
- | echo print_r($arr, true); // Result | + | \mt_srand(1234); |
+ | example_of_additional_code(); | ||
+ | \str_shuffle(' | ||
- | /* | + | function example_of_additional_code() { |
- | Array | + | |
- | ( | + | } |
- | | + | |
- | [1] => 2 | + | |
- | [2] => 5 | + | |
- | [3] => 4 | + | |
- | [4] => 1 | + | |
- | ) | + | |
- | */ | + | |
</ | </ | ||
- | Therefore, it may be a good idea to consider deprecating global state-dependent RNG functions in the future. | + | This is fine if you want to get a completely random result, but it is inconsistent with the existence of the mt_srand() function, which accepts arbitrary seed values. Reproducible results are necessary for implementations that need to be reproduced, such as game logic or test code. |
- | One currently possible userland solution is to implement | + | On the other hand, if you want to get a true " |
- | This implementation will also allow us to support the PHP paradigm, which will become even more complex in the future. | + | The first way to work around this problem is to implement RNG in PHP. In fact, such a library exists and is available. |
- | I have created an extension for PHP to improve these [2]. This could be used to consider what specific goals this RFC is trying to achieve. | + | However, the PHP implementation of RNG has execution speed issues. This is also the case in PHP 8.x when JIT is enabled. |
- | ===== Proposal ===== | + | **PHP 8.1-dev** |
+ | <code shell> | ||
+ | $ git clone " | ||
+ | $ time ./php -r ' | ||
- | Implements an object-scoped PRNG in PHP. | + | real 0m0.745s |
+ | user 0m0.744s | ||
+ | sys | ||
+ | </ | ||
- | When this proposal is introduced, the code can be written as follows: | + | **PHP 8.1-dev + OPcache JIT** |
+ | <code shell> | ||
+ | $ git clone "https:// | ||
+ | $ time ./php -dzend_extension=" | ||
- | <code php> | + | real 0m0.083s |
- | $seed = 1234; | + | user 0m0.081s |
- | $rng = new MT19937($seed); | + | sys |
- | $array = [1, 2, 3, 4, 5]; | + | </ |
- | mt_srand(4321); mt_rand(); // Does not affect to $rng. | + | **RFC Implementation |
+ | <code shell> | ||
+ | $ time ./php -r '$r = new \RNG\XorShift128Plus(1234); for ($i = 0; $i < 1000000; $i++) { rng_next($r); | ||
- | shuffle($array, | + | real 0m0.021s |
+ | user 0m0.010s | ||
+ | sys | ||
+ | </ | ||
- | // Allow user-implemented RNG | + | RFC has been passed and Fiber will be introduced in PHP 8.1. Implementations with unpredictable execution order, such as Fiber, make this problem worse. |
+ | For example (with amphp), the following results are difficult for the user to be aware of and are not guaranteed to be consistent in the future. | ||
- | class FixedNumberGenerator implements RNGInterface | + | <code php> |
- | { | + | use function Amp\defer; |
- | | + | use function Amp\delay; |
- | + | ||
- | | + | function |
- | { | + | |
- | | + | |
+ | while ($running) | ||
+ | | ||
+ | echo "${i} : " . mt_rand() . " | ||
} | } | ||
} | } | ||
- | echo str_shuffle(' | + | mt_srand(1234); |
+ | |||
+ | $running = true; | ||
+ | |||
+ | defer(fn() => task(1)); | ||
+ | defer(fn() => task(2)); | ||
+ | defer(fn() => task(3)); | ||
+ | defer(fn() => task(4)); | ||
+ | |||
+ | delay(1000); | ||
+ | $running = false; | ||
+ | |||
+ | /* | ||
+ | Result: | ||
+ | 1 : 411284887 | ||
+ | 4 : 1068724585 | ||
+ | 2 : 1335968403 | ||
+ | 3 : 1756294682 | ||
+ | 1 : 940013158 | ||
+ | 3 : 1314500282 | ||
+ | 4 : 1686544716 | ||
+ | 2 : 1656482812 | ||
+ | 1 : 1674985287 | ||
+ | 2 : 1848274264 | ||
+ | 3 : 585388171 | ||
+ | 4 : 323490420 | ||
+ | 4 : 593702477 | ||
+ | 3 : 426315791 | ||
+ | 2 : 1722007381 | ||
+ | 1 : 1750549071 | ||
+ | */ | ||
</ | </ | ||
- | The following are the implementation details. | + | In addition, problems with having state in the global scope have been reported in some extensions. For example, the Swoole extension notes that the use of mt_rand() requires reinitialization in the process after forking. |
- | First, it provides | + | |
- | RNG64Interface has a next64() method that returns a 64-bit wide result, but this is not necessary in a 32-bit environment. | + | https://www.easyswoole.com/ |
- | In a 64-bit environment, | + | |
- | The next64() | + | ===== Proposal ===== |
+ | Implements class-based object scoped PRNG into PHP. | ||
+ | |||
+ | First, implement the following interface. This is a hypothetical PHP code.' | ||
+ | |||
+ | Basically, this interface are supposed to be used as arguments to one of the functions. In other words, the next() and next64() | ||
<code php> | <code php> | ||
Line 98: | Line 141: | ||
interface RNGInterface | interface RNGInterface | ||
{ | { | ||
+ | /** Generates 32bit pseudo random number. */ | ||
public function next(): int; | public function next(): int; | ||
+ | |||
+ | /** Genrates 64bit pseudo random nunber */ | ||
+ | public function next64(): int; | ||
} | } | ||
+ | </ | ||
+ | |||
+ | The next step is to implement the RNG classes that implement this interface. This RFC proposes implementations of XorShift128+, | ||
+ | |||
+ | These implementations are done in C and are fast. However, by implementing RNGInterface, | ||
+ | |||
+ | <code php> | ||
+ | namespace RNG; | ||
- | interface RNG64Interface extends | + | class XorShift128Plus implements |
{ | { | ||
- | /** @throws ValueError */ | + | |
- | public function next64(): int; | + | public function next(): int {} |
+ | public function next64(): int {} | ||
+ | public function __serialize(): | ||
+ | public function __unserialize(array $data): void {} | ||
+ | } | ||
+ | |||
+ | class MT19937 implements RNGInterface | ||
+ | { | ||
+ | public function __construct(int $seed) {} | ||
+ | public function next(): int {} | ||
+ | public function next64(): int {} | ||
+ | public function __serialize(): | ||
+ | public function __unserialize(array $data): void {} | ||
+ | } | ||
+ | |||
+ | class OS implements RNGInterface // // Cryptographically Secure PRNG. | ||
+ | { | ||
+ | public function next(): int {} | ||
+ | public function next64(): int {} | ||
} | } | ||
</ | </ | ||
- | Next, make some changes to the existing functions | + | Some RNG implementations can serialize state using the standard PHP serialization methods (serialize() |
<code php> | <code php> | ||
- | function shuffle(array & | + | $rng = new RNG\XorShift128Plus(1234); |
- | function str_shuffle(string $string, ? | + | |
- | function array_rand(array $array, int $num = 1, ? | + | \rng_next($rng); |
- | /** Generates a random number like mt_rand(). */ | + | |
- | function rng_rand(RNGInterface | + | $serialized_string |
- | /** Generates a sequence of bytes for a specified range using RNG. */ | + | |
- | function rng_bytes(RNGInterface | + | $rng2 = \unserialize($serialized_string); |
+ | |||
+ | \rng_next($rng) === rng_next($rng2); // true | ||
</ | </ | ||
- | Existing RNG-specifying | + | For existing |
- | Finally, we provide an RNG class that implements these interfaces. | + | <code php> |
- | At this time, considering support for XorShift128+ | + | function shuffle(array &$array, ?RNG\RNGInterface $rng = null): bool {} |
+ | |||
+ | function str_shuffle(string $string, ? | ||
+ | |||
+ | function array_rand(array $array, int $num = 1, ? | ||
+ | </ | ||
+ | |||
+ | Finally, implement a function that can generate values from RNGs, such as the mt_rand(), random_bytes() function. If the $unsigned argument is false, it will return the value generated by the RNG as is. | ||
<code php> | <code php> | ||
- | namespace | + | function rng_bytes(RNG\RNGInterface $rng, int $length): string {} // simlar random_bytes() |
- | class XorShift128Plus implements RNG64Interface | + | function rng_int(RNG\RNGInterface $rng, int $min, int $max): int {} // simlar mt_rand() with optional arguments |
- | class MT19937 implements RNG64Interface | + | |
- | class OSRNG implements RNG64Interface {} // use php_random_bytes() internal API | + | function rng_next(RNG\RNGInterface $rng, bool $unsigned = true): int {} // simlar mt_rand() without optional arguments |
+ | |||
+ | /** @throws ValueError */ | ||
+ | function rng_next64(RNG\RNGInterface $rng, bool $unsigned = true): int {} // Generates 64bit random number | ||
</ | </ | ||
- | ===== Backward Incompatible Changes ===== | + | The rng_next64() function will throw a ValueError exception if 64-bit integer is not available on the platform. |
- | With the provides | + | This is for proper handling |
- | Some of the functions that use RNGs will have additional optional | + | <code php> |
+ | // If the second argument is true (default), rng_next() performs bit shifting like mt_rand() and always returns an unsigned integer. | ||
+ | \mt_srand(1234); | ||
+ | $mt_state = new \RNG\MT19937(1234); | ||
+ | \mt_rand() === \rng_next($mt_state); | ||
+ | |||
+ | // If false, it will return the value as is. This is exactly the same result as $rng-> | ||
+ | \mt_rand() === \rng_next($mt_state, | ||
+ | |||
+ | // This is useful if you want to use the numbers generated by the RNG directly. | ||
+ | \rng_next(new \RNG\MT19937(1234), | ||
+ | </ | ||
+ | |||
+ | ===== Backward Incompatible Changes ===== | ||
+ | A new optional argument will be added to the existing | ||
* shuffle() | * shuffle() | ||
Line 152: | Line 251: | ||
==== To Existing Extensions ==== | ==== To Existing Extensions ==== | ||
- | orng [[https:// | + | none |
==== To Opcache ==== | ==== To Opcache ==== | ||
Line 164: | Line 263: | ||
===== Open Issues ===== | ===== Open Issues ===== | ||
+ | === In other languages, what methods do you use to get around this problem? === | ||
+ | Similar to this proposal, a class-based implementation is in place. | ||
- | === With JIT, won't the userland implementation reach a useful speed? === | + | |
- | Comparing the speed of the userland implementation of XorShift128+ and the orng extension. | + | * Java https://docs.oracle.com/javase/8/docs/api/java/util/Random.html |
- | + | ||
- | **PHP 8.0** | + | |
- | <code shell> | + | |
- | $ time php -r ' | + | |
- | + | ||
- | real 0m0.441s | + | |
- | user 0m0.429s | + | |
- | sys 0m0.010s | + | |
- | </ | + | |
- | + | ||
- | **PHP 8.0 + OPcache JIT** | + | |
- | <code shell> | + | |
- | $ time php -dopcache.jit_buffer_size=100M -dopcache.enable_cli=1 -r ' | + | |
- | + | ||
- | real 0m0.155s | + | |
- | user 0m0.139s | + | |
- | sys 0m0.015s | + | |
- | </code> | + | |
- | + | ||
- | **PHP 8.0 + orng** | + | |
- | <code shell> | + | |
- | $ time php -r '$r = new \ORNG\XorShift128Plus(1234); | + | |
- | + | ||
- | real 0m0.056s | + | |
- | user 0m0.048s | + | |
- | sys 0m0.008s | + | |
- | </code> | + | |
- | + | ||
- | This provides a significant improvement, | + | |
- | + | ||
- | === Why do we need this feature in the core and not in the extension? === | + | |
- | In order to use the features related to pseudo-random numbers that PHP currently provides, an understanding of the core is required. If this proposal is implemented, | + | |
===== Unaffected PHP Functionality ===== | ===== Unaffected PHP Functionality ===== | ||
- | It does not affect any related existing functions. | + | It does not affect any related existing functions. |
* mt_srand() | * mt_srand() | ||
* mt_rand() | * mt_rand() | ||
- | ===== Proposed Voting Choices | + | ===== Vote ===== |
- | Yes/No, requiring | + | Voting opens 2021-04-01 and 2021-04-15 at 00:00:00 EDT. 2/3 required to accept. |
- | There are a few additional options for implementation. | + | <doodle title=" |
- | + | ||
- | <doodle title=" | + | |
* Yes | * Yes | ||
* No | * No | ||
- | </ | ||
- | |||
- | <doodle title=" | ||
- | * Top Level (\RNGInterface) | ||
- | * " | ||
- | * " | ||
</ | </ | ||
===== Patches and Tests ===== | ===== Patches and Tests ===== | ||
* https:// | * https:// | ||
- | |||
- | ===== References ===== | ||
- | * [1] https:// | ||
- | * [2] https:// | ||
- | * [3] https:// | ||
- | * [4] https:// | ||
- | * [5] https:// |
rfc/object_scope_prng.1610972902.txt.gz · Last modified: 2021/01/18 12:28 by zeriyoshi