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.

5 files changed, 127 insertions, 35 deletions

diff --git a/Process.c b/Process.c
index 6c7b3263..600659c9 100644
--- a/Process.c
+++ b/Process.c
@@ -1095,13 +1095,6 @@ bool Process_sendSignal(Process* this, Arg sgn) {
    return kill(this->pid, sgn.i) == 0;
 }
 
-int Process_pidCompare(const void* v1, const void* v2) {
-   const Process* p1 = (const Process*)v1;
-   const Process* p2 = (const Process*)v2;
-
-   return SPACESHIP_NUMBER(p1->pid, p2->pid);
-}
-
 int Process_compare(const void* v1, const void* v2) {
    const Process* p1 = (const Process*)v1;
    const Process* p2 = (const Process*)v2;
diff --git a/Process.h b/Process.h
index e1408c21..ebaf230b 100644
--- a/Process.h
+++ b/Process.h
@@ -394,7 +394,11 @@ bool Process_changePriorityBy(Process* this, Arg delta);
 
 bool Process_sendSignal(Process* this, Arg sgn);
 
-int Process_pidCompare(const void* v1, const void* v2);
+static inline int Process_pidEqualCompare(const void* v1, const void* v2) {
+   const pid_t p1 = ((const Process*)v1)->pid;
+   const pid_t p2 = ((const Process*)v2)->pid;
+   return p1 != p2; /* return zero when equal */
+}
 
 int Process_compareByKey_Base(const Process* p1, const Process* p2, ProcessField key);
 
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);
 }
diff --git a/Vector.c b/Vector.c
index 52ed44a7..04881503 100644
--- a/Vector.c
+++ b/Vector.c
@@ -29,6 +29,8 @@ Vector* Vector_new(const ObjectClass* type, bool owner, int size) {
    this->items = 0;
    this->type = type;
    this->owner = owner;
+   this->dirty_index = -1;
+   this->dirty_count = 0;
    return this;
 }
 
@@ -44,10 +46,21 @@ void Vector_delete(Vector* this) {
    free(this);
 }
 
+static inline bool Vector_isDirty(const Vector* this) {
+   if (this->dirty_count > 0) {
+      assert(0 <= this->dirty_index && this->dirty_index < this->items);
+      assert(this->dirty_count <= this->items);
+      return true;
+   }
+   assert(this->dirty_index == -1);
+   return false;
+}
+
 #ifndef NDEBUG
 
 static bool Vector_isConsistent(const Vector* this) {
    assert(this->items <= this->arraySize);
+   assert(!Vector_isDirty(this));
 
    if (this->owner) {
       for (int i = 0; i < this->items; i++) {
@@ -60,15 +73,14 @@ static bool Vector_isConsistent(const Vector* this) {
    return true;
 }
 
-unsigned int Vector_count(const Vector* this) {
-   unsigned int items = 0;
+bool Vector_countEquals(const Vector* this, unsigned int expectedCount) {
+   unsigned int n = 0;
    for (int i = 0; i < this->items; i++) {
       if (this->array[i]) {
-         items++;
+         n++;
       }
    }
-   assert(items == (unsigned int)this->items);
-   return items;
+   return n == expectedCount;
 }
 
 Object* Vector_get(const Vector* this, int idx) {
@@ -88,13 +100,16 @@ int Vector_size(const Vector* this) {
 void Vector_prune(Vector* this) {
    assert(Vector_isConsistent(this));
    if (this->owner) {
-      for (int i = 0; i < this->items; i++)
+      for (int i = 0; i < this->items; i++) {
          if (this->array[i]) {
             Object_delete(this->array[i]);
-            //this->array[i] = NULL;
+            this->array[i] = NULL;
          }
+      }
    }
    this->items = 0;
+   this->dirty_index = -1;
+   this->dirty_count = 0;
 }
 
 //static int comparisons = 0;
@@ -242,6 +257,58 @@ Object* Vector_remove(Vector* this, int idx) {
    }
 }
 
+Object* Vector_softRemove(Vector* this, int idx) {
+   assert(idx >= 0 && idx < this->items);
+
+   Object* removed = this->array[idx];
+   assert(removed);
+   if (removed) {
+      this->array[idx] = NULL;
+
+      this->dirty_count++;
+      if (this->dirty_index < 0 || idx < this->dirty_index) {
+         this->dirty_index = idx;
+      }
+
+      if (this->owner) {
+         Object_delete(removed);
+         return NULL;
+      }
+   }
+
+   return removed;
+}
+
+void Vector_compact(Vector* this) {
+   if (!Vector_isDirty(this)) {
+      return;
+   }
+
+   const int size = this->items;
+   assert(0 <= this->dirty_index && this->dirty_index < size);
+   assert(this->array[this->dirty_index] == NULL);
+
+   int idx = this->dirty_index;
+
+   /* one deletion: use memmove, which should be faster */
+   if (this->dirty_count == 1) {
+      memmove(&this->array[idx], &this->array[idx + 1], (this->items - idx) * sizeof(this->array[0]));
+   } else {
+      /* multiple deletions */
+      for (int i = idx + 1; i < size; i++) {
+         if (this->array[i]) {
+            this->array[idx++] = this->array[i];
+         }
+      }
+   }
+
+   this->items -= this->dirty_count;
+   this->dirty_index = -1;
+   this->dirty_count = 0;
+
+   assert(Vector_isConsistent(this));
+}
+
 void Vector_moveUp(Vector* this, int idx) {
    assert(idx >= 0 && idx < this->items);
    assert(Vector_isConsistent(this));
diff --git a/Vector.h b/Vector.h
index 0fdb7069..b7b39031 100644
--- a/Vector.h
+++ b/Vector.h
@@ -22,6 +22,11 @@ typedef struct Vector_ {
    int arraySize;
    int growthRate;
    int items;
+   /* lowest index of a pending soft remove/delete operation,
+      used to speed up compaction */
+   int dirty_index;
+   /* count of soft deletes, required for Vector_count to work in debug mode */
+   int dirty_count;
    bool owner;
 } Vector;
 
@@ -44,6 +49,15 @@ Object* Vector_take(Vector* this, int idx);
 
 Object* Vector_remove(Vector* this, int idx);
 
+/* Vector_softRemove marks the item at index idx for deletion without
+   reclaiming any space. If owned, the item is immediately freed.
+
+   Vector_compact must be called to reclaim space.*/
+Object* Vector_softRemove(Vector* this, int idx);
+
+/* Vector_compact reclaims space free'd up by Vector_softRemove, if any. */
+void Vector_compact(Vector* this);
+
 void Vector_moveUp(Vector* this, int idx);
 
 void Vector_moveDown(Vector* this, int idx);
@@ -54,7 +68,11 @@ void Vector_set(Vector* this, int idx, void* data_);
 
 Object* Vector_get(const Vector* this, int idx);
 int Vector_size(const Vector* this);
-unsigned int Vector_count(const Vector* this);
+
+/* Vector_countEquals returns true if the number of non-NULL items
+   in the Vector is equal to expectedCount. This is only for debugging
+   and consistency checks. */
+bool Vector_countEquals(const Vector* this, unsigned int expectedCount);
 
 #else /* NDEBUG */