On Thu, Aug 29, 2013 at 01:44:13PM +0100, Filipe David Borba Manana wrote: > 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 <fdman...@gmail.com> > --- > 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; > + } > + } > +
This confuses me, if we're at slot 0 we should be at the front of the first page, no matter what, so why not just read the first key and carry on? > + BUG_ON(comp_keys(k, key) != 0); Please use the ASSERT() macro. Thanks, Josef -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html