ΔInfer: Context-Sensitive Delta Inference for Identifying Workload-Dependent Performance Bottlenecks

PROJECT SUMMARY

Software hangs can be caused by expensive operations in responsive actions (such as time-consuming operations in UI threads). Some of the expensive operations depend on the input workloads, referred to as workload-dependent performance bottlenecks (WDPBs). WDPBs are usually caused by workload-dependent loops (i.e., WDPB loops) that contain relatively expensive operations. Traditional performance testing and single-execution profiling may not reveal performance-problem-inducing WDPBs due to incorrect assumptions of workloads. To address these issues, we propose the ΔInfer approach that predicts WDPB loops under large workloads via inferring iteration counts of WDPB loops using complexity models of the workload size. ΔInfer incorporates a novel concept named context-sensitive delta inference that consists of two parts: temporal inference for inferring the complexity models of different program locations, and spatial inference for identifying WDPB loops as WDPB candidates. We conducted evaluations on two popular open source GUI applications, 7-Zip and Notepad++, and identified highly impactful WDPBs that cause 10 performance bugs.

PEOPLE

Faculty

Tao Xie

Students

Xusheng Xiao (PhD Student)

Collaborators

Shi Han and Dongmei Zhang (Software Analytics Group, Microsoft Research Asia)

PUBLICATIONS

1. Xusheng Xiao, Shi Han, Tao Xie, and Dongmei Zhang. Context-Sensitive Delta Inference for Identifying Workload-Dependent Performance Bottlenecks. In Proceedings of the 2013 International Symposium on Software Testing and Analysis (ISSTA 2013), Lugano Switzerland, July 2013. Download: [PDF][BibTeX].

SUBJECTS

1. 7-Zip: 7-Zip is a file archiver with the high compression ratio, supporting archive file formats of 7z, zip, and so on. 83% of 30081 users rated this applications as recommended. (All the rating data is collected on 12/23/2011.) The version of 7-Zip used for our study is 9.20, which consists of 86 files and 7,280 LOCs. Our study focused on the file manager of 7-Zip (7-Zip FM), a GUI tool that enables users to easily navigate and manipulate files for archiving.
2. Notepad++: Notepad++ is a text editor and source code editor for Windows, supporting tabbed editing and several programming languages (e.g., C/C++, Java, and C#). 94% of 14950 users rated this applications as recommended. It is ranked as the most popular free open source text editor that is using by 23% of the developers in a recent survey. The version of the Notepad++ used for our study is 5.9.0, which consists of 396 files and 155,300 LOCs.

Figure 2. Screenshots Of The Subject Applications

SCENARIOS

Table 1. Scenarios For The Evaluations.

As we do not have the developer knowledge of these subject applications, we choose scenarios that would manipulate inputs, so that the performance of the applications will vary based on workloads. Based on the scenarios, we characterize some inputs as performance-relevant workload parameters. The details of the scenarios and focused workload parameters are shown in Table 1. Column "Nbr" shows the scenario number, Column "Scenario" shows the actions performed in each scenario, and Column "W. Param" shows the workload parameters that we use to vary the focused workload values. S1-S5 are scenarios for the 7-Zip file manager, and S6-S10 are scenarios for Notepad++.

For Notepad++, we configure it to use the "Word Wrap" mode, so that we can test its functionality of wrapping words and other functionalities at the same time for each scenario. We executed the instrumented subject applications on each workload, performed the interactions described in each scenario, and collected the call-tree profiles after the executions.

WDPBs FOUND IN 7-ZIP

(a) (b)

Figure 3. Representative WDPBs In The 7-Zip File Manager.

Figure 3(a) shows two WDPBs found in Scenario S3. The first WDPB (PB_1) is caused by the method CPanel::OnRefreshStatusBar, which contains a non-trivial UI update operation (Line 4). PB_1 is invoked when a selection-change event is fired. The second WDPB (PB_2) is caused by the method GetSelectedItemsIndices, which contains a workload-dependent loop L (Lines 13-14). Let us assume that the number of files in the current folder is n; if a user selects a file after selecting all files, the selection-change event will be fired for each file. Such repeated firing will cause PB_1 to be invoked n times (refreshing the status bar n times), and PB_2 to be executed n2 times. Thus, when n is large, PB_1 and PB_2 would be very expensive and cause the 7-Zip file manager to hang.

Figure 3(b) shows the WDPBs for the Scenarios S1, S2, S3, and S5. The first WDPB (PB_3) is RefreshListCtrl. In these scenarios, when the user opens/creates a folder or renames/deletes a file, the method RefreshListCtrl is invoked to refresh the list-view control. In RefreshListCtrl, the linear-workload-dependent loop is captured by the complexity transition (RefreshListCtrl, {GetItemRelPath, _listView.InsertItem, ...}). Inside the loop, GetItemRelPath computes the path prefix of a file using customized string-concatenation operations, which create temporary objects and destroy them after the concatenation. This computation results in intensive creations/destructions of temporary objects when GetItemRelPath is invoked to compute the paths for each file. Another WDPB is _listView.SortItems that invokes ListView_SortItems. ListView_SortItems is a UI library call that repetitively invokes CompareItems to sort the files, behaving like an implicit loop whose complexity model is nlog(n) in theory. ΔInfer correctly identifies this implicit loop with a complexity transition from a constant order to a power-law order. Due to the inefficient implementation of retrieving file properties for comparison, this implicit loop results in a WDPB on large workloads.

WDPBs FOUND IN NOTEPAD++

(a) (b)

Figure 4. Representative WDPBs In Notepad++.

Figure 4 (a) shows the WDPB caused by WrapLines that appears in every scenario. In these scenarios, when the user opens a file or modifies the content of the file (S7 and S10), the method WrapLines is invoked to recompute the word-wrapping data structures by invoking WrapOneLine. WrapOneLine computes the layout of a line, creating temporary objects and dynamically allocating memory chunks for the computation results; such computation is quite expensive when the workload is large.

Figure 4 (b) shows the method Document::FindText that searches for a matching word. The second WDPB is Document::FindText for S9. ΔInfer identifies that Document::FindText contains a linear-workload-dependent loop and performs string comparison to find the matching word in the document. Although the cost per iteration is not high, the workload value in terms of # chars is easy to become huge in practice. For example, searching a 10MB file for matching a character not present in the document would cause the loop in Document::FindText to execute 10M times. Thus, word search is usually considered expensive; and many editors or viewers (such as Adobe PDF Viewer) spawn a separate thread to do so.

PERFORMANCE BUGS

Table 2 shows the statistics of the detected performance bugs in our studies. Column "#Bug" shows the number of performance bugs. Column "#DB" shows the number of performance bugs confirmed by searching their bug database, and Column "#Forum" shows the number of performance bugs confirmed by responses from their forums. Column "#Pending" shows the number of performance bugs waiting to be confirmed.

Table 2. Performance Bugs.

We reported the bugs to the project's forum, and the responses of the developers of 7-Zip are quite encouraging. They confirmed the bugs caused by RefreshListCtrl in S1, S2, S3, and S4, (4 out of 5 bugs reported), and plan to fix the bugs in the next version. Although the bug in S1 was reported in their bug database (# 3193577), our approach further identifies the WDPBs as the root cause of the bug. Capturing the bug caused by OnRefreshStatusBar in S3 demonstrates the advantages of using predictive models in our approach. Such bugs are difficult for traditional performance testing to detect. This newly detected bug has been dormant since it was introduced in version 4.25 beta (released on 2005-08-01), and is not fixed in the latest version 9.22 (released on 2011-4-18). After we reported the bug at the forum, the developers confirmed the bug and plan to fix it in the next version.

For Notepad++, the performance problem of wrapping words in Scenario S6 is confirmed as the bug # 2909745 in their forum. Moreover, our approach further identifies that WrapLines causes performance bugs for Scenarios S7, S8, and S10 after the document is modified. We are waiting for their responses for these not-yet-confirmed bugs. For the performance bug of opening a file, the developers confirmed that Notepad++ did not have good performance on large files, and stated that a patch can be applied to improve the performance. We reported the new bug of finding a word in S9, and are still waiting for the response.