When the binary search returns 0 (exact match), the target key
will necessarily be at slot 0 of all nodes below the current one,
so in this case the binary search is not needed because it will
always return 0, and we waste time doing it, holding node locks
for longer than necessary, etc.
Below follow histograms with the times spent on the current approach of
doing a binary search when the previous binary search returned 0, and
times for the new approach, which directly picks the first item/child
node in the leaf/node.
Current approach:
Count: 5013
Range: 25.000 - 497.000; Mean: 82.767; Median: 64.000; Stddev: 49.972
Percentiles: 90th: 141.000; 95th: 182.000; 99th: 287.000
25.000 - 33.930: 211 ######
33.930 - 45.927: 277 ########
45.927 - 62.045: 1834 #####################################################
62.045 - 83.699: 1203 ###################################
83.699 - 112.789: 609 ##################
112.789 - 151.872: 450 #############
151.872 - 204.377: 246 #######
204.377 - 274.917: 124 ####
274.917 - 369.684: 48 #
369.684 - 497.000: 11 |
Approach proposed by this patch:
Count: 5013
Range: 10.000 - 8303.000; Mean: 28.505; Median: 18.000; Stddev: 119.147
Percentiles: 90th: 49.000; 95th: 74.000; 99th: 115.000
10.000 - 20.339: 3160 #####################################################
20.339 - 40.397: 1131 ###################
40.397 - 79.308: 507 #########
79.308 - 154.794: 199 ###
154.794 - 301.232: 14 |
301.232 - 585.313: 1 |
585.313 - 8303.000: 1 |
These samples were captured during a run of the btrfs tests 001, 002 and
004 in the xfstests, with a leaf/node size of 4Kb.
Signed-off-by: Filipe David Borba Manana <fdmanana@xxxxxxxxx>
---
fs/btrfs/ctree.c | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 59 insertions(+), 2 deletions(-)
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 5fa521b..5b20eec 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -2426,6 +2426,59 @@ done:
return ret;
}
+static int key_search(struct extent_buffer *b, struct btrfs_key *key,
+ int level, int *prev_cmp, int *slot)
+{
+ unsigned long eb_offset = 0;
+ unsigned long len_left = b->len;
+ char *kaddr = NULL;
+ unsigned long map_start = 0;
+ unsigned long map_len = 0;
+ unsigned long offset;
+ struct btrfs_disk_key *k = NULL;
+ struct btrfs_disk_key unaligned;
+
+ if (*prev_cmp != 0) {
+ *prev_cmp = bin_search(b, key, level, slot);
+ return *prev_cmp;
+ }
+
+ if (level == 0)
+ offset = offsetof(struct btrfs_leaf, items);
+ else
+ offset = offsetof(struct btrfs_node, ptrs);
+
+ /*
+ * Map the entire extent buffer, otherwise callers can't access
+ * all keys/items of the leaf/node. Specially needed for case
+ * where leaf/node size is greater than page cache size.
+ */
+ while (len_left > 0) {
+ unsigned long len = min(PAGE_CACHE_SIZE, len_left);
+ int err;
+
+ err = map_private_extent_buffer(b, eb_offset, len, &kaddr,
+ &map_start, &map_len);
+ len_left -= len;
+ eb_offset += len;
+ if (k)
+ continue;
+ if (!err) {
+ k = (struct btrfs_disk_key *)(kaddr + offset -
+ map_start);
+ } else {
+ read_extent_buffer(b, &unaligned,
+ offset, sizeof(unaligned));
+ k = &unaligned;
+ }
+ }
+
+ BUG_ON(comp_keys(k, key) != 0);
+ *slot = 0;
+
+ return 0;
+}
+
/*
* look for key in the tree. path is filled in with nodes along the way
* if key is found, we return zero and you can find the item in the leaf
@@ -2454,6 +2507,7 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
int write_lock_level = 0;
u8 lowest_level = 0;
int min_write_lock_level;
+ int prev_cmp;
lowest_level = p->lowest_level;
WARN_ON(lowest_level && ins_len > 0);
@@ -2484,6 +2538,7 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
min_write_lock_level = write_lock_level;
again:
+ prev_cmp = -1;
/*
* we try very hard to do read locks on the root
*/
@@ -2584,7 +2639,7 @@ cow_done:
if (!cow)
btrfs_unlock_up_safe(p, level + 1);
- ret = bin_search(b, key, level, &slot);
+ ret = key_search(b, key, level, &prev_cmp, &slot);
if (level != 0) {
int dec = 0;
@@ -2719,6 +2774,7 @@ int btrfs_search_old_slot(struct btrfs_root *root, struct btrfs_key *key,
int level;
int lowest_unlock = 1;
u8 lowest_level = 0;
+ int prev_cmp;
lowest_level = p->lowest_level;
WARN_ON(p->nodes[0] != NULL);
@@ -2729,6 +2785,7 @@ int btrfs_search_old_slot(struct btrfs_root *root, struct btrfs_key *key,
}
again:
+ prev_cmp = -1;
b = get_old_root(root, time_seq);
level = btrfs_header_level(b);
p->locks[level] = BTRFS_READ_LOCK;
@@ -2746,7 +2803,7 @@ again:
*/
btrfs_unlock_up_safe(p, level + 1);
- ret = bin_search(b, key, level, &slot);
+ ret = key_search(b, key, level, &prev_cmp, &slot);
if (level != 0) {
int dec = 0;
--
1.7.9.5
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
