Re: Fix bank selection logic in SLRU

Good day, hackers.

Due to long discussion about SLRU size configuration [1] and code
evolution, non-serious bug were introduced:

- intermediate versions assumed cache size is always power of 2,
- therefore to determine bank simple binary-and with mask were used:

bankno = pageno & ctl->bank_mask;

- final merged version allows arbitrary cache size for every cache
type, but code for bankno were not fixed.

It is not critical bug, since it doesn't hurt correctness just
performance. In worst case only one bank will be used.

I attach the patch, that changes SlruCtlData->bank_mask to ->nbanks,
and changes calculation to modulo operation.

bankno = pageno % ctl->nbanks;

Probably, instead of modulo operation could be used multiplication:

bankno = ((uint64) murmurhash32(pageno) * ctl->nbanks) >> 32;

But I didn't bother to measure does it pay for or not.

[1]
https://www.postgresql.org/message-id/flat/CAFiTN-vzDvNz%3DExGXz6gdyjtzGixKSqs0mKHMmaQ8sOSEFZ33A%40mail.gmail.com

Regards,
Yura Sokolov aka funny-falcon

> On 10 Dec 2024, at 15:39, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
>
> It is not critical bug, since it doesn't hurt correctness just performance. In worst case only one bank will be used.

Ugh... yeah. IMO the problem is that we do not have protection that rejects values that are not power of 2.
If other values given system operates as if there are 2^(popcount(n)-1) banks. So if we just round down value to nearest power of 2 - we will help incorrectly configured systems to use proper amount of memory and keep performance of properly configured systems.

IMO doing modulo is not necessary. And hash function is pure waste of CPU cycles.

Best regards, Andrey Borodin.

On Tue, Dec 10, 2024 at 6:32 PM Andrey M. Borodin <x4mmm(at)yandex-team(dot)ru> wrote:
>
>
>
> > On 10 Dec 2024, at 15:39, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
> >
> > It is not critical bug, since it doesn't hurt correctness just performance. In worst case only one bank will be used.
>
> Ugh... yeah. IMO the problem is that we do not have protection that rejects values that are not power of 2.
> If other values given system operates as if there are 2^(popcount(n)-1) banks. So if we just round down value to nearest power of 2 - we will help incorrectly configured systems to use proper amount of memory and keep performance of properly configured systems.
>
> IMO doing modulo is not necessary. And hash function is pure waste of CPU cycles.

IIUC, we do check that it should be in multiple of bank size (i.e.)
which is multiple of 2, right? Am I missing something?

/*
* Helper function for GUC check_hook to check whether slru buffers are in
* multiples of SLRU_BANK_SIZE.
*/
bool
check_slru_buffers(const char *name, int *newval)
{
/* Valid values are multiples of SLRU_BANK_SIZE */
if (*newval % SLRU_BANK_SIZE == 0)
return true;

GUC_check_errdetail("\"%s\" must be a multiple of %d", name,
SLRU_BANK_SIZE);
return false;
}

--
Regards,
Dilip Kumar
EnterpriseDB: http://www.enterprisedb.com

> On 10 Dec 2024, at 16:26, Dilip Kumar <dilipbalaut(at)gmail(dot)com> wrote:
>
> IIUC, we do check that it should be in multiple of bank size (i.e.)
> which is multiple of 2, right? Am I missing something?

Bank selection code assumes that number of buffers is power of 2.
If the number of buffers is not power of 2 - only subset of buffers will be used. In worst case, e.g. 65 buffers, everything will be buffered only in bank 64.

Best regards, Andrey Borodin.

On Tue, 10 Dec 2024 at 7:24 PM, Andrey M. Borodin <x4mmm(at)yandex-team(dot)ru>
wrote:

>
>
> > On 10 Dec 2024, at 16:26, Dilip Kumar <dilipbalaut(at)gmail(dot)com> wrote:
> >
> > IIUC, we do check that it should be in multiple of bank size (i.e.)
> > which is multiple of 2, right? Am I missing something?
>
> Bank selection code assumes that number of buffers is power of 2.
> If the number of buffers is not power of 2 - only subset of buffers will
> be used. In worst case, e.g. 65 buffers, everything will be buffered only
> in bank 64.

But why that would be the case? the acceptable values for GUC to configure
the slru buffers are in multiple of 16(bank size) we have that check to
check the GUC values.

—
Dilip

>

On Tue, Dec 10, 2024 at 8:58 AM Dilip Kumar <dilipbalaut(at)gmail(dot)com> wrote:
>> Bank selection code assumes that number of buffers is power of 2.
>> If the number of buffers is not power of 2 - only subset of buffers will be used. In worst case, e.g. 65 buffers, everything will be buffered only in bank 64.
>
> But why that would be the case? the acceptable values for GUC to configure the slru buffers are in multiple of 16(bank size) we have that check to check the GUC values.

"Must be a multiple of 16" and "must be a power of 2" are different
criteria. For example, 48 is a multiple of 16 but it is not a power of
2. If the code assumes that we have an actual power of 2, the check
you quoted in your previous email is insufficient.

--
Robert Haas
EDB: http://www.enterprisedb.com

On Tue, 10 Dec 2024 at 7:30 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Tue, Dec 10, 2024 at 8:58 AM Dilip Kumar <dilipbalaut(at)gmail(dot)com> wrote:
> >> Bank selection code assumes that number of buffers is power of 2.
> >> If the number of buffers is not power of 2 - only subset of buffers
> will be used. In worst case, e.g. 65 buffers, everything will be buffered
> only in bank 64.
> >
> > But why that would be the case? the acceptable values for GUC to
> configure the slru buffers are in multiple of 16(bank size) we have that
> check to check the GUC values.
>
> "Must be a multiple of 16" and "must be a power of 2" are different
> criteria. For example, 48 is a multiple of 16 but it is not a power of
> 2. If the code assumes that we have an actual power of 2, the check
> you quoted in your previous email is insufficient.

Yeah I see it’s an issue. Thanks for clarifying.

—
Dilip

>

On Tue, 10 Dec 2024 at 6:32 PM, Andrey M. Borodin <x4mmm(at)yandex-team(dot)ru>
wrote:

>
>
> > On 10 Dec 2024, at 15:39, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
> >
> > It is not critical bug, since it doesn't hurt correctness just
> performance. In worst case only one bank will be used.
>
> Ugh... yeah. IMO the problem is that we do not have protection that
> rejects values that are not power of 2.
> If other values given system operates as if there are 2^(popcount(n)-1)
> banks. So if we just round down value to nearest power of 2 - we will help
> incorrectly configured systems to use proper amount of memory and keep
> performance of properly configured systems.

+1

>
> IMO doing modulo is not necessary. And hash function is pure waste of CPU
> cycles.

I agree

—
Dilip

>

> On 10 Dec 2024, at 16:58, Dilip Kumar <dilipbalaut(at)gmail(dot)com> wrote:
>
> slru buffers are in multiple of 16(bank size)

Yes, my example with 64 buffers is incorrect.
The worst case scenario is when user configures 80, 144, 528 or 1040 buffers, but only two banks (32 buffers) will be used.

Best regards, Andrey Borodin.

10.12.2024 17:07, Dilip Kumar wrote:
> On Tue, 10 Dec 2024 at 6:32 PM, Andrey M. Borodin <x4mmm(at)yandex-team(dot)ru
> <mailto:x4mmm(at)yandex-team(dot)ru>> wrote:
>
>
>
> > On 10 Dec 2024, at 15:39, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru
> <mailto:y(dot)sokolov(at)postgrespro(dot)ru>> wrote:
> >
> > It is not critical bug, since it doesn't hurt correctness just
> performance. In worst case only one bank will be used.
>
> Ugh... yeah. IMO the problem is that we do not have protection that
> rejects values that are not power of 2.
> If other values given system operates as if there are
> 2^(popcount(n)-1) banks. So if we just round down value to nearest
> power of 2 - we will help incorrectly configured systems to use
> proper amount of memory and keep performance of properly configured
> systems.
>
>
> +1
>
>
>
> IMO doing modulo is not necessary. And hash function is pure waste
> of CPU cycles.
>
>
> I agree

I did some measurement "divide-modulo" vs "modulo using multiplication by
reciprocal" vs "simple binary and" using simple C program [0].
(Note: loop is made to be dependent on previous iteration result so no
parallel computation happens).

Results on Ryzen 7 5825U:

$ time ./div 100000000 15 3 # binary and
real 0m0,943s
$ time ./div 100000000 15 1 # multiply by reciprocal
real 0m3,123s
$ time ./div 100000000 15 0 # just plain `%`
real 0m4,540s

It means:
- `&` takes 0.69ns
- `mult-rec` takes 2.94ns
- `%` takes 3.24ns.

I believe, compared to further memory accesses it could be count as
negligible.

(Certainly, it could be worse on some older processors. But I still doubt
it will be measurably worse on top of all other things SLRU does.)

[0] https://gist.github.com/funny-falcon/173923b4fea7ffdf9e02595a0f99aa74

Regards,
Yura Sokolov aka funny-falcon

> On 19 Dec 2024, at 15:01, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
>
> - `&` takes 0.69ns
> - `mult-rec` takes 2.94ns
> - `%` takes 3.24ns.

Thanks, Yura, for benchmarks and off-list conversation.
I’ve reproduced similar numbers on my Apple M2.
I agree that additional 3-4ns are negligible in case of SLRU access.

+ bits16 nbanks;

Perhaps, it’s not bits anymore. Also, is 64K banks ought enough for everybody?

Best regards, Andrey Borodin.

19.12.2024 13:10, Andrey Borodin пишет:
>
>
>> On 19 Dec 2024, at 15:01, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
>>
>> - `&` takes 0.69ns
>> - `mult-rec` takes 2.94ns
>> - `%` takes 3.24ns.
>
> Thanks, Yura, for benchmarks and off-list conversation.
> I’ve reproduced similar numbers on my Apple M2.
> I agree that additional 3-4ns are negligible in case of SLRU access.
>
>
>
> + bits16 nbanks;
>
> Perhaps, it’s not bits anymore. Also, is 64K banks ought enough for everybody?
>
>
> Best regards, Andrey Borodin.

There are artificial limit currently:

#define SLRU_MAX_ALLOWED_BUFFERS ((1024 * 1024 * 1024) / BLCKSZ)
#define SLRU_BANK_BITSHIFT 4
#define SLRU_BANK_SIZE (1 << SLRU_BANK_BITSHIFT)

So, there's no more than 8192 banks at the moment.

But I believe, some customers will want to have more than 1GB of SLRU in
the future. (They do already actually)

----
Yura

> On 19 Dec 2024, at 15:37, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
>
> So, there's no more than 8192 banks at the moment.

OK, but still current type indicates bitwise usage, while struct member is used as a number.

Best regards, Andrey Borodin.

19.12.2024 15:10, Andrey M. Borodin wrote:
>
>
>> On 19 Dec 2024, at 15:37, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
>>
>> So, there's no more than 8192 banks at the moment.
>
> OK, but still current type indicates bitwise usage, while struct member is used as a number.

Ok, I agree. Here's version with type change bits16 -> uint16.

> On 19 Dec 2024, at 20:48, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
>
> Here's version with type change bits16 -> uint16

Thanks! This version looks good to me. I’ll mark the CF entry as RfC.

Best regards, Andrey Borodin.

On 2024-Dec-27, Andrey Borodin wrote:

> > On 19 Dec 2024, at 20:48, Yura Sokolov <y(dot)sokolov(at)postgrespro(dot)ru> wrote:
> >
> > Here's version with type change bits16 -> uint16
>
> Thanks! This version looks good to me. I’ll mark the CF entry as RfC.

Thank you, I have pushed this.

--
Álvaro Herrera 48°01'N 7°57'E — https://www.EnterpriseDB.com/
"Once again, thank you and all of the developers for your hard work on
PostgreSQL. This is by far the most pleasant management experience of
any database I've worked on." (Dan Harris)
http://archives.postgresql.org/pgsql-performance/2006-04/msg00247.php