Fast binary search - replacing stl::equal_range()

[Ole Nielsby]

My app (an interpreter for a homebrew language) does lots of
binary searches on sorted arrays of unique keys, for looking up
variables and methods.

Till now I used std::equal_range() for the searching.

I just replaced it with a homebrew binary search which
gave about 3% overall performance improvement of
my interpreter (VC9 release build, using a "real" app
as benchmark).

I figure it's because std::equal_range needs to widen the
range in both directions when a hit is found.

But it feels like I've reinventing the wheel. So I wonder if
there is a standard function I have overlooked?

Stl has a binary_search() algorithm that tests for existence
but it doesn't return the position so it's not of any use.

There is also a standard C funciton bsearch() but it uses a
comparison function ptr, which is overkill for the fast and
simple pointer comparisons I use.

BTW my program compiles with VC9 and GCC but when
I tried compiling parts of it for Symbian I got errors for cases
like this:

===========code==============
#include <algorithm>
class A{};
class B : public A {public: B(){}};
int main(){
const B b;
const A *const aa[1] = {&b};
std::pair<const A*const*, const A*const*> range
= std::equal_range(&aa[0], &aa[1], &b);
}

==========/code===============

They are easily fixed by supplying template arguments:

std::equal_range<const A* const*, const A*>(&aa[0], &aa[1], &b);

I'm just curious to know if it's the Symbion compiler/stlport that is
flawed or GCC/VC happen to be permissive?

[Paavo Helde]

"Ole Nielsby" <ole.n...@tekare-you-spamminglogisk.dk> kirjutas:

> My app (an interpreter for a homebrew language) does lots of
> binary searches on sorted arrays of unique keys, for looking up
> variables and methods.
>
> Till now I used std::equal_range() for the searching.
>
> I just replaced it with a homebrew binary search which
> gave about 3% overall performance improvement of
> my interpreter (VC9 release build, using a "real" app
> as benchmark).

Have you considered std::lower_bound(), std::upper_bound()?

Aside from that, IMO a 3% performance increase would not justify replacing
standard library code with one's own.

Paavo

[Ole Nielsby]

Paavo Helde <pa...@nospam.please.ee> wrote:

> "Ole Nielsby" <ole.n...@tekare-you-spamminglogisk.dk> kirjutas:
>
>> My app (an interpreter for a homebrew language) does lots of
>> binary searches on sorted arrays of unique keys, for looking up
>> variables and methods.
>>
>> Till now I used std::equal_range() for the searching.
>>
>> I just replaced it with a homebrew binary search which
>> gave about 3% overall performance improvement of
>> my interpreter (VC9 release build, using a "real" app
>> as benchmark).
>
> Have you considered std::lower_bound(), std::upper_bound()?

Thanks - I wasn't aware of these. (Google didn't tell, or I
overlooked them.)

It seems std::lower_bound() is marginally faster than my own
binary search, so I'll stick to that.

> Aside from that, IMO a 3% performance increase would not
> justify replacing standard library code with one's own.

I wouldn't do this in an ordinary application - but I find it
worthwile to optimize the central parts of my interpreter
somewhat aggressively, for the same reasons that makes
compiler-writers fine-tune the code generation for marginal
gains: it affects not just a single application but every
application written in the language.