From: | Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr> |
---|---|

To: | Thomas Munro <thomas(dot)munro(at)gmail(dot)com> |

Cc: | Hironobu SUZUKI <hironobu(at)interdb(dot)jp>, PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>, David Steele <david(at)pgmasters(dot)net> |

Subject: | Re: pgbench - add pseudo-random permutation function |

Date: | 2019-07-23 07:44:09 |

Message-ID: | alpine.DEB.2.21.1907230730150.7144@lancre |

Views: | Raw Message | Whole Thread | Download mbox | Resend email |

Thread: | |

Lists: | pgsql-hackers |

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 non uniform random

generators in pgbench.

I'm wondering about the modular_multiply manual implementation which adds

quite a few lines of non trivial code. If int128 is available on all/most

platforms, it could be removed and marked as not supported on these,

although it would create an issue with non regression tests.

> but I have a few trivial comments on the language:

>

> + It allows to mix the output of non uniform random functions so that

>

> "It allows the output of non-uniform random functions to be mixed so that"

Fixed.

> + ensures that a perfect permutation is applied: there are no collisions

> + nor holes in the output values.

>

> "neither collisions nor holes", or "no collisions or holes"

I choose the first.

> + The function errors if size is not positive.

>

> "raises an error"

Fixed.

> + * 24 bits mega primes from https://primes.utm.edu/lists/small/millions/

>

> "24 bit mega primes"

Fixed.

> +/* length of n binary representation */

> +static int

> +nbits(uint64 n)

> +{

> + /* set lower bits to 1 and count them */

> + return pg_popcount64(compute_mask(n));

> +}

>

> I suppose you could use n == 0 ? 0 : pg_leftmost_one_pos64(n) + 1, and then...

It would create a branch, that I'm trying to avoid.

> +/* return smallest mask holding n */

> +static uint64

> +compute_mask(uint64 n)

> +{

> + n |= n >> 1;

> + n |= n >> 2;

> + n |= n >> 4;

> + n |= n >> 8;

> + n |= n >> 16;

> + n |= n >> 32;

> + return n;

> +}

>

> ... here you could use 1 << nbits(n)) - 1. I have no idea if doing it

> that way around is better, it's just a thought and removes a few lines

> of bit-swizzling code.

This would create a infinite recursion as nbits currently uses

compute_mask. The 6 bitfield operation above is pretty efficient, I'd let

it at that.

Attached a v16.

--

Fabien.

Attachment | Content-Type | Size |
---|---|---|

pgbench-prp-func-16.patch | text/x-diff | 18.0 KB |

- Re: pgbench - add pseudo-random permutation function at 2019-07-16 04:47:55 from Thomas Munro

- Re: pgbench - add pseudo-random permutation function at 2020-01-04 22:11:15 from Tomas Vondra

From | Date | Subject | |
---|---|---|---|

Next Message | Michael Paquier | 2019-07-23 08:04:32 | Re: Race conditions with TAP test for syncrep |

Previous Message | Michael Paquier | 2019-07-23 07:38:01 | Re: Add parallelism and glibc dependent only options to reindexdb |