[
https://issues.apache.org/jira/browse/RNG-188?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18059746#comment-18059746
]
Alex Herbert commented on RNG-188:
----------------------------------
I have benchmarked the arbitrary jump function.
I have compared them to other jumping generators that pass TestU01 BigCrush and
PractRand at 4TB of output with comparable periods and fixed distances for
their jump and long jump functions:
||Random Source||Output||Period||Jump||Long Jump||
|PHILOX_4X32|int|2^130|2^66|2^130|
|PHILOX_4X32|long|2^258|2^130|2^194|
|XO_SHI_RO_128_PP|int|2^128 - 1|2^64|2^96|
|XO_SHI_RO_256_PP|long|2^256 - 1|2^128|2^192|
The Xor-Shift-Rotate family of generators have precomputed jump coefficients.
Jumping is performed by 4*n iterations of a loop with a condition statement
inside each loop and a call to advance the generator 1 output. n is the output
size in bits, either 32 or 64. So there are either 128 or 256 calls to create
output values from the generator after some shifting of bits.
The Philox family have a counter and a buffer position. A buffer of 4 output
values is created from the counter. When all output is used the counter is
incremented and the buffer regenerated. Jumping advances the buffer position
and/or the counter. After jumping a check is made to determine if the buffer
should be recomputed. This only occurs when the current position is inside the
buffer. Otherwise the recomputation is deferred until an output value is
requested from the RNG. This allows sequential jumping to be performed
repeatedly without computing the output buffer each time if the generator knows
it will recompute it later. This state always happens when the generator is
first created. I tested Philox using the initial state or skipped forward by 1
output value.
Tested on JDK 17.0.17 Eclipse Adoptium on a Mac M2 Pro. Time is per jump.
||Random Source||Skip||Method||Distance||Time (ns)||
|PHILOX_4X32|0|jump| |5.27|
|PHILOX_4X64|0|jump| |6.69|
|PHILOX_4X32|1|jump| |15.55|
|PHILOX_4X64|1|jump| |44.70|
|XO_SHI_RO_128_PP|0|jump| |167.36|
|XO_SHI_RO_256_PP|0|jump| |239.98|
|PHILOX_4X32|0|long jump| |5.23|
|PHILOX_4X64|0|long jump| |6.94|
|PHILOX_4X32|1|long jump| |15.33|
|PHILOX_4X64|1|long jump| |43.56|
|XO_SHI_RO_128_PP|0|long jump| |174.61|
|XO_SHI_RO_256_PP|0|long jump| |238.64|
|PHILOX_4X32|0|arbitrary jump|2^99+2^49|12.15|
|PHILOX_4X64|0|arbitrary jump|2^99+2^49|9.94|
|PHILOX_4X32|1|arbitrary jump|2^99+2^49|24.17|
|PHILOX_4X64|1|arbitrary jump|2^99+2^49|48.72|
|PHILOX_4X32|0|arbitrary jump power of 2|99|7.21|
|PHILOX_4X64|0|arbitrary jump power of 2|99|9.22|
|PHILOX_4X32|1|arbitrary jump power of 2|99|19.77|
|PHILOX_4X64|1|arbitrary jump power of 2|99|45.28|
The fixed jumps of the Philox generators are very fast when skip=0. The
arbitrary jumps are slightly slower but at most about 2-fold.
If skip=1 then a jump will have to recompute the output buffer. This slows down
the jumps more significantly than the difference between fixed and arbitrary
jumps.
The Philox generators are very fast at jumping compared to other jumpable
generators in the library. The cost of fast jumping by fixed amounts may be
outweighed by the slower generation performance. However if arbitrary jumps are
required then these generators have an arbitrary jump function that will not be
prohibitively expensive.
Note that this benchmark is for a single jump. The jump increment is computed
for every jump. If repeated jumps is required then the stream function has been
coded so that it precomputes the jump increment once and then jumps will be
faster. This makes generation of a series of RNGs very fast, e.g.
{code:java}
ArbitrarilyJumpableUniformRandomProvider source =
(ArbitrarilyJumpableUniformRandomProvider) RandomSource.PHILOX_4X64.create()
int streamSize = 10;
double distance = 123456;
source.jumps(streamSize, distance).forEach(rng -> {
// use rng...
});
{code}
> Add Philox random number generator
> ----------------------------------
>
> Key: RNG-188
> URL: https://issues.apache.org/jira/browse/RNG-188
> Project: Commons RNG
> Issue Type: New Feature
> Components: core
> Reporter: Alex Herbert
> Priority: Minor
> Fix For: 1.7
>
>
> Add two new random number generators: philox4x32 and philox4x64 from
> [https://www.thesalmons.org/john/random123/]
> These are quite standard nowadays (part of CUDA, Numpy, default for Pytorch
> on GPU, default for TensorFlow) and there is no official Java implementation.
> Counter-based PRNGs are great for parallelization, as skipping-ahead is
> nearly as fast as a single random number generation, and the counter makes it
> very easy to create subsequences.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
