Thread: Re: Fix bank selection logic in SLRU

> On 10 Dec 2024, at 15:39, Yura Sokolov <y.sokolov@postgrespro.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
nearestpower of 2 - we will help incorrectly configured systems to use proper amount of memory and keep performance of
properlyconfigured 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@yandex-team.ru> wrote:
>
>
>
> > On 10 Dec 2024, at 15:39, Yura Sokolov <y.sokolov@postgrespro.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
nearestpower of 2 - we will help incorrectly configured systems to use proper amount of memory and keep performance of
properlyconfigured 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@gmail.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,
everythingwill be buffered only in bank 64. 


Best regards, Andrey Borodin.

On Tue, Dec 10, 2024 at 8:58 AM Dilip Kumar <dilipbalaut@gmail.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,
everythingwill 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(banksize) 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 10 Dec 2024, at 16:58, Dilip Kumar <dilipbalaut@gmail.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@yandex-team.ru 
> <mailto:x4mmm@yandex-team.ru>> wrote:
> 
> 
> 
>      > On 10 Dec 2024, at 15:39, Yura Sokolov <y.sokolov@postgrespro.ru
>     <mailto:y.sokolov@postgrespro.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.sokolov@postgrespro.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.sokolov@postgrespro.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.sokolov@postgrespro.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.