lib: One less subtraction in binary search iterations.
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
@@ -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
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;
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.
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.
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.
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
@@ -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
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.
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
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?
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).
Signed-off-by Wedson Almeida Filho <[email protected]>--- lib/bsearch.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)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 ; 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.