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 <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;
> + }
> + }
> +
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 majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
