SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Fri 22 Oct 2021 11:05 - 11:20 at Zurich C - Algorithms, Libraries and Databases Chair(s): Hans-J. Boehm
Fri 22 Oct 2021 19:05 - 19:20 at Zurich C - Algorithms, Libraries and Databases - mirror Chair(s): Fabian Muehlboeck

In 2014, Steele, Lea, and Flood presented
{\sc SplitMix}, an object-oriented pseudorandom number generator
({\sc prng}) that is quite fast (9 64-bit arithmetic/logical operations
per 64 bits generated) and also \emph{splittable}. A conventional
{\sc prng} object provides a \emph{generate} method that returns one
pseudorandom value and updates the state of the {\sc prng}; a splittable
{\sc prng} object also has a second operation, \emph{split}, that replaces
the original {\sc prng} object with two (seemingly) independent {\sc prng}
objects, by creating and returning a new such object and updating
the state of the original object. Splittable {\sc prng} objects make it
easy to organize the use of pseudorandom numbers in multithreaded
programs structured using fork-join parallelism.
This overall strategy still appears to be sound,
but the specific arithmetic calculation used for \emph{generate} in the {\sc SplitMix}
algorithm has some detectable weaknesses, and the period of any one generator
is limited to $2^{64}$.

Here we present the LXM \emph{family} of {\sc prng} algorithms.
The idea is an old one: combine the outputs of two independent {\sc prng} algorithms,
then (optionally) feed the result to a mixing function.
An LXM algorithm uses a linear congruential subgenerator and an $\mathbf{F}_2$-linear subgenerator;
the examples studied in this paper use a linear congruential generator (LCG) of period $2^{16}$, $2^{32}$, $2^{64}$, or $2^{128}$
with one of the multipliers recommended by L'Ecuyer
or by Steele and Vigna,
and an $\mathbf{F}_2$-linear xor-based generator (XBG) of the \texttt{xoshiro} family or \texttt{xoroshiro} family
as described by Blackman and Vigna.
For mixing functions we study the MurmurHash3 finalizer function;
variants by David Stafford, Doug Lea, and \texttt{degski}; and the null (identity) mixing function.

Like {\sc SplitMix}, LXM provides both a \emph{generate}
operation and a \emph{split} operation.
Also like {\sc SplitMix}, LXM requires no locking or other synchronization
(other than the usual memory fence after instance initialization),
and is suitable for use with {\sc simd} instruction sets
because it has no branches or loops.

We analyze the period and equidistribution
properties of LXM generators, and present the results of thorough testing of specific members of this family,
using the TestU01 and PractRand test suites, not only on single instances of the algorithm but also
for collections of instances, used in parallel, ranging in size from $2$ to $2^{24}$.
Single instances of LXM that include a strong mixing function
appear to have no major weaknesses, and LXM is significantly more robust than
{\sc SplitMix} against accidental correlation in a multithreaded setting.
We believe that LXM, like {\sc SplitMix}, is suitable for
``everyday'' scientific and machine-learning applications (but not cryptographic applications),
especially when concurrent threads or distributed processes are involved.

Fri 22 Oct

Displayed time zone: Central Time (US & Canada) change

10:50 - 12:10
Algorithms, Libraries and DatabasesOOPSLA at Zurich C +8h
Chair(s): Hans-J. Boehm Google
10:50
15m
Talk
UDF to SQL Translation through Compositional Lazy Inductive SynthesisVirtual
OOPSLA
Guoqiang Zhang North Carolina State University; Facebook, Yuanchao Xu North Carolina State University, Xipeng Shen North Carolina State University; Facebook, Işıl Dillig University of Texas at Austin
DOI
11:05
15m
Talk
LXM: Better Splittable Pseudorandom Number Generators (and Almost as Fast)Virtual
OOPSLA
Guy L. Steele Jr. Oracle Labs, Sebastiano Vigna University of Milan
DOI
11:20
15m
Talk
FPL: Fast Presburger Arithmetic through TransprecisionIn-PersonDistinguished Paper
OOPSLA
Arjun Pitchanathan IIIT Hyderabad, Christian Ulmann ETH Zurich, Michel Weber ETH Zurich, Torsten Hoefler ETH Zurich, Tobias Grosser University of Edinburgh
DOI
11:35
15m
Talk
Verifying Concurrent Multicopy Search StructuresIn-Person
OOPSLA
Nisarg Patel New York University, Siddharth Krishna Microsoft Research, Dennis Shasha New York University, Thomas Wies New York University
DOI
11:50
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA

18:50 - 20:10
Algorithms, Libraries and Databases - mirrorOOPSLA at Zurich C
Chair(s): Fabian Muehlboeck IST Austria
18:50
15m
Talk
UDF to SQL Translation through Compositional Lazy Inductive SynthesisVirtual
OOPSLA
Guoqiang Zhang North Carolina State University; Facebook, Yuanchao Xu North Carolina State University, Xipeng Shen North Carolina State University; Facebook, Işıl Dillig University of Texas at Austin
DOI
19:05
15m
Talk
LXM: Better Splittable Pseudorandom Number Generators (and Almost as Fast)Virtual
OOPSLA
Guy L. Steele Jr. Oracle Labs, Sebastiano Vigna University of Milan
DOI
19:20
15m
Talk
FPL: Fast Presburger Arithmetic through TransprecisionIn-PersonDistinguished Paper
OOPSLA
Arjun Pitchanathan IIIT Hyderabad, Christian Ulmann ETH Zurich, Michel Weber ETH Zurich, Torsten Hoefler ETH Zurich, Tobias Grosser University of Edinburgh
DOI
19:35
15m
Talk
Verifying Concurrent Multicopy Search StructuresIn-Person
OOPSLA
Nisarg Patel New York University, Siddharth Krishna Microsoft Research, Dennis Shasha New York University, Thomas Wies New York University
DOI
19:50
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA