[2/5] eytzinger: Promote to include/linux/

  eytzinger trees are a faster alternative to binary search. They're a bit
more expensive to setup, but lookups perform much better assuming the
tree isn't entirely in cache.

Binary search is a worst case scenario for branch prediction and
prefetching, but eytzinger trees have children adjacent in memory and
thus we can prefetch before knowing the result of a comparison.

An eytzinger tree is a binary tree laid out in an array, with the same
geometry as the usual binary heap construction, but used as a search
tree instead.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
---
 fs/bcachefs/bset.c                         |   2 +-
 fs/bcachefs/journal_seq_blacklist.c        |   6 +-
 fs/bcachefs/replicas.c                     |  17 ++-
 fs/bcachefs/replicas.h                     |   3 +-
 fs/bcachefs/super-io.h                     |   2 +-
 fs/bcachefs/util.c                         | 145 +--------------------
 fs/bcachefs/util.h                         |   4 -
 {fs/bcachefs => include/linux}/eytzinger.h |  56 ++++----
 lib/sort.c                                 |  85 ++++++++++++
 9 files changed, 136 insertions(+), 184 deletions(-)
 rename {fs/bcachefs => include/linux}/eytzinger.h (78%)
  

On Fri, Jan 26, 2024 at 05:06:52PM -0500, Kent Overstreet wrote:
> eytzinger trees are a faster alternative to binary search. They're a bit
> more expensive to setup, but lookups perform much better assuming the
> tree isn't entirely in cache.
> 
> Binary search is a worst case scenario for branch prediction and
> prefetching, but eytzinger trees have children adjacent in memory and
> thus we can prefetch before knowing the result of a comparison.
> 
> An eytzinger tree is a binary tree laid out in an array, with the same
> geometry as the usual binary heap construction, but used as a search
> tree instead.
> 
> Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

This looks more or less like what I remember of building heaps and
squinting at my horrible handwritten notes about eytzinger trees from
back in the day.

Reviewed-by: Darrick J. Wong <djwong@kernel.org>

--D

> ---
>  fs/bcachefs/bset.c                         |   2 +-
>  fs/bcachefs/journal_seq_blacklist.c        |   6 +-
>  fs/bcachefs/replicas.c                     |  17 ++-
>  fs/bcachefs/replicas.h                     |   3 +-
>  fs/bcachefs/super-io.h                     |   2 +-
>  fs/bcachefs/util.c                         | 145 +--------------------
>  fs/bcachefs/util.h                         |   4 -
>  {fs/bcachefs => include/linux}/eytzinger.h |  56 ++++----
>  lib/sort.c                                 |  85 ++++++++++++
>  9 files changed, 136 insertions(+), 184 deletions(-)
>  rename {fs/bcachefs => include/linux}/eytzinger.h (78%)
> 
> diff --git a/fs/bcachefs/bset.c b/fs/bcachefs/bset.c
> index 3fd1085b6c61..1d77aa55d641 100644
> --- a/fs/bcachefs/bset.c
> +++ b/fs/bcachefs/bset.c
> @@ -9,12 +9,12 @@
>  #include "bcachefs.h"
>  #include "btree_cache.h"
>  #include "bset.h"
> -#include "eytzinger.h"
>  #include "trace.h"
>  #include "util.h"
>  
>  #include <asm/unaligned.h>
>  #include <linux/console.h>
> +#include <linux/eytzinger.h>
>  #include <linux/random.h>
>  #include <linux/prefetch.h>
>  
> diff --git a/fs/bcachefs/journal_seq_blacklist.c b/fs/bcachefs/journal_seq_blacklist.c
> index 0200e299cfbb..024c9b1b323f 100644
> --- a/fs/bcachefs/journal_seq_blacklist.c
> +++ b/fs/bcachefs/journal_seq_blacklist.c
> @@ -2,10 +2,11 @@
>  
>  #include "bcachefs.h"
>  #include "btree_iter.h"
> -#include "eytzinger.h"
>  #include "journal_seq_blacklist.h"
>  #include "super-io.h"
>  
> +#include <linux/eytzinger.h>
> +
>  /*
>   * journal_seq_blacklist machinery:
>   *
> @@ -119,8 +120,7 @@ int bch2_journal_seq_blacklist_add(struct bch_fs *c, u64 start, u64 end)
>  	return ret ?: bch2_blacklist_table_initialize(c);
>  }
>  
> -static int journal_seq_blacklist_table_cmp(const void *_l,
> -					   const void *_r, size_t size)
> +static int journal_seq_blacklist_table_cmp(const void *_l, const void *_r)
>  {
>  	const struct journal_seq_blacklist_table_entry *l = _l;
>  	const struct journal_seq_blacklist_table_entry *r = _r;
> diff --git a/fs/bcachefs/replicas.c b/fs/bcachefs/replicas.c
> index cc2672c12031..75fdce373f76 100644
> --- a/fs/bcachefs/replicas.c
> +++ b/fs/bcachefs/replicas.c
> @@ -6,12 +6,15 @@
>  #include "replicas.h"
>  #include "super-io.h"
>  
> +#include <linux/sort.h>
> +
>  static int bch2_cpu_replicas_to_sb_replicas(struct bch_fs *,
>  					    struct bch_replicas_cpu *);
>  
>  /* Some (buggy!) compilers don't allow memcmp to be passed as a pointer */
> -static int bch2_memcmp(const void *l, const void *r, size_t size)
> +static int bch2_memcmp(const void *l, const void *r,  const void *priv)
>  {
> +	size_t size = (size_t) priv;
>  	return memcmp(l, r, size);
>  }
>  
> @@ -39,7 +42,8 @@ void bch2_replicas_entry_sort(struct bch_replicas_entry_v1 *e)
>  
>  static void bch2_cpu_replicas_sort(struct bch_replicas_cpu *r)
>  {
> -	eytzinger0_sort(r->entries, r->nr, r->entry_size, bch2_memcmp, NULL);
> +	eytzinger0_sort_r(r->entries, r->nr, r->entry_size,
> +			  bch2_memcmp, NULL, (void *)(size_t)r->entry_size);
>  }
>  
>  static void bch2_replicas_entry_v0_to_text(struct printbuf *out,
> @@ -824,10 +828,11 @@ static int bch2_cpu_replicas_validate(struct bch_replicas_cpu *cpu_r,
>  {
>  	unsigned i;
>  
> -	sort_cmp_size(cpu_r->entries,
> -		      cpu_r->nr,
> -		      cpu_r->entry_size,
> -		      bch2_memcmp, NULL);
> +	sort_r(cpu_r->entries,
> +	       cpu_r->nr,
> +	       cpu_r->entry_size,
> +	       bch2_memcmp, NULL,
> +	       (void *)(size_t)cpu_r->entry_size);
>  
>  	for (i = 0; i < cpu_r->nr; i++) {
>  		struct bch_replicas_entry_v1 *e =
> diff --git a/fs/bcachefs/replicas.h b/fs/bcachefs/replicas.h
> index 654a4b26d3a3..983cce782ac2 100644
> --- a/fs/bcachefs/replicas.h
> +++ b/fs/bcachefs/replicas.h
> @@ -3,9 +3,10 @@
>  #define _BCACHEFS_REPLICAS_H
>  
>  #include "bkey.h"
> -#include "eytzinger.h"
>  #include "replicas_types.h"
>  
> +#include <linux/eytzinger.h>
> +
>  void bch2_replicas_entry_sort(struct bch_replicas_entry_v1 *);
>  void bch2_replicas_entry_to_text(struct printbuf *,
>  				 struct bch_replicas_entry_v1 *);
> diff --git a/fs/bcachefs/super-io.h b/fs/bcachefs/super-io.h
> index 95e80e06316b..f37620919e11 100644
> --- a/fs/bcachefs/super-io.h
> +++ b/fs/bcachefs/super-io.h
> @@ -3,12 +3,12 @@
>  #define _BCACHEFS_SUPER_IO_H
>  
>  #include "extents.h"
> -#include "eytzinger.h"
>  #include "super_types.h"
>  #include "super.h"
>  #include "sb-members.h"
>  
>  #include <asm/byteorder.h>
> +#include <linux/eytzinger.h>
>  
>  static inline bool bch2_version_compatible(u16 version)
>  {
> diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c
> index d7ea95abb9df..c7cf9c6fcf9a 100644
> --- a/fs/bcachefs/util.c
> +++ b/fs/bcachefs/util.c
> @@ -11,6 +11,7 @@
>  #include <linux/console.h>
>  #include <linux/ctype.h>
>  #include <linux/debugfs.h>
> +#include <linux/eytzinger.h>
>  #include <linux/freezer.h>
>  #include <linux/kthread.h>
>  #include <linux/log2.h>
> @@ -24,7 +25,6 @@
>  #include <linux/sched/clock.h>
>  #include <linux/mean_and_variance.h>
>  
> -#include "eytzinger.h"
>  #include "util.h"
>  
>  static const char si_units[] = "?kMGTPEZY";
> @@ -863,149 +863,6 @@ void memcpy_from_bio(void *dst, struct bio *src, struct bvec_iter src_iter)
>  	}
>  }
>  
> -static int alignment_ok(const void *base, size_t align)
> -{
> -	return IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) ||
> -		((unsigned long)base & (align - 1)) == 0;
> -}
> -
> -static void u32_swap(void *a, void *b, size_t size)
> -{
> -	u32 t = *(u32 *)a;
> -	*(u32 *)a = *(u32 *)b;
> -	*(u32 *)b = t;
> -}
> -
> -static void u64_swap(void *a, void *b, size_t size)
> -{
> -	u64 t = *(u64 *)a;
> -	*(u64 *)a = *(u64 *)b;
> -	*(u64 *)b = t;
> -}
> -
> -static void generic_swap(void *a, void *b, size_t size)
> -{
> -	char t;
> -
> -	do {
> -		t = *(char *)a;
> -		*(char *)a++ = *(char *)b;
> -		*(char *)b++ = t;
> -	} while (--size > 0);
> -}
> -
> -static inline int do_cmp(void *base, size_t n, size_t size,
> -			 int (*cmp_func)(const void *, const void *, size_t),
> -			 size_t l, size_t r)
> -{
> -	return cmp_func(base + inorder_to_eytzinger0(l, n) * size,
> -			base + inorder_to_eytzinger0(r, n) * size,
> -			size);
> -}
> -
> -static inline void do_swap(void *base, size_t n, size_t size,
> -			   void (*swap_func)(void *, void *, size_t),
> -			   size_t l, size_t r)
> -{
> -	swap_func(base + inorder_to_eytzinger0(l, n) * size,
> -		  base + inorder_to_eytzinger0(r, n) * size,
> -		  size);
> -}
> -
> -void eytzinger0_sort(void *base, size_t n, size_t size,
> -		     int (*cmp_func)(const void *, const void *, size_t),
> -		     void (*swap_func)(void *, void *, size_t))
> -{
> -	int i, c, r;
> -
> -	if (!swap_func) {
> -		if (size == 4 && alignment_ok(base, 4))
> -			swap_func = u32_swap;
> -		else if (size == 8 && alignment_ok(base, 8))
> -			swap_func = u64_swap;
> -		else
> -			swap_func = generic_swap;
> -	}
> -
> -	/* heapify */
> -	for (i = n / 2 - 1; i >= 0; --i) {
> -		for (r = i; r * 2 + 1 < n; r = c) {
> -			c = r * 2 + 1;
> -
> -			if (c + 1 < n &&
> -			    do_cmp(base, n, size, cmp_func, c, c + 1) < 0)
> -				c++;
> -
> -			if (do_cmp(base, n, size, cmp_func, r, c) >= 0)
> -				break;
> -
> -			do_swap(base, n, size, swap_func, r, c);
> -		}
> -	}
> -
> -	/* sort */
> -	for (i = n - 1; i > 0; --i) {
> -		do_swap(base, n, size, swap_func, 0, i);
> -
> -		for (r = 0; r * 2 + 1 < i; r = c) {
> -			c = r * 2 + 1;
> -
> -			if (c + 1 < i &&
> -			    do_cmp(base, n, size, cmp_func, c, c + 1) < 0)
> -				c++;
> -
> -			if (do_cmp(base, n, size, cmp_func, r, c) >= 0)
> -				break;
> -
> -			do_swap(base, n, size, swap_func, r, c);
> -		}
> -	}
> -}
> -
> -void sort_cmp_size(void *base, size_t num, size_t size,
> -	  int (*cmp_func)(const void *, const void *, size_t),
> -	  void (*swap_func)(void *, void *, size_t size))
> -{
> -	/* pre-scale counters for performance */
> -	int i = (num/2 - 1) * size, n = num * size, c, r;
> -
> -	if (!swap_func) {
> -		if (size == 4 && alignment_ok(base, 4))
> -			swap_func = u32_swap;
> -		else if (size == 8 && alignment_ok(base, 8))
> -			swap_func = u64_swap;
> -		else
> -			swap_func = generic_swap;
> -	}
> -
> -	/* heapify */
> -	for ( ; i >= 0; i -= size) {
> -		for (r = i; r * 2 + size < n; r  = c) {
> -			c = r * 2 + size;
> -			if (c < n - size &&
> -			    cmp_func(base + c, base + c + size, size) < 0)
> -				c += size;
> -			if (cmp_func(base + r, base + c, size) >= 0)
> -				break;
> -			swap_func(base + r, base + c, size);
> -		}
> -	}
> -
> -	/* sort */
> -	for (i = n - size; i > 0; i -= size) {
> -		swap_func(base, base + i, size);
> -		for (r = 0; r * 2 + size < i; r = c) {
> -			c = r * 2 + size;
> -			if (c < i - size &&
> -			    cmp_func(base + c, base + c + size, size) < 0)
> -				c += size;
> -			if (cmp_func(base + r, base + c, size) >= 0)
> -				break;
> -			swap_func(base + r, base + c, size);
> -		}
> -	}
> -}
> -
>  static void mempool_free_vp(void *element, void *pool_data)
>  {
>  	size_t size = (size_t) pool_data;
> diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h
> index 0059481995ef..c3b11c3d24ea 100644
> --- a/fs/bcachefs/util.h
> +++ b/fs/bcachefs/util.h
> @@ -737,10 +737,6 @@ static inline void memset_u64s_tail(void *s, int c, unsigned bytes)
>  	memset(s + bytes, c, rem);
>  }
>  
> -void sort_cmp_size(void *base, size_t num, size_t size,
> -	  int (*cmp_func)(const void *, const void *, size_t),
> -	  void (*swap_func)(void *, void *, size_t));
> -
>  /* just the memmove, doesn't update @_nr */
>  #define __array_insert_item(_array, _nr, _pos)				\
>  	memmove(&(_array)[(_pos) + 1],					\
> diff --git a/fs/bcachefs/eytzinger.h b/include/linux/eytzinger.h
> similarity index 78%
> rename from fs/bcachefs/eytzinger.h
> rename to include/linux/eytzinger.h
> index b04750dbf870..9565a5c26cd5 100644
> --- a/fs/bcachefs/eytzinger.h
> +++ b/include/linux/eytzinger.h
> @@ -1,27 +1,37 @@
>  /* SPDX-License-Identifier: GPL-2.0 */
> -#ifndef _EYTZINGER_H
> -#define _EYTZINGER_H
> +#ifndef _LINUX_EYTZINGER_H
> +#define _LINUX_EYTZINGER_H
>  
>  #include <linux/bitops.h>
>  #include <linux/log2.h>
>  
> -#include "util.h"
> +#ifdef EYTZINGER_DEBUG
> +#define EYTZINGER_BUG_ON(cond)		BUG_ON(cond)
> +#else
> +#define EYTZINGER_BUG_ON(cond)
> +#endif
>  
>  /*
>   * Traversal for trees in eytzinger layout - a full binary tree layed out in an
> - * array
> - */
> -
> -/*
> - * One based indexing version:
> + * array.
>   *
> - * With one based indexing each level of the tree starts at a power of two -
> - * good for cacheline alignment:
> + * Consider using an eytzinger tree any time you would otherwise be doing binary
> + * search over an array. Binary search is a worst case scenario for branch
> + * prediction and prefetching, but in an eytzinger tree every node's children
> + * are adjacent in memory, thus we can prefetch children before knowing the
> + * result of the comparison, assuming multiple nodes fit on a cacheline.
> + *
> + * Two variants are provided, for one based indexing and zero based indexing.
> + *
> + * Zero based indexing is more convenient, but one based indexing has better
> + * alignment and thus better performance because each new level of the tree
> + * starts at a power of two, and thus if element 0 was cacheline aligned, each
> + * new level will be as well.
>   */
>  
>  static inline unsigned eytzinger1_child(unsigned i, unsigned child)
>  {
> -	EBUG_ON(child > 1);
> +	EYTZINGER_BUG_ON(child > 1);
>  
>  	return (i << 1) + child;
>  }
> @@ -58,7 +68,7 @@ static inline unsigned eytzinger1_last(unsigned size)
>  
>  static inline unsigned eytzinger1_next(unsigned i, unsigned size)
>  {
> -	EBUG_ON(i > size);
> +	EYTZINGER_BUG_ON(i > size);
>  
>  	if (eytzinger1_right_child(i) <= size) {
>  		i = eytzinger1_right_child(i);
> @@ -74,7 +84,7 @@ static inline unsigned eytzinger1_next(unsigned i, unsigned size)
>  
>  static inline unsigned eytzinger1_prev(unsigned i, unsigned size)
>  {
> -	EBUG_ON(i > size);
> +	EYTZINGER_BUG_ON(i > size);
>  
>  	if (eytzinger1_left_child(i) <= size) {
>  		i = eytzinger1_left_child(i) + 1;
> @@ -101,7 +111,7 @@ static inline unsigned __eytzinger1_to_inorder(unsigned i, unsigned size,
>  	unsigned shift = __fls(size) - b;
>  	int s;
>  
> -	EBUG_ON(!i || i > size);
> +	EYTZINGER_BUG_ON(!i || i > size);
>  
>  	i  ^= 1U << b;
>  	i <<= 1;
> @@ -126,7 +136,7 @@ static inline unsigned __inorder_to_eytzinger1(unsigned i, unsigned size,
>  	unsigned shift;
>  	int s;
>  
> -	EBUG_ON(!i || i > size);
> +	EYTZINGER_BUG_ON(!i || i > size);
>  
>  	/*
>  	 * sign bit trick:
> @@ -164,7 +174,7 @@ static inline unsigned inorder_to_eytzinger1(unsigned i, unsigned size)
>  
>  static inline unsigned eytzinger0_child(unsigned i, unsigned child)
>  {
> -	EBUG_ON(child > 1);
> +	EYTZINGER_BUG_ON(child > 1);
>  
>  	return (i << 1) + 1 + child;
>  }
> @@ -231,11 +241,9 @@ static inline unsigned inorder_to_eytzinger0(unsigned i, unsigned size)
>  	     (_i) != -1;				\
>  	     (_i) = eytzinger0_next((_i), (_size)))
>  
> -typedef int (*eytzinger_cmp_fn)(const void *l, const void *r, size_t size);
> -
>  /* return greatest node <= @search, or -1 if not found */
>  static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
> -					 eytzinger_cmp_fn cmp, const void *search)
> +					 cmp_func_t cmp, const void *search)
>  {
>  	unsigned i, n = 0;
>  
> @@ -244,7 +252,7 @@ static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
>  
>  	do {
>  		i = n;
> -		n = eytzinger0_child(i, cmp(search, base + i * size, size) >= 0);
> +		n = eytzinger0_child(i, cmp(search, base + i * size) >= 0);
>  	} while (n < nr);
>  
>  	if (n & 1) {
> @@ -274,8 +282,8 @@ static inline ssize_t eytzinger0_find_le(void *base, size_t nr, size_t size,
>  	_i;								\
>  })
>  
> -void eytzinger0_sort(void *, size_t, size_t,
> -		    int (*cmp_func)(const void *, const void *, size_t),
> -		    void (*swap_func)(void *, void *, size_t));
> +void eytzinger0_sort_r(void *, size_t, size_t,
> +		       cmp_r_func_t, swap_r_func_t, const void *);
> +void eytzinger0_sort(void *, size_t, size_t, cmp_func_t, swap_func_t);
>  
> -#endif /* _EYTZINGER_H */
> +#endif /* _LINUX_EYTZINGER_H */
> diff --git a/lib/sort.c b/lib/sort.c
> index b399bf10d675..3dfa83d86bbb 100644
> --- a/lib/sort.c
> +++ b/lib/sort.c
> @@ -290,3 +290,88 @@ void sort(void *base, size_t num, size_t size,
>  	return sort_r(base, num, size, _CMP_WRAPPER, SWAP_WRAPPER, &w);
>  }
>  EXPORT_SYMBOL(sort);
> +
> +#include <linux/eytzinger.h>
> +
> +static inline int eytzinger0_do_cmp(void *base, size_t n, size_t size,
> +			 cmp_r_func_t cmp_func, const void *priv,
> +			 size_t l, size_t r)
> +{
> +	return do_cmp(base + inorder_to_eytzinger0(l, n) * size,
> +		      base + inorder_to_eytzinger0(r, n) * size,
> +		      cmp_func, priv);
> +}
> +
> +static inline void eytzinger0_do_swap(void *base, size_t n, size_t size,
> +			   swap_r_func_t swap_func, const void *priv,
> +			   size_t l, size_t r)
> +{
> +	do_swap(base + inorder_to_eytzinger0(l, n) * size,
> +		base + inorder_to_eytzinger0(r, n) * size,
> +		size, swap_func, priv);
> +}
> +
> +void eytzinger0_sort_r(void *base, size_t n, size_t size,
> +		       cmp_r_func_t cmp_func,
> +		       swap_r_func_t swap_func,
> +		       const void *priv)
> +{
> +	int i, c, r;
> +
> +	if (!swap_func) {
> +		if (is_aligned(base, size, 8))
> +			swap_func = SWAP_WORDS_64;
> +		else if (is_aligned(base, size, 4))
> +			swap_func = SWAP_WORDS_32;
> +		else
> +			swap_func = SWAP_BYTES;
> +	}
> +
> +	/* heapify */
> +	for (i = n / 2 - 1; i >= 0; --i) {
> +		for (r = i; r * 2 + 1 < n; r = c) {
> +			c = r * 2 + 1;
> +
> +			if (c + 1 < n &&
> +			    eytzinger0_do_cmp(base, n, size, cmp_func, priv, c, c + 1) < 0)
> +				c++;
> +
> +			if (eytzinger0_do_cmp(base, n, size, cmp_func, priv, r, c) >= 0)
> +				break;
> +
> +			eytzinger0_do_swap(base, n, size, swap_func, priv, r, c);
> +		}
> +	}
> +
> +	/* sort */
> +	for (i = n - 1; i > 0; --i) {
> +		eytzinger0_do_swap(base, n, size, swap_func, priv, 0, i);
> +
> +		for (r = 0; r * 2 + 1 < i; r = c) {
> +			c = r * 2 + 1;
> +
> +			if (c + 1 < i &&
> +			    eytzinger0_do_cmp(base, n, size, cmp_func, priv, c, c + 1) < 0)
> +				c++;
> +
> +			if (eytzinger0_do_cmp(base, n, size, cmp_func, priv, r, c) >= 0)
> +				break;
> +
> +			eytzinger0_do_swap(base, n, size, swap_func, priv, r, c);
> +		}
> +	}
> +}
> +EXPORT_SYMBOL_GPL(eytzinger0_sort_r);
> +
> +void eytzinger0_sort(void *base, size_t n, size_t size,
> +		     cmp_func_t cmp_func,
> +		     swap_func_t swap_func)
> +{
> +	struct wrapper w = {
> +		.cmp  = cmp_func,
> +		.swap = swap_func,
> +	};
> +
> +	return eytzinger0_sort_r(base, n, size, _CMP_WRAPPER, SWAP_WRAPPER, &w);
> +}
> +EXPORT_SYMBOL_GPL(eytzinger0_sort);
> -- 
> 2.43.0
> 
>