LoginSignup
54
14

More than 1 year has passed since last update.

@rana_kualu

【PHP8.2】PHPの乱数がすごい改善される

Posted at

PHPの乱数といえば古来より様々な問題が存在していることで有名です。

乱数の質という大問題についてはrandom_intの登場によってひとまずの解決を見ましたが、それ以外にも状態がグローバルである等いくつかの問題が残っています。

それらを解決するため、PHP8.2においてRandom\Randomizerクラスが導入されることが決まりました。
以下は該当のRFC、Random Extension 5.xの紹介です。

Random Extension 5.x

Introduction

現在のPHPのランダムには幾つかの問題が残っています。

Problems

主な問題点は以下の4つです。

・Global state
・Mersenne Twister
・Randomness
・Internals

Global state

メルセンヌツイスターの内部状態が暗黙のうちにグローバル領域に保存されており、なおかつユーザがそれを変更する方法がありません。
そのため、関数内でランダム関数が使用されるとコードが壊れることがあります。

たとえば、次のコードがあるとします。

function foo(): void {}
 
mt_srand(1234);
foo();
mt_rand(1, 100); // 76

以下のように変更しました。

function foo(): void {
    str_shuffle('abc'); // ランダム関数を入れた
}
 
mt_srand(1234);
foo();
mt_rand(1, 100); // 65

str_shuffle()を使ったせいで、mt_rand()の結果が76から65に変わってしまいました。

外部パッケージを利用すると、このようなコードの保守はさらに困難になります。
それどころか、GeneratorやFiberでは現在の状態が簡単に失われます。

以上から、mt_srand()やsrand()では、再現可能なランダム値を提供することができません。

またSwooleのような拡張モジュールでは、メルセンヌツイスターの内部状態も子プロセスにコピーされるため、乱数が安全でなくなるという問題も発生します。

Mersenne Twister

メルセンヌツイスターは優れた疑似乱数発生器ですが、しかしもはや古い設計であり、現代のニーズには適していません。

2^19937 - 1という非常に長い周期を持つにもかかわらず、BigCrashやCrushといったテストに失敗してしまいます。

また、メルセンヌツイスターは32ビットのサイズしか生成できません。
多くの実行環境が64ビットであり、zend_longも64ビットであるという現状に即していません。

Randomness

PHPの組込関数shuffle、str_shuffle、array_randは乱数源としてメルセンヌツイスターを使用します。
これは、暗号学的に安全ではありません。
暗号学的に安全性を満たす類似の関数が必要になった場合、ユーザはrandom_int等を使って新しい関数を実装しなければなりません。

Internals

PHPにおける乱数の実装は、歴史的理由により様々な箇所にとっちらかっています。
以下のように異なるファイルで実装されていますが、中には相互に依存しているものもあり、拡張モジュールの開発者は困惑することでしょう。

- extension header source
Combined LCG standard php_lcg.h lcg.c
libc rand* standard php_rand.h rand.c
MT19937 standard php_mt_rand.h mt_rand.c
CSPRNG standard php_random.h random.c

Userland approach

上記のような問題をユーザランド実装で解決する方法を考えてみます。
まず乱数ジェネレータを実装します。
ここではPHPで書かれた実装と、我々の実装したXorShift128+を比較してみることにします。

class XorShift128Plus
{
    /* constants */
    protected const MASK_S5 = 0x07ffffffffffffff;
    protected const MASK_S18 = 0x00003fffffffffff;
    protected const MASK_S27 = 0x0000001fffffffff;
    protected const MASK_S30 = 0x00000003ffffffff;
    protected const MASK_S31 = 0x00000001ffffffff;
    protected const MASK_LO = 0x00000000ffffffff;
 
    protected const ADD_HI = 0x9e3779b9;
    protected const ADD_LO = 0x7f4a7c15;
    protected const MUL1_HILO = 0x476d;
    protected const MUL1_HIHI = 0xbf58;
    protected const MUL1_LO = 0x1ce4e5b9;
    protected const MUL2_HIHI = 0x94d0;
    protected const MUL2_HILO = 0x49bb;
    protected const MUL2_LO = 0x133111eb;
 
    /* states */
    protected int $s0;
    protected int $s1;
 
    public function __construct(int $seed)
    {
        $s = $seed;
        $this->s0 = $this->splitmix64($s);
        $this->s1 = $this->splitmix64($s);
    }
 
    public function generate(): int
    {
        $s1 = $this->s0;
        $s0 = $this->s1;
 
        $s0h = ($s0 >> 32) & self::MASK_LO;
        $s0l = $s0 & self::MASK_LO;
        $s1h = ($s1 >> 32) & self::MASK_LO;
        $s1l = $s1 & self::MASK_LO;
        $zl = $s0l + $s1l;
        $zh = $s0h + $s1h + ($zl >> 32);
        $z = ($zh << 32) | ($zl & self::MASK_LO);
 
        $this->s0 = $s0;
        $s1 ^= $s1 << 23;
        $this->s1 = $s1 ^ $s0 ^ (($s1 >> 18) & self::MASK_S18) ^ (($s0 >> 5) & self::MASK_S5);
 
        return $z;
    }
 
    protected function splitmix64(int &$s): int
    {
        $zl = $s & self::MASK_LO;
        $zh = ($s >> 32) & self::MASK_LO;
        $carry = $zl + self::ADD_LO;
        $z = $s = (($zh + self::ADD_HI + ($carry >> 32)) << 32) | ($carry & self::MASK_LO);
 
        $z ^= ($z >> 30) & self::MASK_S30;
        $zl = $z & self::MASK_LO;
        $zh = ($z >> 32) & self::MASK_LO;
        $lo = self::MUL1_LO * $zl;
        $zll = $zl & 0xffff;
        $zlh = $zl >> 16;
        $mul1l = $zll * self::MUL1_HILO;
        $mul1h = $zll * self::MUL1_HIHI + $zlh * self::MUL1_HILO + (($mul1l >> 16) & 0xffff);
        $mul1 = (($mul1h & 0xffff) << 16) | ($mul1l & 0xffff);
        $mul2 = ((self::MUL1_LO * $zh) & self::MASK_LO);
        $carry = (($lo >> 32) & self::MASK_LO);
        $hi = $mul1 + $mul2 + $carry;
        $z = ($hi << 32) | ($lo & self::MASK_LO);
 
        $z ^= ($z >> 27) & self::MASK_S27;
        $zl = $z & self::MASK_LO;
        $zh = ($z >> 32) & self::MASK_LO;
        $lo = self::MUL2_LO * $zl;
 
        $zll = $zl & 0xffff;
        $zlh = $zl >> 16;
        $mul1l = $zll * self::MUL2_HILO;
        $mul1h = $zll * self::MUL2_HIHI + $zlh * self::MUL2_HILO + (($mul1l >> 16) & 0xffff);
        $mul1 = (($mul1h & 0xffff) << 16) | ($mul1l & 0xffff);
 
        $mul2 = (self::MUL2_LO * $zh) & self::MASK_LO;
        $carry = ($lo >> 32) & self::MASK_LO;
        $hi = $mul1 + $mul2 + $carry;
        $z = ($hi << 32) | ($lo & self::MASK_LO);
 
        return $z ^ (($z >> 31) & self::MASK_S31);
    }
}
 
$xs128pp = new \XorShift128Plus(1234);
 
// ベンチマーク
for ($i = 0; $i < 1000000000; $i++) {
    $xs128pp->generate();
}

これらの実装と、mt_rand()を1000000000回実行したときの速度は以下のようになります。

- PHP - XorShift128+ PHP - MtRand (savvot/random) Native - MT
PHP 8.1 0m3.218s 0m4.161s 0m0.160s
PHP 8.1 with JIT 0m1.836s 0m2.184s 0m0.184s

JITの有無に関わらず、ネイティブ実装のほうが圧倒的に高速です。
詳しくはメーリングリストを参照してください。

Proposal

様々なランダムメソッドを提供するクラス、Randomizerを提供します。
このクラスはコンストラクタにEngineインターフェイスを渡すことで、ニーズに合わせた乱数発生器に変更することができます。
利便性のため基本的なエンジンをデフォルトで用意しますが、アルゴリズムを簡単に追加できるようなインターフェイスも用意される予定です。

この提案には、以下のような利点があります。

Swapping RNG Based on Environment

環境に応じて乱数発生器を選択することができます。

たとえば開発時にはPRNGを使いたいが本番ではCSPRNGを使いたい場合など、以下のようなコードで簡単に実現できます。

$rng = $is_production
    ? new Random\Engine\Secure()
    : new Random\Engine\PCG64(1234);
 
$randomizer = new Random\Randomizer($rng);
$randomizer->shuffleString('foobar');

Fixed Random Number Sequence

一定の条件を満たすまで乱数を生成し続けたい場合など、負荷の算出が難しいことがあります。

$required_result = mt_rand(1, 100);
while (($generated = mt_rand(1, 100)) !== $required_result) {
    echo "retry\n";
}

echo "done\n";

Dynamic injectionを用いることで、テスト時の挙動を変更することが可能です。

$engine = new class () implements Random\Engine {
    public function generate(): string
    {
        // Result must be a string.
        return pack('V', 1);
    }
};
$randomizer = new Random\Randomizer($engine);
 
$required_result = $randomizer->getInt(1, 100);
while (($generated = $randomizer->getInt(1, 100)) !== $required_result) {
    echo "retry\n";
}
 
echo "done\n";

Cryptographically Secure Random Operations

CSPRNGを使った文字列や配列のシャッフルは、これまではユーザランドで実装しなければなりませんでした。
今後はユーザランド実装が不要になります。

$engine = new Random\Engine\Secure();
$randomizer = new Random\Randomizer($engine);
 
$items = range(1, 10);
$items = $randomizer->shuffleArray($items);

State safe

スコープがインスタンスに限定されるため、外部パッケージやFiberなどの外部要因による変化を防ぎます。

Approach

以下のインターフェイスとクラスが実装されます。

interface Random\Engine

乱数発生器を提供するインターフェイス。

1つのメソッドgenerate():stringを持っており、バイナリ文字列を返します。
返り値は空であってはならず、その場合RuntimeExceptionが発生します。

乱数発生器をPHPで実装する場合は、値をリトルエンディアンでpackして返す必要があります。

Engine::generate()の返り値は文字列であるため、実行環境によらずシードとシーケンスが同じであれば乱数は同じ結果を返します。
ただしユーザランド実装では、64ビット以上の文字列を返した場合は64ビットで切り捨てられることがあります。

interface Random\CryptoSafeEngine

乱数発生器が暗号学的に安全であることを示すマーカーインターフェイス。

interface Random\SerializableEngine

乱数発生器がserializableであることを示すインターフェイス。
下記2メソッドの実装が必要です。

__serialize(): array
__unserialize(array $data): void

class Random\Engine\CombinedLCG

CombinedLCGアルゴリズムで乱数を生成します。
コンストラクタ引数がシード値になり、省略した際のシード値はCSPRNGで生成されます。

同じシード値を渡した場合は、常に同じ結果になります。

$seed = 1234;
 
$engine = new \Random\Engine\CombinedLCG($seed);
var_dump(bin2hex($engine->generate())); // "fc6ff102"
var_dump(bin2hex($engine->generate())); // "40e0ce05"
 
// 同じシード値からは同じ値になる
$engine = new \Random\Engine\CombinedLCG($seed);
var_dump(bin2hex($engine->generate())); // "fc6ff102"
var_dump(bin2hex($engine->generate())); // "40e0ce05"

class Random\Engine\MersenneTwister

メルセンヌツイスターで乱数を生成します。
コンストラクタ引数がシード値になり、省略した際のシード値はCSPRNGで生成されます。
第二引数に定数MT_RAND_PHPを渡すと、壊れたメルセンヌツイスターになります。

同じシード値を渡した場合は、常に同じ結果になります。

$seed = 1234;
 
$engine = new \Random\Engine\MersenneTwister($seed);
var_dump(bin2hex($engine->generate())); // "2f6b0731"
var_dump(bin2hex($engine->generate())); // "d3e2667f"
 
// 同じシード値からは同じ値になる
$engine = new \Random\Engine\MersenneTwister($seed);
var_dump(bin2hex($engine->generate())); // "2f6b0731"
var_dump(bin2hex($engine->generate())); // "d3e2667f"

class Random\Engine\PCG64

PCG64アルゴリズムで乱数を生成します。
コンストラクタ引数がシード値になり、省略した際のシード値はCSPRNGで生成されます。

同じシード値を渡した場合は、常に同じ結果になります。

$seed = 1234;
 
$engine = new \Random\Engine\PCG64($seed);
var_dump(bin2hex($engine->generate())); // "ecfbe5990a319380"
var_dump(bin2hex($engine->generate())); // "4f6b4a5b53b10e3f"
 
// same seed results in same sequence of results.
$engine = new \Random\Engine\PCG64($seed);
var_dump(bin2hex($engine->generate())); // "ecfbe5990a319380"
var_dump(bin2hex($engine->generate())); // "4f6b4a5b53b10e3f"

class Random\Engine\Secure

Secure::generate()にはシードを渡すことができず、再現性はありません。
本クラスで使用される乱数はCSPRNGであることが保証されます。

Secure::generate()で生成された値は、再現することができません。

final class Random\Randomizer

渡された乱数発生器を用いて乱数処理を行うクラスです。
以下のメソッドが用意されています。

__construct(Random\Engine $engine = new Random\Engine\Secure())
getInt(): int // replaces mt_rand()
getInt(int $min, int $max) // replaces mt_rand() and random_int()
getBytes(int length): string // replaces random_bytes()
shuffleArray(array $array): array // replaces shuffle()
shuffleString(string $string): string // replaces str_shuffle()
__serialize(): array
__unserialize(array $data): void

コンストラクタで乱数発生器を渡すことができます。
省略した際はRandom\Engine\Secureが使用されます。

このクラス自体はSerialize可能ですが、エンジンがSerialize可能でない場合があります。

ユーザランド実装エンジンでは$this->engine->generate()メソッドを用いて値を生成します。
ネイティブエンジンはこの限りではなく、より高速な方法で値を生成します。

各メソッドは、実行環境に依存せず結果を再現することができ、将来の互換性も保証されます。
ただし32ビットより大きい値を生成するエンジンを使って、32ビット環境でRandomizer::getInt()を実行すると、RuntimeExceptionが発生します。

これらのエンジンは、一部のよく知られた乱数発生器を実装しています。
それらは、与えられたシード値に対してリファレンスと同じシーケンスを返すことが保証されています。

Randomizerでは、外部から観測可能な値が変更されることは破壊的変更とみなされます。
破壊的変更を伴う仕様の変更には個別のRFCが必要です。

PRNG shootout

PRNGアルゴリズムの比較。

MT19937(メルセンヌツイスター)は、前述した問題があるため、回避した方がよいでしょう。

新しいRNGアルゴリズムを導入する場合、その選定は重要です。
今回我々が検討したアルゴリズムは以下のとおりです。

アルゴリズム Generate size State size Performance 問題 実装
MT19937 32-bit 32-bit x 624 Normal 幾つかのテストに落ちる PHP, Python, Ruby
XorShift128+ 64-bit 64-bit x 2 Excellent BigCrushに落ちる V8, SpiderMonkey, JavaScriptCore
Xoshiro256++ 64-bit 64-bit x 4 Excellent, SIMD-frendly 現状なし Rust
Xoshiro256** 64-bit 64-bit x 4 Excellent 現状なし Rust, .NET 6.0
PCG64 (XSL-RR) 64-bit 128-bit x 2 Good 現状なし Rust, NumPy

MT19937とXorShift128+は広く使われていますが、テストに落ちたりする問題もあり、これから新しく使うには向いていません。
そこで、テストに問題のないPCG64という最新のアルゴリズムを採用しました。

互換性のために残されたMT19937を除くと、PCG64は再現性のあるRNGの唯一の実装です。

PCG64は128ビット整数を使うため32ビット環境ではネイティブに扱えずシミュレーションが必要ですが、既にほとんどの環境で64ビットなので問題ないでしょう。

Xoshiro256**も検討しましたが、提起された問題について最も適切に対処されたように見えるPCG64を最終的に選択しました。
指摘と対策については、以下のサイトで見ることができます。

https://pcg.di.unimi.it/pcg.php
https://www.pcg-random.org/posts/on-vignas-pcg-critique.html

興味深いのは、これらのアルゴリズムが互いを激しく批判しあっていることです。
どちらの意見にも尊重すべきところはあり、そのため選択は非常に困難でした。

両方を実装することも考えましたが、不必要な選択肢を増やすと混乱が増えるだけなので、この選択はやめました。
もし必要だと思う人がいたら、拡張モジュールなどで追加することができます。

Internal Changes

以下のPHP関数を、新設したext/random拡張モジュールに移行しました。

・lcg_value()
・srand()
・rand()
・mt_srand()
・mt_rand()
・random_int()
・random_bytes()

また、以下の内部APIもext/random拡張モジュールに移動されます。

・php_random_int_throw()
・php_random_int_silent()
・php_combined_lcg()
・php_mt_srand()
・php_mt_rand()
・php_mt_rand_range()
・php_mt_rand_common()
・php_srand()
・php_rand()
・php_random_bytes()
・php_random_int()

RNGを標準化するため、RNG関連の実装は全て新しいrandom拡張にまとめられます。

以下のヘッダファイルは拡張モジュールの互換性のために残されていますが、中身はext/random/php_random.hをインクルードしています。

・ext/standard/php_lcg.h
・ext/standard/php_rand.h
・ext/standard/php_mt_rand.h
・ext/standard/php_random.h

Future Scope

この項目は将来の展望であり、このRFCには含まれていません。

・互換性のために残したヘッダファイルを削除する。
・lcg_value()、mt_srand()・srand()を非推奨にする。

Backward Incompatible Changes

互換性のない変更。

以下の名前が使用できなくなります。

・Random
・Random\Engine
・Random\CryptoSafeEngine
・Random\SerializableEngine
・Random\Engine\CombinedLCG
・Random\Engine\MersenneTwister
・Random\Engine\PCG64
・Random\Engine\Secure
・Random\Randomizer

Proposed PHP Version(s)

PHP8.2

Vote

投票日程は2022/06/14から2022/06/28、投票者の2/3の賛成で受理されます。

このRFCは賛成21反対0の全会一致で受理されました。

Patches and Tests

感想

この改善によって、PHPでも再現性のある乱数が使えるようになります。
個人的には再現性のある乱数に依存した処理を書いたことがないのでよくわからないのですが、ゲームなど再現性の必要な処理にとっては重要な要素でしょう。

また、それ以外にも元々PHPに存在していたランダムにまとわる様々な問題も、このRFCによって一掃されることは間違いありません。
もう誰にも、PHPの乱数は壊れているなんて言わせませんよ。

ちなみにこのRFCを作った人は、最初に例示したPHP の乱数実装がグダグダな話の記事を書いた人です。
『これらの問題を解決するため、 PHP 8.2 に対して Random Extension 5.x の RFC が作成され、投票が始まっています』とか他人事みたいに書いてるけど自演じゃねーか。

54
14
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
54
14