This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] stdlib-bsearch: middle element calculation may overflow
On Thu, Mar 30, 2017 at 12:59 AM, Sergey Senozhatsky
<sergey.senozhatsky.work@gmail.com> wrote:
>
> BTW, FreeBSD's kernel bsearch implementation is quite interesting
> and unique. take a look:
>
> https://github.com/freebsd/freebsd/blob/master/sys/libkern/bsearch.c
Oh, that's clever. I _thought_ there had to be a way to avoid the
addition. This should indeed be immune to the overflow problem,
although we still need to have a test for it.
libstdc++-v3 appears to use the same trick: see
https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/stl_algo.h;h=2cd5303a100b998f80369c0baf2cd39aedf14b52;hb=af44a97c14af3a0079590662d49a8ced98954376#l2037
(sorry for length of URL). So we can crib from that and not have to
worry about copyrights.
As long as we're microoptimizing, I found an article
<https://realm.io/news/how-we-beat-cpp-stl-binary-search/> which, in
essence, says that because the branches after the comparison are going
to be unpredictable, you really want to be using conditional moves
instead. It might be worth trying a little to convince GCC and LLVM
to do that. (It's too bad that there's no __builtin_unpredictable()
to go with __builtin_expect().)
zw