Reusing d-DNNFs for Efficient Feature-Model Counting - Summary

The underlying work Reusing d-DNNFs for Efficient Feature-Model Counting was originally published in the TOSEM journal [Su24] in November, 2024. Software product lines are commonly used to manage families of related products that share different features. Products are composed by combining those features. However, not every combination or configuration of features leads to a desired product as there are dependencies between those features. Feature models are widely used to define the set of valid configurations by describing features and constraints between them. As feature models in practice often contain thousands of features and constraints, numerous automated analyses have been proposed. Many of these analyses rely on computing the number of valid configurations, which is very computationally demanding. Moreover, most applications rely on many counting operations, potentially thousands or even millions in practice. In this work, we propose to reuse d-DNNFs to accelerate repetitive counting queries on feature models. To this end, we realize algorithms that traverse d-DNNFs to perform counting and propose various optimizations. Our large-scale empirical evaluation shows that our approach can reduce runtimes for single analysis by multiple orders of magnitudes (e. g., from days to seconds) compared to state-of-the-art counting tools.