Re: [PATCH v3] Btrfs: optimize key searches in btrfs_search_slot

[Josef Bacik <jbacik@fusionio.com>]

On Thu, Aug 29, 2013 at 11:08:16AM -0700, Zach Brown wrote:
> On Thu, Aug 29, 2013 at 02:59:26PM +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.
> > 
> > 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
> 
> > 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
> 
> Where'd the giant increase in the range max come from?  Just jittery
> measurement?  Maybe get a lot more data points to smooth that out?
> 
> > +static int key_search(struct extent_buffer *b, struct btrfs_key *key,
> > +		      int level, int *prev_cmp, int *slot)
> > +{
> > +	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;
> > +	int err;
> > +
> > +	if (*prev_cmp != 0) {
> > +		*prev_cmp = bin_search(b, key, level, slot);
> > +		return *prev_cmp;
> > +	}
> 
> 
> > +	*slot = 0;
> > +
> > +	return 0;
> 
> So this is the actual work done by the function.
> 
> > +
> > +	if (level == 0)
> > +		offset = offsetof(struct btrfs_leaf, items);
> > +	else
> > +		offset = offsetof(struct btrfs_node, ptrs);
> 
> (+10 fragility points for assuming that the key starts each struct
> instead of using [0].key)
> 
> > +
> > +	err = map_private_extent_buffer(b, offset, sizeof(struct btrfs_disk_key),
> > +					&kaddr, &map_start, &map_len);
> > +	if (!err) {
> > +		k = (struct btrfs_disk_key *)(kaddr + offset - map_start);
> > +	} else {
> > +		read_extent_buffer(b, &unaligned, offset, sizeof(unaligned));
> > +		k = &unaligned;
> > +	}
> > +
> > +	ASSERT(comp_keys(k, key) == 0);
> 
> All of the rest of the function, including most of the local variables,
> is overhead for that assertion.  We don't actually care about the
> relative sorted key position of the two keys so we don't need smart
> field-aware comparisions.  We can use a dumb memcmp.
> 
> We can replace all that stuff with two easy memcmp_extent_buffers()
> which vanish if ASSERT is a nop. 
> 

Actually we can't since we have a cpu key and the keys in the eb are disk keys.
So maybe keep what we have here and wrap it completely in CONFIG_BTRFS_ASSERT?

Josef