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@xxxxxxxxx> wrote:
> >
> > On Tue, Dec 15, 2020 at 5:55 PM Cong Wang <xiyou.wangcong@xxxxxxxxx> wrote:
> > >
> > > On Tue, Dec 15, 2020 at 5:45 PM Alexei Starovoitov
> > > <alexei.starovoitov@xxxxxxxxx> wrote:
> > > >
> > > > On Tue, Dec 15, 2020 at 1:44 PM Cong Wang <xiyou.wangcong@xxxxxxxxx> 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.
