Hello Dean,
Pushed.
I decided not to go with the "joke" randu64() function, but instead
used getrand() directly. This at least removes any *direct* use of
doubles in permute() (though of course they're still used indirectly),
and means that if getrand() is improved in the future, permute()
On Mon, 5 Apr 2021 at 13:07, Fabien COELHO wrote:
>
> Attached a v28 which I hope fixes the many above issues and stays with
> ints. The randu64 is still some kind of a joke, I artificially reduced the
> cost by calling jrand48 once and extending it to 64 bits, so it could give
> an idea of the
Hello Dean,
I think that permute should only use integer operations. I'd suggest to
use one of the integer variants instead of going through a double
computation and casting back to int. The internal state is based on
integers, I do not see the added value of going through floats, possibly
On Fri, 2 Apr 2021 at 06:38, Fabien COELHO wrote:
>
> >> r = (uint64) (pg_erand48(random_state.xseed) * size);
> >>
> >> I do not understand why the random values are multiplied by anything in
> >> the first place…
> >
> > These are just random integers in the range [0,mask] and [0,size-1],
> >
See attached v27 proposal.
As usual, it is easier to see with the actual attachement:-)
--
Fabien.diff --git a/doc/src/sgml/ref/pgbench.sgml b/doc/src/sgml/ref/pgbench.sgml
index 50cf22ba6b..84d9566f49 100644
--- a/doc/src/sgml/ref/pgbench.sgml
+++ b/doc/src/sgml/ref/pgbench.sgml
@@ -1057,7
r = (uint64) (pg_erand48(random_state.xseed) * size);
I do not understand why the random values are multiplied by anything in
the first place…
These are just random integers in the range [0,mask] and [0,size-1],
formed in exactly the same way as getrand().
Indeed, erand returns a double,
On Wed, 31 Mar 2021 at 18:53, Fabien COELHO wrote:
>
> While looking at it, I have some doubts on this part:
>
> m = (uint64) (pg_erand48(random_state.xseed) * (mask + 1)) | 1;
> r = (uint64) (pg_erand48(random_state.xseed) * (mask + 1));
> r = (uint64) (pg_erand48(random_state.xseed) *
Hello Dean,
OK, attached is an update making this change and simplifying the rotate
code, which hopefully just leaves the question of what (if anything) to
do with pg_erand48().
Yep. While looking at it, I have some doubts on this part:
m = (uint64) (pg_erand48(random_state.xseed) * (mask
On Wed, 31 Mar 2021 at 09:02, Fabien COELHO wrote:
>
> >> First, I have a thing against erand48.
> >
> Also, there is a 64 bits seed provided to the function which instantly
> ignores 16 of them, which looks pretty silly to me.
>
Yeah, that was copied from set_random_seed().
> At least, I
Hello Dean,
First, I have a thing against erand48.
Yeah, that's probably a fair point. However, all the existing pgbench
random functions are using it, so I think it's fair enough for permute()
to do the same (and actually 2^48 is pretty huge). Switching to a 64-bit
PRNG might not be a
On Tue, 30 Mar 2021 at 20:31, Dean Rasheed wrote:
>
> Yeah, that's probably a fair point. However, all the existing pgbench
> random functions are using it, so I think it's fair enough for
> permute() to do the same (and actually 2^48 is pretty huge). Switching
> to a 64-bit PRNG might not be a
On Tue, 30 Mar 2021 at 19:26, Fabien COELHO wrote:
>
> First, I have a thing against erand48.
Yeah, that's probably a fair point. However, all the existing pgbench
random functions are using it, so I think it's fair enough for
permute() to do the same (and actually 2^48 is pretty huge).
Hello Dean,
Thanks a lot for this work. This version looks much better than the
previous one you sent, and has significant advantages over the one I sent,
in particular avoiding the prime number stuff and large modular multiply.
So this looks good!
I'm happy that halves-xoring is back
On Mon, 22 Mar 2021 at 13:43, Dean Rasheed wrote:
>
> On Sun, 14 Mar 2021 at 16:08, Fabien COELHO wrote:
> >
> > > My main question on this now is, do you have a scholar reference for
> > > this algorithm?
> >
> > Nope, otherwise I would have put a reference. I'm a scholar though, if
> > it
On Sun, 14 Mar 2021 at 16:08, Fabien COELHO wrote:
>
> > My main question on this now is, do you have a scholar reference for
> > this algorithm?
>
> Nope, otherwise I would have put a reference. I'm a scholar though, if
> it helps:-)
>
> I could not find any algorithm that fitted the bill. The
Hello Alvaro,
+ /*-
+* Apply 4 rounds of bijective transformations using key updated
+* at each stage:
+*
+* (1) whiten: partial xors on overlapping power-of-2 subsets
+* for instance with v in 0 .. 14 (i.e. with size == 15):
+*
On 2021-Mar-14, Fabien COELHO wrote:
> + /*-
> + * Apply 4 rounds of bijective transformations using key updated
> + * at each stage:
> + *
> + * (1) whiten: partial xors on overlapping power-of-2 subsets
> + * for instance with v in 0 .. 14 (i.e. with size ==
See attached v22.
v23:
- replaces remaining occurences of "pr_perm" in the documentation
- removes duplicated includes
--
Fabien.diff --git a/doc/src/sgml/ref/pgbench.sgml b/doc/src/sgml/ref/pgbench.sgml
index 299d93b241..9f49a6a78d 100644
--- a/doc/src/sgml/ref/pgbench.sgml
+++
Hello Alvaro,
Clearly we got rid of a lot of code. About the tests, maybe the easiest
thing to do is "skip ... if $Config{'osname'} eq 'MSWin32'".
I tried that.
One comment in pseudorandom_perm talks about "whitening" while the other
talks about "scramble". I think they should both use
Hello,
On 2021-Mar-13, Fabien COELHO wrote:
> This looks like a good compromise, which can even be a little better because
> we still have 64 bits ints.
Yeah, we rely on those being available elsewhere.
> Attached a simplified patch which does that, removing 1/3 of the code. What
> do you
Hello Alvaro,
That doesn't sound like a bad option to me, if it makes this much
simpler. The main modern system without it seems to be MSVC. The
Linux, BSD, Apple, illumos, AIX systems using Clang/GCC with
Intel/AMD/ARM/PowerPC CPUs have it, and the Windows systems using open
source
On 2021-Mar-13, Thomas Munro wrote:
> That doesn't sound like a bad option to me, if it makes this much
> simpler. The main modern system without it seems to be MSVC. The
> Linux, BSD, Apple, illumos, AIX systems using Clang/GCC with
> Intel/AMD/ARM/PowerPC CPUs have it, and the Windows systems
On Mon, Mar 8, 2021 at 11:50 PM Fabien COELHO wrote:
> > I may have time to become familiar or at least semi-comfortable with all
> > that weird math in it by then.
>
> Yep.
>
> Generating a parametric good-quality low-cost (but not
> cryptographically-secure) pseudo-random permutations on
Hello Dean,
The implementation looks plausible too, though it adds quite a large
amount of new code.
A significant part of this new code the the multiply-modulo
implementation, which can be dropped if we assume that the target has
int128 available, and accept that the feature is not
On Thu, 11 Mar 2021 at 19:06, David Bowen wrote:
>
> The algorithm for generating a random permutation with a uniform distribution
> across all permutations is easy:
> for (i=0; iswap a[n-i] with a[rand(n-i+1)]
> }
>
> where 0 <= rand(x) < x and a[i] is initially i (see Knuth, Section 3.4.2
The algorithm for generating a random permutation with a uniform
distribution across all permutations is easy:
for (i=0; i
wrote:
> On Thu, 11 Mar 2021 at 00:58, Bruce Momjian wrote:
> >
> > Maybe Dean Rasheed can help because of his math background --- CC'ing
> him.
> >
>
> Reading the thread I
On Thu, 11 Mar 2021 at 00:58, Bruce Momjian wrote:
>
> Maybe Dean Rasheed can help because of his math background --- CC'ing him.
>
Reading the thread I can see how such a function might be useful to
scatter non-uniformly random values.
The implementation looks plausible too, though it adds
On Mon, Mar 8, 2021 at 11:50:43AM +0100, Fabien COELHO wrote:
>
> > > What are your current thoughts?
> >
> > Thanks for prodding. I still think it's a useful feature. However I
> > don't think I'll have to time to get it done on the current commitfest.
> > I suggest to let it sit in the
What are your current thoughts?
Thanks for prodding. I still think it's a useful feature. However I
don't think I'll have to time to get it done on the current commitfest.
I suggest to let it sit in the commitfest to see if somebody else will
pick it up -- and if not, we move it to the
Hi David
On 2021-Mar-05, David Steele wrote:
> On 4/2/20 3:01 AM, Alvaro Herrera wrote:
> > On 2020-Apr-02, Fabien COELHO wrote:
> >
> > > > I'm planning to mark this patch RwF on April 8 and I suggest you
> > > > resubmit if you are able to get some consensus.
> > >
> > > People interested in
Hi Álvaro,
On 4/2/20 3:01 AM, Alvaro Herrera wrote:
On 2020-Apr-02, Fabien COELHO wrote:
I'm planning to mark this patch RwF on April 8 and I suggest you
resubmit if you are able to get some consensus.
People interested in non-uniform benchmarks would see the point. Why many
people would be
The following review has been posted through the commitfest application:
make installcheck-world: tested, passed
Implements feature: tested, passed
Spec compliant: tested, passed
Documentation:not tested
There are few "Stripping trailing CRs from the patch" and one
Attached v19 is a rebase, per cfbot.
Attached v20 fixes a doc xml typo, per cfbot again.
--
Fabien.diff --git a/doc/src/sgml/ref/pgbench.sgml b/doc/src/sgml/ref/pgbench.sgml
index 9f3bb5fce6..d4a604c6fa 100644
--- a/doc/src/sgml/ref/pgbench.sgml
+++ b/doc/src/sgml/ref/pgbench.sgml
@@ -1033,7
I don't think we should boot this patch. I don't think I would be able
to get this over the commit line in this CF, but let's not discard it.
Understood. I have moved the patch to the 2020-07 CF in Needs Review state.
Attached v19 is a rebase, per cfbot.
--
Fabien.diff --git
On 4/2/20 3:01 AM, Alvaro Herrera wrote:
On 2020-Apr-02, Fabien COELHO wrote:
I'm planning to mark this patch RwF on April 8 and I suggest you
resubmit if you are able to get some consensus.
People interested in non-uniform benchmarks would see the point. Why many
people would be happy with
Attached is an attempt at improving things. I have added a explicit note and
hijacked an existing example to better illustrate the purpose of the
function.
A significant part of the complexity of the patch is the overflow-handling
implementation of (a * b % c) for 64 bits integers.
On 2020-Apr-02, Fabien COELHO wrote:
> > I'm planning to mark this patch RwF on April 8 and I suggest you
> > resubmit if you are able to get some consensus.
>
> People interested in non-uniform benchmarks would see the point. Why many
> people would be happy with uniform benchmarks only while
Hello David,
Attached is an attempt at improving things. I have added a explicit note
and hijacked an existing example to better illustrate the purpose of the
function.
This patch does not build on Linux due to some unused functions and
variables:
Hi Fabien,
On 2/1/20 5:12 AM, Fabien COELHO wrote:
Attached is an attempt at improving things. I have added a explicit note
and hijacked an existing example to better illustrate the purpose of the
function.
This patch does not build on Linux due to some unused functions and
variables:
Hello Alvaro,
I read the whole thread, I still don't know what this patch is supposed to
do. I know what the words in the subject line mean, but I don't know how
this helps a pgbench user run better benchmarks. I feel this is also the
sentiment expressed by others earlier in the thread. You
Hello Peter,
This patch was marked as RFC on 2019-03-30, but since then there have
been a couple more issues pointed out in a review by Thomas Munro, and
it went through 2019-09 and 2019-11 without any attention. Is the RFC
status still appropriate?
Thomas review was about
On 2020-Jan-30, Peter Eisentraut wrote:
> I read the whole thread, I still don't know what this patch is supposed to
> do. I know what the words in the subject line mean, but I don't know how
> this helps a pgbench user run better benchmarks. I feel this is also the
> sentiment expressed by
On 2020-01-05 10:02, Fabien COELHO wrote:
This patch was marked as RFC on 2019-03-30, but since then there have
been a couple more issues pointed out in a review by Thomas Munro, and
it went through 2019-09 and 2019-11 without any attention. Is the RFC
status still appropriate?
Thomas review
This patch was marked as RFC on 2019-03-30, but since then there have
been a couple more issues pointed out in a review by Thomas Munro, and
it went through 2019-09 and 2019-11 without any attention. Is the RFC
status still appropriate?
Thomas review was about comments/documentation
Hi,
This patch was marked as RFC on 2019-03-30, but since then there have
been a couple more issues pointed out in a review by Thomas Munro, and
it went through 2019-09 and 2019-11 without any attention. Is the RFC
status still appropriate?
regards
--
Tomas Vondra
Hello Thomas,
Function nbits(), which was previously discussed, has been simplified by
using the function pg_popcount64().
Hi Fabien, Suzuki-san,
I am not smart enough to commit this
I'm in no hurry:-)
or judge its value for benchmarking,
I think that it is valuable given that we have
On Fri, May 24, 2019 at 2:46 AM Fabien COELHO wrote:
> Here is a v15 which is a rebase, plus a large simplification of the modmul
> function if an int128 type is available, which is probably always…
> > Function nbits(), which was previously discussed, has been simplified by
> > using the
Hello Hironobu-san,
Here is a v15 which is a rebase, plus a large simplification of the modmul
function if an int128 type is available, which is probably always…
Could you have a look and possibly revalidate?
Sorry for the late reply. I reviewed this patch.
Function nbits(), which was
On 2019/03/21 17:27, David Steele wrote:
Hi Hironobu,
Sorry for the late reply. I reviewed this patch.
Function nbits(), which was previously discussed, has been simplified by
using the function pg_popcount64().
By adding the mathematical explanation, it has been easier to understand
the
Hi Hironobu,
On 3/3/19 12:55 PM, Fabien COELHO wrote:
Indeed, the patch needs a rebase & conflit resolution. I'll do it. Later.
Here is an update:
- take advantage of pg_bitutils (although I noted that the "slow"
popcount there could be speeded-up and shorten with a bitwise operator
Indeed, the patch needs a rebase & conflit resolution. I'll do it. Later.
Here is an update:
- take advantage of pg_bitutils (although I noted that the "slow"
popcount there could be speeded-up and shorten with a bitwise operator
implementation that I just removed from pgbench).
-
Hello Andres,
+# PGAC_C_BUILTIN_CLZLL
I think this has been partially superceded by
commit 711bab1e4d19b5c9967328315a542d93386b1ac5
Author: Alvaro Herrera
Date: 2019-02-13 16:10:06 -0300
Indeed, the patch needs a rebase & conflit resolution. I'll do it. Later.
+Function
Hi,
On 2019-02-10 17:46:15 +, Hironobu SUZUKI wrote:
> I updated the patch. And also I added some explanations and simple examples
> in the modular_multiply function.
It'd be good to update the commitfest entry to say 'needs review' the
next time.
> +# PGAC_C_BUILTIN_CLZLL
> +#
I updated the patch. And also I added some explanations and simple
examples in the modular_multiply function.
Fabian-san,
To make easily understanding, I think it is a good idea to add a brief
explanation of outline the pseudorandom_perm function and bijective
functions/transformations. What
On Thu, Oct 25, 2018 at 08:21:27AM +0200, Fabien COELHO wrote:
> Thanks for the hint. Here is an updated patch using this marker.
>
> I noticed that some instances use a closing "*-" sequence, but it does
> not seem useful, so I left it out.
>
> I have also tried to improve a few comments,
Hello Alvaro,
although not comment changes which break the logic of the algorithm
descriptions. I have not found how to tell pgindent to let comments
indentation alone.
You can use /*- for such comments.
Thanks for the hint. Here is an updated patch using this marker.
I noticed that
On Wed, Oct 24, 2018 at 06:00:08PM -0300, Alvaro Herrera wrote:
> On 2018-Oct-24, Fabien COELHO wrote:
>> although not comment changes which break the logic of the algorithm
>> descriptions. I have not found how to tell pgindent to let comments
>> indentation alone.
>
> You can use /*- for
On 2018-Oct-24, Fabien COELHO wrote:
>
> Hello Alvaro,
>
> > Can you please pgindent this?
>
> Hmmm. After some investigation, I installed some "pg_bsd_indent" and ran the
> "pgindent" script, which reindented far more than the patch... So I picked
> up the patch-related changes and integrated
Hello Alvaro,
Can you please pgindent this?
Hmmm. After some investigation, I installed some "pg_bsd_indent" and ran
the "pgindent" script, which reindented far more than the patch... So I
picked up the patch-related changes and integrated them manually, although
not comment changes which
I thinks this patch is fine.
Thanks!
Hopefully some committer will pick it up at some point.
--
Fabien.
Hi Fabian-san,
I reviewed 'pgbench-prp-func/pgbench-prp-func-10.patch'.
On 2018/10/24 12:55, Fabien COELHO wrote:
Hello Hironobu-san,
In pseudorandom_perm(), `modular_multiply() + (key >> LCG_SHIFT)` may
overflow if the result of modular_multiply() is large. Therefore, I've
improved it.
Hello Hironobu-san,
In pseudorandom_perm(), `modular_multiply() + (key >> LCG_SHIFT)` may
overflow if the result of modular_multiply() is large. Therefore, I've
improved it.
Also, I've simplified Step 5 in modular_multiply().
Attached is a v10, where I have:
- updated some comments
-
Hello,
> Also, the alternate implementation should not change the result, so
> something looks amiss in your version. Moreover, I'm unclear how to
> implement an overflow multiply with the safe no overflow version.
(snip)
I made an honest mistake. I had assumed the modulo number of Knuth's LCG
Hello Hironobu-san,
I reviewed pgbench-prp-func-6.patch.
Thanks.
(1) modular_multiply()
In modular_multiply(), the numbers of digits of inputs are checked in order
to determine using the interleaved modular multiplication algorithm or not.
However, the check condition absolutely depends
in
001_pgbench_with_server.pl.
I attached the new patch `pgbench-prp-func-7.patch`, the python code
`pseudorandom_perm.py`, and the pr_perm check script file
`pr_perm_check.sql`.
Best regards,
On 2018/10/01 12:19, Fabien COELHO wrote:
PostgreSQL Hackers
Subject: Re: pgbench - add pseudo-random
PostgreSQL Hackers
Subject: Re: pgbench - add pseudo-random permutation function
On Wed, Sep 26, 2018 at 01:20:49PM +0200, Fabien COELHO wrote:
So, am I right to deducing that you are satisfied with the current status of
the patch, with the nbits implementation either based on popcount (v4
On Wed, Sep 26, 2018 at 01:20:49PM +0200, Fabien COELHO wrote:
> So, am I right to deducing that you are satisfied with the current status of
> the patch, with the nbits implementation either based on popcount (v4) or
> clz (v5) compiler intrinsics? I think that the clz option is better.
Fabien,
Hello,
That is necessary because most people consume PostgreSQL through
packages from distributions that have to work on an Athlon II or
whatever, so we can't just use -msse4.2 for every translation unit.
So it becomes our job to isolate small bits of code that use newer
instructions, if it's
On Wed, Sep 26, 2018 at 8:26 PM Fabien COELHO wrote:
> > modular_multiply() is an interesting device. I will leave this to
> > committers with a stronger mathematical background than me, but I have
> > a small comment in passing:
>
> For testing this function, I have manually commented out the
Hello Thomas,
modular_multiply() is an interesting device. I will leave this to
committers with a stronger mathematical background than me, but I have
a small comment in passing:
For testing this function, I have manually commented out the various
shortcuts so that the manual
On Wed, Sep 19, 2018 at 7:07 AM Fabien COELHO wrote:
> > I reviewed 'pgbench-prp-func/pgbench-prp-func-4.patch'. [...] I thinks
> > this patch is fine.
modular_multiply() is an interesting device. I will leave this to
committers with a stronger mathematical background than me, but I have
a
I reviewed 'pgbench-prp-func/pgbench-prp-func-4.patch'. [...] I thinks
this patch is fine.
Thanks!
You may consider turning it "ready" in the CF app, so as to see whether
some committer agrees with you.
--
Fabien.
Hi Fabian-san,
I reviewed 'pgbench-prp-func/pgbench-prp-func-4.patch'.
I could apply it and did the TAP test successfully. I could not find
typo in the documentations and comments.
To make sure, I checked the new routine which contains the
__builtin_popcountll() function on Linux + gcc
Hello Hironobu-san,
Here is a v4, based on our out-of-list discussion:
- the mask function is factored out
- the popcount builtin is used if available
Attached a v3, based on your fix, plus some additional changes:
- explicitly declare unsigned variables where appropriate, to avoid casts
-
Hello Hironobu-san,
However, the implementation of the scatter operation in this patch overflows
in many cases if the variable:size is 38 bit integer or greater. Because the
variable:size and the item of the array:primes[] which stores 27-29 bit
integers are multiplicated. If overflow
Hello Hironobu-san,
I reviewed `pgbench-prp-func-1.patch` and found an incomplete implementation.
Indeed, thanks a lot for the debug, and the proposed fix!
I'm going to work a little bit more on the patch based on your proposed
changes, and submit a v3, hopefully soon.
--
Fabien.
Hi Fabian,
I reviewed `pgbench-prp-func-1.patch` and found an incomplete
implementation.
In the pseudorandom_perm function, I confirmed that the scramble and
scatter operations are mathematically bijections. Therefore, this
function is mathematically correct.
However, the implementation
77 matches
Mail list logo
