Automated Decomposition of Build Targets

A (build) target specifies the information that is needed to automatically build a software artifact. Managing the de-pendencies between the targets of a large code base is chal-lenging. This paper focuses on underutilized targets—an im-portant dependency problem that we identified at Google. An underutilized target is one with files not needed by some of its dependents. Underutilized targets result in less mod-ular code, overly large artifacts, slow builds, and unneces-sary build and test triggers. To mitigate these problems, programmers decompose underutilized targets into smaller targets. However, manually decomposing a target is tedious and error-prone. Although we prove that finding the best target decomposition is NP-hard, we introduce a greedy algo-rithm that proposes a decomposition through iterative uni-fication of the strongly connected components of the target. Our tool found 19,994 decomposable targets in a set of 40,000 Java library targets at Google. A decomposable target is one that can be decomposed to at least two targets. Our tool found that decomposing any of the 5,129 decomposable tar-gets would save at least one build or test trigger. The eval-uation results show that our tool is (1) efficient because on average, it analyzes a target in two minutes and (2) effective because for each of 1,010 targets, it would save more than 50 % of the total execution time of the tests triggered by the target. 1