summaryrefslogtreecommitdiffstats
path: root/ProcessList.c
diff options
context:
space:
mode:
authorCharlie Vieth <charlie.vieth@gmail.com>2022-02-05 18:47:43 -0500
committerBenBE <BenBE@geshi.org>2022-05-05 09:17:51 +0200
commit08166b27b191e7be62d74054d92a9720c3a141ab (patch)
treec5b839805f0565b11058ff7b7832b5fadfb4bc55 /ProcessList.c
parentc7413fd6771b65388bea14ef42863444c6eaa419 (diff)
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.
Diffstat (limited to 'ProcessList.c')
-rw-r--r--ProcessList.c48
1 files changed, 29 insertions, 19 deletions
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);
}

© 2014-2024 Faster IT GmbH | imprint | privacy policy