CVS commit: pkgsrc/pkgtools

["Joerg Sonnenberger" <joerg%netbsd.org@localhost>]

Module Name:    pkgsrc
Committed By:   joerg
Date:           Fri Feb 10 23:14:32 UTC 2023

Modified Files:
        pkgsrc/pkgtools/pbulk-base: Makefile
        pkgsrc/pkgtools/pbulk/files/pbulk/pbuild: jobs.c pbuild.h

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.


To generate a diff of this commit:
cvs rdiff -u -r1.25 -r1.26 pkgsrc/pkgtools/pbulk-base/Makefile
cvs rdiff -u -r1.17 -r1.18 pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c
cvs rdiff -u -r1.7 -r1.8 pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h

Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.

Modified files:

Index: pkgsrc/pkgtools/pbulk-base/Makefile
diff -u pkgsrc/pkgtools/pbulk-base/Makefile:1.25 pkgsrc/pkgtools/pbulk-base/Makefile:1.26
--- pkgsrc/pkgtools/pbulk-base/Makefile:1.25    Tue Mar 12 15:37:51 2019
+++ pkgsrc/pkgtools/pbulk-base/Makefile Fri Feb 10 23:14:32 2023
@@ -1,6 +1,6 @@
-# $NetBSD: Makefile,v 1.25 2019/03/12 15:37:51 wiz Exp $
+# $NetBSD: Makefile,v 1.26 2023/02/10 23:14:32 joerg Exp $
 
-DISTNAME=      pbulk-base-0.54
+DISTNAME=      pbulk-base-0.55
 COMMENT=       Core components of the modular bulk build framework
 
 .include "../../pkgtools/pbulk/Makefile.common"

Index: pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c
diff -u pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c:1.17 pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c:1.18
--- pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c:1.17        Fri Feb 10 22:59:13 2023
+++ pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/jobs.c     Fri Feb 10 23:14:32 2023
@@ -1,4 +1,4 @@
-/* $NetBSD: jobs.c,v 1.17 2023/02/10 22:59:13 joerg Exp $ */
+/* $NetBSD: jobs.c,v 1.18 2023/02/10 23:14:32 joerg Exp $ */
 
 /*-
  * Copyright (c) 2007, 2009, 2011 Joerg Sonnenberger <joerg%NetBSD.org@localhost>.
@@ -149,11 +149,8 @@ pbulk_item_end(const char *line)
        return line;
 }
 
-SLIST_HEAD(depth_tree_head, build_job);
-
 static int
-compute_tree_depth_rec(struct build_job *job, struct build_job *root,
-    struct depth_tree_head *head)
+compute_tree_depth_rec(struct build_job *job, struct build_job *root, char *seen)
 {
        struct dependency_list *dep_iter;
        struct build_job *job_iter;
@@ -163,14 +160,12 @@ compute_tree_depth_rec(struct build_job 
                return -1;
        }
 
-       SLIST_FOREACH(job_iter, head, depth_tree_link) {
-               if (job_iter == job)
-                       return 0;
-       }
-       SLIST_INSERT_HEAD(head, job, depth_tree_link);
+       if (seen[job - jobs])
+               return 0;
+       seen[job - jobs] = 1;
        ++root->pkg_depth;
        SLIST_FOREACH(dep_iter, &job->depending_pkgs, depends_link) {
-               if (compute_tree_depth_rec(dep_iter->dependency, root, head)) {
+               if (compute_tree_depth_rec(dep_iter->dependency, root, seen)) {
                        fprintf(stderr, "%s\n", job->pkgname);
                        return -1;
                }
@@ -179,20 +174,19 @@ compute_tree_depth_rec(struct build_job 
 }
 
 static void
-compute_tree_depth(struct build_job *job)
+compute_tree_depth(struct build_job *job, char *seen)
 {
-       struct depth_tree_head head;
+       memset(seen, 0, len_jobs);
 
-       SLIST_INIT(&head);
        job->pkg_depth = 0;
-       if (compute_tree_depth_rec(job, job, &head))
+       if (compute_tree_depth_rec(job, job, seen))
                exit(1);
 }
 
 void
 init_jobs(const char *scan_output, const char *success_file, const char *error_file)
 {
-       char *input;
+       char *input, *seen;
        const char *input_iter;
        int fd;
        size_t i;
@@ -242,8 +236,10 @@ init_jobs(const char *scan_output, const
        hash_entries();
        build_tree();
 
+       seen = xmalloc(len_jobs);
        for (i = 0; i < len_jobs; ++i)
-               compute_tree_depth(&jobs[i]);
+               compute_tree_depth(&jobs[i], seen);
+       free(seen);
 
        mark_initial();
 

Index: pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h
diff -u pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h:1.7 pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h:1.8
--- pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h:1.7       Tue Nov  3 19:06:47 2015
+++ pkgsrc/pkgtools/pbulk/files/pbulk/pbuild/pbuild.h   Fri Feb 10 23:14:32 2023
@@ -1,4 +1,4 @@
-/* $NetBSD: pbuild.h,v 1.7 2015/11/03 19:06:47 joerg Exp $ */
+/* $NetBSD: pbuild.h,v 1.8 2023/02/10 23:14:32 joerg Exp $ */
 
 /*-
  * Copyright (c) 2007 Joerg Sonnenberger <joerg%NetBSD.org@localhost>.
@@ -108,7 +108,6 @@ struct build_job {
 
        TAILQ_ENTRY(build_job) build_link;
        SLIST_ENTRY(build_job) hash_link;
-       SLIST_ENTRY(build_job) depth_tree_link;
 };
 
 extern int              verbosity;