Skip to contentSkip to conversation

lib: One less subtraction in binary search iterations.

PATCH Superseded Wedson Almeida Filho 5 participants 10 messages Jul 6, 2013 – Jul 15, 2013 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib: One less subtraction in binary search iterations.

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

---
 lib/bsearch.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/bsearch.c +1 -1
index e33c179..3264146 100644
@@ -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)
Signature · 1 line
1.7.9.5
#1 lore raw
Quoted 2 lines · 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).

Not correct.

lib/bsearch.c

Quoted 1 line
lib/bsearch.c +0 -0

[]

lib/bsearch.c void *bsearch(const void *key, const void *base, size_t num, size_t size, · line 40

Quoted 6 lines
lib/bsearch.c +1 -1
@@ -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;
#2 lore raw
Quoted 9 lines · Joe Perches

Not correct.

lib/bsearch.c void *bsearch(const void *key, const void *base, size_t num, size_t size, · line 40

Quoted 3 lines
      while (start < end) {
lib/bsearch.c +1 -1
-             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.

#3 lore raw
Quoted 13 lines · Wedson Almeida Filho
Quoted 9 lines · Joe Perches

Not correct.

lib/bsearch.c void *bsearch(const void *key, const void *base, size_t num, size_t size, · line 40

Quoted 3 lines
      while (start < end) {
lib/bsearch.c +1 -1
-             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.

Quoted 8 lines

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.

Quoted 2 lines

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.

#4 lore raw
Quoted 4 lines · Joe Perches
Quoted 2 lines

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.

Quoted 3 lines

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.

#5 lore raw

PATCH v2 1/1 lib: One less subtraction in binary search iterations.

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.

---
 lib/bsearch.c |    7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
lib/bsearch.c +6 -1
index e33c179..668ae6c 100644
@@ -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)
Signature · 1 line
1.7.9.5
#6 lore raw
Quoted 3 lines · 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.

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.

#7 lore raw
In reply to Wedson Almeida Filho
Quoted 13 lines · Wedson Almeida Filho
Quoted 9 lines · Joe Perches

Not correct.

lib/bsearch.c void *bsearch(const void *key, const void *base, size_t num, size_t size, · line 40

Quoted 3 lines
      while (start < end) {
lib/bsearch.c +1 -1
-             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.

Quoted 9 lines

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

#8 lore raw
Quoted 24 lines · Vineet Gupta
Quoted 13 lines · Wedson Almeida Filho
Quoted 9 lines · Joe Perches

Not correct.

lib/bsearch.c void *bsearch(const void *key, const void *base, size_t num, size_t size, · line 40

Quoted 3 lines
      while (start < end) {
lib/bsearch.c +1 -1
-             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.

Quoted 9 lines

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.

Quoted 4 lines

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?

#9 lore raw
In reply to Wedson Almeida Filho
Quoted 23 lines · 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).

---
 lib/bsearch.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/bsearch.c +1 -1
index e33c179..3264146 100644
@@ -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)
Signature · 1 line
1.7.9.5

Please add a comment about overflow instead?

Thanks,
Rusty.