From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2BC1FC4361B for ; Wed, 16 Dec 2020 01:56:27 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DE567230FF for ; Wed, 16 Dec 2020 01:56:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1725789AbgLPB4Z (ORCPT ); Tue, 15 Dec 2020 20:56:25 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37160 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725783AbgLPB4Y (ORCPT ); Tue, 15 Dec 2020 20:56:24 -0500 Received: from mail-pj1-x1036.google.com (mail-pj1-x1036.google.com [IPv6:2607:f8b0:4864:20::1036]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A6F3EC061793 for ; Tue, 15 Dec 2020 17:55:44 -0800 (PST) Received: by mail-pj1-x1036.google.com with SMTP id iq13so623489pjb.3 for ; Tue, 15 Dec 2020 17:55:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=lOnaNx+FOjfjzTvevCJ8dWeetPW4iWtEiTISdNYyoT4=; b=kG4PvUiAFncGD79/MeEKZE6xSsCDcSx90v0/hfbdMJp5bnUkkL5iWMUI28oEvN/FyI Ml15x0ryjDID03W8KAJ9tBP3d1gmjIn2LEJyak7REgnhUe0sRq3vnC1qdVPRXD8szhgB Cq2XT9wPCjG4CENMvvY9oFlPQAdlrv45AvVLw5huCVEyY3lw0MXRAzvEXffmvgJmJi8C ZV1/RKnpHJvFi/vP+BVa4iG13v20/cvfvpWYdsBtZXDHEVk1GPNIUbSB+DK+/HbeWHdd ZP8fFR10h+UczG3CS6cmDhr59FvCOTTT+YLjnVLCpOPyBqinS/btOLXDOfbs6FmRsu88 T/oQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=lOnaNx+FOjfjzTvevCJ8dWeetPW4iWtEiTISdNYyoT4=; b=fSldsXywy6sepGNrbqK8OjvFiVOF3F80i5/NyemWyIKNLEmYs3dQl3w8Rr+wzZfZGk Hw/88pyrAulJ6UfWBmByxjC5FRfSNMeJYeM0GHWxxFatFm59yHNR8oEv0OrSvvndR7oL 0sO9vgGxEraoSMiwrmSDR2SEvXN3pUfPROZhXjxrsirqsg5YvLB7C62d7WU65QBRCa/Z 15xYosfDLiP1NWj4bX2rPgCrrHnhaTbzezcY3CkbCDMs/qHMHu2kJMypDlDoBgVaH9Xq q9WnmnPXhB7bj3lJwaRVLYImONh1dHKNF5soyWttJ7w5UAX+2Op6t+rpOnMy6tnhRbxh q2cw== X-Gm-Message-State: AOAM532sslTOByA7x7dctXSYridy4C21xz1O+rf6NJrrKFJ4ffjlQFHc hNg51W/KzE5dX5uISr75sRE5Gs03cX9wCj7J9hk= X-Google-Smtp-Source: ABdhPJw0PsvXssdcQGynJELc29ATHocsnk2gk9SGrvog6d9T6A5MlDwc8m+JZQ4KxdwDK0Mhy5+/i9NhlYIsbxjRD7M= X-Received: by 2002:a17:902:9302:b029:da:f6b0:643a with SMTP id bc2-20020a1709029302b02900daf6b0643amr29593394plb.33.1608083744178; Tue, 15 Dec 2020 17:55:44 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Cong Wang Date: Tue, 15 Dec 2020 17:55:33 -0800 Message-ID: Subject: Re: Why n_buckets is at least max_entries? To: Alexei Starovoitov Cc: bpf , Alexei Starovoitov Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org On Tue, Dec 15, 2020 at 5:45 PM Alexei Starovoitov wrote: > > On Tue, Dec 15, 2020 at 1: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); > > 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.