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 Next revision Both sides next revision | ||
rfc:object_scope_prng [2021/01/10 20:55] zeriyoshi fix typos |
rfc:object_scope_prng [2021/04/01 06:27] zeriyoshi fix vote |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== PHP RFC: Object scoped RNG Implementations. ====== | ====== PHP RFC: Object scoped RNG Implementations. ====== | ||
- | * Version: 1.04 | + | * Version: 2.1 (Implementation: 1.3) |
- | * Date: 2021-01-11 | + | * Date: 2020-12-20 |
* Author: Go Kudo < | * Author: Go Kudo < | ||
- | * Status: | + | * Status: |
- | * Implementation | + | * Implementation: |
- | * Type I: https:// | + | |
- | * Type II: https:// | + | |
* 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); // This result is always consistent. | + | \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, providing methods equivalent to functions that use RNG results. | + | real 0m0.745s |
+ | user 0m0.744s | ||
+ | sys | ||
+ | </ | ||
- | Two methods have been proposed in the discussion. | + | **PHP 8.1-dev + OPcache JIT** |
+ | <code shell> | ||
+ | $ git clone " | ||
+ | $ time ./php -dzend_extension=" | ||
- | === Type I === | + | real 0m0.083s |
+ | user 0m0.081s | ||
+ | sys | ||
+ | </ | ||
- | First, it provides the following interface. | + | **RFC Implementation (based PHP 8.1-dev)** |
+ | <code shell> | ||
+ | $ time ./php -r '$r = new \RNG\XorShift128Plus(1234); | ||
- | <code php> | + | real 0m0.021s |
- | namespace RNG; | + | user 0m0.010s |
- | + | sys | |
- | interface RNGInterface | + | |
- | { | + | |
- | public function next(): int; | + | |
- | /** @throws ValueError */ | + | |
- | | + | |
- | } | + | |
</ | </ | ||
- | The next64() method throws a ValueError exception when running on a non-64bit architecture or not supported RNG class. | + | 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. | |
- | Next, define an interface that provides methods equivalent to PHP functions that use the output | + | |
<code php> | <code php> | ||
- | namespace RNG; | + | use function Amp\defer; |
+ | use function Amp\delay; | ||
- | interface RandomInterface extends RNGInterface | + | function |
- | { | + | global $running; |
- | public | + | |
- | | + | |
- | | + | delay(250); |
+ | echo "${i} : " . mt_rand() . " | ||
+ | } | ||
} | } | ||
- | </ | ||
- | These methods are safe for the internal state of the RNG class. | + | mt_srand(1234); |
- | Finally, we provide an RNG class that implements these interfaces. | + | $running = true; |
- | At this time, considering support for XorShift128+ , MT19937 and OSRNG. | + | |
- | <code php> | + | defer(fn() => task(1)); |
- | namespace RNG; | + | defer(fn() => task(2)); |
+ | defer(fn() => task(3)); | ||
+ | defer(fn() => task(4)); | ||
- | class XorShift128Plus implements RandomInterface {} // use XorShift128+ algorithm | + | delay(1000); |
- | class MT19937 implements RandomInterface {} // use MT19937 algorithm | + | $running = false; |
- | class OSRNG implements RandomInterface {} // use php_random_bytes() internal API | + | |
+ | /* | ||
+ | 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 | ||
+ | */ | ||
</ | </ | ||
- | This implementation is superior to the Type II implementation | + | 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 |
- | * Userland can provide an arbitrary RNGInterface | + | https://www.easyswoole.com/ |
- | * Providing methods based on inheritance is user-friendly. | + | |
- | * The implementation will be simple. | + | |
- | However, it is inferior in the following areas | + | ===== Proposal ===== |
+ | Implements class-based object scoped PRNG into PHP. | ||
- | * Implementation will be redundant. | + | First, implement the following interface. This is a hypothetical PHP code.' |
- | * Inheritance patterns are not modern. | + | |
- | * Unable to recognize incorrect usage of existing functions. | + | |
- | === Type II === | + | Basically, this interface |
- | + | ||
- | First, it provides the following | + | |
<code php> | <code php> | ||
Line 127: | Line 141: | ||
interface RNGInterface | interface RNGInterface | ||
{ | { | ||
+ | /** Generates 32bit pseudo random number. */ | ||
public function next(): int; | public function next(): int; | ||
- | | + | |
+ | | ||
public function next64(): int; | public function next64(): int; | ||
} | } | ||
</ | </ | ||
- | The next64() method throws a ValueError exception when running on a non-64bit architecture or not supported RNG class. | + | The next step is to implement the RNG classes that implement this interface. This RFC proposes implementations of XorShift128+, |
- | Next, make some changes to the existing functions and add some new ones. | + | These implementations are done in C and are fast. However, by implementing RNGInterface, |
<code php> | <code php> | ||
- | function shuffle(array & | + | namespace RNG; |
- | function str_shuffle(string $string, ?RNGInterface | + | |
- | function array_rand(array $array, int $num = 1, ?RNGInterface | + | class XorShift128Plus implements |
- | /** Generates a random number for the specified range using RNG. */ | + | class MT19937 implements |
- | function rng_range(RNGInterface $rng, int $min, int $max): int [} | + | class OS implements |
- | /** Generates a sequence of bytes for a specified range using RNG. */ | + | |
- | function rng_bytes(RNGInterface | + | |
</ | </ | ||
- | Existing | + | Some RNG implementations can serialize state using the standard PHP serialization methods (serialize() and unserialize() function). This is useful for the purpose of storing state. |
- | Finally, we provide an RNG class that implements | + | <code php> |
- | At this time, considering support for XorShift128+ , MT19937 and OSRNG. | + | $rng = new RNG\XorShift128Plus(1234); |
+ | |||
+ | \rng_next($rng); | ||
+ | |||
+ | $serialized_string = \serialize($rng); | ||
+ | |||
+ | $rng2 = \unserialize($serialized_string); | ||
+ | |||
+ | \rng_next($rng) === rng_next($rng2); | ||
+ | </ | ||
+ | |||
+ | For existing functions | ||
<code php> | <code php> | ||
- | namespace | + | function shuffle(array & |
- | final class XorShift128Plus implements | + | function str_shuffle(string $string, ?RNG\RNGInterface |
- | final class MT19937 implements RNGInterface {} // use MT19937 algorithm | + | |
- | final class OSRNG implements | + | function array_rand(array $array, int $num = 1, ?RNG\RNGInterface |
</ | </ | ||
- | This implementation | + | Finally, implement a function that can generate values from RNGs, such as the mt_rand(), random_bytes() function. If the $unsigned argument |
- | * User will be able to notice in advance that the function | + | <code php> |
- | * RandomInterface is not required. | + | function |
- | * Simplifies the internal implementation of the class. | + | |
- | However, it is inferior in the following areas | + | function rng_int(RNG\RNGInterface $rng, int $min, int $max): int {} // simlar mt_rand() with optional arguments |
- | | + | function rng_next(RNG\RNGInterface $rng, bool $unsigned = true): int {} // simlar mt_rand() without optional arguments |
- | * Implementations that handle userland RNGInterface implementations can be complex. | + | |
- | * May not need to support this. | + | /** @throws ValueError */ |
+ | function rng_next64(RNG\RNGInterface $rng, bool $unsigned = true): int {} // Generates 64bit random number | ||
+ | </ | ||
+ | |||
+ | The rng_next64() function will throw a ValueError exception if 64-bit integer is not available on the platform. | ||
+ | |||
+ | This is for proper handling of next64() in a 32-bit environment and to improve interoperability with the mt_rand() function. The mt_rand() function performs a bit shift on the result and always returns | ||
+ | |||
+ | <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 ===== | ===== Backward Incompatible Changes ===== | ||
+ | A new optional argument will be added to the existing arguments below. If you are using reflection for these functions, this may cause problems. | ||
- | With the provides of new classes, some class names (or namespaces) will no longer be available in userland. | + | * shuffle() |
+ | * str_shuffle() | ||
+ | * array_rand() | ||
===== Proposed PHP Version(s) ===== | ===== Proposed PHP Version(s) ===== | ||
Line 185: | Line 231: | ||
==== To Existing Extensions ==== | ==== To Existing Extensions ==== | ||
- | orng [[https:// | + | none |
==== To Opcache ==== | ==== To Opcache ==== | ||
Line 197: | Line 243: | ||
===== Open Issues ===== | ===== Open Issues ===== | ||
- | === Why implement a method that is almost identical | + | === In other languages, what methods do you use to get around this problem? === |
- | It is intended | + | Similar |
- | === With JIT, won't the userland implementation reach a useful speed? === | + | * C# https:// |
- | Comparing the speed of the userland implementation of XorShift128+ and the orng extension. | + | * Java https:// |
- | **PHP 8.0** | + | ===== Unaffected |
- | <code shell> | + | It does not affect any related existing functions. |
- | $ 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 | ||
- | </ | ||
- | |||
- | **PHP 8.0 + orng** | ||
- | <code shell> | ||
- | $ time php -r '$r = new \ORNG\XorShift128Plus(1234); | ||
- | |||
- | real 0m0.056s | ||
- | user 0m0.048s | ||
- | sys 0m0.008s | ||
- | </ | ||
- | |||
- | 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 ===== | ||
- | It does not affect any related existing functions. (However, in the case of Type II, non-destructive arguments will be added.) | ||
* mt_srand() | * mt_srand() | ||
* mt_rand() | * mt_rand() | ||
- | * shuffle() | ||
- | * str_shuffle() | ||
- | * array_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=" | + | |
- | | + | |
- | | + | |
- | </ | + | |
- | + | ||
- | <doodle title=" | + | |
- | * Top Level (\RNGInterface) | + | |
- | * " | + | |
- | * " | + | |
</ | </ | ||
===== Patches and Tests ===== | ===== Patches and Tests ===== | ||
- | * https:// | + | * https:// |
- | * https:// | + | |
- | + | ||
- | ===== References ===== | + | |
- | * [1] https:// | + | |
- | * [2] https:// | + | |
- | * [3] https:// | + | |
- | * [4] https:// | + | |
- | * [5] https:// | + |
rfc/object_scope_prng.txt · Last modified: 2021/04/14 14:38 by zeriyoshi