PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding Faster Configurations using FLASH

Vivek Nair, Zhe Yu, Tim Menzies, Norbert Siegmund, Sven Apel

arXiv:1801.02175v2cs.SE

TL;DR

Large software configuration spaces, poor defaults, and expensive measurements make finding good configurations difficult. FLASH uses sequential model-based search with fast surrogate modeling to choose promising configurations, achieving strong single- and multi-objective results across software systems while reducing measurement effort.

  • Problem

    Large configuration spaces and poor defaults make good software configurations difficult to find, while evaluating candidates can be expensive.

  • Method

    FLASH sequentially reflects on evaluated configurations, using CART surrogate models and a stochastic Maximum-Mean Bazza acquisition function to select the next configuration.

  • Results

    Across 30 scenarios from seven software systems, FLASH uses an order of magnitude fewer solutions in 57% of single-objective scenarios and remains effective and scalable for multi-objective problems.

  • Takeaways & Limitations

    FLASH reduces measurement costs while extending sequential model-based configuration optimization to multi-objective problems and systems with more than 10 configuration options.

  • Takeaways & Limitations

    The evaluation samples only a few hundred configurations, focuses on predicting performance for a given workload, and covers six selected common software-system types.

Abstract

from arXiv · show

Finding good configurations for a software system is often challenging since the number of configuration options can be large. Software engineers often make poor choices about configuration or, even worse, they usually use a sub-optimal configuration in production, which leads to inadequate performance. To assist engineers in finding the (near) optimal configuration, this paper introduces FLASH, a sequential model-based method, which sequentially explores the configuration space by reflecting on the configurations evaluated so far to determine the next best configuration to explore. FLASH scales up to software systems that defeat the prior state of the art model-based methods in this area. FLASH runs much faster than existing methods and can solve both single-objective and multi-objective optimization problems. The central insight of this paper is to use the prior knowledge (gained from prior runs) to choose the next promising configuration. This strategy reduces the effort (i.e., number of measurements) required to find the (near) optimal configuration. We evaluate FLASH using 30 scenarios based on 7 software systems to demonstrate that FLASH saves effort in 100% and 80% of cases in single-objective and multi-objective problems respectively by up to several orders of magnitude compared to the state of the art techniques.

1 INTRODUCTION

FLASH targets costly software configuration optimization by sequentially selecting promising configurations, using scalable modeling to reduce measurements and runtime for single- and multi-objective problems.

  • 1 INTRODUCTION: Large configuration spaces are difficult to understand, and long benchmarking times make exploring more than a handful of configurations infeasible.Poor defaults further motivate automated search for better configurations.
  • 1 INTRODUCTION: FLASH selects the next configuration by reflecting on previously evaluated configurations, reducing evaluations needed to find better configurations.It uses sequential model-based optimization rather than exploring many configurations blindly.
  • 1 INTRODUCTION: FLASH uses a performance model accurate enough to distinguish better configurations and replaces Gaussian processes with a fast, scalable decision-tree learner.The approach tolerates model inaccuracy to reduce evaluation cost and search time.
  • 1 INTRODUCTION: FLASH solves single-objective optimization with an order of magnitude fewer measurements than state-of-the-art methods.This matters when each measurement requires compiling and benchmarking the software system.
  • 1 INTRODUCTION: FLASH extends configuration optimization to multi-objective performance problems and achieves similar performance and scalability with greatly reduced runtimes.The introduction identifies multi-objective optimization and reduced runtime as central contributions.

2 PERFORMANCE CONFIGURATION OPTIMIZATION FOR SOFTWARE

Software configuration optimization is motivated by large, interacting configuration spaces, poor defaults, and expensive benchmarking across diverse application domains.

  • 2 PERFORMANCE CONFIGURATION OPTIMIZATION FOR SOFTWARE: Configuration spaces can grow exponentially, while developers may ignore over 80% of options, leaving optimization potential untapped.Apache grew from 150 to more than 550 options over 16 years.
  • 2 PERFORMANCE CONFIGURATION OPTIMIZATION FOR SOFTWARE: Poor defaults can severely degrade performance, including a reported 480-fold throughput difference between the worst and best Apache Storm configurations.Other examples include outdated MySQL memory assumptions and worst-case Hadoop execution times.
  • 2 PERFORMANCE CONFIGURATION OPTIMIZATION FOR SOFTWARE: Benchmarking candidate configurations can take weeks, hours, or days when each candidate requires executing or synthesizing the full system.This makes exhaustive exploration impractical.
  • 2 PERFORMANCE CONFIGURATION OPTIMIZATION FOR SOFTWARE: Configuration optimization also appears in software product lines, machine learning hyperparameter tuning, cloud computing, and virtual-machine security settings.These domains face analogous choices among configurations with different performance or operational consequences.

3 THEORY

The paper formulates configuration optimization as finding high-performing configurations with few measurements and explains SMBO as iterative model-guided sampling of an expensive objective.

  • 3 THEORY: A configurable system maps configurations x_i in X to one or more performance measures y_i,k through an unknown function f.Single-objective problems have one measure, while multi-objective problems use a vector of measures.
  • 3 THEORY: The optimization goal is to find better configurations while minimizing the number of performance measurements.Multi-objective optimization seeks a set of configurations that dominate alternatives.
  • 3 THEORY: SMBO builds a model from measured configurations, predicts unevaluated configurations, and uses an acquisition function to choose the next sample.The process continues until a predefined stopping criterion or budget is reached.
  • 3 THEORY: The acquisition function balances exploration of uncertain regions with exploitation of configurations predicted to perform well.It selects the configuration maximizing the acquisition value.
  • 3 THEORY: Gaussian-process-based methods can be fragile and do not scale well to high-dimensional configuration spaces or large datasets.Prior software-engineering methods were limited to roughly ten decisions, and intricate acquisition functions can also become costly beyond a dozen decisions.

URABLE SOFTWARE SYSTEMS

Prior configuration-optimization methods build performance models through sequential sampling, using residual accuracy or rank preservation for single-objective problems, while ePAL applies uncertainty-driven multi-objective SMBO.

  • Prior methods: Both residual-based and rank-based methods use flat acquisition functions, so configurations are selected through random sampling.
  • Residual-based: “Build an Accurate Model”: Progressive sampling randomly adds evaluated configurations until the performance model reaches a predefined accuracy threshold or stops improving.It validates the model on a holdout set and uses an accuracy-based termination criterion.
  • Residual-based: “Build an Accurate Model”: Residual-based optimization measures model correctness with error metrics such as MMRE and is limited to single-objective scenarios.
  • Residual-based: “Build an Accurate Model”: The Word Count learning curve shows that model accuracy does not improve substantially after 20 sampled configurations.
  • Rank-based: “Build a Rank-preserving Model”: Rank-based optimization compares predicted and actual configuration orders using mean rank difference rather than residual error.The measure captures incorrectly ordered test pairs and the magnitude of ranking differences.
  • ePAL: ePAL builds a Gaussian-process performance model, discards configurations likely to be dominated, and measures the most uncertain remaining configuration.It uses predictive uncertainty as its acquisition function and supports multi-objective optimization.

5 FLASH: A FAST SEQUENTIAL MODEL-BASED METHOD

FLASH is a sequential model-based optimizer that incrementally learns configuration performance and selects promising evaluations using scalable CART surrogates and the Bazza acquisition strategy.

  • Bazza selects configurations with strong predicted objective values across random weighted projections for multi-objective optimization.The method decomposes the problem into subproblems using random weight vectors and evaluates predicted objective scores from CART models.
  • For each candidate, FLASH predicts performance, computes a mean weight, and retains the candidate with the highest mean.This acquisition step uses CART predictions rather than fully evaluating every configuration.
  • FLASH begins with randomly sampled configurations, trains CART models, iteratively selects candidates, and stops when its evaluation budget is exhausted.The user specifies N, size, and budget before execution.
  • The method targets fewer evaluations and shorter search time by accepting models accurate enough to distinguish promising configurations from the rest.FLASH deliberately tolerates prediction inaccuracy when it reduces measurement cost.
  • FLASH incrementally builds models from evaluated configurations and uses them to select the next configuration without an expensive holdout set.The evaluated configurations are used to train CART models, while the unevaluated pool supplies candidates for subsequent selection.
  • FLASH replaces Gaussian Process Models with CART surrogates to scale model-based optimization beyond software systems with many configuration options.CART avoids smoothness assumptions and scales more effectively than GPM for larger configuration spaces.

6 EVALUATION

The evaluation compares FLASH with prior configuration-optimization methods on effectiveness and measurement effort in single- and multi-objective settings. It uses rank-based and Pareto-frontier metrics while controlling data splits for fair comparisons.

  • Baselines: Prior methods divide configurations into training, validation, and holdout sets, with prior work using up to 20% of the configuration space as holdout data.The evaluation highlights the measurement cost of populating validation and holdout sets.
  • Research Questions: The evaluation measures whether FLASH finds better configurations and how many measurements it requires to do so.Effectiveness is assessed through rank difference for single-objective optimization and Pareto-frontier quality for multi-objective optimization.
  • Experimental Settings: FLASH is evaluated on 30 scenarios spanning single-objective and multi-objective optimization across six software systems.The systems were selected as established benchmark problems in configuration and search-based software engineering.
  • RQ1 and RQ2: Single-objective effectiveness is quantified by the absolute rank difference between the predicted best configuration and the actual optimal configuration.Configurations are ranked by performance, with the minimum score assigned rank 1 and the highest score assigned rank N.
  • Experimental Settings: For fair comparison, FLASH searches an 80% subset corresponding to the training and validation data used by competing methods.The remaining split structure follows the prior experimental setup while merging training and validation pools for FLASH.
  • RQ3, RQ4, and RQ5: Multi-objective effectiveness uses GD and IGD, where lower values indicate closer convergence and IGD additionally reflects spread across the true Pareto-optimal solutions.GD alone does not measure diversity, so IGD is used to assess how solutions are distributed across the solution space.

7 RESULTS

FLASH finds configurations comparable to established single-objective methods while using substantially fewer measurements, and it remains effective for multi-objective optimization.

  • 7.1 Single-objective Problems: FLASH finds better configurations similarly to residual-based and rank-based methods without using a holdout set.
  • 7.1 Single-objective Problems: 9% of the measurements are required by FLASH in SS-E1 compared with the residual-based and rank-based methods.
  • 7.1 Single-objective Problems: 57% of software systems require an order of magnitude fewer measurements with FLASH than with residual-based and rank-based methods.
  • 7.2 Multi-objective Optimization: FLASH remains effective with more than 10 configuration options, whereas ePAL variants fail to terminate within reasonable time in those cases.
  • 7.2 Multi-objective Optimization: FLASH requires fewer measurements than ePAL for Pareto-optimal approximation in all 15 cases against ePAL-0.01 and 12 of 15 against ePAL-0.3.
  • 7.2 Multi-objective Optimization: FLASH is faster than ePAL variants in 13 of 15 cases and is an order of magnitude faster in 5 of 15 cases.

8 DISCUSSION

FLASH uses scalable decision trees and balances exploration against exploitation through its size and budget parameters. Its evaluation compares convergence, diversity, measurements, and runtime against ePAL.

  • 8 DISCUSSION: FLASH replaces Gaussian Process Models with a fast, scalable decision tree learner to support larger configuration spaces.
  • 8 DISCUSSION: FLASH’s size parameter controls exploration, while budget controls exploitation, creating a trade-off between convergence and diversity.
  • 8 DISCUSSION: Table 2 compares FLASH and ePAL using GD, IGD, and measurement counts, with lower values better and X marking nontermination within 10 hours.
  • 8 DISCUSSION: FLASH does not yet explicitly use decision-tree rules to select the next sample or recursively prune the configuration space.
  • 8 DISCUSSION: FLASH evaluates configurations sequentially and therefore does not parallelize evaluations in its current version.
  • 8 DISCUSSION: FLASH assumes stationary workloads, equal evaluation costs, and randomly selected initial configurations.

9 THREATS TO VALIDITY

The evaluation addresses reproducibility, statistical variability, and internal and external validity, but samples only a subset of configurations and software-system types.

  • 9 THREATS TO VALIDITY: Public-domain implementations and released code were used to improve external reliability and reproducibility.
  • 9 THREATS TO VALIDITY: The evaluation samples only a few hundred configurations because measuring all configurations is infeasible, leaving room for outliers and measurement bias.
  • 9 THREATS TO VALIDITY: The study repeats experiments for 20 runs, reports median indicators, and applies statistical tests to mitigate stochastic bias.
  • 9 THREATS TO VALIDITY: The case studies cover six common software-system types, so broader software systems and other SBSE domains remain for future exploration.

10 CONCLUSION

FLASH is a sequential model-based optimizer that minimizes measurements while finding better configurations across single- and multi-objective problems. Experiments across 30 scenarios and seven software systems demonstrate effectiveness, while future work targets broader case studies and improved scalability.

  • FLASH found better configurations while minimizing measurements across single-objective and multi-objective problems in 30 scenarios from seven software systems.The method uses a CART surrogate model and stochastic Maximum-Mean Bazza acquisition function.
  • The evaluation demonstrated FLASH's effectiveness on both single-objective and multi-objective optimization problems.The study covered 30 scenarios drawn from seven software systems.
  • In 57% of single-objective scenarios, FLASH used an order of magnitude fewer solutions than state-of-the-art approaches.It also removed the need for a holdout dataset, saving measurement costs.
  • FLASH overcame ePAL's shortcomings while matching its effectiveness and scaling to systems with more than 10 configuration options.The passage states that ePAL does not terminate in a reasonable timeframe for such systems.
  • Future work includes testing different case studies and further improving FLASH's scalability.
Loading 1801.02175v2…