[PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Mykyta Yatsenko]

From: Mykyta Yatsenko <yatsenko@meta.com>

Four- and eight-byte keys are common enough to warrant specialized htab
lookups. Fold JHASH_INITVAL and the key length into hashrnd once when
allocating maps with these key sizes.

For JITed BPF_MAP_TYPE_HASH lookups, htab_map_gen_lookup() also knows the
map's fixed key size. Select u32- and u64-specific lookup entry points so
the compiler can specialize both hash setup and key comparison. Other key
sizes continue to use the generic lookup entry point.

This preserves the jhash2() result and lookup semantics while avoiding
generic length handling and repeated state setup.

Measure this with six runs of:

  ./bench -w3 -d10 -a bpf-hashmap-lookup \
      --key_size KEY_SIZE --max_entries MAX_ENTRIES \
      --nr_entries NR_ENTRIES --nr_loops NR_LOOPS \
      --map_flags 0x40

inside a vng guest with two vCPUs and 4 GiB of RAM. Run the baseline
first and the optimized kernel second. Use these workloads:

             max_entries   nr_entries    nr_loops
  small              512          256   8,388,608
  medium          10,000        5,000   8,000,000
  large          100,000       50,000   8,000,000

Mean throughput in million lookups per second is:

  Baseline:
                         key size (bytes)
                      1        4        8       10
    small         89.45    91.21   103.40    91.74
    medium       125.97    80.25    91.94    78.52
    large        140.67    53.56    58.68    47.31

  Optimized:
                         key size (bytes)
                      1        4        8       10
    small         86.95   233.63   168.65    90.88
    medium       124.97   150.20   137.76    77.51
    large        131.06    80.51    76.04    47.25

  Change:
                         key size (bytes)
                      1        4        8       10
    small         -2.79% +156.15%  +63.11%   -0.94%
    medium        -0.79%  +87.17%  +49.83%   -1.28%
    large         -6.84%  +50.32%  +29.58%   -0.12%

The u32 specialization improves lookup throughput by 50-156%, and the
u64 specialization improves it by 30-63%. Ten-byte controls remain
within a 1.3% slowdown. One-byte controls range from -6.8% to -0.8%.

Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
---
Changes in v2:
- Added variants of __htab_map_lookup_elem() functions with inlined
u32/u64 key sizes, use them in htab_map_gen_lookup();
improved lookup perf significantly (Alexei)
- Link to v1: https://patch.msgid.link/20260921-hashtab_fast_hashfn-v1-1-f92ae72cefcd@meta.com
---
 kernel/bpf/hashtab.c | 49 ++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 42 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 6f331c80130d..77c96105eda8 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -612,6 +612,13 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
 		htab->hashrnd = 0;
 	else
 		htab->hashrnd = get_random_u32();
+	/*
+	 * Fold the jhash constant and key length into hashrnd once for the
+	 * fixed-size fast paths instead of doing it on every lookup.
+	 */
+	if (htab->map.key_size == sizeof(u32) ||
+	    htab->map.key_size == sizeof(u64))
+		htab->hashrnd += JHASH_INITVAL + htab->map.key_size;
 
 	htab_init_buckets(htab);
 
@@ -679,9 +686,19 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
 
 static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
 {
-	if (likely(key_len % 4 == 0))
+	const u32 *k = key;
+	u32 b;
+
+	if (key_len == sizeof(u32))
+		b = 0;
+	else if (key_len == sizeof(u64))
+		b = k[1];
+	else if (likely(key_len % 4 == 0))
 		return jhash2(key, key_len / 4, hashrnd);
-	return jhash(key, key_len, hashrnd);
+	else
+		return jhash(key, key_len, hashrnd);
+
+	return __jhash_nwords(k[0], b, 0, hashrnd);
 }
 
 static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
@@ -735,17 +752,15 @@ static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
  * The return value is adjusted by BPF instructions
  * in htab_map_gen_lookup().
  */
-static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
+static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)
 {
 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
 	struct hlist_nulls_head *head;
 	struct htab_elem *l;
-	u32 hash, key_size;
+	u32 hash;
 
 	WARN_ON_ONCE(!bpf_rcu_lock_held());
 
-	key_size = map->key_size;
-
 	hash = htab_map_hash(key, key_size, htab->hashrnd);
 
 	head = select_bucket(htab, hash);
@@ -755,6 +770,21 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
 	return l;
 }
 
+static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
+{
+	return __htab_lookup(map, key, map->key_size);
+}
+
+static void *__htab_map_lookup_elem_u32(struct bpf_map *map, void *key)
+{
+	return __htab_lookup(map, key, sizeof(u32));
+}
+
+static void *__htab_map_lookup_elem_u64(struct bpf_map *map, void *key)
+{
+	return __htab_lookup(map, key, sizeof(u64));
+}
+
 static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
 {
 	struct htab_elem *l = __htab_map_lookup_elem(map, key);
@@ -783,7 +813,12 @@ static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
 
 	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
 		     (void *(*)(struct bpf_map *map, void *key))NULL));
-	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
+	if (map->key_size == sizeof(u32))
+		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u32);
+	else if (map->key_size == sizeof(u64))
+		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u64);
+	else
+		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
 	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
 	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
 				offsetof(struct htab_elem, key) +

---
base-commit: 6e1ac8758fcd07bee12ccaff0087cc66930a4187
change-id: 20260916-hashtab_fast_hashfn-9e52b3c2276e

Best regards,
--  
Mykyta Yatsenko <yatsenko@meta.com>

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Alexei Starovoitov]

On Mon Sep 21, 2026 at 9:28 PM UTC, Mykyta Yatsenko wrote:
>   Change:
>                          key size (bytes)
>                       1        4        8       10
>     small         -2.79% +156.15%  +63.11%   -0.94%
>     medium        -0.79%  +87.17%  +49.83%   -1.28%
>     large         -6.84%  +50.32%  +29.58%   -0.12%

now we're talking :)

Will apply after CI finishes.

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 3401 bytes --]

> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 6f331c80130d7..77c96105eda84 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c

[ ... ]

> @@ -735,17 +752,15 @@ static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
>   * The return value is adjusted by BPF instructions
>   * in htab_map_gen_lookup().
>   */
> -static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> +static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)
>  {
>  	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
>  	struct hlist_nulls_head *head;
>  	struct htab_elem *l;
> -	u32 hash, key_size;
> +	u32 hash;
>
>  	WARN_ON_ONCE(!bpf_rcu_lock_held());
>
> -	key_size = map->key_size;
> -
>  	hash = htab_map_hash(key, key_size, htab->hashrnd);
>
>  	head = select_bucket(htab, hash);
> @@ -755,6 +770,21 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>  	return l;
>  }
>
> +static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> +{
> +	return __htab_lookup(map, key, map->key_size);
> +}
> +
> +static void *__htab_map_lookup_elem_u32(struct bpf_map *map, void *key)
> +{
> +	return __htab_lookup(map, key, sizeof(u32));
> +}
> +
> +static void *__htab_map_lookup_elem_u64(struct bpf_map *map, void *key)
> +{
> +	return __htab_lookup(map, key, sizeof(u64));
> +}
> +

Does the comment block at the top of this hunk still describe the right
function? It says "arguments have to match bpf_map_lookup_elem() exactly",
but __htab_lookup() now takes three arguments (map, key, key_size) rather
than two. The comment also says the function is called directly from BPF
programs or syscalls, but __htab_lookup() is __always_inline, so it is
never the target of BPF_EMIT_CALL() in htab_map_gen_lookup().

The signature constraint looks like it actually applies to the three new
wrappers added below (__htab_map_lookup_elem, __htab_map_lookup_elem_u32,
__htab_map_lookup_elem_u64), which all take two arguments and are the real
call targets. Those wrappers carry no comment at all.

Should the "arguments have to match" note move down onto the wrapper group?

There is a related staleness in the call-flow comment at htab_map_gen_lookup()
around the BUILD_BUG_ON():

>  * do:
>  * bpf_prog
>  *   __htab_map_lookup_elem

The body now emits calls to __htab_map_lookup_elem_u32 and
__htab_map_lookup_elem_u64 for 4- and 8-byte keys, not just
__htab_map_lookup_elem.

> @@ -783,7 +813,12 @@ static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
>
>  	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
>  		     (void *(*)(struct bpf_map *map, void *key))NULL));
> -	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
> +	if (map->key_size == sizeof(u32))
> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u32);
> +	else if (map->key_size == sizeof(u64))
> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u64);
> +	else
> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
>  	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
>  	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
>  				offsetof(struct htab_elem, key) +

[ ... ]


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35659099108

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Alexei Starovoitov]

On Mon, Sep 21, 2026 at 02:28 PM Mykyta Yatsenko <mykyta.yatsenko5@gmail.com> wrote:
> +	/*
> +	 * Fold the jhash constant and key length into hashrnd once for the
> +	 * fixed-size fast paths instead of doing it on every lookup.
> +	 */
> +	if (htab->map.key_size == sizeof(u32) ||
> +	    htab->map.key_size == sizeof(u64))
> +		htab->hashrnd += JHASH_INITVAL + htab->map.key_size;

This optimization is probably not needed anymore?

> -static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> +static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)

__htab_lookup() is __always_inline, but htab_map_hash() and
lookup_nulls_elem_raw() that consume key_size are not.
Whether memcmp() becomes a single compare in _u32/_u64 variants
is up to the compiler. Make both __always_inline?

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Mykyta Yatsenko]

On 9/22/26 2:40 AM, Alexei Starovoitov wrote:
> On Mon, Sep 21, 2026 at 02:28 PM Mykyta Yatsenko <mykyta.yatsenko5@gmail.com> wrote:
>> +	/*
>> +	 * Fold the jhash constant and key length into hashrnd once for the
>> +	 * fixed-size fast paths instead of doing it on every lookup.
>> +	 */
>> +	if (htab->map.key_size == sizeof(u32) ||
>> +	    htab->map.key_size == sizeof(u64))
>> +		htab->hashrnd += JHASH_INITVAL + htab->map.key_size;
> 
> This optimization is probably not needed anymore?
> 
I'll double check with benchmark and remove if not needed in v3.>> -static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>> +static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)
> 
> __htab_lookup() is __always_inline, but htab_map_hash() and
> lookup_nulls_elem_raw() that consume key_size are not.
> Whether memcmp() becomes a single compare in _u32/_u64 variants
> is up to the compiler. Make both __always_inline?
> 
Make sense, thanks.

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Anton Protopopov]

On 26/09/21 02:28PM, Mykyta Yatsenko wrote:
> From: Mykyta Yatsenko <yatsenko@meta.com>
> 
> Four- and eight-byte keys are common enough to warrant specialized htab
> lookups. Fold JHASH_INITVAL and the key length into hashrnd once when
> allocating maps with these key sizes.
> 
> For JITed BPF_MAP_TYPE_HASH lookups, htab_map_gen_lookup() also knows the
> map's fixed key size. Select u32- and u64-specific lookup entry points so
> the compiler can specialize both hash setup and key comparison. Other key
> sizes continue to use the generic lookup entry point.
> 
> This preserves the jhash2() result and lookup semantics while avoiding
> generic length handling and repeated state setup.
> 
> Measure this with six runs of:
> 
>   ./bench -w3 -d10 -a bpf-hashmap-lookup \
>       --key_size KEY_SIZE --max_entries MAX_ENTRIES \
>       --nr_entries NR_ENTRIES --nr_loops NR_LOOPS \
>       --map_flags 0x40
> 
> inside a vng guest with two vCPUs and 4 GiB of RAM. Run the baseline
> first and the optimized kernel second. Use these workloads:
> 
>              max_entries   nr_entries    nr_loops
>   small              512          256   8,388,608
>   medium          10,000        5,000   8,000,000
>   large          100,000       50,000   8,000,000
> 
> Mean throughput in million lookups per second is:
> 
>   Baseline:
>                          key size (bytes)
>                       1        4        8       10
>     small         89.45    91.21   103.40    91.74
>     medium       125.97    80.25    91.94    78.52
>     large        140.67    53.56    58.68    47.31
> 
>   Optimized:
>                          key size (bytes)
>                       1        4        8       10
>     small         86.95   233.63   168.65    90.88
>     medium       124.97   150.20   137.76    77.51
>     large        131.06    80.51    76.04    47.25
> 
>   Change:
>                          key size (bytes)
>                       1        4        8       10
>     small         -2.79% +156.15%  +63.11%   -0.94%
>     medium        -0.79%  +87.17%  +49.83%   -1.28%
>     large         -6.84%  +50.32%  +29.58%   -0.12%
> 
> The u32 specialization improves lookup throughput by 50-156%, and the
> u64 specialization improves it by 30-63%. Ten-byte controls remain
> within a 1.3% slowdown. One-byte controls range from -6.8% to -0.8%.
> 
> Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
> Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
> ---
> Changes in v2:
> - Added variants of __htab_map_lookup_elem() functions with inlined
> u32/u64 key sizes, use them in htab_map_gen_lookup();
> improved lookup perf significantly (Alexei)
> - Link to v1: https://patch.msgid.link/20260921-hashtab_fast_hashfn-v1-1-f92ae72cefcd@meta.com
> ---
>  kernel/bpf/hashtab.c | 49 ++++++++++++++++++++++++++++++++++++++++++-------
>  1 file changed, 42 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 6f331c80130d..77c96105eda8 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c
> @@ -612,6 +612,13 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>  		htab->hashrnd = 0;
>  	else
>  		htab->hashrnd = get_random_u32();
> +	/*
> +	 * Fold the jhash constant and key length into hashrnd once for the
> +	 * fixed-size fast paths instead of doing it on every lookup.
> +	 */
> +	if (htab->map.key_size == sizeof(u32) ||
> +	    htab->map.key_size == sizeof(u64))
> +		htab->hashrnd += JHASH_INITVAL + htab->map.key_size;
>  
>  	htab_init_buckets(htab);
>  
> @@ -679,9 +686,19 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>  
>  static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
>  {
> -	if (likely(key_len % 4 == 0))
> +	const u32 *k = key;
> +	u32 b;
> +
> +	if (key_len == sizeof(u32))
> +		b = 0;
> +	else if (key_len == sizeof(u64))
> +		b = k[1];
> +	else if (likely(key_len % 4 == 0))
>  		return jhash2(key, key_len / 4, hashrnd);
> -	return jhash(key, key_len, hashrnd);
> +	else
> +		return jhash(key, key_len, hashrnd);
> +
> +	return __jhash_nwords(k[0], b, 0, hashrnd);
>  
>  static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
> @@ -735,17 +752,15 @@ static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
>   * The return value is adjusted by BPF instructions
>   * in htab_map_gen_lookup().
>   */
> -static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> +static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)
>  {
>  	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
>  	struct hlist_nulls_head *head;
>  	struct htab_elem *l;
> -	u32 hash, key_size;
> +	u32 hash;
>  
>  	WARN_ON_ONCE(!bpf_rcu_lock_held());
>  
> -	key_size = map->key_size;
> -
>  	hash = htab_map_hash(key, key_size, htab->hashrnd);
>  
>  	head = select_bucket(htab, hash);
> @@ -755,6 +770,21 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>  	return l;
>  }
>  
> +static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> +{
> +	return __htab_lookup(map, key, map->key_size);
> +}
> +
> +static void *__htab_map_lookup_elem_u32(struct bpf_map *map, void *key)
> +{
> +	return __htab_lookup(map, key, sizeof(u32));
> +}
> +
> +static void *__htab_map_lookup_elem_u64(struct bpf_map *map, void *key)
> +{
> +	return __htab_lookup(map, key, sizeof(u64));
> +}
> +
>  static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
>  {
>  	struct htab_elem *l = __htab_map_lookup_elem(map, key);
> @@ -783,7 +813,12 @@ static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
>  
>  	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
>  		     (void *(*)(struct bpf_map *map, void *key))NULL));
> -	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
> +	if (map->key_size == sizeof(u32))
> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u32);
> +	else if (map->key_size == sizeof(u64))
> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u64);
> +	else
> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);

I am trying to remember why I didn't do this when I was touching this
code, I was definitely thinking about it... Given your changes,
it is worth to approach xxh3 again, it works way better for bigger key
sizes, see [1].

  [1] https://archive.fosdem.org/2023/schedule/event/bpf_hashing/



>  	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
>  	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
>  				offsetof(struct htab_elem, key) +
> 
> ---
> base-commit: 6e1ac8758fcd07bee12ccaff0087cc66930a4187
> change-id: 20260916-hashtab_fast_hashfn-9e52b3c2276e
> 
> Best regards,
> --  
> Mykyta Yatsenko <yatsenko@meta.com>
> 

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Mykyta Yatsenko]

On 9/22/26 8:31 AM, Anton Protopopov wrote:
> On 26/09/21 02:28PM, Mykyta Yatsenko wrote:
>> From: Mykyta Yatsenko <yatsenko@meta.com>
>>
>> Four- and eight-byte keys are common enough to warrant specialized htab
>> lookups. Fold JHASH_INITVAL and the key length into hashrnd once when
>> allocating maps with these key sizes.
>>
>> For JITed BPF_MAP_TYPE_HASH lookups, htab_map_gen_lookup() also knows the
>> map's fixed key size. Select u32- and u64-specific lookup entry points so
>> the compiler can specialize both hash setup and key comparison. Other key
>> sizes continue to use the generic lookup entry point.
>>
>> This preserves the jhash2() result and lookup semantics while avoiding
>> generic length handling and repeated state setup.
>>
>> Measure this with six runs of:
>>
>>   ./bench -w3 -d10 -a bpf-hashmap-lookup \
>>       --key_size KEY_SIZE --max_entries MAX_ENTRIES \
>>       --nr_entries NR_ENTRIES --nr_loops NR_LOOPS \
>>       --map_flags 0x40
>>
>> inside a vng guest with two vCPUs and 4 GiB of RAM. Run the baseline
>> first and the optimized kernel second. Use these workloads:
>>
>>              max_entries   nr_entries    nr_loops
>>   small              512          256   8,388,608
>>   medium          10,000        5,000   8,000,000
>>   large          100,000       50,000   8,000,000
>>
>> Mean throughput in million lookups per second is:
>>
>>   Baseline:
>>                          key size (bytes)
>>                       1        4        8       10
>>     small         89.45    91.21   103.40    91.74
>>     medium       125.97    80.25    91.94    78.52
>>     large        140.67    53.56    58.68    47.31
>>
>>   Optimized:
>>                          key size (bytes)
>>                       1        4        8       10
>>     small         86.95   233.63   168.65    90.88
>>     medium       124.97   150.20   137.76    77.51
>>     large        131.06    80.51    76.04    47.25
>>
>>   Change:
>>                          key size (bytes)
>>                       1        4        8       10
>>     small         -2.79% +156.15%  +63.11%   -0.94%
>>     medium        -0.79%  +87.17%  +49.83%   -1.28%
>>     large         -6.84%  +50.32%  +29.58%   -0.12%
>>
>> The u32 specialization improves lookup throughput by 50-156%, and the
>> u64 specialization improves it by 30-63%. Ten-byte controls remain
>> within a 1.3% slowdown. One-byte controls range from -6.8% to -0.8%.
>>
>> Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
>> Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
>> ---
>> Changes in v2:
>> - Added variants of __htab_map_lookup_elem() functions with inlined
>> u32/u64 key sizes, use them in htab_map_gen_lookup();
>> improved lookup perf significantly (Alexei)
>> - Link to v1: https://patch.msgid.link/20260921-hashtab_fast_hashfn-v1-1-f92ae72cefcd@meta.com
>> ---
>>  kernel/bpf/hashtab.c | 49 ++++++++++++++++++++++++++++++++++++++++++-------
>>  1 file changed, 42 insertions(+), 7 deletions(-)
>>
>> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
>> index 6f331c80130d..77c96105eda8 100644
>> --- a/kernel/bpf/hashtab.c
>> +++ b/kernel/bpf/hashtab.c
>> @@ -612,6 +612,13 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>  		htab->hashrnd = 0;
>>  	else
>>  		htab->hashrnd = get_random_u32();
>> +	/*
>> +	 * Fold the jhash constant and key length into hashrnd once for the
>> +	 * fixed-size fast paths instead of doing it on every lookup.
>> +	 */
>> +	if (htab->map.key_size == sizeof(u32) ||
>> +	    htab->map.key_size == sizeof(u64))
>> +		htab->hashrnd += JHASH_INITVAL + htab->map.key_size;
>>  
>>  	htab_init_buckets(htab);
>>  
>> @@ -679,9 +686,19 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>  
>>  static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
>>  {
>> -	if (likely(key_len % 4 == 0))
>> +	const u32 *k = key;
>> +	u32 b;
>> +
>> +	if (key_len == sizeof(u32))
>> +		b = 0;
>> +	else if (key_len == sizeof(u64))
>> +		b = k[1];
>> +	else if (likely(key_len % 4 == 0))
>>  		return jhash2(key, key_len / 4, hashrnd);
>> -	return jhash(key, key_len, hashrnd);
>> +	else
>> +		return jhash(key, key_len, hashrnd);
>> +
>> +	return __jhash_nwords(k[0], b, 0, hashrnd);
>>  
>>  static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
>> @@ -735,17 +752,15 @@ static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
>>   * The return value is adjusted by BPF instructions
>>   * in htab_map_gen_lookup().
>>   */
>> -static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>> +static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)
>>  {
>>  	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
>>  	struct hlist_nulls_head *head;
>>  	struct htab_elem *l;
>> -	u32 hash, key_size;
>> +	u32 hash;
>>  
>>  	WARN_ON_ONCE(!bpf_rcu_lock_held());
>>  
>> -	key_size = map->key_size;
>> -
>>  	hash = htab_map_hash(key, key_size, htab->hashrnd);
>>  
>>  	head = select_bucket(htab, hash);
>> @@ -755,6 +770,21 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>>  	return l;
>>  }
>>  
>> +static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>> +{
>> +	return __htab_lookup(map, key, map->key_size);
>> +}
>> +
>> +static void *__htab_map_lookup_elem_u32(struct bpf_map *map, void *key)
>> +{
>> +	return __htab_lookup(map, key, sizeof(u32));
>> +}
>> +
>> +static void *__htab_map_lookup_elem_u64(struct bpf_map *map, void *key)
>> +{
>> +	return __htab_lookup(map, key, sizeof(u64));
>> +}
>> +
>>  static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
>>  {
>>  	struct htab_elem *l = __htab_map_lookup_elem(map, key);
>> @@ -783,7 +813,12 @@ static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
>>  
>>  	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
>>  		     (void *(*)(struct bpf_map *map, void *key))NULL));
>> -	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
>> +	if (map->key_size == sizeof(u32))
>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u32);
>> +	else if (map->key_size == sizeof(u64))
>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u64);
>> +	else
>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
> 
> I am trying to remember why I didn't do this when I was touching this
> code, I was definitely thinking about it... Given your changes,
> it is worth to approach xxh3 again, it works way better for bigger key
> sizes, see [1].
> 
>   [1] https://archive.fosdem.org/2023/schedule/event/bpf_hashing/
> 
> 
Let me try to run the benchmark. Did you use an actual xxh3 (not
available in kernel) or xxh32/xxh64?> 
>>  	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
>>  	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
>>  				offsetof(struct htab_elem, key) +
>>
>> ---
>> base-commit: 6e1ac8758fcd07bee12ccaff0087cc66930a4187
>> change-id: 20260916-hashtab_fast_hashfn-9e52b3c2276e
>>
>> Best regards,
>> --  
>> Mykyta Yatsenko <yatsenko@meta.com>
>>

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Anton Protopopov]

On 26/09/22 12:45PM, Mykyta Yatsenko wrote:
> 
> 
> On 9/22/26 8:31 AM, Anton Protopopov wrote:
> > On 26/09/21 02:28PM, Mykyta Yatsenko wrote:
> >> From: Mykyta Yatsenko <yatsenko@meta.com>
> >>
> >> Four- and eight-byte keys are common enough to warrant specialized htab
> >> lookups. Fold JHASH_INITVAL and the key length into hashrnd once when
> >> allocating maps with these key sizes.
> >>
> >> For JITed BPF_MAP_TYPE_HASH lookups, htab_map_gen_lookup() also knows the
> >> map's fixed key size. Select u32- and u64-specific lookup entry points so
> >> the compiler can specialize both hash setup and key comparison. Other key
> >> sizes continue to use the generic lookup entry point.
> >>
> >> This preserves the jhash2() result and lookup semantics while avoiding
> >> generic length handling and repeated state setup.
> >>
> >> Measure this with six runs of:
> >>
> >>   ./bench -w3 -d10 -a bpf-hashmap-lookup \
> >>       --key_size KEY_SIZE --max_entries MAX_ENTRIES \
> >>       --nr_entries NR_ENTRIES --nr_loops NR_LOOPS \
> >>       --map_flags 0x40
> >>
> >> inside a vng guest with two vCPUs and 4 GiB of RAM. Run the baseline
> >> first and the optimized kernel second. Use these workloads:
> >>
> >>              max_entries   nr_entries    nr_loops
> >>   small              512          256   8,388,608
> >>   medium          10,000        5,000   8,000,000
> >>   large          100,000       50,000   8,000,000
> >>
> >> Mean throughput in million lookups per second is:
> >>
> >>   Baseline:
> >>                          key size (bytes)
> >>                       1        4        8       10
> >>     small         89.45    91.21   103.40    91.74
> >>     medium       125.97    80.25    91.94    78.52
> >>     large        140.67    53.56    58.68    47.31
> >>
> >>   Optimized:
> >>                          key size (bytes)
> >>                       1        4        8       10
> >>     small         86.95   233.63   168.65    90.88
> >>     medium       124.97   150.20   137.76    77.51
> >>     large        131.06    80.51    76.04    47.25
> >>
> >>   Change:
> >>                          key size (bytes)
> >>                       1        4        8       10
> >>     small         -2.79% +156.15%  +63.11%   -0.94%
> >>     medium        -0.79%  +87.17%  +49.83%   -1.28%
> >>     large         -6.84%  +50.32%  +29.58%   -0.12%
> >>
> >> The u32 specialization improves lookup throughput by 50-156%, and the
> >> u64 specialization improves it by 30-63%. Ten-byte controls remain
> >> within a 1.3% slowdown. One-byte controls range from -6.8% to -0.8%.
> >>
> >> Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
> >> Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
> >> ---
> >> Changes in v2:
> >> - Added variants of __htab_map_lookup_elem() functions with inlined
> >> u32/u64 key sizes, use them in htab_map_gen_lookup();
> >> improved lookup perf significantly (Alexei)
> >> - Link to v1: https://patch.msgid.link/20260921-hashtab_fast_hashfn-v1-1-f92ae72cefcd@meta.com
> >> ---
> >>  kernel/bpf/hashtab.c | 49 ++++++++++++++++++++++++++++++++++++++++++-------
> >>  1 file changed, 42 insertions(+), 7 deletions(-)
> >>
> >> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> >> index 6f331c80130d..77c96105eda8 100644
> >> --- a/kernel/bpf/hashtab.c
> >> +++ b/kernel/bpf/hashtab.c
> >> @@ -612,6 +612,13 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
> >>  		htab->hashrnd = 0;
> >>  	else
> >>  		htab->hashrnd = get_random_u32();
> >> +	/*
> >> +	 * Fold the jhash constant and key length into hashrnd once for the
> >> +	 * fixed-size fast paths instead of doing it on every lookup.
> >> +	 */
> >> +	if (htab->map.key_size == sizeof(u32) ||
> >> +	    htab->map.key_size == sizeof(u64))
> >> +		htab->hashrnd += JHASH_INITVAL + htab->map.key_size;
> >>  
> >>  	htab_init_buckets(htab);
> >>  
> >> @@ -679,9 +686,19 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
> >>  
> >>  static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
> >>  {
> >> -	if (likely(key_len % 4 == 0))
> >> +	const u32 *k = key;
> >> +	u32 b;
> >> +
> >> +	if (key_len == sizeof(u32))
> >> +		b = 0;
> >> +	else if (key_len == sizeof(u64))
> >> +		b = k[1];
> >> +	else if (likely(key_len % 4 == 0))
> >>  		return jhash2(key, key_len / 4, hashrnd);
> >> -	return jhash(key, key_len, hashrnd);
> >> +	else
> >> +		return jhash(key, key_len, hashrnd);
> >> +
> >> +	return __jhash_nwords(k[0], b, 0, hashrnd);
> >>  
> >>  static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
> >> @@ -735,17 +752,15 @@ static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
> >>   * The return value is adjusted by BPF instructions
> >>   * in htab_map_gen_lookup().
> >>   */
> >> -static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> >> +static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)
> >>  {
> >>  	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
> >>  	struct hlist_nulls_head *head;
> >>  	struct htab_elem *l;
> >> -	u32 hash, key_size;
> >> +	u32 hash;
> >>  
> >>  	WARN_ON_ONCE(!bpf_rcu_lock_held());
> >>  
> >> -	key_size = map->key_size;
> >> -
> >>  	hash = htab_map_hash(key, key_size, htab->hashrnd);
> >>  
> >>  	head = select_bucket(htab, hash);
> >> @@ -755,6 +770,21 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> >>  	return l;
> >>  }
> >>  
> >> +static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> >> +{
> >> +	return __htab_lookup(map, key, map->key_size);
> >> +}
> >> +
> >> +static void *__htab_map_lookup_elem_u32(struct bpf_map *map, void *key)
> >> +{
> >> +	return __htab_lookup(map, key, sizeof(u32));
> >> +}
> >> +
> >> +static void *__htab_map_lookup_elem_u64(struct bpf_map *map, void *key)
> >> +{
> >> +	return __htab_lookup(map, key, sizeof(u64));
> >> +}
> >> +
> >>  static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
> >>  {
> >>  	struct htab_elem *l = __htab_map_lookup_elem(map, key);
> >> @@ -783,7 +813,12 @@ static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
> >>  
> >>  	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
> >>  		     (void *(*)(struct bpf_map *map, void *key))NULL));
> >> -	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
> >> +	if (map->key_size == sizeof(u32))
> >> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u32);
> >> +	else if (map->key_size == sizeof(u64))
> >> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u64);
> >> +	else
> >> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
> > 
> > I am trying to remember why I didn't do this when I was touching this
> > code, I was definitely thinking about it... Given your changes,
> > it is worth to approach xxh3 again, it works way better for bigger key
> > sizes, see [1].
> > 
> >   [1] https://archive.fosdem.org/2023/schedule/event/bpf_hashing/
> > 
> > 
> Let me try to run the benchmark. Did you use an actual xxh3 (not
> available in kernel) or xxh32/xxh64?> 

The actual xxh3. For small keys xxh3 was really fragile (the hash was
outperforming in hash-only benchmarks, but was not that good when used in the
hashmap), so I ended up only patching code to use jhash2. For keys >=20,
I think, xxh3 becomes definitely better for all benchmarks. One further note:
the original xxh3 uses vectorized instructions for keys >=240 and for such keys
the fastest ist xxh64. (Well, for keys >5-6K the spooky hash was the best,
but are there any such use cases?)

For the code, I've used my own kernel port of xxh3. The XXH3 also uses a
key-size-based switch internally, so for generated lookups something like
xxh3_17_to_128 can be used specifically. Unfortanetely, I am not sure
what was the latest version I had... You can find one here:

  https://github.com/aspsk/bpf-next/commit/e86be3c926051ee87375da4f0df4b873d2f7e9c2

(notably see xxh3_17_to_128() and xxh3_129_to_240()). The code should work,
but definitely needs some love, maybe it's easier to re-import it using
modern tools.

> >>  	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
> >>  	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
> >>  				offsetof(struct htab_elem, key) +
> >>
> >> ---
> >> base-commit: 6e1ac8758fcd07bee12ccaff0087cc66930a4187
> >> change-id: 20260916-hashtab_fast_hashfn-9e52b3c2276e
> >>
> >> Best regards,
> >> --  
> >> Mykyta Yatsenko <yatsenko@meta.com>
> >>
> 

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Mykyta Yatsenko]

On 9/22/26 2:03 PM, Anton Protopopov wrote:
> On 26/09/22 12:45PM, Mykyta Yatsenko wrote:
>>
>>
>> On 9/22/26 8:31 AM, Anton Protopopov wrote:
>>> On 26/09/21 02:28PM, Mykyta Yatsenko wrote:
>>>> From: Mykyta Yatsenko <yatsenko@meta.com>
>>>>
>>>> Four- and eight-byte keys are common enough to warrant specialized htab
>>>> lookups. Fold JHASH_INITVAL and the key length into hashrnd once when
>>>> allocating maps with these key sizes.
>>>>
>>>> For JITed BPF_MAP_TYPE_HASH lookups, htab_map_gen_lookup() also knows the
>>>> map's fixed key size. Select u32- and u64-specific lookup entry points so
>>>> the compiler can specialize both hash setup and key comparison. Other key
>>>> sizes continue to use the generic lookup entry point.
>>>>
>>>> This preserves the jhash2() result and lookup semantics while avoiding
>>>> generic length handling and repeated state setup.
>>>>
>>>> Measure this with six runs of:
>>>>
>>>>   ./bench -w3 -d10 -a bpf-hashmap-lookup \
>>>>       --key_size KEY_SIZE --max_entries MAX_ENTRIES \
>>>>       --nr_entries NR_ENTRIES --nr_loops NR_LOOPS \
>>>>       --map_flags 0x40
>>>>
>>>> inside a vng guest with two vCPUs and 4 GiB of RAM. Run the baseline
>>>> first and the optimized kernel second. Use these workloads:
>>>>
>>>>              max_entries   nr_entries    nr_loops
>>>>   small              512          256   8,388,608
>>>>   medium          10,000        5,000   8,000,000
>>>>   large          100,000       50,000   8,000,000
>>>>
>>>> Mean throughput in million lookups per second is:
>>>>
>>>>   Baseline:
>>>>                          key size (bytes)
>>>>                       1        4        8       10
>>>>     small         89.45    91.21   103.40    91.74
>>>>     medium       125.97    80.25    91.94    78.52
>>>>     large        140.67    53.56    58.68    47.31
>>>>
>>>>   Optimized:
>>>>                          key size (bytes)
>>>>                       1        4        8       10
>>>>     small         86.95   233.63   168.65    90.88
>>>>     medium       124.97   150.20   137.76    77.51
>>>>     large        131.06    80.51    76.04    47.25
>>>>
>>>>   Change:
>>>>                          key size (bytes)
>>>>                       1        4        8       10
>>>>     small         -2.79% +156.15%  +63.11%   -0.94%
>>>>     medium        -0.79%  +87.17%  +49.83%   -1.28%
>>>>     large         -6.84%  +50.32%  +29.58%   -0.12%
>>>>
>>>> The u32 specialization improves lookup throughput by 50-156%, and the
>>>> u64 specialization improves it by 30-63%. Ten-byte controls remain
>>>> within a 1.3% slowdown. One-byte controls range from -6.8% to -0.8%.
>>>>
>>>> Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
>>>> Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
>>>> ---
>>>> Changes in v2:
>>>> - Added variants of __htab_map_lookup_elem() functions with inlined
>>>> u32/u64 key sizes, use them in htab_map_gen_lookup();
>>>> improved lookup perf significantly (Alexei)
>>>> - Link to v1: https://patch.msgid.link/20260921-hashtab_fast_hashfn-v1-1-f92ae72cefcd@meta.com
>>>> ---
>>>>  kernel/bpf/hashtab.c | 49 ++++++++++++++++++++++++++++++++++++++++++-------
>>>>  1 file changed, 42 insertions(+), 7 deletions(-)
>>>>
>>>> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
>>>> index 6f331c80130d..77c96105eda8 100644
>>>> --- a/kernel/bpf/hashtab.c
>>>> +++ b/kernel/bpf/hashtab.c
>>>> @@ -612,6 +612,13 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>>>  		htab->hashrnd = 0;
>>>>  	else
>>>>  		htab->hashrnd = get_random_u32();
>>>> +	/*
>>>> +	 * Fold the jhash constant and key length into hashrnd once for the
>>>> +	 * fixed-size fast paths instead of doing it on every lookup.
>>>> +	 */
>>>> +	if (htab->map.key_size == sizeof(u32) ||
>>>> +	    htab->map.key_size == sizeof(u64))
>>>> +		htab->hashrnd += JHASH_INITVAL + htab->map.key_size;
>>>>  
>>>>  	htab_init_buckets(htab);
>>>>  
>>>> @@ -679,9 +686,19 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>>>  
>>>>  static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
>>>>  {
>>>> -	if (likely(key_len % 4 == 0))
>>>> +	const u32 *k = key;
>>>> +	u32 b;
>>>> +
>>>> +	if (key_len == sizeof(u32))
>>>> +		b = 0;
>>>> +	else if (key_len == sizeof(u64))
>>>> +		b = k[1];
>>>> +	else if (likely(key_len % 4 == 0))
>>>>  		return jhash2(key, key_len / 4, hashrnd);
>>>> -	return jhash(key, key_len, hashrnd);
>>>> +	else
>>>> +		return jhash(key, key_len, hashrnd);
>>>> +
>>>> +	return __jhash_nwords(k[0], b, 0, hashrnd);
>>>>  
>>>>  static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
>>>> @@ -735,17 +752,15 @@ static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
>>>>   * The return value is adjusted by BPF instructions
>>>>   * in htab_map_gen_lookup().
>>>>   */
>>>> -static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>>>> +static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)
>>>>  {
>>>>  	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
>>>>  	struct hlist_nulls_head *head;
>>>>  	struct htab_elem *l;
>>>> -	u32 hash, key_size;
>>>> +	u32 hash;
>>>>  
>>>>  	WARN_ON_ONCE(!bpf_rcu_lock_held());
>>>>  
>>>> -	key_size = map->key_size;
>>>> -
>>>>  	hash = htab_map_hash(key, key_size, htab->hashrnd);
>>>>  
>>>>  	head = select_bucket(htab, hash);
>>>> @@ -755,6 +770,21 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>>>>  	return l;
>>>>  }
>>>>  
>>>> +static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
>>>> +{
>>>> +	return __htab_lookup(map, key, map->key_size);
>>>> +}
>>>> +
>>>> +static void *__htab_map_lookup_elem_u32(struct bpf_map *map, void *key)
>>>> +{
>>>> +	return __htab_lookup(map, key, sizeof(u32));
>>>> +}
>>>> +
>>>> +static void *__htab_map_lookup_elem_u64(struct bpf_map *map, void *key)
>>>> +{
>>>> +	return __htab_lookup(map, key, sizeof(u64));
>>>> +}
>>>> +
>>>>  static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
>>>>  {
>>>>  	struct htab_elem *l = __htab_map_lookup_elem(map, key);
>>>> @@ -783,7 +813,12 @@ static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
>>>>  
>>>>  	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
>>>>  		     (void *(*)(struct bpf_map *map, void *key))NULL));
>>>> -	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
>>>> +	if (map->key_size == sizeof(u32))
>>>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u32);
>>>> +	else if (map->key_size == sizeof(u64))
>>>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u64);
>>>> +	else
>>>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
>>>
>>> I am trying to remember why I didn't do this when I was touching this
>>> code, I was definitely thinking about it... Given your changes,
>>> it is worth to approach xxh3 again, it works way better for bigger key
>>> sizes, see [1].
>>>
>>>   [1] https://archive.fosdem.org/2023/schedule/event/bpf_hashing/
>>>
>>>
>> Let me try to run the benchmark. Did you use an actual xxh3 (not
>> available in kernel) or xxh32/xxh64?> 
> 
> The actual xxh3. For small keys xxh3 was really fragile (the hash was
> outperforming in hash-only benchmarks, but was not that good when used in the
> hashmap), so I ended up only patching code to use jhash2. For keys >=20,
> I think, xxh3 becomes definitely better for all benchmarks. One further note:
> the original xxh3 uses vectorized instructions for keys >=240 and for such keys
> the fastest ist xxh64. (Well, for keys >5-6K the spooky hash was the best,
> but are there any such use cases?)
> 
> For the code, I've used my own kernel port of xxh3. The XXH3 also uses a
> key-size-based switch internally, so for generated lookups something like
> xxh3_17_to_128 can be used specifically. Unfortanetely, I am not sure
> what was the latest version I had... You can find one here:
> 
>   https://github.com/aspsk/bpf-next/commit/e86be3c926051ee87375da4f0df4b873d2f7e9c2
> 
> (notably see xxh3_17_to_128() and xxh3_129_to_240()). The code should work,
> but definitely needs some love, maybe it's easier to re-import it using
> modern tools.
> 

Trying xxh3:
```
  Small map:
                            key size (bytes)
                    16      32      64     128     256     512    1024
    jhash        91.15   61.31   32.26   16.55    8.26    4.34    2.20
    full_name    53.43   47.50   36.96   25.37   15.29    8.93    4.93
    XXH64        40.16   32.50   29.65   23.73   17.25   11.57    7.19
    XXH3         54.94   53.56   48.39   37.66   22.33   13.31    7.71

  Medium map:
                            key size (bytes)
                    16      32      64     128     256     512    1024
    jhash        68.93   52.25   28.27   16.02    7.98    3.92    2.08
    full_name    43.71   39.56   31.52   22.19   13.90    7.20    4.21
    XXH64        35.18   28.95   25.83   21.40   15.51    8.97    5.66
    XXH3         43.06   42.86   39.05   32.37   19.78   10.58    6.13

  Large map:
                            key size (bytes)
                    16      32      64     128     256     512    1024
    jhash        45.42   35.95   21.62   13.35    6.84    2.94    1.43
    full_name    24.14   22.50   19.46   15.15   10.59    4.31    2.23
    XXH64        20.73   18.35   17.43   14.99   11.75    4.89    2.78
    XXH3         24.63   24.26   23.17   20.75   13.97    5.27    2.76

                            key size (bytes)
                    64     128     256     512    1024
   small        +54.9% +128.4% +167.2% +203.7% +256.0%
   medium       +37.1% +104.7% +149.6% +169.6% +209.3%
   large        +14.6%  +59.0% +104.6%  +95.5%  +98.6%

XXH3 starts winning consistently at 64-byte keys. Additional
measurements at 40, 48, and 56 bytes still showed regressions for the
large map, so 64 bytes is used as the conservative cutoff.
```

I don't think we have a lot of maps with 64+ bytes keys on the
hot paths, but generally looks like a useful addition.

We'll need to bring xxh3 into the kernel (it's not small), 
do we want to limit it to bpf only or not.
Either way sounds like a good direction, but maybe for another
patch series.
Anton, Alexei, any thoughts, on xxh3 direction? Do we need it
at all, where to put hash implementation, should it go into this patch series 
or new.
>>>>  	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
>>>>  	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
>>>>  				offsetof(struct htab_elem, key) +
>>>>
>>>> ---
>>>> base-commit: 6e1ac8758fcd07bee12ccaff0087cc66930a4187
>>>> change-id: 20260916-hashtab_fast_hashfn-9e52b3c2276e
>>>>
>>>> Best regards,
>>>> --  
>>>> Mykyta Yatsenko <yatsenko@meta.com>
>>>>
>>

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Anton Protopopov]

On 26/09/22 04:57PM, Mykyta Yatsenko wrote:
> On 9/22/26 2:03 PM, Anton Protopopov wrote:
> > On 26/09/22 12:45PM, Mykyta Yatsenko wrote:
> >>
> >>
> >> On 9/22/26 8:31 AM, Anton Protopopov wrote:
> >>> On 26/09/21 02:28PM, Mykyta Yatsenko wrote:
> >>>> From: Mykyta Yatsenko <yatsenko@meta.com>
> >>>>
> >>>> Four- and eight-byte keys are common enough to warrant specialized htab
> >>>> lookups. Fold JHASH_INITVAL and the key length into hashrnd once when
> >>>> allocating maps with these key sizes.
> >>>>
> >>>> For JITed BPF_MAP_TYPE_HASH lookups, htab_map_gen_lookup() also knows the
> >>>> map's fixed key size. Select u32- and u64-specific lookup entry points so
> >>>> the compiler can specialize both hash setup and key comparison. Other key
> >>>> sizes continue to use the generic lookup entry point.
> >>>>
> >>>> This preserves the jhash2() result and lookup semantics while avoiding
> >>>> generic length handling and repeated state setup.
> >>>>
> >>>> Measure this with six runs of:
> >>>>
> >>>>   ./bench -w3 -d10 -a bpf-hashmap-lookup \
> >>>>       --key_size KEY_SIZE --max_entries MAX_ENTRIES \
> >>>>       --nr_entries NR_ENTRIES --nr_loops NR_LOOPS \
> >>>>       --map_flags 0x40
> >>>>
> >>>> inside a vng guest with two vCPUs and 4 GiB of RAM. Run the baseline
> >>>> first and the optimized kernel second. Use these workloads:
> >>>>
> >>>>              max_entries   nr_entries    nr_loops
> >>>>   small              512          256   8,388,608
> >>>>   medium          10,000        5,000   8,000,000
> >>>>   large          100,000       50,000   8,000,000
> >>>>
> >>>> Mean throughput in million lookups per second is:
> >>>>
> >>>>   Baseline:
> >>>>                          key size (bytes)
> >>>>                       1        4        8       10
> >>>>     small         89.45    91.21   103.40    91.74
> >>>>     medium       125.97    80.25    91.94    78.52
> >>>>     large        140.67    53.56    58.68    47.31
> >>>>
> >>>>   Optimized:
> >>>>                          key size (bytes)
> >>>>                       1        4        8       10
> >>>>     small         86.95   233.63   168.65    90.88
> >>>>     medium       124.97   150.20   137.76    77.51
> >>>>     large        131.06    80.51    76.04    47.25
> >>>>
> >>>>   Change:
> >>>>                          key size (bytes)
> >>>>                       1        4        8       10
> >>>>     small         -2.79% +156.15%  +63.11%   -0.94%
> >>>>     medium        -0.79%  +87.17%  +49.83%   -1.28%
> >>>>     large         -6.84%  +50.32%  +29.58%   -0.12%
> >>>>
> >>>> The u32 specialization improves lookup throughput by 50-156%, and the
> >>>> u64 specialization improves it by 30-63%. Ten-byte controls remain
> >>>> within a 1.3% slowdown. One-byte controls range from -6.8% to -0.8%.
> >>>>
> >>>> Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
> >>>> Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>
> >>>> ---
> >>>> Changes in v2:
> >>>> - Added variants of __htab_map_lookup_elem() functions with inlined
> >>>> u32/u64 key sizes, use them in htab_map_gen_lookup();
> >>>> improved lookup perf significantly (Alexei)
> >>>> - Link to v1: https://patch.msgid.link/20260921-hashtab_fast_hashfn-v1-1-f92ae72cefcd@meta.com
> >>>> ---
> >>>>  kernel/bpf/hashtab.c | 49 ++++++++++++++++++++++++++++++++++++++++++-------
> >>>>  1 file changed, 42 insertions(+), 7 deletions(-)
> >>>>
> >>>> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> >>>> index 6f331c80130d..77c96105eda8 100644
> >>>> --- a/kernel/bpf/hashtab.c
> >>>> +++ b/kernel/bpf/hashtab.c
> >>>> @@ -612,6 +612,13 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
> >>>>  		htab->hashrnd = 0;
> >>>>  	else
> >>>>  		htab->hashrnd = get_random_u32();
> >>>> +	/*
> >>>> +	 * Fold the jhash constant and key length into hashrnd once for the
> >>>> +	 * fixed-size fast paths instead of doing it on every lookup.
> >>>> +	 */
> >>>> +	if (htab->map.key_size == sizeof(u32) ||
> >>>> +	    htab->map.key_size == sizeof(u64))
> >>>> +		htab->hashrnd += JHASH_INITVAL + htab->map.key_size;
> >>>>  
> >>>>  	htab_init_buckets(htab);
> >>>>  
> >>>> @@ -679,9 +686,19 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
> >>>>  
> >>>>  static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
> >>>>  {
> >>>> -	if (likely(key_len % 4 == 0))
> >>>> +	const u32 *k = key;
> >>>> +	u32 b;
> >>>> +
> >>>> +	if (key_len == sizeof(u32))
> >>>> +		b = 0;
> >>>> +	else if (key_len == sizeof(u64))
> >>>> +		b = k[1];
> >>>> +	else if (likely(key_len % 4 == 0))
> >>>>  		return jhash2(key, key_len / 4, hashrnd);
> >>>> -	return jhash(key, key_len, hashrnd);
> >>>> +	else
> >>>> +		return jhash(key, key_len, hashrnd);
> >>>> +
> >>>> +	return __jhash_nwords(k[0], b, 0, hashrnd);
> >>>>  
> >>>>  static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
> >>>> @@ -735,17 +752,15 @@ static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
> >>>>   * The return value is adjusted by BPF instructions
> >>>>   * in htab_map_gen_lookup().
> >>>>   */
> >>>> -static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> >>>> +static __always_inline void *__htab_lookup(struct bpf_map *map, void *key, u32 key_size)
> >>>>  {
> >>>>  	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
> >>>>  	struct hlist_nulls_head *head;
> >>>>  	struct htab_elem *l;
> >>>> -	u32 hash, key_size;
> >>>> +	u32 hash;
> >>>>  
> >>>>  	WARN_ON_ONCE(!bpf_rcu_lock_held());
> >>>>  
> >>>> -	key_size = map->key_size;
> >>>> -
> >>>>  	hash = htab_map_hash(key, key_size, htab->hashrnd);
> >>>>  
> >>>>  	head = select_bucket(htab, hash);
> >>>> @@ -755,6 +770,21 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> >>>>  	return l;
> >>>>  }
> >>>>  
> >>>> +static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
> >>>> +{
> >>>> +	return __htab_lookup(map, key, map->key_size);
> >>>> +}
> >>>> +
> >>>> +static void *__htab_map_lookup_elem_u32(struct bpf_map *map, void *key)
> >>>> +{
> >>>> +	return __htab_lookup(map, key, sizeof(u32));
> >>>> +}
> >>>> +
> >>>> +static void *__htab_map_lookup_elem_u64(struct bpf_map *map, void *key)
> >>>> +{
> >>>> +	return __htab_lookup(map, key, sizeof(u64));
> >>>> +}
> >>>> +
> >>>>  static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
> >>>>  {
> >>>>  	struct htab_elem *l = __htab_map_lookup_elem(map, key);
> >>>> @@ -783,7 +813,12 @@ static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
> >>>>  
> >>>>  	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
> >>>>  		     (void *(*)(struct bpf_map *map, void *key))NULL));
> >>>> -	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
> >>>> +	if (map->key_size == sizeof(u32))
> >>>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u32);
> >>>> +	else if (map->key_size == sizeof(u64))
> >>>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u64);
> >>>> +	else
> >>>> +		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
> >>>
> >>> I am trying to remember why I didn't do this when I was touching this
> >>> code, I was definitely thinking about it... Given your changes,
> >>> it is worth to approach xxh3 again, it works way better for bigger key
> >>> sizes, see [1].
> >>>
> >>>   [1] https://archive.fosdem.org/2023/schedule/event/bpf_hashing/
> >>>
> >>>
> >> Let me try to run the benchmark. Did you use an actual xxh3 (not
> >> available in kernel) or xxh32/xxh64?> 
> > 
> > The actual xxh3. For small keys xxh3 was really fragile (the hash was
> > outperforming in hash-only benchmarks, but was not that good when used in the
> > hashmap), so I ended up only patching code to use jhash2. For keys >=20,
> > I think, xxh3 becomes definitely better for all benchmarks. One further note:
> > the original xxh3 uses vectorized instructions for keys >=240 and for such keys
> > the fastest ist xxh64. (Well, for keys >5-6K the spooky hash was the best,
> > but are there any such use cases?)
> > 
> > For the code, I've used my own kernel port of xxh3. The XXH3 also uses a
> > key-size-based switch internally, so for generated lookups something like
> > xxh3_17_to_128 can be used specifically. Unfortanetely, I am not sure
> > what was the latest version I had... You can find one here:
> > 
> >   https://github.com/aspsk/bpf-next/commit/e86be3c926051ee87375da4f0df4b873d2f7e9c2
> > 
> > (notably see xxh3_17_to_128() and xxh3_129_to_240()). The code should work,
> > but definitely needs some love, maybe it's easier to re-import it using
> > modern tools.
> > 
> 
> Trying xxh3:
> ```
>   Small map:
>                             key size (bytes)
>                     16      32      64     128     256     512    1024
>     jhash        91.15   61.31   32.26   16.55    8.26    4.34    2.20
>     full_name    53.43   47.50   36.96   25.37   15.29    8.93    4.93
>     XXH64        40.16   32.50   29.65   23.73   17.25   11.57    7.19
>     XXH3         54.94   53.56   48.39   37.66   22.33   13.31    7.71
> 
>   Medium map:
>                             key size (bytes)
>                     16      32      64     128     256     512    1024
>     jhash        68.93   52.25   28.27   16.02    7.98    3.92    2.08
>     full_name    43.71   39.56   31.52   22.19   13.90    7.20    4.21
>     XXH64        35.18   28.95   25.83   21.40   15.51    8.97    5.66
>     XXH3         43.06   42.86   39.05   32.37   19.78   10.58    6.13
> 
>   Large map:
>                             key size (bytes)
>                     16      32      64     128     256     512    1024
>     jhash        45.42   35.95   21.62   13.35    6.84    2.94    1.43
>     full_name    24.14   22.50   19.46   15.15   10.59    4.31    2.23
>     XXH64        20.73   18.35   17.43   14.99   11.75    4.89    2.78
>     XXH3         24.63   24.26   23.17   20.75   13.97    5.27    2.76
> 
>                             key size (bytes)
>                     64     128     256     512    1024
>    small        +54.9% +128.4% +167.2% +203.7% +256.0%
>    medium       +37.1% +104.7% +149.6% +169.6% +209.3%
>    large        +14.6%  +59.0% +104.6%  +95.5%  +98.6%
> 
> XXH3 starts winning consistently at 64-byte keys. Additional
> measurements at 40, 48, and 56 bytes still showed regressions for the
> large map, so 64 bytes is used as the conservative cutoff.
> ```
> 
> I don't think we have a lot of maps with 64+ bytes keys on the
> hot paths, but generally looks like a useful addition.
> 
> We'll need to bring xxh3 into the kernel (it's not small), 
> do we want to limit it to bpf only or not.
> Either way sounds like a good direction, but maybe for another
> patch series.
> Anton, Alexei, any thoughts, on xxh3 direction? Do we need it
> at all, where to put hash implementation, should it go into this patch series 
> or new.

I think this patch is great as is, no reason to block it by xxh3.

I've mentioned that xxh3 fragile, and I had few variants,
and the benchmarks depended a lot on compiler & hardware
it was run on (say, didn't get to testing it on arm at all).
So if you're getting mixed results as well, then let's pass
on it, until there is "reliably optimized" implementation...

> >>>>  	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
> >>>>  	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
> >>>>  				offsetof(struct htab_elem, key) +
> >>>>
> >>>> ---
> >>>> base-commit: 6e1ac8758fcd07bee12ccaff0087cc66930a4187
> >>>> change-id: 20260916-hashtab_fast_hashfn-9e52b3c2276e
> >>>>
> >>>> Best regards,
> >>>> --  
> >>>> Mykyta Yatsenko <yatsenko@meta.com>
> >>>>
> >>
> 

Re: [PATCH bpf-next v2] bpf: Speed up htab lookups for u32/u64 keys

[Alexei Starovoitov]

On Tue Sep 22, 2026 at 4:19 PM UTC, Anton Protopopov wrote:
>> I don't think we have a lot of maps with 64+ bytes keys on the
>> hot paths, but generally looks like a useful addition.
>> 
>> We'll need to bring xxh3 into the kernel (it's not small), 
>> do we want to limit it to bpf only or not.

Let's not rush with xxh. Sure, it's faster, but cost to maintain
a new hash function is not trivial.

>> Either way sounds like a good direction, but maybe for another
>> patch series.
>> Anton, Alexei, any thoughts, on xxh3 direction? Do we need it
>> at all, where to put hash implementation, should it go into this patch series 
>> or new.
>
> I think this patch is great as is, no reason to block it by xxh3.

+1.
Proceed without xxh3 for now.