pg.ddx.io  pgsql-general@postgresql.org mailing list archive  
help / color / mirror / Atom feed
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





view thread (25+ messages)  latest in thread

Message-ID: <61893dc9-e584-b548-0fcf-6e3be195ca37@aboutsource.net>
Permalink:  ../61893dc9-e584-b548-0fcf-6e3be195ca37@aboutsource.net/
Also on:    postgresql.org/message-id/61893dc9-e584-b548-0fcf-6e3be195ca37@aboutsource.net

 · 

reply

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