[Sheepdog] [PATCH 2/2] use binary search in hval_to_sheep()

[Liu Yuan]

On 05/14/2012 12:12 PM, levin li wrote:

> As we know, binary search is much faster than sequential search,
> we can use binary search to make hval_to_sheep() faster.
> 
> Signed-off-by: levin li <xingke.lwp at taobao.com>
> ---
>  include/sheep.h |   57 +++++++++++++++++++++++++++++++++++++++++--------------
>  1 file changed, 43 insertions(+), 14 deletions(-)
> 
> diff --git a/include/sheep.h b/include/sheep.h
> index 4fd05f7..e280862 100644
> --- a/include/sheep.h
> +++ b/include/sheep.h
> @@ -228,15 +228,29 @@ next:
>  static inline int hval_to_sheep(struct sd_vnode *entries,
>  				int nr_entries, uint64_t id, int idx)
>  {
> -	int i;
> -	struct sd_vnode *e = entries, *n;
> +	int start, end, pos;
> +
> +	start = 0;
> +	end = nr_entries - 1;
>  
> -	for (i = 0; i < nr_entries - 1; i++, e++) {
> -		n = e + 1;
> -		if (id > e->id && id <= n->id)
> -			break;
> +	if (id > entries[end].id) {
> +		pos = end;
> +		goto found;
>  	}
> -	return get_nth_node(entries, nr_entries, (i + 1) % nr_entries, idx);
> +
> +again:
> +	pos = (end - start) / 2 + start;
> +
> +	if (entries[pos].id < id) {
> +		if (entries[pos + 1].id >= id)
> +			goto found;
> +		start = pos;
> +	} else
> +		end = pos;
> +	goto again;
> +
> +found:
> +	return get_nth_node(entries, nr_entries, (pos + 1) % nr_entries, idx);
>  }
>  
>  static inline int obj_to_sheep(struct sd_vnode *entries,
> @@ -250,17 +264,32 @@ static inline int obj_to_sheep(struct sd_vnode *entries,
>  static inline void hval_to_sheeps(struct sd_vnode *entries,
>  			int nr_entries, uint64_t id, int nr_copies, int *idxs)
>  {
> -	int i, idx;
> -	struct sd_vnode *e = entries, *n;
> +	int start, end, pos, idx;
>  
> -	for (i = 0; i < nr_entries - 1; i++, e++) {
> -		n = e + 1;
> -		if (id > e->id && id <= n->id)
> -			break;
> +	start = 0;
> +	end = nr_entries - 1;
> +
> +	if (id > entries[end].id) {
> +		pos = end;
> +		goto found;
>  	}
> +
> +again:
> +	pos = (end - start) / 2 + start;
> +
> +	if (entries[pos].id < id) {
> +		if (entries[pos + 1].id >= id)
> +			goto found;
> +		start = pos;
> +	} else
> +		end = pos;
> +	dprintf("BINARY start %d, pos %d, end %d\n", start, pos, end);
> +	goto again;
> +
> +found:
>  	for (idx = 0; idx < nr_copies; idx++)
>  		idxs[idx] = get_nth_node(entries, nr_entries,
> -				(i + 1) % nr_entries, idx);
> +				(pos + 1) % nr_entries, idx);
>  }
>  
>  static inline void obj_to_sheeps(struct sd_vnode *entries,


Use a inline helper for binary search would be better.

Thanks,
Yuan