[2/2] gdb/dwarf: use std::equal_range in cooked_index_shard::find
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_gdb_build--master-aarch64 |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gdb_build--master-arm |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gdb_check--master-arm |
success
|
Test passed
|
| linaro-tcwg-bot/tcwg_gdb_check--master-aarch64 |
success
|
Test passed
|
Commit Message
From: Simon Marchi <simon.marchi@polymtl.ca>
Looking at `cooked_index_shard::find`, I thought that we could make a
small optimization: when finding the upper bound, we already know the
lower bound. And we know that the upper bound is >= the lower bound.
So we could pass `lower` as the first argument of the `std::upper_bound`
call to cut the part of the search space that is below `lower`.
It then occured to me that what we do is basically what
`std::equal_range` is for, so why not use it. Implementations of
`std::equal_range` are likely do to things as efficiently as possible.
Unfortunately, because `cooked_index_entry::compare` is sensitive to the
order of its parameters, we need to provide two different comparison
functions (just like we do know, to the lower_bound and upper_bound
calls). But I think that the use of equal_range makes it clear what the
intent of the code is.
Regression tested using the various DWARF target boards on Debian 12.
Change-Id: Idfad812fb9abae1b942d81ad9976aeed7c2cf762
---
gdb/dwarf2/cooked-index.c | 35 ++++++++++++++++++++---------------
1 file changed, 20 insertions(+), 15 deletions(-)
Comments
>>>>> "Simon" == simon marchi <simon.marchi@polymtl.ca> writes:
Simon> It then occured to me that what we do is basically what
Simon> `std::equal_range` is for, so why not use it. Implementations of
Simon> `std::equal_range` are likely do to things as efficiently as possible.
Thanks. I'm not sure I was aware of this algorithm.
It's a little scary to touch this code since it's required a reasonable
amount of debugging but OTOH it does seem good and I don't have a
specific reason to be afraid.
Approved-By: Tom Tromey <tom@tromey.com>
Simon> + auto [lower, upper]
[...]
Simon> return range (lower, upper);
I wonder if C++20 lets us get rid of this little
unpacking-and-repacking.
Tom
On 3/25/25 9:48 AM, Tom Tromey wrote:
>>>>>> "Simon" == simon marchi <simon.marchi@polymtl.ca> writes:
>
> Simon> It then occured to me that what we do is basically what
> Simon> `std::equal_range` is for, so why not use it. Implementations of
> Simon> `std::equal_range` are likely do to things as efficiently as possible.
>
> Thanks. I'm not sure I was aware of this algorithm.
> It's a little scary to touch this code since it's required a reasonable
> amount of debugging but OTOH it does seem good and I don't have a
> specific reason to be afraid.
What reassured me is that std::equal_range is defined to be equivalent
to:
make_pair(lower_bound(first, last, value, comp),
upper_bound(first, last, value, comp))
So the result should be equivalent, but the implementations are free to
implement it more efficiently than separate lower_bound/upper_bound
calls.
> Approved-By: Tom Tromey <tom@tromey.com>
Thanks, will push.
> Simon> + auto [lower, upper]
> [...]
> Simon> return range (lower, upper);
>
> I wonder if C++20 lets us get rid of this little
> unpacking-and-repacking.
I asked ChatGPT about it, we can do this:
return std::make_from_tuple<range>
(std::equal_range (m_entries.cbegin (), m_entries.cend (),
name.c_str (),
comparator { (completing
? cooked_index_entry::COMPLETE
: cooked_index_entry::MATCH) }));
I updated the patch to use it.
Simon
@@ -547,23 +547,28 @@ cooked_index_shard::finalize (const parent_map_map *parent_maps)
cooked_index_shard::range
cooked_index_shard::find (const std::string &name, bool completing) const
{
- cooked_index_entry::comparison_mode mode = (completing
- ? cooked_index_entry::COMPLETE
- : cooked_index_entry::MATCH);
-
- auto lower = std::lower_bound (m_entries.cbegin (), m_entries.cend (), name,
- [=] (const cooked_index_entry *entry,
- const std::string &n)
+ struct comparator
{
- return cooked_index_entry::compare (entry->canonical, n.c_str (), mode) < 0;
- });
+ cooked_index_entry::comparison_mode mode;
- auto upper = std::upper_bound (m_entries.cbegin (), m_entries.cend (), name,
- [=] (const std::string &n,
- const cooked_index_entry *entry)
- {
- return cooked_index_entry::compare (entry->canonical, n.c_str (), mode) > 0;
- });
+ bool operator() (const cooked_index_entry *entry,
+ const char *name) const noexcept
+ {
+ return cooked_index_entry::compare (entry->canonical, name, mode) < 0;
+ }
+
+ bool operator() (const char *name,
+ const cooked_index_entry *entry) const noexcept
+ {
+ return cooked_index_entry::compare (entry->canonical, name, mode) > 0;
+ }
+ };
+
+ auto [lower, upper]
+ = std::equal_range (m_entries.cbegin (), m_entries.cend (), name.c_str (),
+ comparator {(completing
+ ? cooked_index_entry::COMPLETE
+ : cooked_index_entry::MATCH)});
return range (lower, upper);
}