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@xxxxxxxxxxx> 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?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/