Re: Optimisation of std::binary_search of the <algorithm> header

[jay pokarna <jay dot pokarna10 at gmail dot com>]

Respected Sir,
                          I am sorry , for the use of wrong language
in the previous mail. I wanted to convey that c++ has generalised the
algorithm on various data structures , which is not required due to
low performance.

Could you give me the contact of the standard committee?

Regards,
Jay Pokarna

On Mon, May 29, 2017 at 1:13 PM, Tim Song <t.canens.cpp@gmail.com> wrote:
> I'm not sure if you forgot to CC the lists or intended to direct the
> email to me alone.
>
> On Mon, May 29, 2017 at 2:41 AM, jay pokarna <jay.pokarna10@gmail.com> wrote:
>> I know that cpp wants to generalise its methods so that they can be
>> used with various data structures. But the cost of generalisation is
>> that we have to compromise a lot on performance.
>
> That's neither here nor there. binary_search's performance as applied
> to forward iterators has nothing to do with its performance as to
> random access iterators.
>
>> I would like to recommend cpp to allow the use of binary_search only
>> on data structures that use random access models.
>
> C++ has an international standard and GCC/libstdc++ is an
> implementation of that standard. Proposal for changes to the standard
> should be directed to the standards committee, not GCC's mailing
> lists.
>
>> The technique that I have used is square root decomposition . I think
>> that it will be better than the one that is implemented.
>
> And here's the problem: you *think* it will be better. Just thinking
> is not enough. You need to *prove* it with benchmarks that show that
> your technique is in fact faster than the current one.
>
> If there is in fact substantial improvement, *then* it's the time to
> consider generalization: when is this technique faster than the stock
> one? Always? Only random access? Only pointers? Only built-in types?
> Again, this needs to be shown with appropriate benchmark numbers.
>
> Then, finally, you can write a patch proposing that libstdc++'s
> binary_search be modified to use this technique in situations when
> it's shown to be faster.
>
> For a recent example of how something like this should look like, see
> https://gcc.gnu.org/ml/libstdc++/2016-12/msg00051.html and its
> LLVM/libc++ counterpart, https://reviews.llvm.org/D27068. Note the
> copious benchmark numbers showing that the proposed change was indeed
> (much) better than the previous.



-- 
Regards,
Jay Pokarna
CS Sophomore
Wordpress | Linkedin
Birla Institute of Technology and Science, Pilani
Pilani Campus
Rajasthan - 333031.