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:
RevisionActionfile
1.26modifypkgsrc/pkgtools/pbulk-base/Makefile
1.18modifypkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c
1.8modifypkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h