Path to this page:
Subject: CVS commit: pkgsrc/pkgtools
From: Joerg Sonnenberger
Date: 2023-02-11 00:14:32
Message id: 20230210231432.9CD7EFA90@cvs.NetBSD.org
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.
Files: