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:air<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?

 

[Ole Nielsby]

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.