• Faster lower_bound / upper_bound

    From Bonita Montero@Bonita.Montero@gmail.com to comp.lang.c++ on Mon Nov 2 10:24:16 2026
    From Newsgroup: comp.lang.c++

    I wondered why lower_bound and upper_bound are almost twice as fast
    with clang-cl than with MSVC. I inspected the code and MSVC didn't
    use conditional moves (see below) and the non-predictible branches
    did really hurt.
    So I wrote two generic functions which do the same and make it easier
    for MSVC to do the optimization. And it worked: The MSVC-code is only
    slightly slower than the clang-cl-code with that.

    #pragma once
    #include <type_traits>
    #include <functional>

    template<typename Iterator, typename Ref, typename Cmp = std::less<std::iter_value_t<Iterator>>>
    inline Iterator xlower_bound( Iterator begin, Iterator end, const Ref
    &value, Cmp cmp = Cmp() )
    {
    for( size_t n = end - begin; n; )
    {
    size_t
    mid = n / 2,
    nRight = n - mid - 1;
    Iterator right = begin + mid + 1;
    bool less = cmp( begin[mid], value );
    begin = less ? right : begin;
    n = less ? nRight : mid;
    }
    return begin;
    }

    template<typename Iterator, typename Ref, typename Cmp = std::less<std::iter_value_t<Iterator>>>
    inline Iterator xupper_bound( Iterator begin, Iterator end, const Ref
    &value, Cmp cmp = Cmp() )
    {
    for( size_t n = end - begin; n; )
    {
    size_t
    mid = n / 2,
    nRight = n - mid - 1;
    Iterator right = begin + mid + 1;
    bool less = cmp( value, begin[mid] );
    begin = less ? begin : right;
    n = less ? mid : nRight;
    }
    return begin;
    }
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Oodini@svdbg@free.fr to comp.lang.c++ on Fri Nov 6 23:50:05 2026
    From Newsgroup: comp.lang.c++

    Le 02/11/2026 |a 10:24, Bonita Montero a |-crit-a:

    I wondered why lower_bound and upper_bound are almost twice as fast
    with clang-cl than with MSVC. I inspected the code and MSVC didn't
    use conditional moves (see below) and the non-predictible branches
    did really hurt.
    Which version of MSVC ?
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Bonita Montero@Bonita.Montero@gmail.com to comp.lang.c++ on Sat Nov 7 15:15:06 2026
    From Newsgroup: comp.lang.c++

    Am 06.11.2026 um 23:50 schrieb Oodini:

    Le 02/11/2026 |a 10:24, Bonita Montero a |-crit-a:

    I wondered why lower_bound and upper_bound are almost twice as fast
    with clang-cl than with MSVC. I inspected the code and MSVC didn't
    use conditional moves (see below) and the non-predictible branches
    did really hurt.

    Which version of MSVC ?

    19.51.36260

    --- Synchronet 3.22a-Linux NewsLink 1.2