Subject: CVS commit: pkgsrc/pkgtools
From: Joerg Sonnenberger
Date: 2023-02-11 00:14:32
Message id:

Log Message:
pbulk-base-0.55: Optimize DAG computation

Before the build starts, pbulk-build computes the size of the dependee
graph for each package. This is naturally a O(n^2) problem. The existing
algorithm used a linked list to check for duplicates. Replace this with
a simple array for seen markers. While it is still quadratic to reset
the array for every package, clearing the array is a simple memset.
A no-op run after a full build now needs 0.3s on my work station
compared to over 3min before.