Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) client-ip=2620:137:e000::3:2;
MIME-Version: 1.0
References: <20230918210631.3882376-1-jbrennen@google.com> <CAK7LNASSgCFYequw+0zQpUC-9yLHvJLHZ97Ko1ejUYZVTkM81w@mail.gmail.com>
 <20230924222019.dipusbpgntepnq2y@google.com>
In-Reply-To: <20230924222019.dipusbpgntepnq2y@google.com>
From:   Masahiro Yamada <masahiroy@kernel.org>
Date:   Mon, 25 Sep 2023 23:24:11 +0900
Message-ID: <CAK7LNATg+cnvs9P5Ud6FPAoqQUozrGif5SJm+Pw7cs5qJ1C3gw@mail.gmail.com>
Subject: Re: [PATCH] modpost: Optimize symbol search from linear to binary search
To:     Fangrui Song <maskray@google.com>
Cc:     Jack Brennen <jbrennen@google.com>,
        Nathan Chancellor <nathan@kernel.org>,
        Nick Desaulniers <ndesaulniers@google.com>,
        Nicolas Schier <nicolas@fjasle.eu>, Tom Rix <trix@redhat.com>,
        linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org,
        llvm@lists.linux.dev
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Mon, Sep 25, 2023 at 7:20=E2=80=AFAM Fangrui Song <maskray@google.com> w=
rote:

> However, the `- 1` part in `unsigned int hi =3D elf->symsearch->table_siz=
e - 1;` can be improved.
> I'd prefer an implementation similar to typical C++ https://en.cppreferen=
ce.com/w/cpp/algorithm/upper_bound implementation.
>
> lo =3D 0;
> hi =3D n;  // or replace hi with count
> while (lo < hi) {
>    mid =3D (lo + hi) / 2;  // we don't care about (lo+hi) overflow
>    if (less_or_eq(&table[mid], &target))
>      lo =3D mid+1;
>    else
>      hi =3D mid;
> }
>
> // lo =3D=3D hi: the index of the first element that is > target
> // if elements equal to target are present, they are on the left of lo


Ah, it is much more elegant!

Thanks.


--=20
Best Regards
Masahiro Yamada