diff options
author | Charlie Vieth <charlie.vieth@gmail.com> | 2022-02-05 18:47:43 -0500 |
---|---|---|
committer | BenBE <BenBE@geshi.org> | 2022-05-05 09:17:51 +0200 |
commit | 08166b27b191e7be62d74054d92a9720c3a141ab (patch) | |
tree | c5b839805f0565b11058ff7b7832b5fadfb4bc55 /ProcessList.c | |
parent | c7413fd6771b65388bea14ef42863444c6eaa419 (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.c | 48 |
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); } |