Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oD0jy-0001zD-O3 for pgsql-hackers@arkaria.postgresql.org; Sun, 17 Jul 2022 09:39:06 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1oD0jx-0004SY-Cr for pgsql-hackers@arkaria.postgresql.org; Sun, 17 Jul 2022 09:39:05 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oD0jx-0004SP-3J for pgsql-hackers@lists.postgresql.org; Sun, 17 Jul 2022 09:39:05 +0000 Received: from mout-b-206.mailbox.org ([195.10.208.51]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oD0jt-0007xP-Vc for pgsql-hackers@lists.postgresql.org; Sun, 17 Jul 2022 09:39:03 +0000 Received: from smtp102.mailbox.org (smtp102.mailbox.org [10.196.197.102]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-b-206.mailbox.org (Postfix) with ESMTPS id 4Lm0R40qTJz9sTV; Sun, 17 Jul 2022 11:38:56 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aboutsource.net; s=MBO0001; t=1658050736; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=8IU77wDPkV7yTuDmHGhLEgIyuQf7K5wi6i9WSiqkIBg=; b=FEkxfxPPuzUNhiq0DaF51xtSR3ekSxdR7mlXXsIX1UIzQvX3xQuI2iVNinFbsZWMniXH+b s+WeZiyac7PGjg0pz6H/DCxbNBaOfOY3kJ/CfSpq/Zab5b+bPpSs1NxR3ySHYXjeBT7C0C tFWl3l9kIwuSfDmfNjfMQvdreH3ynG+rAdLTM3O7ONLjWsBhhgXeBYCmzVb3AC6li+vJ0s t2hvVyrAtkcifSabIA6sKKVUeeJtPsK9DXPIKGm59tzTJ9J631htg/Wse1lYb1RgdJEg09 FzIJAkFnNuGo67vbRGy6wXcEizdLnbDEGkTkqTx09IOkz57HKmA/UeqbUUZeMQ== Message-ID: <61893dc9-e584-b548-0fcf-6e3be195ca37@aboutsource.net> Date: Sun, 17 Jul 2022 11:38:55 +0200 MIME-Version: 1.0 Content-Language: de-DE To: Thomas Munro , Tom Lane Cc: PostgreSQL Hackers References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net> <4073858.1658027909@sss.pgh.pa.us> <4077925.1658029046@sss.pgh.pa.us> From: Martin Kalcher Subject: Re: Proposal to introduce a shuffle function to intarray extension In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk 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