From 08166b27b191e7be62d74054d92a9720c3a141ab Mon Sep 17 00:00:00 2001
From: Charlie Vieth <charlie.vieth@gmail.com>
Date: Sat, 5 Feb 2022 18:47:43 -0500
Subject: ProcessList: fix quadratic process removal when scanning

This commit changes ProcessList_scan to lazily remove Processes by
index, which is known, instead of performing a brute-force search by
pid and immediately reclaiming the lost vector space via compaction.

Searching by pid is potentially quadratic in ProcessList_scan because
the process we are searching for is always at the back of the vector
(the scan starts from the back of the vector). Additionally, removal
via Vector_remove immediately reclaims space (by sliding elements
down).

With these changes process removal in ProcessList_scan is now linear.

Changes:
  * ProcessList: add new ProcessList_removeIndex function to remove
    by index
  * Vector: add Vector_softRemove and Vector_compact functions to
    support lazy removal/deletion of entries Vector_softRemove
    Vector_compact
  * Vector: replace Vector_count with Vector_countEquals since it only
    used for consistency assertions.
---
 ProcessList.c | 48 +++++++++++++++++++++++++++++-------------------
 1 file changed, 29 insertions(+), 19 deletions(-)

(limited to 'ProcessList.c')

diff --git a/ProcessList.c b/ProcessList.c
index 2e5ad7cd..fc896add 100644
--- a/ProcessList.c
+++ b/ProcessList.c
@@ -158,7 +158,7 @@ void ProcessList_printHeader(const ProcessList* this, RichString* header) {
 }
 
 void ProcessList_add(ProcessList* this, Process* p) {
-   assert(Vector_indexOf(this->processes, p, Process_pidCompare) == -1);
+   assert(Vector_indexOf(this->processes, p, Process_pidEqualCompare) == -1);
    assert(Hashtable_get(this->processTable, p->pid) == NULL);
    p->processList = this;
 
@@ -168,25 +168,22 @@ void ProcessList_add(ProcessList* this, Process* p) {
    Vector_add(this->processes, p);
    Hashtable_put(this->processTable, p->pid, p);
 
-   assert(Vector_indexOf(this->processes, p, Process_pidCompare) != -1);
+   assert(Vector_indexOf(this->processes, p, Process_pidEqualCompare) != -1);
    assert(Hashtable_get(this->processTable, p->pid) != NULL);
-   assert(Hashtable_count(this->processTable) == Vector_count(this->processes));
+   assert(Vector_countEquals(this->processes, Hashtable_count(this->processTable)));
 }
 
-void ProcessList_remove(ProcessList* this, const Process* p) {
-   assert(Vector_indexOf(this->processes, p, Process_pidCompare) != -1);
-   assert(Hashtable_get(this->processTable, p->pid) != NULL);
-
-   const Process* pp = Hashtable_remove(this->processTable, p->pid);
-   assert(pp == p); (void)pp;
-
+// ProcessList_removeIndex removes Process p from the list's map and soft deletes
+// it from its vector. Vector_compact *must* be called once the caller is done
+// removing items.
+static void ProcessList_removeIndex(ProcessList* this, const Process* p, int idx) {
    pid_t pid = p->pid;
-   int idx = Vector_indexOf(this->processes, p, Process_pidCompare);
-   assert(idx != -1);
 
-   if (idx >= 0) {
-      Vector_remove(this->processes, idx);
-   }
+   assert(p == (Process*)Vector_get(this->processes, idx));
+   assert(Hashtable_get(this->processTable, pid) != NULL);
+
+   Hashtable_remove(this->processTable, pid);
+   Vector_softRemove(this->processes, idx);
 
    if (this->following != -1 && this->following == pid) {
       this->following = -1;
@@ -194,7 +191,17 @@ void ProcessList_remove(ProcessList* this, const Process* p) {
    }
 
    assert(Hashtable_get(this->processTable, pid) == NULL);
-   assert(Hashtable_count(this->processTable) == Vector_count(this->processes));
+   assert(Vector_countEquals(this->processes, Hashtable_count(this->processTable)));
+}
+
+void ProcessList_remove(ProcessList* this, const Process* p) {
+   int idx = Vector_indexOf(this->processes, p, Process_pidEqualCompare);
+   assert(0 <= idx && idx < Vector_size(this->processes));
+   if (idx >= 0) {
+      ProcessList_removeIndex(this, p, idx);
+      // This function is public so must not require callers to compact the Vector
+      Vector_compact(this->processes);
+   }
 }
 
 static void ProcessList_buildTreeBranch(ProcessList* this, pid_t pid, int level, int indent, bool show) {
@@ -429,7 +436,7 @@ Process* ProcessList_getProcess(ProcessList* this, pid_t pid, bool* preExisting,
    Process* proc = (Process*) Hashtable_get(this->processTable, pid);
    *preExisting = proc != NULL;
    if (proc) {
-      assert(Vector_indexOf(this->processes, proc, Process_pidCompare) != -1);
+      assert(Vector_indexOf(this->processes, proc, Process_pidEqualCompare) != -1);
       assert(proc->pid == pid);
    } else {
       proc = constructor(this->settings);
@@ -484,7 +491,7 @@ void ProcessList_scan(ProcessList* this, bool pauseProcessUpdate) {
       if (p->tombStampMs > 0) {
          // remove tombed process
          if (this->monotonicMs >= p->tombStampMs) {
-            ProcessList_remove(this, p);
+            ProcessList_removeIndex(this, p, i);
          }
       } else if (p->updated == false) {
          // process no longer exists
@@ -493,11 +500,14 @@ void ProcessList_scan(ProcessList* this, bool pauseProcessUpdate) {
             p->tombStampMs = this->monotonicMs + 1000 * this->settings->highlightDelaySecs;
          } else {
             // immediately remove
-            ProcessList_remove(this, p);
+            ProcessList_removeIndex(this, p, i);
          }
       }
    }
 
+   // Compact the processes vector in case of any deletions
+   Vector_compact(this->processes);
+
    // Set UID column width based on max UID.
    Process_setUidColumnWidth(maxUid);
 }
-- 
cgit v1.2.3