Finding near-optimal configurations in colossal product spaces of highly configurable systems

Highly Configurable Systems (HCSs) have options and parameters, called features, that allow users to customize a system. Features cause an HCS to have a vast number of configurations to choose from, which raises the need for an efficient way to search for optimal configurations, called HCS Optimization (HCSO). Existing work on HCSO learns a performance model to predict the performance of any configuration. An optimization algorithm, in turn, uses it to find configurations. However, learning a performance model can be costly compared to searching. Also, how many samples are needed to produce an “accurate enough” model is unknown; only unreliable heuristics guide this important decision. HCSO also lacks a scalable Simple Random Sampling (SRS) technique which is a prerequisite for accurate reasoning and searching of a large space. In this dissertation, we demonstrate statistical reasoning over samples using a scalable SRS technique can achieve cost-efficient HCSO whether or not performance models are used. To achieve this, we first introduce a scalable SRS technique called Smarch. Smarch can sample from HCSs with up to 10⁴¹⁷ configurations, which is 10⁴⁰⁵ times larger than the prior state-of-the-art. Although recent work achieved higher scalability, Smarch was the first to achieve a scalable SRS by the one-to-one mapping between integers and configurations. Second, we show how SRS solves HCSO problems. We derive a way to estimate the rank of the samples from SRS based on the number of samples and vice versa, regardless of the HCS. We also propose a search algorithm called ROpt that finds solutions with 49% lower normalized rank compared to using SRS alone. Third, we utilize Bit-blasting to encode features with numerical values into a propositional formula and use existing tools to SRS configurations. Compared to the tools that inherently support reasoning with numerical values, this approach is faster and achieves SRS. Lastly, we compare our sampling methods with state-of-the-art performance modeling approaches. We demonstrate that performance models are not the best fit for HCSO. They often underperformed SRS alone. Further, we found a weak correlation between performance model accuracy and HCSO accuracy. This discovery is important as it contradicts assumptions made in performance model construction. We also evaluated ROpt for HCSs with at least 10⁶ times more configurations than previously evaluated, which sets a baseline for others to match and improve in future research.Computer Science