HomeFreeBSD

lib/libc/gen: use Lemire's algorithm for arc4random_uniform().

Description

lib/libc/gen: use Lemire's algorithm for arc4random_uniform().

Daniel Lemire has published a more efficient range reduction algorithm
for finding a random number in a given range without bias, reducing the
number of divisions to none in the common case and 1 in case the initial
sample is rejected.

This speeds up performance by 22% on amd64, 15% on i386, and 70% on armv7.

os: FreeBSD
arch: amd64
cpu: Intel(R) Core(TM) i7-4910MQ CPU @ 2.90GHz

│ benchmark.out │
│    sec/op     │

Arc4random_uniform 56.53n ± 0%
Fast_uniform 44.00n ± 0%
geomean 49.87n

Reviewed by: cem
Approved by: emaste
Differential Revision: https://reviews.freebsd.org/D47659

Details

Provenance
fuzAuthored on Nov 18 2024, 12:30 PM
Reviewer
cem
Differential Revision
D47659: lib/libc/gen: use Lemire's algorithm for arc4random_uniform().
Parents
rGff1aec7ccb54: ipfw: do not reset fwmark when one_pass is disabled.
Branches
Unknown
Tags
Unknown