[lldb][NFCI] Remove n^2 loops and simplify iterator usage

[fdeazeve]

Summary

The code inside Broadcaster makes usage of iterators using olden C++ coding
style. Hidden in this old style is a couple of N^2 loops: we iterate over a map
(sequentially), removing the first element that matches some predicate. The
search is _always_ done from the start of the map, which implies that, if the
map has N elements and if all matches happen on the second half of the map, then
we visit the first N/2 elements exactly N/2 * N/2 times.

Ideally some of the code here would benefit from std::maps own "erase_if", but
this is only available with C++20:
https://en.cppreference.com/w/cpp/container/map/erase_if

We spent quite some time trying to make these loops more elegant, but it is
surprisingly tricky to do so.

[fdeazeve]

Update commit message

[fdeazeve]

Heavily inspired by @bulbazord's D150168

[fdeazeve]

lldb/source/Utility/Broadcaster.cpp

382

Oh, this should be == end

436

this should be == end

[mib]

lldb/source/Utility/Broadcaster.cpp

430–437

434–439

Would be nice to add a // TODO: use 'std::map::erase_if' when moving to c++20 comment

455–461

ditto

[fdeazeve]

lldb/source/Utility/Broadcaster.cpp

430–437

listener is a raw pointer, we shouldn't capture those by reference

[mib]

lldb/source/Utility/Broadcaster.cpp

430–437

I didn't pay attention, I thought it was a local variable. Good point!

[mib]

LGTM!

[bulbazord]

I like this. :)

lldb/source/Utility/Broadcaster.cpp

392

I don't think you need to actually capture the iterator here? std::map::erase doesn't invalidate existing iterators* (so begin and end are fine) and we redefine iter at the beginning of this loop.

*:https://en.cppreference.com/w/cpp/container/map/erase

[jingham]

You are inconsistent in a couple of places about whether you re-look up m_event_map.end or use the version you captured in a variable, which is a little confusing. Other than that this looks equivalent

lldb/source/Utility/Broadcaster.cpp

381

Why do you re-look-up m_event_map.end() instead of using the end variable you defined in the for initializer?

std::map::erase says it only invalidates iterators to the erased element, so you should be fine to use end here (and since you do exactly that in the previous line) it should be good here too.

436

Again here, you don't trust the "end" variable, but then in the next function you do reuse end_iter.

[fdeazeve]

Address review comments

lldb/source/Utility/Broadcaster.cpp

381

Yup, this was just a mistake on my part. Will address in the next version

392

Argh, the variable begin shouldn't exist, it should all be iter, otherwise we're not addressing the quadratic behaviour.

lldb/source/Utility/Broadcaster.cpp

return input.first.GetBroadcasterClass() ==
            (input.first.GetEventBits() & event_spec.GetEventBits()) != 0 &&
            input.second == listener_sp;
   };
   std::vector<BroadcastEventSpec> to_be_readded;
   uint32_t event_bits_to_remove = event_spec.GetEventBits();
 
   // Go through the map and delete the exact matches, and build a list of
   // matches that weren't exact to re-add:
-  while (true) {
-    collection::iterator iter, end_iter = m_event_map.end();
-    iter = find_if(m_event_map.begin(), end_iter,
-                   listener_matches_and_shared_bits);
-    if (iter == end_iter) {
+  for (auto iter = m_event_map.begin(), end = m_event_map.end();;) {
+    iter = find_if(iter, end, listener_matches_and_shared_bits);
+    if (iter == end)
       break;
-    }
     uint32_t iter_event_bits = (*iter).first.GetEventBits();
     removed_some = true;
 
     if (event_bits_to_remove != iter_event_bits) {
       uint32_t new_event_bits = iter_event_bits & ~event_bits_to_remove;
       to_be_readded.emplace_back(event_spec.GetBroadcasterClass(),
                                  new_event_bits);
     }
-    m_event_map.erase(iter);
+    iter = m_event_map.erase(iter);
   }
 
   // Okay now add back the bits that weren't completely removed:
-  for (size_t i = 0; i < to_be_readded.size(); i++) {
-    m_event_map.insert(event_listener_key(to_be_readded[i], listener_sp));
+  for (const auto &event : to_be_readded) {
+    m_event_map.insert(event_listener_key(event, listener_sp));
   }
 
   return removed_some;
 }
 
 ListenerSP BroadcasterManager::GetListenerForEventSpec(
     const BroadcastEventSpec &event_spec) const {
   std::lock_guard<std::recursive_mutex> guard(m_manager_mutex);
 
   auto event_spec_matches =
       [&event_spec](const event_listener_key &input) -> bool {
     return input.first.IsContainedIn(event_spec);
   };
 
-  collection::const_iterator iter, end_iter = m_event_map.end();
-  iter = find_if(m_event_map.begin(), end_iter, event_spec_matches);
-  if (iter != end_iter)
+  auto iter = llvm::find_if(m_event_map, event_spec_matches);
+  if (iter != m_event_map.end())
     return (*iter).second;
 
   return nullptr;
 }
 
 void BroadcasterManager::RemoveListener(Listener *listener) {
   std::lock_guard<std::recursive_mutex> guard(m_manager_mutex);
   auto listeners_predicate =
       [&listener](const lldb::ListenerSP &input) -> bool {
     return input.get() == listener;
   };
 
-  listener_collection::iterator iter = m_listeners.begin(),
-                                end_iter = m_listeners.end();
-
-  iter = std::find_if(iter, end_iter, listeners_predicate);
-  if (iter != end_iter)
+  if (auto iter = llvm::find_if(m_listeners, listeners_predicate);
+      iter != m_listeners.end())
     m_listeners.erase(iter);
 
-  while (true) {
-    auto events_predicate =
-        [&listener](const event_listener_key &input) -> bool {
-      return input.second.get() == listener;
-    };
-    collection::iterator iter, end_iter = m_event_map.end();
-    iter = find_if(m_event_map.begin(), end_iter, events_predicate);
-    if (iter == end_iter)
+  auto events_predicate = [listener](const event_listener_key &input) -> bool {
+
+  // TODO: use 'std::map::erase_if' when moving to c++20.
+  for (auto iter = m_event_map.begin(), end = m_event_map.end();;) {
+    iter = find_if(iter, end, events_predicate);
+    if (iter == end)
       break;
 
-    m_event_map.erase(iter);
+    iter = m_event_map.erase(iter);
   }
 }
 
 void BroadcasterManager::RemoveListener(const lldb::ListenerSP &listener_sp) {
   std::lock_guard<std::recursive_mutex> guard(m_manager_mutex);
 
   auto listener_matches =
       [&listener_sp](const event_listener_key &input) -> bool {
     return input.second == listener_sp;
   };
 
   if (m_listeners.erase(listener_sp) == 0)
     return;
 
-  while (true) {
-    collection::iterator iter, end_iter = m_event_map.end();
-    iter = find_if(m_event_map.begin(), end_iter, listener_matches);
+  // TODO: use 'std::map::erase_if' when moving to c++20.
+  for (auto iter = m_event_map.begin(), end_iter = m_event_map.end();;) {
+    iter = find_if(iter, end_iter, listener_matches);
     if (iter == end_iter)
       break;
 
-    m_event_map.erase(iter);
+    iter = m_event_map.erase(iter);
   }
 }
 
 void BroadcasterManager::SignUpListenersForBroadcaster(
     Broadcaster &broadcaster) {
   std::lock_guard<std::recursive_mutex> guard(m_manager_mutex);
 
   collection::iterator iter = m_event_map.begin(), end_iter = m_event_map.end();
 
   auto class_matches = [&broadcaster](const event_listener_key &input) -> bool {
     return input.first.GetBroadcasterClass() ==
            broadcaster.GetBroadcasterClass();
   };
 
   while (iter != end_iter &&
          (iter = find_if(iter, end_iter, class_matches)) != end_iter) {
     (*iter).second->StartListeningForEvents(&broadcaster,
                                             (*iter).first.GetEventBits());
     iter++;
   }
 }
 
 void BroadcasterManager::Clear() {
   std::lock_guard<std::recursive_mutex> guard(m_manager_mutex);
-  listener_collection::iterator end_iter = m_listeners.end();
 
-  for (listener_collection::iterator iter = m_listeners.begin();
-       iter != end_iter; iter++)
-    (*iter)->BroadcasterManagerWillDestruct(this->shared_from_this());
+  for (auto &listener : m_listeners)
+    listener->BroadcasterManagerWillDestruct(this->shared_from_this());
   m_listeners.clear();
   m_event_map.clear();
 }