Skip to content

Commit 3804539

Browse files
tglsfdctglsfdc
committed
Replace random(), pg_erand48(), etc with a better PRNG API and algorithm.
Standardize on xoroshiro128** as our basic PRNG algorithm, eliminating a bunch of platform dependencies as well as fundamentally-obsolete PRNG code. In addition, this API replacement will ease replacing the algorithm again in future, should that become necessary. xoroshiro128** is a few percent slower than the drand48 family, but it can produce full-width 64-bit random values not only 48-bit, and it should be much more trustworthy. It's likely to be noticeably faster than the platform's random(), depending on which platform you are thinking about; and we can have non-global state vectors easily, unlike with random(). It is not cryptographically strong, but neither are the functions it replaces. Fabien Coelho, reviewed by Dean Rasheed, Aleksander Alekseev, and myself Discussion: https://postgr.es/m/alpine.DEB.2.22.394.2105241211230.165418@pseudo
1 parent f44ceb4 commit 3804539

File tree

50 files changed

+544
-481
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

50 files changed

+544
-481
lines changed

‎configure

-26
Original file line numberDiff line numberDiff line change
@@ -16463,32 +16463,6 @@ esac
1646316463

1646416464
fi
1646516465

16466-
ac_fn_c_check_func "$LINENO" "random" "ac_cv_func_random"
16467-
if test "x$ac_cv_func_random" = xyes; then :
16468-
$as_echo "#define HAVE_RANDOM 1" >>confdefs.h
16469-
16470-
else
16471-
case " $LIBOBJS " in
16472-
*" random.$ac_objext "* ) ;;
16473-
*) LIBOBJS="$LIBOBJS random.$ac_objext"
16474-
;;
16475-
esac
16476-
16477-
fi
16478-
16479-
ac_fn_c_check_func "$LINENO" "srandom" "ac_cv_func_srandom"
16480-
if test "x$ac_cv_func_srandom" = xyes; then :
16481-
$as_echo "#define HAVE_SRANDOM 1" >>confdefs.h
16482-
16483-
else
16484-
case " $LIBOBJS " in
16485-
*" srandom.$ac_objext "* ) ;;
16486-
*) LIBOBJS="$LIBOBJS srandom.$ac_objext"
16487-
;;
16488-
esac
16489-
16490-
fi
16491-
1649216466
ac_fn_c_check_func "$LINENO" "strlcat" "ac_cv_func_strlcat"
1649316467
if test "x$ac_cv_func_strlcat" = xyes; then :
1649416468
$as_echo "#define HAVE_STRLCAT 1" >>confdefs.h

‎configure.ac

-2
Original file line numberDiff line numberDiff line change
@@ -1858,8 +1858,6 @@ AC_REPLACE_FUNCS(m4_normalize([
18581858
mkdtemp
18591859
pread
18601860
pwrite
1861-
random
1862-
srandom
18631861
strlcat
18641862
strlcpy
18651863
strnlen

‎contrib/amcheck/verify_nbtree.c

+3-2
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@
3232
#include "catalog/index.h"
3333
#include "catalog/pg_am.h"
3434
#include "commands/tablecmds.h"
35+
#include "common/pg_prng.h"
3536
#include "lib/bloomfilter.h"
3637
#include "miscadmin.h"
3738
#include "storage/lmgr.h"
@@ -466,8 +467,8 @@ bt_check_every_level(Relation rel, Relation heaprel, bool heapkeyspace,
466467
total_pages = RelationGetNumberOfBlocks(rel);
467468
total_elems = Max(total_pages * (MaxTIDsPerBTreePage / 3),
468469
(int64) state->rel->rd_rel->reltuples);
469-
/* Random seed relies on backend srandom() call to avoid repetition */
470-
seed = random();
470+
/* Generate a random seed to avoid repetition */
471+
seed = pg_prng_uint64(&pg_global_prng_state);
471472
/* Create Bloom filter to fingerprint index */
472473
state->filter = bloom_create(total_elems, maintenance_work_mem, seed);
473474
state->heaptuplespresent = 0;

‎contrib/auto_explain/auto_explain.c

+2-2
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616

1717
#include "access/parallel.h"
1818
#include "commands/explain.h"
19+
#include "common/pg_prng.h"
1920
#include "executor/instrument.h"
2021
#include "jit/jit.h"
2122
#include "utils/guc.h"
@@ -275,8 +276,7 @@ explain_ExecutorStart(QueryDesc *queryDesc, int eflags)
275276
if (nesting_level == 0)
276277
{
277278
if (auto_explain_log_min_duration >= 0 && !IsParallelWorker())
278-
current_query_sampled = (random() < auto_explain_sample_rate *
279-
((double) MAX_RANDOM_VALUE + 1));
279+
current_query_sampled = (pg_prng_double(&pg_global_prng_state) < auto_explain_sample_rate);
280280
else
281281
current_query_sampled = false;
282282
}

‎contrib/file_fdw/file_fdw.c

+1-1
Original file line numberDiff line numberDiff line change
@@ -1188,7 +1188,7 @@ file_acquire_sample_rows(Relation onerel, int elevel,
11881188
* Found a suitable tuple, so save it, replacing one old tuple
11891189
* at random
11901190
*/
1191-
int k = (int) (targrows * sampler_random_fract(rstate.randstate));
1191+
int k = (int) (targrows * sampler_random_fract(&rstate.randstate));
11921192

11931193
Assert(k >= 0 && k < targrows);
11941194
heap_freetuple(rows[k]);

‎contrib/postgres_fdw/postgres_fdw.c

+1-1
Original file line numberDiff line numberDiff line change
@@ -5158,7 +5158,7 @@ analyze_row_processor(PGresult *res, int row, PgFdwAnalyzeState *astate)
51585158
if (astate->rowstoskip <= 0)
51595159
{
51605160
/* Choose a random reservoir element to replace. */
5161-
pos = (int) (targrows * sampler_random_fract(astate->rstate.randstate));
5161+
pos = (int) (targrows * sampler_random_fract(&astate->rstate.randstate));
51625162
Assert(pos >= 0 && pos < targrows);
51635163
heap_freetuple(astate->rows[pos]);
51645164
}

‎contrib/tablefunc/tablefunc.c

+3-2
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,7 @@
3636

3737
#include "access/htup_details.h"
3838
#include "catalog/pg_type.h"
39+
#include "common/pg_prng.h"
3940
#include "executor/spi.h"
4041
#include "funcapi.h"
4142
#include "lib/stringinfo.h"
@@ -290,8 +291,8 @@ get_normal_pair(float8 *x1, float8 *x2)
290291

291292
do
292293
{
293-
u1 = (float8) random() / (float8) MAX_RANDOM_VALUE;
294-
u2 = (float8) random() / (float8) MAX_RANDOM_VALUE;
294+
u1 = pg_prng_double(&pg_global_prng_state);
295+
u2 = pg_prng_double(&pg_global_prng_state);
295296

296297
v1 = (2.0 * u1) - 1.0;
297298
v2 = (2.0 * u2) - 1.0;

‎contrib/tsm_system_rows/tsm_system_rows.c

+6-6
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@ static BlockNumber system_rows_nextsampleblock(SampleScanState *node, BlockNumbe
6969
static OffsetNumber system_rows_nextsampletuple(SampleScanState *node,
7070
BlockNumber blockno,
7171
OffsetNumber maxoffset);
72-
static uint32 random_relative_prime(uint32 n, SamplerRandomState randstate);
72+
static uint32 random_relative_prime(uint32 n, pg_prng_state *randstate);
7373

7474

7575
/*
@@ -213,25 +213,25 @@ system_rows_nextsampleblock(SampleScanState *node, BlockNumber nblocks)
213213
if (sampler->step == 0)
214214
{
215215
/* Initialize now that we have scan descriptor */
216-
SamplerRandomState randstate;
216+
pg_prng_state randstate;
217217

218218
/* If relation is empty, there's nothing to scan */
219219
if (nblocks == 0)
220220
return InvalidBlockNumber;
221221

222222
/* We only need an RNG during this setup step */
223-
sampler_random_init_state(sampler->seed, randstate);
223+
sampler_random_init_state(sampler->seed, &randstate);
224224

225225
/* Compute nblocks/firstblock/step only once per query */
226226
sampler->nblocks = nblocks;
227227

228228
/* Choose random starting block within the relation */
229229
/* (Actually this is the predecessor of the first block visited) */
230-
sampler->firstblock = sampler_random_fract(randstate) *
230+
sampler->firstblock = sampler_random_fract(&randstate) *
231231
sampler->nblocks;
232232

233233
/* Find relative prime as step size for linear probing */
234-
sampler->step = random_relative_prime(sampler->nblocks, randstate);
234+
sampler->step = random_relative_prime(sampler->nblocks, &randstate);
235235
}
236236

237237
/* Reinitialize lb */
@@ -317,7 +317,7 @@ gcd(uint32 a, uint32 b)
317317
* (else return 1).
318318
*/
319319
static uint32
320-
random_relative_prime(uint32 n, SamplerRandomState randstate)
320+
random_relative_prime(uint32 n, pg_prng_state *randstate)
321321
{
322322
uint32 r;
323323

‎contrib/tsm_system_time/tsm_system_time.c

+6-6
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@ static BlockNumber system_time_nextsampleblock(SampleScanState *node, BlockNumbe
6969
static OffsetNumber system_time_nextsampletuple(SampleScanState *node,
7070
BlockNumber blockno,
7171
OffsetNumber maxoffset);
72-
static uint32 random_relative_prime(uint32 n, SamplerRandomState randstate);
72+
static uint32 random_relative_prime(uint32 n, pg_prng_state *randstate);
7373

7474

7575
/*
@@ -224,25 +224,25 @@ system_time_nextsampleblock(SampleScanState *node, BlockNumber nblocks)
224224
if (sampler->step == 0)
225225
{
226226
/* Initialize now that we have scan descriptor */
227-
SamplerRandomState randstate;
227+
pg_prng_state randstate;
228228

229229
/* If relation is empty, there's nothing to scan */
230230
if (nblocks == 0)
231231
return InvalidBlockNumber;
232232

233233
/* We only need an RNG during this setup step */
234-
sampler_random_init_state(sampler->seed, randstate);
234+
sampler_random_init_state(sampler->seed, &randstate);
235235

236236
/* Compute nblocks/firstblock/step only once per query */
237237
sampler->nblocks = nblocks;
238238

239239
/* Choose random starting block within the relation */
240240
/* (Actually this is the predecessor of the first block visited) */
241-
sampler->firstblock = sampler_random_fract(randstate) *
241+
sampler->firstblock = sampler_random_fract(&randstate) *
242242
sampler->nblocks;
243243

244244
/* Find relative prime as step size for linear probing */
245-
sampler->step = random_relative_prime(sampler->nblocks, randstate);
245+
sampler->step = random_relative_prime(sampler->nblocks, &randstate);
246246
}
247247

248248
/* Reinitialize lb and start_time */
@@ -330,7 +330,7 @@ gcd(uint32 a, uint32 b)
330330
* (else return 1).
331331
*/
332332
static uint32
333-
random_relative_prime(uint32 n, SamplerRandomState randstate)
333+
random_relative_prime(uint32 n, pg_prng_state *randstate)
334334
{
335335
uint32 r;
336336

‎src/backend/access/gin/ginget.c

+2-1
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616

1717
#include "access/gin_private.h"
1818
#include "access/relscan.h"
19+
#include "common/pg_prng.h"
1920
#include "miscadmin.h"
2021
#include "storage/predicate.h"
2122
#include "utils/datum.h"
@@ -787,7 +788,7 @@ entryLoadMoreItems(GinState *ginstate, GinScanEntry entry,
787788
}
788789
}
789790

790-
#define gin_rand() (((double) random()) / ((double) MAX_RANDOM_VALUE))
791+
#define gin_rand() pg_prng_double(&pg_global_prng_state)
791792
#define dropItem(e) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )
792793

793794
/*

‎src/backend/access/gist/gistutil.c

+3-2
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
#include "access/htup_details.h"
2020
#include "access/reloptions.h"
2121
#include "catalog/pg_opclass.h"
22+
#include "common/pg_prng.h"
2223
#include "storage/indexfsm.h"
2324
#include "storage/lmgr.h"
2425
#include "utils/float.h"
@@ -507,7 +508,7 @@ gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
507508
if (keep_current_best == -1)
508509
{
509510
/* we didn't make the random choice yet for this old best */
510-
keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
511+
keep_current_best = pg_prng_bool(&pg_global_prng_state) ? 1 : 0;
511512
}
512513
if (keep_current_best == 0)
513514
{
@@ -529,7 +530,7 @@ gistchoose(Relation r, Page p, IndexTuple it, /* it has compressed entry */
529530
if (keep_current_best == -1)
530531
{
531532
/* we didn't make the random choice yet for this old best */
532-
keep_current_best = (random() <= (MAX_RANDOM_VALUE / 2)) ? 1 : 0;
533+
keep_current_best = pg_prng_bool(&pg_global_prng_state) ? 1 : 0;
533534
}
534535
if (keep_current_best == 1)
535536
break;

‎src/backend/access/nbtree/nbtinsert.c

+2-1
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
#include "access/nbtxlog.h"
2020
#include "access/transam.h"
2121
#include "access/xloginsert.h"
22+
#include "common/pg_prng.h"
2223
#include "lib/qunique.h"
2324
#include "miscadmin.h"
2425
#include "storage/lmgr.h"
@@ -965,7 +966,7 @@ _bt_findinsertloc(Relation rel,
965966

966967
if (P_RIGHTMOST(opaque) ||
967968
_bt_compare(rel, itup_key, page, P_HIKEY) != 0 ||
968-
random() <= (MAX_RANDOM_VALUE / 100))
969+
pg_prng_uint32(&pg_global_prng_state) <= (PG_UINT32_MAX / 100))
969970
break;
970971

971972
_bt_stepright(rel, insertstate, stack);

‎src/backend/access/spgist/spgdoinsert.c

+4-1
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
#include "access/spgist_private.h"
2020
#include "access/spgxlog.h"
2121
#include "access/xloginsert.h"
22+
#include "common/pg_prng.h"
2223
#include "miscadmin.h"
2324
#include "storage/bufmgr.h"
2425
#include "utils/rel.h"
@@ -2210,7 +2211,9 @@ spgdoinsert(Relation index, SpGistState *state,
22102211
if (out.resultType == spgAddNode)
22112212
elog(ERROR, "cannot add a node to an allTheSame inner tuple");
22122213
else if (out.resultType == spgMatchNode)
2213-
out.result.matchNode.nodeN = random() % innerTuple->nNodes;
2214+
out.result.matchNode.nodeN =
2215+
pg_prng_uint64_range(&pg_global_prng_state,
2216+
0, innerTuple->nNodes - 1);
22142217
}
22152218

22162219
switch (out.resultType)

‎src/backend/access/transam/xact.c

+2-1
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,7 @@
3737
#include "commands/async.h"
3838
#include "commands/tablecmds.h"
3939
#include "commands/trigger.h"
40+
#include "common/pg_prng.h"
4041
#include "executor/spi.h"
4142
#include "libpq/be-fsstubs.h"
4243
#include "libpq/pqsignal.h"
@@ -1990,7 +1991,7 @@ StartTransaction(void)
19901991
/* Determine if statements are logged in this transaction */
19911992
xact_is_sampled = log_xact_sample_rate != 0 &&
19921993
(log_xact_sample_rate == 1 ||
1993-
random() <= log_xact_sample_rate * MAX_RANDOM_VALUE);
1994+
pg_prng_double(&pg_global_prng_state) <= log_xact_sample_rate);
19941995

19951996
/*
19961997
* initialize current transaction state fields

‎src/backend/commands/analyze.c

+4-3
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@
3838
#include "commands/progress.h"
3939
#include "commands/tablecmds.h"
4040
#include "commands/vacuum.h"
41+
#include "common/pg_prng.h"
4142
#include "executor/executor.h"
4243
#include "foreign/fdwapi.h"
4344
#include "miscadmin.h"
@@ -1140,7 +1141,7 @@ acquire_sample_rows(Relation onerel, int elevel,
11401141
double liverows = 0; /* # live rows seen */
11411142
double deadrows = 0; /* # dead rows seen */
11421143
double rowstoskip = -1; /* -1 means not set yet */
1143-
long randseed; /* Seed for block sampler(s) */
1144+
uint32 randseed; /* Seed for block sampler(s) */
11441145
BlockNumber totalblocks;
11451146
TransactionId OldestXmin;
11461147
BlockSamplerData bs;
@@ -1162,7 +1163,7 @@ acquire_sample_rows(Relation onerel, int elevel,
11621163
OldestXmin = GetOldestNonRemovableTransactionId(onerel);
11631164

11641165
/* Prepare for sampling block numbers */
1165-
randseed = random();
1166+
randseed = pg_prng_uint32(&pg_global_prng_state);
11661167
nblocks = BlockSampler_Init(&bs, totalblocks, targrows, randseed);
11671168

11681169
#ifdef USE_PREFETCH
@@ -1279,7 +1280,7 @@ acquire_sample_rows(Relation onerel, int elevel,
12791280
* Found a suitable tuple, so save it, replacing one old
12801281
* tuple at random
12811282
*/
1282-
int k = (int) (targrows * sampler_random_fract(rstate.randstate));
1283+
int k = (int) (targrows * sampler_random_fract(&rstate.randstate));
12831284

12841285
Assert(k >= 0 && k < targrows);
12851286
heap_freetuple(rows[k]);

‎src/backend/executor/nodeSamplescan.c

+2-1
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
#include "access/relscan.h"
1818
#include "access/tableam.h"
1919
#include "access/tsmapi.h"
20+
#include "common/pg_prng.h"
2021
#include "executor/executor.h"
2122
#include "executor/nodeSamplescan.h"
2223
#include "miscadmin.h"
@@ -154,7 +155,7 @@ ExecInitSampleScan(SampleScan *node, EState *estate, int eflags)
154155
* do this just once, since the seed shouldn't change over rescans.
155156
*/
156157
if (tsc->repeatable == NULL)
157-
scanstate->seed = random();
158+
scanstate->seed = pg_prng_uint32(&pg_global_prng_state);
158159

159160
/*
160161
* Finally, initialize the TABLESAMPLE method handler.

‎src/backend/lib/bloomfilter.c

+1-2
Original file line numberDiff line numberDiff line change
@@ -81,8 +81,7 @@ static inline uint32 mod_m(uint32 a, uint64 m);
8181
* distinct seed value on every call makes it unlikely that the same false
8282
* positives will reoccur when the same set is fingerprinted a second time.
8383
* Callers that don't care about this pass a constant as their seed, typically
84-
* 0. Callers can use a pseudo-random seed in the range of 0 - INT_MAX by
85-
* calling random().
84+
* 0. Callers can also use a pseudo-random seed, eg from pg_prng_uint64().
8685
*/
8786
bloom_filter *
8887
bloom_create(int64 total_elems, int bloom_work_mem, uint64 seed)

0 commit comments

Comments
 (0)