Product optimization in stepwise design

Product Optimization in Stepwise Design Don Batory1(B), Jeho Oh1, Ruben Heradio2, and David Benavides3 1The University of Texas at Austin, Austin, TX 78712, USA {batory,jeho}@cs.utexas.edu 2Universidad Nacional de Educaci´on a Distancia, Madrid, Spain [email protected] 3University of Seville, Seville, Spain [email protected] Abstract. Stepwise design of programs is a divide-and-conquer strategy to control complexity in program modularization and theorems. It has been studied extensively in the last 30 years and has worked well, although it is not yet commonplace. This paper explores a new area of research, finding efficient products in colossal product spaces, that builds upon past work. 1 To My Friend Egon Egon and I (Batory) first met at the “Logic for System Engineering” Dagstuhl Seminar on March 3–7, 1997. Egon presented his recent work on Abstract State Machines (ASMs) entitled “An Industrial Use of ASMs for System Documentation Case Study: The Production Cell Control Program”. I presented my work on Database Management System (DBMS) customization via feature/layer composition. I had not yet directed my sights beyond DBMS software to software development in general. At the heart of our presentations was the use and scaling of Dijkstra’s concepts of layering and software virtual machines [15] and Wirth’s notions of stepwise refinement [53]. The connection between our presentations was evident to us but likely no others. I was not yet technically mature enough to have a productive conversation with Egon then to explore our technical commonalities in-depth. Our next encounter was at a Stanford workshop on Hoare’s “Verifying Compiler Grand Challenge” in Spring 2006. Egon would make a point in workshop discussions and I would think: That is exactly what I would say! And to my delight as I learned later, Egon reacted similarly about my discussion points. At the end of the workshop, we agreed to explore interests and exchanged visits – I to Pisa and he to Austin. We wrote a joint paper [6] and presented it as a keynote at the June 2007 Abstract State Machine Workshop in June 2007. In doing so, I learned about his pioneering JBook case study [44]. Our interactions This work was partially funded by the EU FEDER program, the MINECO project OPHELIA (RTI2018-101204-B-C22), the TASOVA network (MCIU-AEI TIN201790644-REDT), and the Junta de Andalucia METAMORFOSIS project. https://doi.org/10.1007/978-3-030-76020-5_4 64 D. Batory et al. were a revelation to me as our thinking, although addressing related problems from very different perspectives, led us to similar world view. In this paper, I explain our source of commonality and where these ideas have been taken recently in my community, Software Product Lines (SPLs). 2 Similarity of Thought in Scaling Stepwise Design CentraltotheStepwise Design (SWD) of large programs is the scaling of a step to an increment in program functionality. A program is a composition of such increments. To demonstrate that such technology is possible, one must necessarily focus on the SWD of a single application (as in JBook [44]) or a family of related applications (as in SPLs) where stereotypical increments in functionality can be reused in building similar programs. These increments are features; think of features as the legos [49] of domain-specific software construction. The JBook [44] presented a SWD of a suite of programs: a parser, ASTs (Abstract Syntax Trees), an interpreter, a compiler and a JVM for Java 1.0. At each step, there is a proof that the interpretation of any Java 1.0 program P and the compilation and then JVM execution of Pproduced identical results. The divide-and-conquer strategy used in JBook centered on the Java 1.0 grammar. The base language was the sublanguage of Java imperative expressions (ExpI). For this sublanguage, its grammar, ASTs, interpreter, compiler and JVM were defined, along with a proof of their consistency, Fig. 1a. Then imperative statements (ΔStmI) were added to ExpI, lock-step extending its grammar, ASTs, interpreter, compiler, JVM and proof of their composite consistency, Fig. 1b.1 ExpI grammar interpreter compiler JVM interpreter consistency proof AST (a) ExpI ΔStmI + grammar grammar interpreter interpreter compiler compiler JVM interpreter JVM interpreter consistency interpreter consistency proof AST AST (b) ExpI ΔStmI + ΔExpC + grammar grammar grammar interpreter interpreter interpreter compiler compiler compiler JVM interpreter JVM interpreter JVM interpreter consistency interpreter consistency interpreter consistency proof AST AST AST (c) ExpI ΔStmI + ΔExpC + ΔStmC + ΔExpO + ΔExpE + ΔStmE + grammar grammar grammar grammar grammar grammar grammar interpreter interpreter interpreter interpreter interpreter interpreter interpreter compiler compiler compiler compiler compiler compiler compiler JVM interpreter JVM interpreter JVM interpreter JVM interpreter JVM interpreter JVM interpreter JVM interpreter consistency interpreter consistency interpreter consistency interpreter consistency interpreter consistency interpreter consistency interpreter consistency proof AST AST AST AST AST AST AST (d) Fig. 1. SWD of JBook. 1All extensions were manually defined – this is normal. Product Optimization in Stepwise Design 65 And then static fields and expressions (ΔExpC) were added, Fig. 1c, and so on until the complete syntax of Java 1.0 was formed, with its complete AST definitions, a complete interpreter, compiler and JVM for Java 1.0 too, Fig. 1d. The JBook was a masterful case study in SWD. It fit my SPL theory of features, where an application is defined by a set representations (programs, documents, property files, etc..). Features incrementally extend each representation so that they are consistent. Features could add new documents as well. An SPL follows the JBook example, but with important differences. Some programs can have different numbers of features and different features can implement identical functionalities in different ways.2This enables a family of related programs to be built simply by composing features. Each program in an SPL is defined by a unique set of features. If there are noptional features, the size of the SPL’s product space can be up to 2ndistinct programs/products. It is well-known that features obey constraints: selecting one feature may demand the selection and/or exclusion of other features. And there is a preferred order in which features are composed. It was discovered that a context sensitive grammar could define the product space of an SPL whose sentences are legal sequences of features. Such a grammar is a feature model [7]. A partial feature model for JBook is below (given that each of the sublanguages in its design is useful); the first line is a context free grammar. Notation “[T]” denotes feature Tis optional. Subsequent lines define propositional formulas as compositional constraints to make the grammar context sensitive: JBook : Expl [ΔStml] [ΔExpC] [ΔStmC] ... ; // constraints ΔExpC ⇒ΔStml; // if ΔExpC then so too must ΔStml ΔStmC ⇒ΔExpC; // if ΔStmC then so too must ΔExpC These are the basics of SPLs[4]; a more advanced discussion is in [5]. 3 SPL Feature Models and Product Spaces A feature model can be translated to a propositional formula φ[2–4]. This is accomplished in two steps: (1) the context free grammar is translated to a propositional formula φ, and (2) composition constraints are conjoined with φto produce φ. For example, the lone production of the JBook context free grammar, defined above, is translated to:3 φ=JBook ⇔(Expl)∧(ΔStml ∨ΔExpC ∨ΔStmC ∨...)⇒JBook  where each term is a boolean variable. The complete propositional formula φis: φ=φ∧(ΔExpC ⇒ΔStml)∧(ΔStmC ⇒ΔExpC) 2Much like different data structures implement the same container abstraction [8]. 3More involved examples and explanations are given in [2–4]. 66 D. Batory et al. Every solution of φcorresponds to a unique product (a unique set of features) in that SPL. Binary Decision Diagrams (BDD) and Sharp-SAT solvers (#SAT) can count the number of products of φ[12,21,32,40]. Industrial SPLs can have colossal product spaces. Consider the table below from [5,21]: Model #Variables #SAT-solutions Source axTLS 1.5.3 64 1012 http://axtls.sourceforge.net/ uClibc 201 50420 298 1050 https://www.uclibc.org/ Toybox 0.7.5 316 1081 http://landley.net/toybox/ BusyBox 1.23.2 613 10146 https://busybox.net/ EmbToolkit 1.7.0 2331 10334 https://www.embtoolkit.org LargeAutomotive 17365 101441 [26] 272 is a magic number in SPLs. If an SPL has 272 optional features, it has 2272 unique products. 2272≈1082 is a really big number :1082 is the current estimate of the number of atoms in the universe [46]. The LargeAutomotive SPL in the above table has a colossal space of 101441 products. That makes the largest numbers theoretically possible in Modern Cosmology look really, really small [35].4And there are even larger known SPLs(e.g., the Linux Kernel), whose size exceeds the ability of state-of-the-art tools to compute. Beyond admiring the size of these spaces, suppose you want to know which product in a space (or a user-defined subspace) has the best performance for a given a workload. Obviously, enumerating and benchmarking each product is infeasible. The immediate question is: How does one search colossal product spaces efficiently? A brief survey of current approaches is next. 4 Searching SPL Product Spaces To predict the performance of SPL products, a mathematical performance model is created. Historically, such models are developed manually using domainspecific knowledge [1,13]. More recently, performance prediction models are learned from performance measurements of sampled products. In either case, a performance model is given to an optimizer, which can then find near-optimal products that observe user-imposed feature constraints (e.g., product predicates that exclude feature Fand include feature G). 4.1 Prediction Models Models can estimate the performance of any valid product [17,37,42,43,54]. The goal is to use as few samples as possible to learn a model that is ‘accurate’. Finding a good set of training samples to use is one challenge; another is minimizing the variance in predictions. 4Still 101441 does pale in comparison to 10284265, the size of the space of texts a monkey can randomly type out, one text of which is Hamlet [34,36]or1040000, the size of the space of texts a monkey can type out, one text of which is this paper. Product Optimization in Stepwise Design 67 Let Cbe the set of all legal SPL products. 1st-order performance models have the following form: let $Pbe the estimated performance of an SPL product P∈C, where êPis the set of P’s selected features and $Fiis the performance contribution of feature Fi: $P= i∈êP $Fi(1) $Fimight be as simple as a constant (ci) or a constant-weighted expression [17]: $Fi=c0(2) or =c0+c1·n+c2·n·log(n)+c3·n2+... (3) where nis a global variable that indicates a metric of product or application ‘size’. The value for nis given; the values of constants (ci) must be ‘learned’. 1st-order performance models are linear regression equations without (feature) interaction terms. Such models are inaccurate. Let $Fij denote the performance contribution of the interaction of features Fiand Fj, which requires both Fiand Fjto be present in a product; $Fij =0otherwise. 2nd-order models take into account 2-way interactions: $P=⎛ ⎝ i∈êP $Fi⎞ ⎠+⎛ ⎝ i∈êP j∈êP $Fij⎞ ⎠(4) Models with n-way interactions add even more nested-summations to (4)[42]. Manually-developed performance models [1,9,13] are different as they: – Identify operations [ O1.. ] invoked by system clients; – Define a function $Okto estimate the performance of each operation Ok; – Encode system workloads by operation execution frequencies, where νkis the frequency of Ok;and – Express performance $Pof a program Pas a weighted sum of frequency times operation cost: $P= k νk·$Ok(5) Features complicate the cost function of each operation, where the set of features of product P∈Cbecomes an explicit parameter of each Ok: $P= k νk·$Ok(êP) (6) In summary, manual performance models include workload variances in their predictions, whereas current SPL performance models use a fixed workload. Workload variations play a significant role in SPL product performance. To include workloads in learned models requires relearning models from scratch or transfer learning which has its own set of issues [23].5 5Transfer learning is an automatic translation of one performance model to another. 68 D. Batory et al. 4.2 Finding a Near-Optimal is NP-Hard The simplest formulation of this problem, namely as linear regression equations, is NP-Hard [52]. Here’s a reformulation of Eq. (1) as a 0–1 Integer Programming Problem. Let 1i(P) be a boolean indicator variable to designate if feature Fiis present (1i(P)=1) or absent (1i(P)=0)inP.RewriteEq.(1)as: $P= i∈êP $Fi= i $Fi·1i(P) We want to find a configuration cnear to minimize $P,Eq.(7). To do so, convert Eq. (7) into a inequality with a cost bound b,Eq.(8). By solving Eq. (8) a polynomial number of times (progressively reducing b) we can determine a near optimal performance $cnear and cnear’s features (the values of its indicator variables): min P∈C($P) = min P∈C i $Fi·1i(P)(7) min P∈C i∈ê $Fi·1i(P)≤b(8) Prop Formula Linear Constraint Linear Inequality Fig. 2. Prop Formula to an integer inequality. Recall a feature model defines constraints among features, like those in the “Prop Formula” column of Fig. 2. There are well-known procedures to translate a propositional formula to a linear constraint, and then to ≤ inequalities [16,22]. To optimize Eq. (8) correctly, feature model constraints must be observed. The general structure of the optimization problem described above is: find xsuch that cTx≤brewrite of Eq.(8) subject to Ax≤dfeature model constraints where x∈1n(xis an array of nbooleans), c∈Znand b∈Z(cis an array of n integers, bis an integer), A∈Zm×n(Ais an m×narray of integers), and d∈Zm(d is an array of nintegers). This is the definition of 0–1 Linear Programming, which is NP-Complete [52]. The NP-hard version removes bound band minimizes cTx. Product Optimization in Stepwise Design 69 4.3 Uniform Random Sampling Optimizers and prediction models [17–19,37–39,54] rely on ‘random sampling’, but the samples used are not provably uniform. Uniform Random Sampling (URS) conceptually enumerates all η=|C|legal products in an array A.An integer i∈[1..η ] is randomly selected (giving all elements in the space an equal chance) and A[i] is returned. This simple approach is not used because ηcould be astronomically large. Interestingly, URS of large SPLswas considered infeasible as late as 2019 [24,33]. An alternative is to randomly select features. If the set of features is valid, a product was “randomly” selected. However, this approach creates far too many invalid feature combinations to be practical [17,18,37,39,54]. Another approach uses SAT solvers to generate valid products [19,38], but this produces products with similar features due to the way solvers enumerate solutions. Although Henard et al. [19] mitigated these issues by randomly permuting the parameter settings in SAT solvers, true URS was not demonstrated. The top path of Fig. 3summarizes prior work: the product space is nonuniformly sampled to derive a performance model; samples are interleaved with performance model learning until a model is sufficiently ‘accurate’. That model is then used by an optimizer, along with user-imposed feature constraints, to find a near-optimal performing product. URS product space feature model user imposed feature constraints near-optimal performing product learn performance model use optimizer non-URS sample products Performance Model Approach Pure Uniform Random Sampling Approach Fig. 3. Different ways to find near-optimal products. In contrast, a pure URS approach (the bottom path of Fig. 3) uses neither performance models nor optimizers. Near-optimal products are found by uniformly probing the product space directly, and benchmarking the performance of sampled products using the required workload. User-imposed feature constraints simply reduce the space to probe. A benefit of URS is that it is a standard way to estimate properties accurately and efficiently of colossal spaces [14]. It replaces heuristics with no guarantees with mathematics with confidence guarantees. Note For some, it may not evident that URS could be used for optimization. In fact, Random Search (R S)algorithms [10,50] do exactly this – find near-optimal solutions in a configuration space. We present evidence later that URS requires many fewer samples than existing performance model approaches [30]. 70 D. Batory et al. 5 URS Without Enumeration Let η=|φ|be the size of an SPL product space whose propositional formula is φ.LetF=[F1,F2,..Fθ] be a list of optional SPL features. Randomly select an integer i∈[1..η] and compute s1=|φ∧F1|, the number of products with feature F1.Ifi≤s1, then F1belongs to the ith product and recurse on the subspace φ∧F1using feature F2. Otherwise ¬F1belongs to the ith product and recurse on subspace φ∧¬F1with i=i−|φ∧F1|using feature F2. Recursion continues until feature Fθis processed, at that point every feature in the ith product is known. Note Historically, Knuth first proposed this algorithm in 2012 [25]; Oh and Batory reinvented and implemented it in 2017 using classical BDDs [30]. Since then other SAT technologies were tried [11,32,40]. (A #SAT solver is a variant of a SAT solver: instead of finding a solution of φ efficiently, #SAT counts φsolutions efficiently.) The most scalable version today is by Heradio et al. and uses reduced BDDs [21], which in itself is surprising as for about a decade, SAT technologies have dominated feature model analysis. Given the ability to URS a SPL colossal product space, how can a nearoptimal product for a given workload be found? That’s next. 6 Performance Configuration Space (PCS) Graphs Let Cdenote the product space of φ, where η=|φ|=|C|. Imagine that for every product P∈Cwe predict or measure a performance metric $(P) for a given benchmark. By “performance metric”, we mean any non-functional property of interest of P(response time, memory size, energy consumption, throughput, etc.). A small $ value is good (efficient) and a large $ value is bad (inefficient). An optimal product Pbest in Chas the smallest $ metric:6 ∃Pbest ∈C:∀P∈C:$(Pbest)≤$(P)(9) For large C, creating all (P,$(P)) pairs is impossible... but imagine that we could do so. Further, let’s normalize the range of $ values: Let $(Pbest)=0be the best performance metric and let $(Pworst)=1betheworst.Nowsortthe (P,$(P)) pairs in increasing $(P) order where $(Pbest)=0isfirstand$(Pworst)=1 is last, and plot them. The result is a Performance Configuration/Product Space (PCS) graph, Fig. 4a. This graph suggests that PCS graphs are continuous; they are not. PCS graphs are stair-stepped, discontinuous and nondifferentiable [27] because consecutive products on the X-axis encode discrete decisions (features) that can make discontinuous jumps in performance, Fig. 4b. 6To maximize a metric, negate it. Product Optimization in Stepwise Design 71 $(c) 1 η1 $(c) 1 η 1 (a) (b) Fig. 4. Normalized PCS graphs. Example Suppose product Pihas feature Fand Fis replaced by Gin Pi+1.IfFincrements performance by .01, say, and Gincrements performance by .20, there will be a discontinuity from $(Pi)and$(Pi+1)ina PCS graph. Note Every PCS graph is monotonically non-decreasing. The latter means that consecutive products on the X-axis, like Piand Pi+1,mustsatisfy $(Pi)≤$(Pi+1). Many products in Cmay have indistinguishable performance values/metrics because their differing features have no impact on performance, leading to $(Pi)=$(Pi+1). Random Search (R S)is a family of numerical optimization algorithms that can be used on functions that are discontinuous and non-differentiable [10,50]. The simplest of all RSalgorithms is the Best-of-n-Samples below. Here we use URS for sampling: 1. Initialize x with a random product in the search space. 2. Until a termination criterion is met (n−1 samples) repeat: 2.1 Sample a new product y in the search space. 2.2 If $(y)<$(x) set x=y. 3. Return x. Listing 1.1. Best-of-n-Samples How accurate is the returned product? An answer can be derived by exploiting a PCS graph’s monotonicity, next. 78 D. Batory et al. –H264 is a video encoder library for H.264/MPEG-4 AVC format written in C. With 16 features and 1152 configurations, Sintel trailer encoding times were measured, see Fig. 12aand –BerkeleyDBC is an embedded database system written in C. With 18 features and 2560 configurations, benchmark response times were measured. Note its multiple “stairs” or vertical leaps. See Fig. 12b. Figure 12a–b are Complete PCS graphs – meaning all products are plotted. This is possible when configuration spaces are tiny. But what about SPLs with colossal spaces? What then? A number of techniques were tried, and the simplest performed best: – Randomly select n=100 or n=200 configurations, as 100–200 points are sufficient resolution for a graph in a paper, – Predict the performance or build-and-benchmark each sample, – Sort the samples from best-performing to worst, –Letpibe the ith best performance. Plot a PCS graph using the npoints {(xi,yi)}n i=1={(i n+1,pi)}n i=1. Example. ToyBox 0.7.5 provides Android systems with a collection of Linux command-line utilities within a single executable. It has 316 features and 1081 configurations [45]. Build size was measured. Its PCS graph, Fig. 12c, was produced with n=100, although the graph for n=200 was identical. 11 Future Work and Next Steps There is a hunger in Software Engineering research for more scientific approaches to be used, where mathematics can help solve fundamental design problems. The use of mathematics is evident in the work of B¨orger et al. on ASMs and the JBook [44]; so too in the area of SPLs. Software design indeed has a mathematical foundation, but perhaps not how Dijkstra, Hoare, and Wirth initially envisioned. Science must deliver quite a lot before it can overcome Cowboy Programming [48]. The Science of Software Design will answer questions that were unanswerable previously. This holds for finding near-optimal products in colossal SPL product spaces, a practical problem whose roots are found in early work on SWD. Given the ability to URS such spaces, an entire world of prior results on RSis now applicable. The simplest RSalgorithm, Best-of-n-Samples, can answer scientific questions that prior approaches could not. Namely, given any two of (confidence of answer, accuracy of answer, and number of samples to take), the third can be computed. Perhaps other RSalgorithms may be analyzable as well. Software Engineering research is fad-driven – the latest is Machine Learning (ML). ML also can provide answers to questions that couldn’t be answered before. We showed in Sect. 7that near-optimal results can be accompanied with accuracy or confidence metrics – to give precision about returned results that Product Optimization in Stepwise Design 79 could not be determined before. Or that the number of samples to take is no longer a guess – it can be precisely computed. And in Sect. 8, URS can also provide more accurate answers than performance models with less work (fewer samples), although these results need to be refreshed as they used small product spaces (what was available at that time). Today’s open question is whether the provisional results in this paper scale to colossal spaces. In this paper, URS may have been offered unintentionally as a tool to solve all analysis problems. Far from the truth, URS is but one in an ever-increasing sophisticated arsenal of techniques that can be used. Coupled with domainspecific knowledge, URS tools will be even better. URS will likely become a lowerbound on what can be accomplished and accepted (w.r.t. accuracy, confidence, and work) in future work. If so, we have indeed made progress. To Egon. You and your work continue to inspire me and others. Thank you. Acknowledgments. We thank the referees for their helpful comments on this paper. References 1. Agrawal, S., Chaudhuri, S., Narasayya, V.R.: Automated selection of materialized views and indexes in SQL Databases. In: VLDB (2000) 2. Apel, S., Batory, D., K¨astner, C., Saake, G.: Feature-Oriented Software Product Lines. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37521-7 3. Batory, D.: Feature Models, Grammars and Propositional Formulas. In: SPLC (2005) 4. Batory, D.: Automated Software Design Volume 1. Lulu.com (2020) 5. Batory, D.: Automated Software Design Volume 2. in development (2022) 6. Batory, D., B¨orger, E.: Modularizing theorems for software product lines: the JBook case study. JUCS 14(12) (2008) 7. Batory, D., O’Malley, S.: The Design and Implementation of Hierarchical Software Systems with Reusable Components. ACM TOSEM (1992) 8. Batory, D., Singhal, V., Thomas, J., Sirkin, M.: Scalable software libraries. In: ACM SIGSOFT (1993) 9. Batory, D.S., Gotlieb, C.C.: A unifying model of physical databases. In: ACM TODS (1982) 10. Bergstra, J., Bengio, Y.: Random search for hyper-parameter optimization. J. Mach. Learn. Res. (2012) 11. Chakraborty, S., Fremont, D.J., Meel, K.S., Seshia, S.A., Vardi, M.Y.: On parallel scalable uniform SAT witness generation. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 304–319. Springer, Heidelberg (2015). https://doi.org/ 10.1007/978-3-662-46681-0 25 12. Chakraborty, S., Meel, K., Vardi, M.: A scalable and nearly uniform generator of SAT witnesses. In: CAV (2013) 13. Chaudhuri, S.: An overview of query optimization in relational systems. In: PODS (1998) 14. Devore, J.: Probability and Statistics for Engineering and the Sciences. Cengage Learning (2021) 15. Dijkstra, E.W.: The Structure of ‘THE’-multiprogramming System. CACM (1968) 80 D. Batory et al. 16. Emmanuel, J.: Integer Linear Programming - Binary (0–1) Variables (2021). https://www.youtube.com/watch?v=-3my1TkyFiM 17. Guo, J., Czarnecki, K., Apel, S., Siegmund, N., Wasowski, A.: Variability-aware performance prediction: a statistical learning approach. In: ASE (2013) 18. Guo, J., White, J., Wang, G., Li, J., Wang, Y.: A genetic algorithm for optimized feature selection with resource constraints in software product lines. J. Syst. Softw. 84, 2208 (2011) 19. Henard, C., Papadakis, M., Harman, M., Le Traon, Y.: Combining multi-objective search and constraint solving for configuring large software product lines. In: ICSE (2015) 20. Heradio, R.: Derivation of Sample Set Size. Private Correspondence with Batory (2020) 21. Heradio, R., Fernandez-Amoros, D., Galindo, J., Benavides, D., Batory, D.: Uniform and Scalable Sampling of Highly Configurable Systems. In Submitted (2021) 22. Hodes, L.: Solving problems by formula manipulation in logic and linear inequalities. Artif. Intell. 3, 165–174 (1972) 23. Jamshidi, P., et al.: Transfer learning for performance modeling of configurable systems: an exploratory analysis. In: ASE (2017) 24. Kaltenecker, C., Grebhahn, A., Siegmund, N., Guo, J., Apel, S.: Distance-based sampling of software configuration spaces. In: ICSE (2019) 25. Knuth, D.E.: The Art of Computer Programming, Fascicle 1: Bitwise Tricks and Techniques; Binary Decision Diagrams, vol. 4. Addison-Wesley Professional, New York (2009) 26. Krieter, S., Th¨um, T., Schulze, S., Schr¨oter, R., Saake, G.: Propagating configuration decisions with modal implication graphs. In: ICSE (2018) 27. Marker, B., Batory, D., van de Geijn, R.: Understanding performance stairs: elucidating heuristics. In: ASE (2014) 28. MathIsFun. Percentiles. https://www.mathsisfun.com/data/percentiles.html 29. MathIsFun. Standard Deviation Formulas (2019). https://www.mathsisfun.com/ data/standard-deviation-formulas.html 30. Oh, J., Batory, D., Myers, M., Siegmund, N.: Finding near-optimal configurations in product lines by random sampling. In: FSE (2017) 31. Oh, J., Gazzillo, P., Batory, D., Heule, M., Myers, M.: Percentile Calculations for Randomly Searching Colossal Product Spaces. Technical Report TR-18-05, Dept. of Computer Science, University of Texas at Austin (2018) 32. Oh, J., Gazzillo, P., Batory, D., Heule, M., Myers, M.: Scalable Uniform Sampling for Real-World Software Product Lines. Technical Report TR-20-01, Dept. of Computer Science, University of Texas at Austin (2020) 33. Plazar, Q., Acher, N., Perrouins, G., Devroey, X., Cordy, M.: Uniform sampling of SAT solutions for configurable systems: are we there yet? In: Software Testing, Verification, and Validation (2019) 34. Saibian, S.: Sbiis Saibian’s Large Number Site. https://sites.google.com/site/ largenumbers/home 35. Saibian, S.: The Largest Numbers Theoretically Possible in Modern Cosmology. https://sites.google.com/site/largenumbers/home/2-1/Largest Numbers in Science 36. Saibian, S.: Larger Numbers in Probability, Statistics, and Combinatorics (2021). https://sites.google.com/site/largenumbers/home/2-1/Large Numbers in Probability 37. Sarkar, A., Guo, J., Siegmund, N., Apel, S., Czarnecki, K.: Cost-efficient sampling for performance prediction of configurable systems. In: ASE (2015) Product Optimization in Stepwise Design 81 38. Sayyad, A.S., Ingram, J., Menzies, T., Ammar, H.: Scalable product line configuration: a straw to break the camel’s back. In: ASE (2013) 39. Sayyad, A.S., Menzies, T., Ammar, H.: On the value of user preferences in searchbased software engineering: a case study in software product lines. In: ICSE (2013) 40. Sharma, S., Gupta, R., Roy, S., Meel, K.: Knowledge compilation meets uniform sampling. In: Logic for Programming, Artificial Intelligence, and Reasoning (LPAR) (2018) 41. Siegmund, N., et al.: Dataset for Siegmund (2012). http://fosd.de/SPLConqueror 42. Siegmund, N., et al.: Predicting performance via automated feature-interaction detection. In: ICSE (2012) 43. Siegmund, N., Grebhahn, A., Apel, S., K¨astner, C.: Performance-influence models for highly configurable systems. In: FSE (2015) 44. St¨ark,R.,Schmid,J.,B¨orger, E.: Java and the Java Virtual Machine: Definition, Verification, Validation. Springer-Verlag, Heidelberg (2001). https://doi.org/ 10.1007/978-3-642-59495-3 45. Toybox Website (2018). http://landley.net/toybox/ 46. Villanueva, J.: How Many Atoms Are There in the Universe? https://www. universetoday.com/36302/atoms-in-the-universe/ 47. Wikipedia. Beta Distribution. https://en.wikipedia.org/wiki/Beta distribution 48. Wikipedia. Cowboy Coders. https://en.wikipedia.org/wiki/Cowboy coding 49. Wikipedia. Lego. https://en.wikipedia.org/wiki/Lego 50. Random Search. https://en.wikipedia.org/wiki/Random search 51. Wikipedia. 68–95-99.7 Rule (2019). https://en.wikipedia.org/wiki/68%E2%80 %9395%E2%80%9399.7 rule 52. Wikipedia. Integer Programming (2021). https://en.wikipedia.org/wiki/Integer programming 53. Wirth, N.: Program Development by Stepwise Refinement. CACM (1971) 54. Zhang, Y., Guo, J., Blais, E., Czarnecki, K.: Performance prediction of configurable software systems by fourier learning. In: ASE (2015)