From: Martin Kalcher <martin.kalcher@aboutsource.net>
To: Thomas Munro <thomas.munro@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Proposal to introduce a shuffle function to intarray extension
Date: Sun, 17 Jul 2022 11:38:55 +0200
Message-ID: <61893dc9-e584-b548-0fcf-6e3be195ca37@aboutsource.net> (raw)
In-Reply-To: <CA+hUKGLcjrJ9Q2OZAKHN-SQyq_m5QDv8d3WKHYq5HW8Lyozu4w@mail.gmail.com>
References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net>
<CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com>
<b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net>
<4073858.1658027909@sss.pgh.pa.us>
<4077925.1658029046@sss.pgh.pa.us>
<CA+hUKGLcjrJ9Q2OZAKHN-SQyq_m5QDv8d3WKHYq5HW8Lyozu4w@mail.gmail.com>
Am 17.07.22 um 08:00 schrieb Thomas Munro:
>
> I went to see what Professor Lemire would have to say about all this,
> expecting to find a SIMD rabbit hole to fall down for some Sunday
> evening reading, but the main thing that jumped out was this article
> about the modulo operation required by textbook Fisher-Yates to get a
> bounded random number, the random() % n that appears in the patch. He
> talks about shuffling twice as fast by using a no-division trick to
> get bounded random numbers[1]. I guess you might need to use our
> pg_prng_uint32() for that trick because random()'s 0..RAND_MAX might
> introduce bias. Anyway, file that under go-faster ideas for later.
>
> [1] https://lemire.me/blog/2016/06/30/fast-random-shuffling/
Hi Thomas,
the small bias of random() % n is not a problem for my use case, but
might be for others. Its easily replaceable with
(int) pg_prng_uint64_range(&pg_global_prng_state, 0, n-1)
Unfortunately it is a bit slower (on my machine), but thats negligible.
Martin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-general@postgresql.org
Cc: martin.kalcher@aboutsource.net, thomas.munro@gmail.com, tgl@sss.pgh.pa.us, pgsql-hackers@lists.postgresql.org
Subject: Re: Proposal to introduce a shuffle function to intarray extension
In-Reply-To: <61893dc9-e584-b548-0fcf-6e3be195ca37@aboutsource.net>
References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net> <CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com> <b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net> <4073858.1658027909@sss.pgh.pa.us> <4077925.1658029046@sss.pgh.pa.us> <CA+hUKGLcjrJ9Q2OZAKHN-SQyq_m5QDv8d3WKHYq5HW8Lyozu4w@mail.gmail.com> <61893dc9-e584-b548-0fcf-6e3be195ca37@aboutsource.net>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox