Re: [PATCH] modpost: Optimize symbol search from linear to binary search

[Masahiro Yamada]

On Mon, Sep 25, 2023 at 7:20 AM Fangrui Song <maskray@xxxxxxxxxx> wrote:

> However, the `- 1` part in `unsigned int hi = elf->symsearch->table_size - 1;` can be improved.
> I'd prefer an implementation similar to typical C++ https://en.cppreference.com/w/cpp/algorithm/upper_bound implementation.
>
> lo = 0;
> hi = n;  // or replace hi with count
> while (lo < hi) {
>    mid = (lo + hi) / 2;  // we don't care about (lo+hi) overflow
>    if (less_or_eq(&table[mid], &target))
>      lo = mid+1;
>    else
>      hi = mid;
> }
>
> // lo == 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.



-- 
Best Regards
Masahiro Yamada