Why n_buckets is at least max_entries?

Why n_buckets is at least max_entries?

[Cong Wang]

Hello,

Any reason why we allocate at least max_entries of buckets of a hash map?

 466
 467         /* hash table size must be power of 2 */
 468         htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);

This looks very odd to me, as I never see any other hash table
implementation like this. I _guess_ we try to make it a perfect hash?
But in reality no hash is perfect, so it is impossible to have no
conflicts, that is, there is almost always a bucket that has multiple
elements.

Or is it because other special maps (LRU?) require this? I can not
immediately see it from htab_map_alloc().

Thanks!

Re: Why n_buckets is at least max_entries?

[Daniel Borkmann]

On 12/15/20 10:44 PM, Cong Wang wrote:
> Hello,
> 
> Any reason why we allocate at least max_entries of buckets of a hash map?
> 
>   466
>   467         /* hash table size must be power of 2 */
>   468         htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
> 
> This looks very odd to me, as I never see any other hash table
> implementation like this. I _guess_ we try to make it a perfect hash?
> But in reality no hash is perfect, so it is impossible to have no
> conflicts, that is, there is almost always a bucket that has multiple
> elements.
> 
> Or is it because other special maps (LRU?) require this? I can not
> immediately see it from htab_map_alloc().

hash/LRU map is optimized for lookup speed, so __select_bucket() makes use
of the fact that it's power of 2.

Thanks,
Daniel

Re: Why n_buckets is at least max_entries?

[Alexei Starovoitov]

On Tue, Dec 15, 2020 at 1:44 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
>
> Hello,
>
> Any reason why we allocate at least max_entries of buckets of a hash map?
>
>  466
>  467         /* hash table size must be power of 2 */
>  468         htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);

because hashmap performance matters a lot.

Re: Why n_buckets is at least max_entries?

[Cong Wang]

On Tue, Dec 15, 2020 at 5:45 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Tue, Dec 15, 2020 at 1:44 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> >
> > Hello,
> >
> > Any reason why we allocate at least max_entries of buckets of a hash map?
> >
> >  466
> >  467         /* hash table size must be power of 2 */
> >  468         htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
>
> because hashmap performance matters a lot.

Unless you believe hash is perfect, there is always conflict no matter
how many buckets we have.

Other hashmap implementations also care about performance, but none
of them allocates the number of buckets in this aggressive way. In some
particular cases, for instance max_entries=1025, we end up having almost
buckets twice of max_entries.

Thanks.

Re: Why n_buckets is at least max_entries?

[Alexei Starovoitov]

On Tue, Dec 15, 2020 at 5:55 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
>
> On Tue, Dec 15, 2020 at 5:45 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Tue, Dec 15, 2020 at 1:44 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > >
> > > Hello,
> > >
> > > Any reason why we allocate at least max_entries of buckets of a hash map?
> > >
> > >  466
> > >  467         /* hash table size must be power of 2 */
> > >  468         htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
> >
> > because hashmap performance matters a lot.
>
> Unless you believe hash is perfect, there is always conflict no matter
> how many buckets we have.
>
> Other hashmap implementations also care about performance, but none
> of them allocates the number of buckets in this aggressive way. In some
> particular cases, for instance max_entries=1025, we end up having almost
> buckets twice of max_entries.

Do you have any numbers to prove that max_entries > 1024 with n_buckets == 1024
would still provide the same level of performance?

Re: Why n_buckets is at least max_entries?

[Cong Wang]

On Tue, Dec 15, 2020 at 6:29 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Tue, Dec 15, 2020 at 5:55 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> >
> > On Tue, Dec 15, 2020 at 5:45 PM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Tue, Dec 15, 2020 at 1:44 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > > >
> > > > Hello,
> > > >
> > > > Any reason why we allocate at least max_entries of buckets of a hash map?
> > > >
> > > >  466
> > > >  467         /* hash table size must be power of 2 */
> > > >  468         htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
> > >
> > > because hashmap performance matters a lot.
> >
> > Unless you believe hash is perfect, there is always conflict no matter
> > how many buckets we have.
> >
> > Other hashmap implementations also care about performance, but none
> > of them allocates the number of buckets in this aggressive way. In some
> > particular cases, for instance max_entries=1025, we end up having almost
> > buckets twice of max_entries.
>
> Do you have any numbers to prove that max_entries > 1024 with n_buckets == 1024
> would still provide the same level of performance?

No, I assume you had when you added this implementation?

Also, it depends on what performance you are talking about too, the
lookup path is lockless so has nothing to do with the number of buckets.

The update path does content for bucket locks, but it is arguably the
slow path.

Thanks.

Re: Why n_buckets is at least max_entries?

[Alexei Starovoitov]

On Tue, Dec 15, 2020 at 06:39:26PM -0800, Cong Wang wrote:
> On Tue, Dec 15, 2020 at 6:29 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Tue, Dec 15, 2020 at 5:55 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > >
> > > On Tue, Dec 15, 2020 at 5:45 PM Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > On Tue, Dec 15, 2020 at 1:44 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
> > > > >
> > > > > Hello,
> > > > >
> > > > > Any reason why we allocate at least max_entries of buckets of a hash map?
> > > > >
> > > > >  466
> > > > >  467         /* hash table size must be power of 2 */
> > > > >  468         htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
> > > >
> > > > because hashmap performance matters a lot.
> > >
> > > Unless you believe hash is perfect, there is always conflict no matter
> > > how many buckets we have.
> > >
> > > Other hashmap implementations also care about performance, but none
> > > of them allocates the number of buckets in this aggressive way. In some
> > > particular cases, for instance max_entries=1025, we end up having almost
> > > buckets twice of max_entries.
> >
> > Do you have any numbers to prove that max_entries > 1024 with n_buckets == 1024
> > would still provide the same level of performance?
> 
> No, I assume you had when you added this implementation?
> 
> Also, it depends on what performance you are talking about too, the
> lookup path is lockless so has nothing to do with the number of buckets.
> 
> The update path does content for bucket locks, but it is arguably the
> slow path.

The update/delete _is_ the fast path for many use cases.
Please see commit 6c9059817432 ("bpf: pre-allocate hash map elements")
Six! different implementation of prealloc were considered at that time.
Just as much, if not more, performance analysis went into LRU design.
See git log kernel/bpf/bpf_lru_list.c.
BPF was always laser focused on performance.