Re: [PATCH 4/4] gdb: change regcache list to be a map

Simon Marchi
2020-07-30T16:58:21Z

On 2020-07-23 9:53 p.m., Pedro Alves wrote:
> On 7/20/20 9:41 PM, Simon Marchi via Gdb-patches wrote:
>> One regcache object is created for each stopped thread and is stored in
>> the regcache::regcaches linked list. Looking up a regcache for a given
>> thread is therefore in O(number of threads). Stopping all threads then
>> becomes O((number of threads) ^ 2). It becomes noticeable when
>> debugging thousands of threads, which is typical with GPU targets. This
>> patch replaces the linked list with an std::unordered_multimap, indexed
>> by (target, ptid).
>>
>> I originally designed it using an std::unordered_map with (target, ptid,
>> arch) as the key, because that's how lookups are done (in
>> get_thread_arch_aspace_regcache). However, the registers_changed_ptid
>> function, also somewhat on the hot path (it is used when resuming
>> threads), needs to delete all regcaches associated to a given (target,
>> ptid) tuple. Using (target, ptid) as a key allows to do this more
>> efficiently (see exception below). If the key of the map was (target,
>> ptid, arch), we'd have to walk all items of the map.
>>
>> The lookup (in get_thread_arch_aspace_regcache), walks over all existing
>> regcaches belonging to this (target, ptid), looking to find the one with
>> the right arch. This is ok, as there will be very few regcaches for a
>> given key (typically one). Lookups become faster when the number of
>> threads grows, compared to the linked list. With a small number of
>> threads, it will probably be a bit slower to do a map lookup than to
>> walk a few linked list nodes, but I don't think it will be noticeable in
>> practice.
>>
>> The function registers_changed_ptid deletes all regcaches related to a
>> given (target, ptid). We must now handle the different cases
>> separately:
>>
>> - NULL target and minus_one_ptid: we delete all the entries
>> - NULL target and non-minus_one_ptid: invalid (checked by assert)
>> - non-NULL target and non-minus_one_ptid: we delete all the entries
>> associated to that tuple, this is done efficiently
>> - a non-NULL target and minus_one_ptid: we delete all the entries
>> associated to that target, whatever the ptid. This is the slightly
>> annoying case, as we can't easily look up all items having this target
>> in their key. I implemented it by walking the list, which is not
>> ideal.
>
> Given the last case, did you consider using a two-level map instead?
>
> using ptid_regcache_map
> = std::unordered_multimap<ptid_t, regcache *>;
>
> using target_ptid_regcache_map
> = std::unordered_map<process_stratum_target *, ptid_regcache_map>;
>
> static target_ptid_regcache_map regcaches;
>
> The result for registers_changed_ptid would be:
>
> - NULL target and minus_one_ptid: we delete all the REGCACHES entries,
>
> - NULL target and non-minus_one_ptid: invalid (checked by assert)
>
> - non-NULL target and non-minus_one_ptid: we lookup the target
> in REGCACHES, and then delete all the entries in that map
> associated to that ptid.
>
> - a non-NULL target and minus_one_ptid: we delete the map entry
> in REGCACHES associated to that target.

I thought about it early on, but dismissed it thinking it would be too heavy
for nothing, having a map of maps. But I didn't think it would help that last
case, that might be a good reason to go with that.

> Looking up a regcache does two map lookups instead of one, but
> that is 2x amortized O(1), so should be a constant hit.
>
> I gave this a try, to see how feasible it would be. See attached
> patches on top of yours (the first two address comments I'll make below).
> I've also put these in the users/palves/regcache-map branch on
> sourceware.org.

Thanks, I'll run with that.

> I did not run performance tests, though. It may be that in
> registers_changed_ptid, it would be more efficient to
> not clear the first level map entry for a given target (i.e.,
> destroy the second level map object completely), but instead
> clear the second level map entry. I.e., avoid destroying the
> unordered_multimap for a given target, only to recreate it soon
> enough. But I kept it simple in case that isn't noticeable.

Will try.

> A similar two-level data structure would be to put an instance of:
>
> using ptid_regcache_map
> = std::unordered_multimap<ptid_t, regcache *>;
>
> in process_stratum_target directly.
>
> IOW, target-connection.c:process_targets has a list of open targets,
> which could be used to walk over all targets in the
> "NULL target and minus_one_ptid" scenario.

Ok, that would be an extra step, I suggest we keep it in mind for a subsequent
refactor.

>> The function regcache_thread_ptid_changed is called when a thread
>> changes ptid. It is implemented efficiently using the map, although
>> that's not very important: it is not called often, mostly when creating
>> an inferior, on some specific platforms.
>>
>> Note: In hash_target_ptid, I am combining hash values from std::hash by
>> summing them. I don't think it's ideal, since std::hash is just the
>> identity function for base types. But I don't know what would be better
>> to reduce the change of collisions. If anybody has a better idea, I'd
>> be interested.
>
> I'd maybe look in some kernel sources, e.g., Linux or BSD, what they
> use as hash function for pids.

Ok.

>> +/* Hash function for target_ptid. */
>> +
>> +struct hash_target_ptid
>> +{
>> + size_t operator() (const target_ptid &val) const
>> + {
>> + std::hash<long> h_long;
>> + hash_ptid h_ptid;
>> +
>> + return h_long ((long) val.target) + h_ptid (val.ptid);
>
> Note that on 64-bit Windows, long is 32-bit, so pointers don't
> fit. It just means you're only hashing half the bits.
> I wonder whether using libiberty's htab_hash_pointer would be
> a good idea here.

Huh, I did that because there's no std::hash overload for uintptr_t. But
I just saw there is:

template< class T > struct hash<T*>;

which seems to be for hashing pointers. It is implemented as:

return reinterpret_cast<size_t>(__p);

So I'll just use that. Otherwise, htab_hash_pointer would be good too.

>> @@ -417,10 +458,25 @@ static void
>> regcache_thread_ptid_changed (process_stratum_target *target,
>> ptid_t old_ptid, ptid_t new_ptid)
>> {
>> - for (auto &regcache : regcaches)
>> + /* Find all the regcaches to updates. */
>
> typo: to update.

Fixed.
>> + std::vector<regcache *> regcaches_to_update;
>> + target_ptid old_key (target, old_ptid);
>> + auto range = regcaches.equal_range (old_key);
>> + for (auto it = range.first; it != range.second; it++)
>> + regcaches_to_update.push_back (it->second);
>> +
>> + /* Remove all entries associated to OLD_KEY. We could have erased the items
>> + in the previous `for`, but it is only safe to erase items while iterating
>> + starting with C++14. */
>> + regcaches.erase (old_key);
>
> I don't think that's really true in practice. The idiom used pretty
> much by everyone is:
>
> for (auto it = range.first; it != range.second;)
> {
> regcaches_to_update.push_back (it->second);
> it = regcaches.erase (it);
> }
>
> Note that even the resolution of the C++ issue at:
>
> https://wg21.cmeerw.net/lwg/issue2356
>
> says:
>
> "not that any actual implementation does that, anyway"
>
> There's no need to be super pedantic wrt to an issue
> that no compiler is going to miscompile.

Ok, didn't know about that.

> See here as well:
> https://stackoverflow.com/questions/25047241/c11-is-it-safe-to-remove-individual-elements-from-stdunordered-map-while-it
>
> And then, given we know that there are no entries for
> new_ptid in the map, I think we could instead do it all in
> one iteration, like:
>
> target_ptid old_key (target, old_ptid);
> target_ptid new_key (target, new_ptid);
>
> auto range = regcaches.equal_range (old_key);
> for (auto it = range.first; it != range.second;)
> {
> regcache *rc = it->second;
> rc->set_ptid (new_ptid);
>
> /* Remove old before inserting new, to avoid rehashing, which
> would invalidate iterators. */
> it = regcaches.erase (it);
> regcaches.insert (std::make_pair (new_key, rc));
> }

Thanks, I used this.

>> +
>> + /* Update the regcaches' ptid, insert them back in the map with an updated
>> + key. */
>> + target_ptid new_key (target, new_ptid);
>> + for (regcache *rc : regcaches_to_update)
>> {
>> - if (regcache->ptid () == old_ptid && regcache->target () == target)
>> - regcache->set_ptid (new_ptid);
>> + rc->set_ptid (new_ptid);
>> + regcaches.insert (std::make_pair (new_key, rc));
>> }
>> }
>>
>> @@ -438,19 +494,53 @@ regcache_thread_ptid_changed (process_stratum_target *target,
>> void
>> registers_changed_ptid (process_stratum_target *target, ptid_t ptid)
>> {
>> - for (auto oit = regcaches.before_begin (), it = std::next (oit);
>> - it != regcaches.end (); )
>> + if (target == nullptr)
>> {
>> - struct regcache *regcache = *it;
>> - if ((target == nullptr || regcache->target () == target)
>> - && regcache->ptid ().matches (ptid))
>> - {
>> - delete regcache;
>> - it = regcaches.erase_after (oit);
>> - }
>> - else
>> - oit = it++;
>> + /* Since there can be ptid clashes between targets, it's not valid to
>> + pass a ptid without saying to which target it belongs. */
>> + gdb_assert (ptid == minus_one_ptid);
>> +
>> + /* Delete all the regcaches. */
>> + for (auto pair : regcaches)
>> + delete pair.second;
>
> We could store a std::unique_ptr<regcache> in the map instead
> to avoid all these manual deletes.

Indeed, I'll do that.

>> +
>> + regcaches.clear ();
>> }
>> + else if (ptid != minus_one_ptid)
>> + {
>> + /* Non-NULL target and non-minus_one_ptid, delete all regcaches belonging
>> + to this (TARGET, PTID). */
>> + target_ptid key (target, ptid);
>> + auto range = regcaches.equal_range (key);
>> + for (auto it = range.first; it != range.second; it++)
>> + delete it->second;
>
> Like this one.

Done.

>> +
>> + regcaches.erase (key);
>
> Here as well could do:
>
> for (auto it = range.first; it != range.second;)
> {
> delete it->second;
> it = regcaches.erase (it);
> }

With the unique_ptr, it's now just:

regcaches.erase (target_ptid (target, ptid));

>> + }
>> + else
>> + {
>> + /* Non-NULL target and minus_one_ptid, delete all regcaches associated
>> + to this target.
>> +
>> + We unfortunately don't have an efficient way to do this. Fall back
>> + to iterating all items to find all those belonging to TARGET.
>> +
>> + Note that in C++11, it's not safe to erase map entries while
>> + iterating, so we keep track of them and delete them at the end. */
>
> Here as well.

It's down to:

for (auto it = regcaches.begin (); it != regcaches.end ();)
{
if (it->second->target () == target)
it = regcaches.erase (it);
else
it++;
}

Thanks for the comments. I'll try the multi-level map thing and come back with
another version.

Simon