[PATCH] lib: One less subtraction in binary search iterations.

[PATCH] lib: One less subtraction in binary search iterations.

[Wedson Almeida Filho]

There is no functional change, but this change eliminates a subtraction that
the compiler doesn't optimize out (as of gcc 4.7.3).

Signed-off-by: Wedson Almeida Filho <wedsonaf@gmail.com>
---
 lib/bsearch.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/bsearch.c b/lib/bsearch.c
index e33c179..3264146 100644
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -37,7 +37,7 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	int result;
 
 	while (start < end) {
-		size_t mid = start + (end - start) / 2;
+		size_t mid = (start + end) / 2;
 
 		result = cmp(key, base + mid * size);
 		if (result < 0)
-- 
1.7.9.5

Re: [PATCH] lib: One less subtraction in binary search iterations.

[Joe Perches]

On Sat, 2013-07-06 at 16:07 -0700, Wedson Almeida Filho wrote:
> There is no functional change, but this change eliminates a subtraction that
> the compiler doesn't optimize out (as of gcc 4.7.3).

Not correct.

> diff --git a/lib/bsearch.c b/lib/bsearch.c
[]
> @@ -37,7 +37,7 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
>  	int result;
>  
>  	while (start < end) {
> -		size_t mid = start + (end - start) / 2;
> +		size_t mid = (start + end) / 2;

	size_t start = 0x80000000;
	size_t end   = 0x80000001;

Re: [PATCH] lib: One less subtraction in binary search iterations.

[Wedson Almeida Filho]

On Sat, Jul 6, 2013 at 9:59 PM, Joe Perches <joe@perches.com> wrote:
>
> Not correct.
>
>>       while (start < end) {
>> -             size_t mid = start + (end - start) / 2;
>> +             size_t mid = (start + end) / 2;
>
>         size_t start = 0x80000000;
>         size_t end   = 0x80000001;

Good point, they aren't equivalent in all cases.

For the overflow to happen though, we need an array with at least
N/2+1 entries, where N is the address space size. The array wouldn't
fit in addressable memory if the element size is greater than 1, so
this can only really happen when the element size is 1. Even then, it
would require the kernel range to be greater than half of all
addressable memory, and allow an allocation taking that much memory. I
don't know all architectures where linux runs, but I don't think such
configuration is likely to exist.

Re: [PATCH] lib: One less subtraction in binary search iterations.

[Joe Perches]

On Mon, 2013-07-08 at 20:51 -0700, Wedson Almeida Filho wrote:
> On Sat, Jul 6, 2013 at 9:59 PM, Joe Perches <joe@perches.com> wrote:
> >
> > Not correct.
> >
> >>       while (start < end) {
> >> -             size_t mid = start + (end - start) / 2;
> >> +             size_t mid = (start + end) / 2;
> >
> >         size_t start = 0x80000000;
> >         size_t end   = 0x80000001;
> 
> Good point, they aren't equivalent in all cases.
> 
> For the overflow to happen though, we need an array with at least
> N/2+1 entries, where N is the address space size. The array wouldn't
> fit in addressable memory if the element size is greater than 1, so
> this can only really happen when the element size is 1. Even then, it
> would require the kernel range to be greater than half of all
> addressable memory, and allow an allocation taking that much memory. I
> don't know all architectures where linux runs, but I don't think such
> configuration is likely to exist.

Nor do I but that wasn't what you wrote.

> There is no functional change, but this change eliminates a subtraction that
> the compiler doesn't optimize out (as of gcc 4.7.3).

That's flatly incorrect.

I don't mind if you change it, for just the reason
you wrote, but you still have to now say under what
conditions the test works and when it doesn't.

Re: [PATCH] lib: One less subtraction in binary search iterations.

[Wedson Almeida Filho]

On Mon, Jul 8, 2013 at 9:12 PM, Joe Perches <joe@perches.com> wrote:
>> There is no functional change, but this change eliminates a subtraction that
>> the compiler doesn't optimize out (as of gcc 4.7.3).
>
> That's flatly incorrect.

I'm not arguing this. I in fact already acknowledged that the
statement is incorrect.

> I don't mind if you change it, for just the reason
> you wrote, but you still have to now say under what
> conditions the test works and when it doesn't.

Yes, I'll update and respin the patch as also suggested by Rusty.

Thanks for the review.

[PATCH v2] lib: One less subtraction in binary search iterations.

[Wedson Almeida Filho]

The subtraction is removed at the expense of generality: when the element size
is 1, the array length cannot exceed half the architecture's addressable
memory.

Signed-off-by: Wedson Almeida Filho <wedsonaf@gmail.com>
---
 lib/bsearch.c |    7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/lib/bsearch.c b/lib/bsearch.c
index e33c179..668ae6c 100644
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -24,6 +24,11 @@
  * contents of the array should already be in ascending sorted order
  * under the provided comparison function.
  *
+ * There is a limitation when @size is 1: in this case @num must be at
+ * most SIZE_MAX / 2; that is, the number of elements in the sorted
+ * array must be at most half the maximum number expressible as a size_t
+ * to avoid overflows.
+ *
  * Note that the key need not have the same type as the elements in
  * the array, e.g. key could be a string and the comparison function
  * could compare the string with the struct's name field.  However, if
@@ -37,7 +42,7 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	int result;
 
 	while (start < end) {
-		size_t mid = start + (end - start) / 2;
+		size_t mid = (start + end) / 2;
 
 		result = cmp(key, base + mid * size);
 		if (result < 0)
-- 
1.7.9.5

Re: [PATCH v2] lib: One less subtraction in binary search iterations.

[Rusty Russell]

Wedson Almeida Filho <wedsonaf@gmail.com> writes:
> The subtraction is removed at the expense of generality: when the element size
> is 1, the array length cannot exceed half the architecture's addressable
> memory.

People do copy code, so I prefer to set the best example possible.

Unless it's a useful optimization, I think it should stay the way it is.

Cheers,
Rusty.

Re: [PATCH] lib: One less subtraction in binary search iterations.

[Vineet Gupta]

On 07/09/2013 09:21 AM, Wedson Almeida Filho wrote:
> On Sat, Jul 6, 2013 at 9:59 PM, Joe Perches <joe@perches.com> wrote:
>>
>> Not correct.
>>
>>>       while (start < end) {
>>> -             size_t mid = start + (end - start) / 2;
>>> +             size_t mid = (start + end) / 2;
>>
>>         size_t start = 0x80000000;
>>         size_t end   = 0x80000001;
> 
> Good point, they aren't equivalent in all cases.
> 
> For the overflow to happen though, we need an array with at least
> N/2+1 entries, where N is the address space size. The array wouldn't
> fit in addressable memory if the element size is greater than 1, so
> this can only really happen when the element size is 1. Even then, it
> would require the kernel range to be greater than half of all
> addressable memory, and allow an allocation taking that much memory. I
> don't know all architectures where linux runs, but I don't think such
> configuration is likely to exist.
> 

It does. In ARC port (arch/arc), the untranslated address space starts at
0x8000_0000 and this is where kernel is linked at. So all ARC kernel addresses
(code/data) lie in that range. This means you don't need special corner case for
this trip on ARC - it will break rightaway - unless I'm missing something.

P.S. Sorry for not replying earlier than ur v2.

-Vineet

Re: [PATCH] lib: One less subtraction in binary search iterations.

[Mikael Pettersson]

Vineet Gupta writes:
 > On 07/09/2013 09:21 AM, Wedson Almeida Filho wrote:
 > > On Sat, Jul 6, 2013 at 9:59 PM, Joe Perches <joe@perches.com> wrote:
 > >>
 > >> Not correct.
 > >>
 > >>>       while (start < end) {
 > >>> -             size_t mid = start + (end - start) / 2;
 > >>> +             size_t mid = (start + end) / 2;
 > >>
 > >>         size_t start = 0x80000000;
 > >>         size_t end   = 0x80000001;
 > > 
 > > Good point, they aren't equivalent in all cases.
 > > 
 > > For the overflow to happen though, we need an array with at least
 > > N/2+1 entries, where N is the address space size. The array wouldn't
 > > fit in addressable memory if the element size is greater than 1, so
 > > this can only really happen when the element size is 1. Even then, it
 > > would require the kernel range to be greater than half of all
 > > addressable memory, and allow an allocation taking that much memory. I
 > > don't know all architectures where linux runs, but I don't think such
 > > configuration is likely to exist.
 > > 
 > 
 > It does. In ARC port (arch/arc), the untranslated address space starts at
 > 0x8000_0000 and this is where kernel is linked at. So all ARC kernel addresses
 > (code/data) lie in that range. This means you don't need special corner case for
 > this trip on ARC - it will break rightaway - unless I'm missing something.

start and end aren't addresses but array indices relative to 'base'.
So even on ARC you should be safe, as long as no array has SIZE_MAX/2
or more elements.

I'm however far from convinced this micro-optimization is worth the
obvious source code quality reduction.  Surely the eliminated subtraction
is in the noise compared to the multiplies, indirect function calls,
and memory dereferences (in the cmp functions)?

It should be possible to eliminate the multiplies, since no array can
cross the -1/0 address boundary.  But even that is questionable: does
anyone have perf data showing that bsearch performance is a problem?

Re: [PATCH] lib: One less subtraction in binary search iterations.

[Rusty Russell]

Wedson Almeida Filho <wedsonaf@gmail.com> writes:
> There is no functional change, but this change eliminates a subtraction that
> the compiler doesn't optimize out (as of gcc 4.7.3).
>
> Signed-off-by: Wedson Almeida Filho <wedsonaf@gmail.com>
> ---
>  lib/bsearch.c |    2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/lib/bsearch.c b/lib/bsearch.c
> index e33c179..3264146 100644
> --- a/lib/bsearch.c
> +++ b/lib/bsearch.c
> @@ -37,7 +37,7 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
>  	int result;
>  
>  	while (start < end) {
> -		size_t mid = start + (end - start) / 2;
> +		size_t mid = (start + end) / 2;
>  
>  		result = cmp(key, base + mid * size);
>  		if (result < 0)
> -- 
> 1.7.9.5

Please add a comment about overflow instead?

Thanks,
Rusty.