PaperlayerView exact revision on arXiv

Source-linked AI summary

Using Bad Learners to find Good Configurations

Vivek Nair, Tim Menzies, Norbert Siegmund, Sven Apel

arXiv:1702.05701v2cs.SE

TL;DR

Building accurate performance models for configurable systems can be costly. This paper uses configuration rankings instead of exact prediction accuracy to guide sampling and search, finding optimal configurations for most evaluated systems with fewer measurements.

  • Problem

    Finding an optimal configuration is challenging when accurate performance models are expensive to build for complex systems.

    Source: §1 · p. 2, §3.2 · p. 3

  • Method

    The rank-based approach uses rank difference rather than residual error to evaluate models and guide iterative sampling.

    Source: §10 · p. 10, §8.4 · p. 10

  • Results

    The rank-based approach finds optimal configurations for most subject systems with fewer measurements; exceptions are systems for which accurate models are already easy to build.

    Source: §10 · p. 10

  • Takeaways & Limitations

    A model need not predict raw performance accurately to be useful for ranking configurations and optimization.

    Source: §10 · p. 10

    For SQLite, the evaluation sampled only 100 configurations and did not vary benchmarks beyond the given workload.

    Source: §9 · p. 10

Abstract

from arXiv · show

Finding the optimally performing configuration of a software system for a given setting is often challenging. Recent approaches address this challenge by learning performance models based on a sample set of configurations. However, building an accurate performance model can be very expensive (and is often infeasible in practice). The central insight of this paper is that exact performance values (e.g. the response time of a software system) are not required to rank configurations and to identify the optimal one. As shown by our experiments, models that are cheap to learn but inaccurate (with respect to the difference between actual and predicted performance) can still be used rank configurations and hence find the optimal configuration. This novel \emph{rank-based approach} allows us to significantly reduce the cost (in terms of number of measurements of sample configuration) as well as the time required to build models. We evaluate our approach with 21 scenarios based on 9 software systems and demonstrate that our approach is beneficial in 16 scenarios; for the remaining 5 scenarios, an accurate model can be built by using very few samples anyway, without the need for a rank-based approach.

1 INTRODUCTION

Accurate performance models can be difficult to build for complex systems, while measuring large configuration spaces is costly. The paper asks whether ranking can identify good configurations with fewer measurements even when performance predictions are inaccurate.

1 INTRODUCTION

  • Rather than predict how long a configuration runs, the approach asks whether one runs faster than another or which is fastest.The paper argues that useful predictors can be built with very small sample sets.Source: §1 · p. 1
  • State-of-the-art predictors had errors up to 80% on some harder-to-model systems, prompting questions about whether prior work addressed only easy problems.The passage identifies the affected systems as the yellow and red systems in Figure 1.Source: §1 · p. 1
  • Measuring all configurations can be prohibitively expensive; the authors report needing over a month of CPU time to collect their experimental data.The paper frames its goals as finding predictors for hard-to-model systems and using as few sample configurations as possible.Source: §1 · p. 2
  • Ranking is useful when developers need the fastest configuration or want to compare alternatives, rather than predict exact performance values.The paper identifies these as practical use cases for ranking models.Source: §1 · p. 2
  • 5% of the measurements used by a residual-based approach sufficed for Apache Storm scenario SS11; overall, rank-based search was rarely worse and often better.The evaluation covered 21 scenarios based on 9 open-source systems.Source: §1 · p. 2

2 PROBLEM FORMALIZATION

The paper formalizes a configurable system as a space of configurations with associated performance measures. Its objective is to rank configurations and find a near-optimal one with few measurements when accurate performance modeling is not feasible.

2 PROBLEM FORMALIZATION

  • A configuration space is the Cartesian product of the finite domains of a system’s configuration options, with each configuration associated with a performance measure.The options are generally integer or Boolean variables.Source: §2 · p. 2
  • The formalized task ranks configurations by their performance values to identify an optimal configuration within the configuration space.Source: §2 · p. 3
  • The objective is to find a near-optimal configuration with few measurements when an accurate performance model cannot be built.Source: §2 · p. 3

3 RESIDUAL-BASED APPROACHES

This section describes residual-based performance modeling and sampling procedures intended to limit measurements. It contrasts progressive sampling’s accuracy-based stopping rule with projective sampling’s estimate of modeling cost.

3 RESIDUAL-BASED APPROACHES

  • Residual-based approaches build performance models for configurable software systems, with Sarkar et al. cited for further details.The section then describes sampling strategies for reducing the measurements required to build models.Source: §3 · p. 3

3.1 Progressive Sampling

  • Progressive sampling adds and measures training-pool configurations iteratively, builds and tests a model, and stops after repeated additions fail to improve accuracy.Its goal is to stop when the learning curve flattens, but reaching acceptable accuracy may require many iterations and high modeling cost.Source: §3.1 · p. 3, §3.2 · p. 3

3.2 Projective Sampling

  • Projective sampling uses an initial set of samples to approximate the learning curve and estimate the number of configurations needed for model convergence.It tracks feature-selection and deselection frequencies, fits a function to the sampled learning-curve points, and extrapolates the convergence point.Source: §3.2 · pp. 3–4

4 RANK-BASED APPROACH

The rank-based approach evaluates whether a model orders configurations correctly rather than focusing on residual error. It adds measured configurations during training and uses changes in rank difference to determine when to stop sampling.

4 RANK-BASED APPROACH

  • Ranking is the target when practitioners need top-performing configurations, and it is described as robust to errors and outliers.The paper argues that finding an optimal configuration may require fewer training samples than residual-based modeling.Source: §4 · p. 4
  • The approach compares predicted and actual test-set ranks using mean rank difference, which measures the average magnitude of ranking differences.The paper contrasts this rank-based measure with evaluation based on residual error.Source: §4 · p. 4
  • Sampling adds configurations, measures their performance, and trains a model; it stops when rank difference fails to improve for the configured number of lives.The lives parameter is intended to detect convergence and avoid resource use when additional data no longer improves accuracy.Source: §4 · pp. 4–5

5 SUBJECT SYSTEMS

The evaluation uses 21 test cases from nine open-source software systems, including software libraries and Apache Storm scenarios. Storm experiments span multiple benchmarks, cloud clusters, and measurement conditions.

5 SUBJECT SYSTEMS

  • To compare residual-based approaches with its rank-based approach, the study evaluates 21 test cases collected in nine open-source software systems.The passages identify x264, Berkeley DB, SQLite, wget, and lrzip among the systems.Source: §5 · p. 5
  • Apache Storm scenarios cover WordCount, RollingSort, and SOL benchmarks across five cloud clusters.The experiments include multi-tenant settings, where concurrent workloads increased latency and measurement variability.Source: §5 · p. 5
  • One rs workload varies 6 features across 3,839 configurations and measures throughput; another wc workload shares a multi-tenant cluster with rs, varies 3 features across 195 configurations, and measures latency.Source: §5 · pp. 5–6

6 EVALUATION

The evaluation asks whether inaccurate models can rank configurations accurately and how many measurements the rank-based approach requires. These questions address settings where building an accurate model may be infeasible.

6 EVALUATION

  • Accurate configuration models can require hundreds of training measurements, and some systems may not permit accurate models at all.The evaluation focuses on finding optimal configurations in such settings.Source: §6.1 · p. 6
  • The evaluation tests whether inaccurate rank-based models can find near-optimal configurations with fewer measurements than residual-based models.This is framed as the study’s hypothesis, not as a reported finding in this section.Source: §6.1 · p. 6
  • The evaluation considers both ranking accuracy from inaccurate models and the measurement effort required to build them.These considerations motivate the paper’s two research questions.Source: §6.1 · p. 6

RQ1: Can inaccurate models accurately rank configurations?

RQ1 asks whether inaccurate predictive models can still rank configurations well, while RQ2 asks how many measurements a rank-based approach needs. The evaluation compares optimal-configuration ranks from rank-based and residual-based models using held-out configurations.

RQ1: Can inaccurate models accurately rank configurations?

  • The study compares rank-based models with residual-based approaches by checking whether each identifies the optimal configuration on held-out data.Model accuracy is assessed using rank difference for the rank-based approach and MMRE for residual-based approaches.Source: RQ1: Can inaccurate models accurately… · p. 6, §6.2 · p. 6

6.2 Experimental Rig

  • Measurements record benchmark performance for valid configurations, except SQLite, where the study measures sampled configurations because its full space is impractically large.SQLite has 3,932,160 possible configurations; its measured set includes feature-wise and pair-wise samples plus 100 random configurations.Source: §6.2 · p. 6
  • The evaluation splits datasets into training, testing, and validation pools of 40%, 20%, and 40%, respectively; using training data and accuracy, it builds a CART performance model and assesses accuracy with data from the testing pool.Source: §6.2 · p. 6
  • Rank difference is the absolute gap between the ranks of the predicted-optimal and actual-optimal configurations.Configurations are ranked by performance score, with the least score assigned rank 1 and the highest score rank N.Source: §6.2 · p. 6

7 RESULTS

Across the results, rank-based models can identify near-optimal configurations even when performance predictions are inaccurate, while often requiring fewer measurements than residual-based approaches. The measurement advantage is greatest for harder-to-model systems, though residual-based approaches can use fewer samples when accurate models are easy to build.

7.1 RQ1: Can inaccurate models accurately rank configurations?

  • Figure 6 shows rank differences usually close to 0% of the configuration space, including systems with very large spaces.For example, SS3 has over three million possible configurations.Source: §7.1 · p. 6, Figure 6 · p. 7
  • For systems with performance-model error above 10% MMRE, rank difference remains below 4, showing that inaccurate models can still rank configurations.Across the three approaches, mean rank difference is 1.4 for rank-based, 0.77 for progressive sampling, and 0.939 for projective sampling.Source: §7.1 · p. 7
  • For SS20, rank-based sampling finds the fifth-best configuration with 33 measurements, versus 251 for progressive and 576 for projective sampling.The residual-based approaches find the optimal configurations more consistently on this system.Source: §7.1 · p. 8

7.2 RQ2: How expensive is a rank-based approach?

  • In easier-to-model systems SS1–SS4, rank-based sampling uses fewer measurements than projective but more than progressive sampling.For SS14–SS21, it always uses fewer measurements than residual-based approaches, with significant gains on SS19–SS21.Source: §7.2 · p. 8
  • Rank-based sampling uses substantially fewer measurements than residual-based approaches in most systems, with SS4 and SS8 as exceptions.Figure 9 presents measurement ratios as percentages of the projective-sampling measurement count.Source: §7.2 · p. 8, Figure 9 · p. 9
  • Rank-based models require fewer measurements in 17 of 21 cases, and use an order of magnitude fewer in 8 of 21 cases.Residual-based progressive sampling uses fewer measurements in four cases, where accurate models are easier to build.Source: §7.2 · p. 8

8 DISCUSSION

The discussion explains that ranking can support configuration optimization without accurate performance-value predictions and that sampling criteria can guide which modeling approach to use. Practitioners must balance measurement effort against the quality of the configuration found.

8.1 How is rank difference useful in configuration optimization?

  • Rank-based training targets predicted values correlated with actual performance values, and that correlation rises as the training set grows.The authors report that inaccurate models can still find an optimal configuration.Source: §8.1 · p. 9

8.2 Can inaccurate models be built using residual-based approaches?

  • Rank difference can be replaced by a correlation measure such as Pearson’s or Spearman’s, while residual-based sampling requires more data and lacks the same stopping signal.The paper says MMRE can serve as a stopping criterion, but residual-based approaches are not cost-effective for that purpose in the described setting.Source: §8.2 · p. 9

8.3 Can we predict the complexity of a system to determine which approach to use?

  • Choose residual-based approaches when model accuracy is high and rank-based sampling when accuracy is low.Both approaches use random sampling, but differ primarily in their termination criteria: MMRE-based measures versus rank difference.Source: §8.3 · pp. 9–10

8.4 What is the trade-off between the number of lives and the number of measurements?

  • The practitioner sets the number of lives before sampling; more lives require more measurements but can find a better-performing configuration.Two lives require few measurements but yield the highest minimum rank, while ten lives require many measurements and find the best-performing configuration; the experiments use three lives.Source: §8.4 · p. 10

9 RELIABILITY AND VALIDITY

The authors discuss reliability, validity, and limits of their evaluation. The SQLite analysis sampled 100 configurations and did not vary workloads.

9 RELIABILITY AND VALIDITY

  • External reliability is supported by clearly defined algorithms or public-domain implementations, with the work's data and code available online.The authors also state that subject systems come from different domains and are deployed in real-world settings.Source: §9 · p. 10
  • The authors define reliability as consistency of results, including whether independent researchers can reproduce the study.Source: §9 · p. 10
  • Validity concerns whether research investigates what it claims to investigate; internal validity asks whether observed treatment differences can be attributed to the treatments.Source: §9 · p. 10
  • SQLite evaluation sampled 100 configurations and did not vary benchmarks, leaving room for outliers and measurement bias.The authors limit the analysis to performance prediction for a given workload.Source: §9 · p. 10

10 CONCLUSION

The paper proposes using configuration ranks rather than requiring highly accurate performance models. Experiments find the approach effective on most subject systems while using fewer measurements, except where accurate models are already easy to build.

10 CONCLUSION

  • The proposed rank-based approach replaces the requirement for highly accurate models with ranks as the evaluation criterion, reducing the number of measurements needed to find an optimal configuration.Source: §10 · p. 10
  • Rank-preserving models can support configuration ranking despite low predictive accuracy, and the authors introduce rank-based sampling termination based on predicted values correlated with actual scores.The paper reports usefulness even for a model with accuracy as low as 26%.Source: §10 · p. 10
  • The rank-based approach finds optimal configurations for most subject systems using fewer measurements than residual-based approaches, except where accurate models are easy to build.Source: §10 · p. 10
Loading 1702.05701v2…