Random seed initialization with splitmix

Enlil50 · February 19, 2024, 10:34pm

I know that to use Xoshiro256++ is better to randomize the seed with a fast rng as splitmix. This enables us to generate the 4 states of xoshiro256++.
Is this done by default?

StefanKarpinski · February 20, 2024, 12:14am

Yes:

github.com

JuliaLang/julia/blob/02699bb6cd83d16b1e51e2fb127241e18df7c56b/src/task.c#L854


      
              s3 = (s3 << 45) | (s3 >> 19);
          
              rngState[0] = s0;
              rngState[1] = s1;
              rngState[2] = s2;
              rngState[3] = s3;
              return res;
          }
          
          /*
          The jl_rng_split function forks a task's RNG state in a way that is essentially
          guaranteed to avoid collisions between the RNG streams of all tasks. The main
          RNG is the xoshiro256++ RNG whose state is stored in rngState[0..3]. There is
          also a small internal RNG used for task forking stored in rngState[4]. This
          state is used to iterate a linear congruential generator (LCG), which is then
          put through four different variations of the strongest PCG output function,
          referred to as PCG-RXS-M-XS-64 [1]. This output function is invertible: it maps
          a 64-bit state to 64-bit output. This is one of the reasons it's not recommended
          for general purpose RNGs unless space is at an absolute premium, but in our
          usage invertibility is actually a benefit (as is explained below) and adding as
          little additional memory overhead to each task object as possible is preferred.

Although I figured out a way to majorly simplify the splitmix algorithm so that it doesn’t require arithmetic in a prime modulus, all explained in that massive comment.

StefanKarpinski · February 20, 2024, 3:26am

If you’re asking about the initial seeding rather than the task splitting, then we do way better and use SHA256 to go from user-provided seeds to create the actual RNG state.

Oscar_Smith · February 20, 2024, 3:44am

Have you thought about putting that comment on arxiv?

mbauman · February 20, 2024, 2:04pm

A post was split to a new topic: Linear relationship between Xoshiro tasks

StefanKarpinski · February 20, 2024, 1:49pm

Yeah, I’ve thought about writing it up. But making something into a paper is always so much extra work…

caleb-allen · February 21, 2024, 6:45pm

github.com

JuliaLang/julia/blob/02699bb6cd83d16b1e51e2fb127241e18df7c56b/src/task.c#L903-L910


      
          we instead limit pedigree coordinates to being binary, guaranteeing
          invertibility regardless of modulus. When a task spawns a child, the parent and
          child share the parent's previous pedigree prefix and the parent appends a zero
          to its coordinates, which doesn't affect the task's dot product value, while the
          child appends a one, which does produce a new dot product. In this manner a
          binary pedigree vector uniquely identifies each task and since the coordinates
          are binary, the difference between coordinates is always invertible: 1 and -1
          are their own multiplicative inverses regardless of the modulus.

Wow, this feels like a magic trick!

StefanKarpinski · February 21, 2024, 7:02pm

It does, right?! But task forks are inherently binary—each task only forks one child at a time—so it really felt like there had to be some way to make the task coordinates binary. The tricky bit is that you have a choice of somewhat unintuitive ways of thinking about binary “pedigree” coordinates:

The parent task’s coordinates changing every time it spawns a child—weird since shouldn’t a tasks have a fixed coordinate?
Upon fork, parent task is actually replaced by two children—the actual child, and a replacement of itself that is in practice the same object, but is theoretically different with a longer coordinate tuple. This is also weird.
Or each task has infinite coordinates, that are all zeros beyond some point. That’s how I formalize it in my proof in the other thread.

Despite the infinite part, I think the last option is the best: each task has a single, fixed (albeit infinite) coordinate tuple.