[Dexter] Optimize breakpoint deletion in Visual Studio

Breakpoint deletion in visual studio is currently implemented by
iterating over the breakpoints we want to delete, for each of which we
iterate over the complete set of breakpoints in the debugger instance
until we find the one we wish to delete. Ideally we would resolve this
by directly deleting each breakpoint by some ID rather than searching
through the full breakpoint list for them, but in the absence of such a
feature in VS we can instead invert the loop to improve performance.

This patch changes breakpoint deletion to iterate over the complete list
of breakpoints, deleting breakpoints that match the breakpoints we
expect to delete by checking set membership. This represents a
worst-case improvement from O(nm) to O(n), for 'm' breakpoints being
deleted out of 'n' total. In practise this is almost exactly 'm'-times
faster, as when we delete multiple breakpoints they are typically
adjacent in the full breakpoint list.

Differential Revision: https://reviews.llvm.org/D120658

5 files changed, 40 insertions, 30 deletions

diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/DebuggerBase.py b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/DebuggerBase.py
index efb23899b77e..8a18ee0bfcdb 100644
--- a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/DebuggerBase.py
+++ b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/DebuggerBase.py
@@ -167,10 +167,10 @@ class DebuggerBase(object, metaclass=abc.ABCMeta):
         pass
 
     @abc.abstractmethod
-    def delete_breakpoint(self, id):
-        """Delete a breakpoint by id.
+    def delete_breakpoints(self, ids):
+        """Delete a set of breakpoints by ids.
 
-        Raises a KeyError if no breakpoint with this id exists.
+        Raises a KeyError if, for any id, no breakpoint with that id exists.
         """
         pass
 
diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py
index 569a2f941d3a..ccff7419d682 100644
--- a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py
+++ b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/DebuggerControllers/ConditionalController.py
@@ -175,8 +175,7 @@ class ConditionalController(DebuggerControllerBase):
                     self.debugger.add_breakpoint(bpr.path, line)
 
             # Remove any trailing or expired leading breakpoints we just hit.
-            for bp_id in bp_to_delete:
-                self.debugger.delete_breakpoint(bp_id)
+            self.debugger.delete_breakpoints(bp_to_delete)
 
             if exit_desired:
                 break
diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py
index a3021853eb14..c89920d5cd86 100644
--- a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py
+++ b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/dbgeng/dbgeng.py
@@ -90,7 +90,7 @@ class DbgEng(DebuggerBase):
     def get_triggered_breakpoint_ids(self):
       raise NotImplementedError('get_triggered_breakpoint_ids is not yet implemented by dbgeng')
 
-    def delete_breakpoint(self, id):
+    def delete_breakpoints(self, ids):
         # breakpoint setting/deleting is not supported by dbgeng at this moment
         # but is something that should be considered in the future.
         raise NotImplementedError('delete_conditional_breakpoint is not yet implemented by dbgeng')
diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py
index cde83af82732..46505e9f8b92 100644
--- a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py
+++ b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/lldb/LLDB.py
@@ -157,17 +157,18 @@ class LLDB(DebuggerBase):
                 breakpoint_ids.add(id)
         return breakpoint_ids
 
-    def delete_breakpoint(self, id):
-        bp = self._target.FindBreakpointByID(id)
-        if not bp:
-            # The ID is not valid.
-            raise KeyError
-        try:
-            del self._breakpoint_conditions[id]
-        except KeyError:
-            # This must be an unconditional breakpoint.
-            pass
-        self._target.BreakpointDelete(id)
+    def delete_breakpoints(self, ids):
+        for id in ids:
+            bp = self._target.FindBreakpointByID(id)
+            if not bp:
+                # The ID is not valid.
+                raise KeyError
+            try:
+                del self._breakpoint_conditions[id]
+            except KeyError:
+                # This must be an unconditional breakpoint.
+                pass
+            self._target.BreakpointDelete(id)
 
     def launch(self, cmdline):
         self._process = self._target.LaunchSimple(cmdline, None, os.getcwd())
diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py
index 9a291a9f4982..bbeb7b8cedd8 100644
--- a/cross-project-tests/debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py
+++ b/cross-project-tests/debuginfo-tests/dexter/dex/debugger/visualstudio/VisualStudio.py
@@ -204,30 +204,40 @@ class VisualStudio(DebuggerBase, metaclass=abc.ABCMeta):  # pylint: disable=abst
                 bp_id_list += ids
         return set(bp_id_list)
 
-    def delete_breakpoint(self, id):
-        """Delete a breakpoint by id.
+    def delete_breakpoints(self, ids):
+        """Delete breakpoints by their ids.
 
         Raises a KeyError if no breakpoint with this id exists.
         """
-        vsbp = self._dex_id_to_vs[id]
+        vsbp_set = set()
+        for id in ids:
+            vsbp = self._dex_id_to_vs[id]
 
-        # Remove our id from the associated list of dex ids.
-        self._vs_to_dex_ids[vsbp].remove(id)
-        del self._dex_id_to_vs[id]
+            # Remove our id from the associated list of dex ids.
+            self._vs_to_dex_ids[vsbp].remove(id)
+            del self._dex_id_to_vs[id]
+
+            # Bail if there are other uses of this vsbp.
+            if len(self._vs_to_dex_ids[vsbp]) > 0:
+                continue
+            # Otherwise find and delete it.
+            vsbp_set.add(vsbp)
+
+        vsbp_to_del_count = len(vsbp_set)
 
-        # Bail if there are other uses of this vsbp.
-        if len(self._vs_to_dex_ids[vsbp]) > 0:
-            return
-        # Otherwise find and delete it.
         for bp in self._debugger.Breakpoints:
-            # We're looking at the user-set breakpoints so there shouild be no
+            # We're looking at the user-set breakpoints so there should be no
             # Parent.
             assert bp.Parent == None
             this_vsbp = VSBreakpoint(PurePath(bp.File), bp.FileLine,
                                      bp.FileColumn, bp.Condition)
-            if vsbp == this_vsbp:
+            if this_vsbp in vsbp_set:
                 bp.Delete()
-                break
+                vsbp_to_del_count -= 1
+                if vsbp_to_del_count == 0:
+                    break
+        if vsbp_to_del_count:
+            raise KeyError('did not find breakpoint to be deleted')
 
     def _fetch_property(self, props, name):
         num_props = props.Count