Skip to contentSkip to conversation

Minimize the search range used

PATCH In review Alan Huang 2 participants 4 messages Aug 13, 2024

lore
Share & tools
lore

Alan Huang

author
#0 lore raw

v2 cover Minimize the search range used

Hi,

Changes in v2:
- In v1, bset_aux_tree_buf_end still includes the size of the prev array when calculating the buffer end, v2 removes it.

This series minimize the search range used to calculate the mantissa, so that the mantissa can have more meaningful bits which reduces the slow path comparison when search a key.

The prev array stuff becomes useless after minimizing the search range, so this series also removes the prev array stuff.

Alan Huang (2):
bcachefs: Minimize the search range used to calculate the mantissa
bcachefs: Remove the prev array stuff

 fs/bcachefs/bset.c | 36 +++++-------------------------------
 1 file changed, 5 insertions(+), 31 deletions(-)
Signature · 1 line
2.45.2
author
#1 lore raw

PATCH v2 1/2 bcachefs: Minimize the search range used to calculate the mantissa

When the search key's mantissa is larger than the node i's, we know that the search key is larger than the first key of the cacheline corresponding to node i, so that when we are calculating the mantissa of right side nodes of node i, the left side of the search range can be the first key of node i. Once the search range is minimized, the mantissa we are calculating can have more useful bits, thus reduce the slow path comparison. Besides, we can now remove all the prev array stuff.

---
 fs/bcachefs/bset.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
fs/bcachefs/bset.c +1 -1
index 00a821f617a5..43b40f6b8c0a 100644
@@ -616,7 +616,7 @@ static __always_inline void make_bfloat(struct btree *b, struct bset_tree *t,
 	struct bkey_packed *m = tree_to_bkey(b, t, j);
 	struct bkey_packed *l = is_power_of_2(j)
 		? min_key
-		: tree_to_prev_bkey(b, t, j >> ffs(j));
+		: tree_to_bkey(b, t, j >> ffs(j));
 	struct bkey_packed *r = is_power_of_2(j + 1)
 		? max_key
 		: tree_to_bkey(b, t, j >> (ffz(j) + 1));
Signature · 1 line
2.45.2
author
#2 lore raw

PATCH v2 2/2 bcachefs: Remove the prev array stuff

In reply to Alan Huang

After reducing the search range when building the aux tree, the prev array stuff is no longer useful, so remove it.

---
 fs/bcachefs/bset.c | 34 ++++------------------------------
 1 file changed, 4 insertions(+), 30 deletions(-)
fs/bcachefs/bset.c +4 -30
index 43b40f6b8c0a..0ccc1d962428 100644
@@ -304,11 +304,6 @@ struct bkey_float {
 };
 #define BKEY_MANTISSA_BITS	16
 
-static unsigned bkey_float_byte_offset(unsigned idx)
-{
-	return idx * sizeof(struct bkey_float);
-}
-
 struct ro_aux_tree {
 	u8			nothing[0];
 	struct bkey_float	f[];
@@ -328,8 +323,7 @@ static unsigned bset_aux_tree_buf_end(const struct bset_tree *t)
 		return t->aux_data_offset;
 	case BSET_RO_AUX_TREE:
 		return t->aux_data_offset +
-			DIV_ROUND_UP(t->size * sizeof(struct bkey_float) +
-				     t->size * sizeof(u8), 8);
+			DIV_ROUND_UP(t->size * sizeof(struct bkey_float), 8);
 	case BSET_RW_AUX_TREE:
 		return t->aux_data_offset +
 			DIV_ROUND_UP(sizeof(struct rw_aux_tree) * t->size, 8);
@@ -360,14 +354,6 @@ static struct ro_aux_tree *ro_aux_tree_base(const struct btree *b,
 	return __aux_tree_base(b, t);
 }
 
-static u8 *ro_aux_tree_prev(const struct btree *b,
-			    const struct bset_tree *t)
-{
-	EBUG_ON(bset_aux_tree_type(t) != BSET_RO_AUX_TREE);
-
-	return __aux_tree_base(b, t) + bkey_float_byte_offset(t->size);
-}
-
 static struct bkey_float *bkey_float(const struct btree *b,
 				     const struct bset_tree *t,
 				     unsigned idx)
@@ -479,15 +465,6 @@ static inline struct bkey_packed *tree_to_bkey(const struct btree *b,
 			bkey_float(b, t, j)->key_offset);
 }
 
-static struct bkey_packed *tree_to_prev_bkey(const struct btree *b,
-					     const struct bset_tree *t,
-					     unsigned j)
-{
-	unsigned prev_u64s = ro_aux_tree_prev(b, t)[j];
-
-	return (void *) ((u64 *) tree_to_bkey(b, t, j)->_data - prev_u64s);
-}
-
 static struct rw_aux_tree *rw_aux_tree(const struct btree *b,
 				       const struct bset_tree *t)
 {
@@ -689,8 +666,7 @@ static unsigned __bset_tree_capacity(struct btree *b, const struct bset_tree *t)
 
 static unsigned bset_ro_tree_capacity(struct btree *b, const struct bset_tree *t)
 {
-	return __bset_tree_capacity(b, t) /
-		(sizeof(struct bkey_float) + sizeof(u8));
+	return __bset_tree_capacity(b, t) / sizeof(struct bkey_float);
 }
 
 static unsigned bset_rw_tree_capacity(struct btree *b, const struct bset_tree *t)
@@ -719,7 +695,7 @@ static noinline void __build_rw_aux_tree(struct btree *b, struct bset_tree *t)
 
 static noinline void __build_ro_aux_tree(struct btree *b, struct bset_tree *t)
 {
-	struct bkey_packed *prev = NULL, *k = btree_bkey_first(b, t);
+	struct bkey_packed *k = btree_bkey_first(b, t);
 	struct bkey_i min_key, max_key;
 	unsigned cacheline = 1;
 
@@ -737,7 +713,7 @@ static noinline void __build_ro_aux_tree(struct btree *b, struct bset_tree *t)
 	/* First we figure out where the first key in each cacheline is */
 	eytzinger1_for_each(j, t->size - 1) {
 		while (bkey_to_cacheline(b, t, k) < cacheline)
-			prev = k, k = bkey_p_next(k);
+			k = bkey_p_next(k);
 
 		if (k >= btree_bkey_last(b, t)) {
 			/* XXX: this path sucks */
@@ -745,11 +721,9 @@ static noinline void __build_ro_aux_tree(struct btree *b, struct bset_tree *t)
 			goto retry;
 		}
 
-		ro_aux_tree_prev(b, t)[j] = prev->u64s;
 		bkey_float(b, t, j)->key_offset =
 			bkey_to_cacheline_offset(b, t, cacheline++, k);
 
-		EBUG_ON(tree_to_prev_bkey(b, t, j) != prev);
 		EBUG_ON(tree_to_bkey(b, t, j) != k);
 	}
 
Signature · 1 line
2.45.2
#3 lore raw
In reply to Alan Huang
Quoted 13 lines · Alan Huang

Hi,

Changes in v2:
- In v1, bset_aux_tree_buf_end still includes the size of the prev array when calculating the buffer end, v2 removes it.

This series minimize the search range used to calculate the mantissa, so that the mantissa can have more meaningful bits which reduces the slow path comparison when search a key.

The prev array stuff becomes useless after minimizing the search range, so this series also removes the prev array stuff.

Quoted 6 lines

Alan Huang (2):
bcachefs: Minimize the search range used to calculate the mantissa
bcachefs: Remove the prev array stuff

 fs/bcachefs/bset.c | 36 +++++-------------------------------
 1 file changed, 5 insertions(+), 31 deletions(-)

Nice - tests pass, applied