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() wi
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 co
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
endu
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) * size
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 sugges
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 ba
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 ba
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). Switching
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 becau
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 helps
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 us
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
+++ b/doc/src/s
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 th
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 think
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 compilers
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 arbitra
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 availab
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 quit
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 commi
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 next
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 "Hu
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 a/doc/src/sgml
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 u
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.
Howeve
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 li
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: http://cfbot.cputube.org/patch_27_1712.log
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: http
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 comments/documenta
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 othe
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 wording
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 http://www.2
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 functio
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 prev
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).
- ad
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 pr_pe
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, an
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 so
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 such
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
Can you please pgindent this?
--
Álvaro Herrerahttps://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
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
- th
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 o
rs 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-r
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, p
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 va
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 multiplication
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 small
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 7.3.1
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
- u
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 occurs,
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 o
Hello,
This patch adds a pseudo-random permutation function to pgbench. It allows
to mix non uniform random keys to avoid trivial correlations between
neighboring values, hence between pages.
The function is a simplistic form of encryption adapted to any size, using
a few iterations of scra
79 matches
Mail list logo
