Please note: This PhD seminar will take place in DC 2310 and online.
Hongxu Xu, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Chengnian Sun
As projects grow, the maintenance of intra- and inter-project dependencies declarations becomes increasingly complex. If dependency maintenance is lax, redundant dependencies may accrue, inflating incremental build and test latencies. The heterogeneity of language- and tool-specific dependency expressions and the complexity of the dependency graphs that they specify exacerbate the challenge of identifying and removing redundant dependencies. To address these challenges, this paper introduces DepReduce, a dependency optimization approach designed to be language-agnostic and compatible with all languages supported by the underlying build system. We formalized the dependency optimization objective as minimizing rebuild cost. To achieve this objective, DepReduce performs dependency lifting and dependency flattening operations on the dependency graph in a topological order, and we proved that DepReduce is both correct and optimal.
To empirically evaluate the approach, we implemented BazelDepReduce, an automated dependency optimization tool for Bazel. Bazel is a modern build system with native support for multiple programming languages. We evaluated BazelDepReduce on 14 open-source projects written in five programming languages, with eleven of them achieving reductions in rebuild cost. In total, BazelDepReduce identified and removed 250 redundant dependencies, which we used to produce eleven Pull Requests (PRs). Nine PRs have been merged by the target projects, including Angular and Apache RocketMQ. These contributions affected up to 57.6% of subsequent commits, with a median of 26.3%. The two other PRs remain open, awaiting a response from project maintainers. We also adapted BazelDepReduce to support Buck and Cargo, further demonstrating the generalizability of our approach. These results demonstrate the effectiveness of our approach in optimizing dependencies across projects with different programming languages.
To attend this PhD seminar in person, please go to DC 2310. You can also attend virtually on Zoom.