Statistical Debugging for Real-World Performance Problems

1 Statistical Debugging for Real-World Performance ProblemsLinhai SongShan Lu University of Wisconsin Madison{songlh, and implementation defects that lead to inefficientcomputation widely exist in software. These defects are dif-ficult to avoid and discover. They lead to severe performancedegradation and energy waste during production runs, andare becoming increasingly critical with the meager increaseof single-core hardware Performance and the increasing con-cerns about energy constraints. Effective tools that diagnoseperformance Problems and point out the inefficiency rootcause are sorely state of the art of Performance diagnosis is pre-liminary. Profiling can identify the functions that consumethe most computation resources, but can neither identifythe ones that waste the most resources nor explain detectors can identify specific type of in-efficient computation, but are not suited for diagnosing gen-eral Performance Problems .}

2 Effective failure diagnosis tech-niques, such as Statistical Debugging , have been proposedfor functional bugs. However, whether they work for per-formance Problems is still an open this paper, we first conduct an empirical study to un-derstand how Performance Problems are observed and re-ported by Real-World users. Our study shows that statisticaldebugging is a natural fit for diagnosing Performance prob-lems, which are often observed through comparison-basedapproaches and reported together with both good and bad in-puts. We then thoroughly investigate different design pointsin Statistical Debugging , including three different predicatesand two different types of Statistical models, to understandwhich design point works the best for Performance diagno-sis. Finally, we study how some unique nature of perfor-mance bugs allows sampling techniques to lower the over- Shan is now with University of to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page.

3 Copyrights for components of this work owned by others than ACMmust be honored. Abstracting with credit is permitted. To copy otherwise, or republish,to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from 14,October 20 24, 2014, Portland, OR, 2014 ACM 978-1-4503-2585-1/14/10.. $ of run-time Performance diagnosis without extendingthe diagnosis and Subject [Software Engi-neering]: Software/Program Verification Statistical meth-ods; [Software Engineering]: Testing and Debugging Debugging aidsGeneral TermsLanguages, Measurement, Performance ,ReliabilityKeywordsempirical study; Performance diagnosis; perfor-mance bugs; Statistical debugging1. MotivationImplementation or design defects in software can lead toinefficient computation, causing unnecessary performancelosses at run time. Previous studies have shown that thistype of Performance -related software defects1widely existin Real-World [10, 21, 24, 35, 41].

4 They are difficult for de-velopers to avoid due to the lack of Performance documenta-tion of APIs and the quickly changing workload of modernsoftware [21]. A lot of Performance bugs escape the in-housetesting and manifest during production runs, causing severeperformance degradation and huge energy waste in the field[21]. Making things worse, the negative impact of these per-formance Problems is getting increasingly important, withthe increasing complexity of modern software and workload,the meager increases of single-core hardware Performance ,and the pressing energy concerns. Effective techniques to di-agnose Real-World Performance Problems are sorely state of practice of Performance diagnosis is prelimi-nary. The most commonly used and often the only availabletool during diagnosis is profiler [1, 38]. Although useful,profilers are far from sufficient. They can tell where com-putation resources are spent, but not where orwhycompu-tation resources arewasted.

5 As a result, they still demand ahuge amount of manual effort to figure out the root cause2of Performance will refer to these defects as Performance bugs or Performance prob-lems interchangeably following previous work in this area [21, 24, 37].2In this paper, root cause refers to a static code region that can causeinefficient start_bulk_insert(ha_rows rows){..- if (!rows)- { //slow path where caching is not used- DBUG_VOID_RETURN;- }- rows = rows/m_tot_parts + 1;+ rows = rows ? (rows/m_tot_parts + 1) : 0;..//fast path where caching is usedDBUG_VOID_RETURN;}Figure 1: A Real-World Performance bug in MySQL (the - and + demonstrate the patch)Figure 1 shows a Real-World Performance problem inMySQL. MySQL users noticed surprisingly poor per-formance for queries on certain type of tables. Profil-ing could not provide any useful information, as the topranked functions are either low-level library functions, likepthreadgetspecificandpthreadmutexloc k,or simple utility functions, likehakeycmp(key com-parison).

6 After thorough code inspection, developers fi-nally figured out that the problem is in functionstartbulkinsert, which does not even get ranked bythe profiler. The developer who implemented this functionassumed that parameter-0 indicates no need of cache, whilethe developers who wrote the caller functions thought thatparameter-0 indicates the allocation of a large buffer. Thismis-communication led to unexpected cache-less execution,which is extremely slow. The final patch simply removes theunnecessary branch in Figure 1, but it took developers a lotof effort to figure recently, non-profiling tools have been proposed tohelp diagnose certain type of Performance Problems . Forexample, X-Ray can help pin-point the configuration entryor input entry that is most responsible for poor Performance [7]; trace analysis techniques have been proposed to figureout the Performance -causality relationship among systemevents and components [11, 48].

7 Although promising, thesetools are still far from automatically identifying source-codelevel root causes and helping figure out source-code level fixstrategies for general Performance automated Performance -bug detection tools havebeen proposed recently, but they are ill suited for perfor-mance diagnosis. Each of these tools detects one specifictype of Performance bugs, such as inefficient nested loops[37], under-utilized data structures [46], and temporary ob-ject bloat [12, 44, 45], through static or dynamic programanalysis. They are not designed to cover a wide variety ofperformance bugs. They are also not designed to focus onany specific Performance symptom reported by end users,and would inevitably lead to false positives when used forfailure Can we learn from functional failure diagnosis?Automated failure diagnosis has been studied for decadesfor functional bugs3.

8 Many useful and generic techniques[16, 19, 20, 22, 29, 50] have been proposed. Among thesetechniques, Statistical Debugging is one of the most effec-tive [20, 22, 29]. Specifically, Statistical Debugging collectsprogram predicates, such as whether a branch is taken, dur-ing both success runs and failure runs, and then uses statisti-cal models to automatically identify predicates that are mostcorrelated with a failure, referred to as failure predictors. Itwould be nice if Statistical Debugging can also work for di-agnosing Performance Statistical Debugging is useful for performancebugs is still an open question. Whether it isfeasibleto applythe Statistical Debugging technique to Performance problemsis unclear, not to mentionhowto apply the it feasible to apply Statistical Debugging ?The prereq-uisites for Statistical Debugging are two sets of inputs, oneleading to success runs, referred to asgood inputs, and oneleading to failure runs, referred to asbad inputs.

9 They areeasy to obtain for functional bugs, but may be difficult forsome Performance functional bugs, failure runs are often easy to tellfrom success runs due to clear-cut failure symptoms, such ascrashes, assertion violations, incorrect outputs, and , it is straightforward to collect good and badinputs. In the past, the main research challenge has beengenerating good inputs and bad inputs that are similar witheach other [50], which can improve the diagnosis some Performance bugs, failure runs could be dif-ficult to distinguish from success runs, because executionslowness can be caused by either large workload or mani-festation of Performance study is needed to understand whether statis-tical Debugging is feasible for Real-World Performance bugsand, if feasible, how to obtain good inputs and bad to conduct effective Statistical Debugging ?

10 The ef-fectiveness of Statistical Debugging is not guaranteed by theavailability of good and bad inputs. Instead, it requires care-ful design of predicates and Statistical models that are suit-able for the problem under predicates and Statistical models have been de-signed to target different types of common functional example, branch predicates and function-return predi-cates have been designed to diagnose sequential bugs [29,30]; interleaving-related predicates have been designed to di-agnose concurrency bugs [6, 20]; LDA Statistical model [5]has been used to locate failure root causes that have weaksignals. What type of predicates and Statistical models, if3 Any software defects that lead to functional misbehavior, such as incorrectoutputs, crashes, and hangs. They include semantic bugs, memory bugs,concurrency bugs, and , would work well for Performance diagnosis is still anopen ContributionsThis paper presents a thorough study of Statistical debuggingfor Real-World Performance Problems .