Data races are one of the most difficult types of bugs in concurrent multithreaded systems. It requires significant time and cost to accurately detect bugs in complex largescale programs. Although many race detection techniques have been proposed by various researchers, none of them are effective in all aspects. In this paper, we compare the performance of five recent dynamic race detection techniques: FastTrack, Acculock, Multilock-HB, SimpleLock+, and causally precedes (CP) detection. We experimentally demonstrate the strengths and weaknesses of these dynamic race detection techniques in terms of their detection capability, running time, and runtime overhead using 20 benchmark programs with different characteristics. The comparison results show that the detection capability of CP detection does not differ from that of FastTrack, and that SimpleLock+ generates the lowest overhead among the hybrid detection techniques (Acculock, SimpleLock+, and Multilock-HB) for all benchmark programs. SimpleLock+ is 1.2 times slower than FastTrack on average, but misses one true data race reported from Mutilock-HB on the large-scale benchmark programs. Data race, Dynamic detection, Multithreaded programming, Debugging, happens before, Lockset, Causally precedes. Manuscript received Dec. 1, 2015; revised Oct. 4, 2016; accepted Nov. 15, 2016 This is an Open Access article distributed under the term of Korea Open Government License (KOGL) Type 4: Source Indiction + Commercial Use Prohibition + Change Prohibition (http://www.kogl.or.kr/news/dataFileDown.do?dataIdx=71&dataFileIdx=2). Multithreading is an essential programming technique commonly used in fields ranging from operating systems to mobile-multimedia applications for the purpose of improving the performance or responsiveness of a particular program. However, writing a correctly executing multithreaded program is far more difficult than writing a correctly executing sequential program owing to the nondeterminism in concurrent thread executions. Nondeterministic thread interleaving may produce nondeterministic outputs for the same input when the threads are not properly synchronized. When this nondeterministic thread behavior causes a system failure or incorrect results, it is referred to as a concurrency bug. Owing to the difficulty of detection, concurrency bugs may be unintentionally left in a program after release, which can have disastrous results [1], [2] . A data race is one type of concurrency bug that occurs when two different threads access the same memory location without an ordering constraint enforced between the accesses, where at least one access is a write access [3] . Because a data race can easily occur and is very common, a large number of studies [4]-[18] on dynamic detection techniques have been conducted to accurately detect as many as data races as possible by analyzing the execution trace of a program. Among the previous techniques, several [4] , [5] , [17] proposed fundamental algorithms for developing precise or highcoverage dynamic race detection techniques. Based on these basic algorithms, some [6]-[16] proposed various techniques to increase the performance of the previous techniques. All of these dynamic detection techniques verified their superiority by showing the running time, runtime overheads, detection capability, and accuracy (ratio of false positives), which are the important factors for the practical use of a race detector. A low runtime slowdown frequently leads developers to use race detectors during the development phase of a concurrent program, which can increase the reliability of the program by rapidly removing problematic concurrency bugs. With the detection speed, the detection capability and accuracy should be considered to develop and select a race detection tool because a high detection capability implies a small number of repeated executions of a program for detection, and a high accuracy implies a low laborious effort to filter false warnings. In this paper, we analyzed the performance of state-of-the-art and current dynamic techniques in terms of detection speed, capability, and accuracy on the same platform for a fair comparison. We collected the performance data on these techniques through extensive experiments using the same benchmark programs and configurations. Our work makes the following specific contributions: • We select five pure dynamic data race detection techniques: FastTrack, Acculock, Multilock-HB, SimpleLock+, and Causally precedes (CP) detection. We evaluate their performance on the same platform with the same input. • We compare the running time, runtime overhead, detection capability, and accuracy of all five detection techniques using 12 small programs containing various data races, and the most-used eight large-scale programs categorized into three groups with different numbers of access and synchronization events. • Our experiments show that Multilock-HB and CP-detection can accurately and precisely detect actually occurred and potential data races. However, both methods require significant processing time. In addition, we showed that SimpleLock+ has almost the same detection capability and accuracy as Multilock-HB, and generates a detection speed similar to that of FastTrack. The rest of this paper is organized as follows. Section II discusses previous studies in this area. In Section IV, we briefly review the dynamic data race detection techniques compared in this paper. In Section III, an analysis of these techniques based on the experimental results is presented. In Section V, we provide some concluding remarks regarding this research. There have been a number of studies on increasing the detection speed and capability of dynamic data race detection techniques with high accuracy, especially for Java programs. Here, we discuss the relevant research along two main axes: dynamic analysis and static analysis. For dynamic analysis techniques, we additionally describe their performance evaluation methods. [22] . Pacer was implemented on the Jikes RVM and compared the detection capability and runtime overhead to LiteRace using the DaCapo benchmark suite and SPEC JBB2000. A shortcoming of the HB detection technique is that it cannot detect hidden data races that are detectable in other thread interleaving sequences. To report hidden races as well as actually occurred data races, hybrid detection was introduced. This [13] is the first hybrid detection method that combines HB-relation and Lockset-based detection algorithms. Acculock and Multilock-HB [15] are epoch-based hybrid detectors based on Hybrid. Acculock provides a fast detection speed comparable to that of FastTrack, but may introduce additional false positives. Multilock-HB accurately detects actually occurred and potential data races; however, it incurs a large amount of computational runtime overhead. The latest study on hybrid detection [16] provides the fastest hybrid detection technique that may miss a data race when both accesses of the data race are protected by different locks. This study compared the detection capability and runtime slowdown among FastTrack, Multilock-HB, and SimpleLock+ on the same RoadRunner framework using the Dacapo and Grand benchmark suites. To relax the sensitivity to thread interleaving while maintaining the precision of HB detection, CP detection based on a CP relation [17] was recently proposed. The authors of [17] demonstrated that CP can detect more data races than HB detection, and compared the detection speed to HB detection using small-sized (86-49k LOC) benchmark programs. [23] using the small-sized IBM Contest benchmark suite and the parallel Java Grand benchmark programs (with a reduced data set). All algorithms were implemented in RVPredict. In this paper, we compare the detection speed, capability, and accuracy of the current pure dynamic data race detection techniques (FastTrack, Acculock, Multilock-HB, SimpleLock+, and CP) using the most-used large-scale benchmark suites without modification and small benchmark programs on the same platform. Detectors based on data flow analysis can report potential data races but produce many false alarms and are difficult to scale to large programs. The object use graph-based technique [31] reports object races using an approximation of the HB relation of accesses to an object by different threads. Chord [32] improved the precision of lockset computation using kobject context sensitivity. Follow-up research [33] refined this study using a conditional must not aliasing property to reduce false positives. Recent static detectors specialized in specific kinds of program structures or data races to improve precision and scalability. IteRace [34] is a set of three techniques that are specialized to the parallel loops for collections that are introduced in Java 8. CTADetector [35] uses static analysis to detect a misused CHECK-THEN-ACT idiom that is a composition of two operations where a check on the concurrent collection precedes an action. Dynamic data race detection algorithms can be categorized into Lockset, HB, and hybrid detection algorithms. Among them, Lockset algorithms are not used alone because of their high false-positive rate. Therefore, we exclude Lockset algorithms from our comparison. FastTrack CP detection is the latest dynamic detection method used to relax scheduling sensitivity and remove the possibility of false positives that may be generated by hybrid detection techniques. For a precise comparison of detection overhead and detection capability, we include CP detection in our comparison, although it has yet to be commonly used for program testing. FastTrack reduces the complexity of most VC comparisons (⊑) from O (n) to O (l) by introducing an epoch-VC comparison (≼). Herein, an epoch includes only a clock and a thread id (tid). The epoch is used to record the last write and read of the totally ordered writes and reads. Algorithm 1 shows the FastTrack algorithm. FastTrack maintains vector clocks C t and L m for each thread t and lock m. The clock entry C t (u) records the clock for the last event of thread u that happens before the current event of thread t. In Algorithm 1, E(t) returns the current epoch of thread t. The clock-update algorithm of FastTrack for the lock acquire and release, as well as for explicit synchronizations (fork and join), is the same as in previous VC-based race detectors including Djit+. Lock acquire: t acquires a lock m 1: Fork and Join: t creates u; t blocks until u terminates 3: FastTrack reports a write-read race if the last write access to shared memory location x does not occur before the current read access to x (line 6 of Algorithm 1). In addition, it reports a read-write race if the last read of totally ordered read access to x does not occur before the current write access to x (line 14 of Algorithm 1). In another case, FastTrack reports a read-write race if the VCs of the last read access and current write are not partially ordered (line 16 of Algorithm 1). Hybrid detection that combines HB and Lockset detection, and has its origins in Hybrid [10], aims to increase the detection capability by weakening the sensitivity to a thread interleaving sequence of HB detection. Hybrid detectors can report potential data races in a single execution trace. To detect additional potential data races, hybrid detectors monitor the sets of locks (locksets) that are protecting the shared memory accesses. In addition, they do not conduct vector clock operations for lock acquire and release events because the HB relation between two accesses of different threads owing to the lock acquire-release can be changed in other thread interleaving sequences. That is, a relaxed HB relation is used, which is held when two different accesses of different threads are ordered through explicit synchronizations such as a fork and join, with the exception of lock operations. For hybrid detection, Lockset is applied for two accesses that are not ordered through explicit synchronizations. The underlying idea of Lockset is that, to prevent data races, all accesses of multiple threads to a shared memory location must be protected through the same lock. Algorithm 2 shows the basic algorithm of Lockset.  Hybrid detection requires a high runtime overhead to accurately detect data races because it maintains the access history and the related information (the set of locks and clocks) for each access. Acculock first introduced an epoch representation, which was presented by FastTrack, into hybrid detection. In addition, Acculock only keeps a lockset that protects the last read access to shared memory location x for each thread. In addition, it maintains the intersection of the two locksets protecting the last and the previous write accesses to x when these two accesses are not ordered through explicit synchronizations. That is, Acculock keeps only one lockset and epoch for write accesses to x regardless of the number of threads. Therefore, Acculock has a low memory requirement and a fast detection speed comparable to that of FastTrack. However, Acculock generates additional false positives when nested locks are used because it must maintain the subset of the access information. Acculock provides O(nlogl) complexity for the number of elements l in a lockset. Multilock-HB was introduced to remove the false positives of Acculock. To remove the false positives, Multilock-HB maintains all read and write access histories for each thread. Each item of a read and write access history includes a lockset and a clock for each read and write access. To avoid duplicated race warnings to the same shared memory location and to reduce the runtime overhead, Multilock-HB provides an optimization technique but requires a large amount of memory and time for large-scale real-world programs. The complexity of Multilock-HB is O(nmlogl) for the number of threads n, the length of access events m, and the number of elements l in a lockset. SimpleLock+ was proposed to improve the performance of the previous accurate hybrid detector. SimpleLock+ improves the performance based on two assumptions: (1) most data races are caused by accesses without any lock protection to a shared memory location, and (2) the distance between two accesses that cause a data race is not long. Based on the first assumption, SimpleLock+ only reports a data race when at least one access of a race is not protected through any locks (zero-locked access). This technique replaces the set intersection operations of the previous hybrid detection into Boolean operations that verify the existence of locks protecting the accesses. Based on the second assumption, SimpleLock+ maintains information on the reads and writes after the last explicit synchronization of all threads for each shared memory location. This information includes two clocks for a read and write, and two flags indicating whether a read or write not protected by any lock during the clocks occurs. Owing to the above two improvement techniques, SimpleLock+ provides O(n) complexity for the number of threads n, and generates a fast detection speed comparable to that of FastTrack. However, SimpleLock+ may miss data races if two accesses of different threads that are not ordered by  CP detection reports a data race by checking the CP relation between two accesses to a shared memory location. A CP relation is a new relation proposed in 2012 that generalizes an HB relation to detect more data races without introducing false positives or false negatives. CP detectors can detect potential data races as well as actually occurred data races in one execution trace. Although detected data races are a subset of the results from hybrid detectors, CP detectors do not report false warnings that hybrid detectors may generate owing to the algorithmic limitations of hybrid detection. A CP relation is a subset of an HB relation, and can partially detect potential data races that may be missed by HB detectors. Figure 1 shows an example of these data races. In Fig. 1 , HB detectors cannot detect a data race on x because a lock release of t1 happens before the lock acquisition of t2, masking the lack of synchronization between the write of t1 and the read of t1 on x. However, CP detection can predict this data race based on the definition of the CP (<< CP ) relation as follows: • << CP has a release-acquire edge between critical sections over the same lock that contains conflicting events. Herein, two events by different threads conflict if they access the same shared memory location and one of them is a write. • << CP has a release-acquire edge between critical sections over the same lock that contains CP-ordered events. • CP is closed under left and right compositions with HB. We compared the performance of five data race detection techniques: FastTrack (FT), Acculock (AC), Multilock-HB (ML), SimpleLock+ (SL+), and CP detection (CP). The evaluation was conducted on the same platform using 21 Java benchmark programs. Time, detection capability, and accuracy were considered. The race detection techniques being evaluated are categorized into two types: online (runtime) and offline detection. FT, AC, ML, and SL+ are VC-based online detection techniques. We implemented four online detection techniques in the RoadRunner framework as independent tools. RoadRunner is a dynamic analysis framework for Java programs, which provides event handlers for memory and synchronization operations that are executed during program execution. These event handlers can be overridden to implement user-defined data race detectors. RoadRunner relies on the just-in-time compiler to optimize the instrumentation code and tool dispatches. For the offline detection technique (CP), we borrowed the implementation from [18] for the most efficient implementation. CP was implemented in RVPredict, which is available at http://fsl.cs.illinois.edu/rvpredict/. RVPredict first stores the execution traces (including shared data accesses and synchronization events) into a database, and then conducts a predictive analysis based on these traces. Methodology The evaluation was conducted on a machine with a 3.40 GHz Intel Core i7-3770K (quad core) CPU and 32 GB of RAM running 64-bit Ubuntu 12.4 OS. The SSD free space was 10 GB, which was used for recording the execution traces of CP. We installed H2 database engine 1.4 to manage the execution traces on our SSD. We conducted out experiments on 21 different benchmark programs, which were classified into two groups. The first group includes small example programs that were used in the previous work [18]: critical, airline, account, pingpong, bbuffer, bubblesort, bufwriter, mergesort, raytracer-s, montecarlo-s, and moldyn-s. In this first group, raytracer-s, montecarlo-s, and moldyn-s are modifications of raytracer, montecarlo, and moldyn from the parallel Java Grand benchmark suite, respectively, and shrink the internal data size to reduce the program execution time. The second group includes large-scale real-world applications that were selected from the parallel Java Grand benchmark suite and Dacapo benchmark suite (9.12 bach), which were generally used for comparing the performance of race detection algorithms in previous research [9] selected programs that are executed on the RoadRunner framework from the Dacapo benchmark suite. Table 1 lists brief descriptions of these large-scale benchmark programs. We configured moldyn, raytracer, and montecarlo to create four worker threads, used BenchSizeA as a dataset, and used the default settings for all other benchmark programs. Detailed characteristics such as the lines of code, the number of threads, and the number of memory accesses are listed in Tables 2 and  3 . Runtime detection techniques track all accesses to the elements of shared arrays only for small programs. For reasons of efficiency, we did not track each array element for largescale programs. We measured the running time and slowdowns of the target techniques. The running time of a detection technique is the total detection time, which includes the instrumentation time and execution time of the detection algorithm. A slowdown of a detection technique is the ratio of the instrumented running time to the original running time of the benchmark program. For FT, AC, ML, and SL+, we measured the runtime instrumentation and detection time on the RoadRunner framework. For CP, we summed the instrumentation, logging, and offline detection times. We executed and measured each detection technique 10 times using the same input, and averaged the results. Similar to the measurement of the slowdown of each detection technique, we conducted 10 executions for each technique using the same input. We counted only the number of warnings for distinct shared variables during the 10 executions. With the total number of reported data races, we also specified the number of true data races only when the hybrid detectors reported more races than FT. For the 12 small benchmark programs, we verified the true data races by analyzing the source code and execution trace manually because these programs are simple enough for manual analysis. For the eight large-scale programs, we randomly and heuristically inserted noises by calling a Java sleep () method before the accesses to shared variables by threads because we could not find a systematic method or an automatic tool to precisely verify a data race in these large-scale programs. The insertion of the sleep () method can allow for variety in the thread interleaving sequences of a program. Then, we analyzed the executions using FT to precisely check whether the shared variables cause data races. We considered only shared variables that were reported by the hybrid detectors. When we could not expose a data race to a shared variable, we decided that the warning for the shared variable was not a true positive. Table 2 lists the running times and the number (total warnings and true positives) of data races for the five dynamic detection techniques studied (FT, AC, SL+, ML, and CP) on small benchmark programs. We measured the total running time instead of the runtime overhead because CP is an offline detection technique based on the analysis of the execution-trace information recorded in a database. In addition, Table 3 lists the runtime overheads and the number (total warnings and true positives) of data races of the online detection techniques (FT, AC, SL+, and ML) on large-scale benchmark programs. We could not run CP on the large-scale benchmark programs owing to a lack of disk space required to record the executiontrace information generated by CP. A general computer that is used by a developer has difficulty in handling the excessive amount of execution traces, which exceeds dozens of gigabytes using CP because of its significant processing and memory requirements. Results and Analysis The CP was shown to be about 8.2 times slower than FastTrack, but the detection capability was the same for all small benchmark programs array, critical, airline, account, pingpong, bbuffer, bubblesort, bufwriter, mergesort, raytracers, montecarlo-s, and moldyn-s. Based on this fact, we can infer that the types of potential data races that CP can detect, as shown in Fig. 1 , are not general. All hybrid detectors (SL+, AC, and ML) reported more data races than FastTrack, and SL+ generated the lowest amount of overhead for all benchmark programs. The overhead of SL+ was 1.2 times that of FastTrack on our large-scale benchmark programs, but SL+ missed one true data race that ML reported on raytracer. ML provides the highest detection capability without the possibility of false positives that may be introduced by AC, and detected 29 more true data races than FT on our benchmark programs. However, the runtime overhead of ML is 13.7 times that of FT on large-scale benchmark programs, and reaches 159.5 times on jython. Figure 3 illustrates the running time of the five dynamic detection techniques, which are listed in Table 2 . As shown in Fig. 2 , the CP is about 9.3-times slower than FastTrack for the 12 small benchmark programs array, critical, airline, account, pingpong, bbuffer, bubblesort, bufwriter, mergesort, raytracers, montecarlo-s, and moldyn-s. In particular, CP requires a long detection time for long-running programs that generate many access events (montecarlo-s), as shown in Fig. 3 . With the exception of CP, the online detection techniques show a similar running time on the 12 small benchmark programs. ML shows a particularly high runtime overhead for bubblesort and montecarlo-s, which have many threads, and generates many explicit synchronization and volatile-variable To analyze the performance correlation between the types of events (memory access and synchronization events) and the online detection techniques, we measured the runtime overhead of these techniques on large-scale benchmark programs. Because of the very high overhead of ML on jython, we limited the length of history that ML must maintain for each thread to 3,000. Figure 4 illustrates the runtime overhead of the online detection techniques listed in Table 3 . To easily distinguish the program groups that incur high detection overhead, we classified the benchmark programs into three categories, as shown in Fig. 5 . Categories 1 is the program group of longrunning programs that generate many shared memory accesses. Category 2 generates many synchronizations (explicit synchronizations and volatile-variable access) but generates a smaller number of shared memory accesses than Category 1. Category 3 includes programs that generate a relatively small number of shared memory accesses and synchronizations. As shown in Fig. 4 , ML generates the highest runtime overhead for all of the large-scale benchmark programs. In particular, ML generates very high overhead (532.6 times slower than the original program on average) for Category 1 and Category 2. The overhead of ML on jython is more than 1,228.4 times, which is 159.5 times that of FT. FT generates the lowest amount of runtime overhead, and SL+ and AC are 1.2 times and 1.5 times slower than FT, respectively. In addition, FT, SL+, and AC generate slightly more overhead for Category 1 programs, which are long-running programs. As a result, FT shows the smallest amount of overhead, and SL+ was shown to be the fastest among the four other dynamic detection techniques studied. The detection capability of CP detection is the same as that for FastTrack in all of the small benchmark programs. On the small benchmark programs, all of the hybrid detection techniques (AC, SL+, and ML) additionally detected two .. 9: } 10: .. 11:} potential data races in bufwriter, which were missed by FT. In addition, SL+ missed two potential data races in mergesort and raytracer-s, which were detected by AC and ML. We verified that all these potential data races are true data races that can be exposed in other thread interleaving sequences. For the large-scale benchmark programs, the hybrid detectors reported more data races than FastTrack. Among the hybrid detectors, AC and ML reported the same data races, and SL+ missed one in raytracer, which is identical to that missed by SL+ in raytracer-s. Although AC detected the same data races as ML on our benchmark programs, AC has the possibility of additional false positives, which were not reported by SL+ and ML, as described in Section II. Except for raytracer, hybrid detectors reported 30 more data races than FT on large-scale benchmark programs. Among these data races, we verified that 26 data races in sunflow are real data races, which can be exposed by delaying thread accesses to a shared variable during program execution using the Java sleep() method, as shown in Fig. 6 . Figure 6 shows the part of the sunflow source code that we used to verify the data races that are reported from hybrid data races. We detected 31 data races using FT by inserting "sleep (40)" into delaying thread access to a shared memory location to which primitiveList is pointing. We presented the performance comparison results of five recent dynamic data race detection techniques: FastTrack, Acculock, SimpleLock+, Multilock-HB, and CP detection. We conducted experiments on the same platform using 12 small and 8 large-scale benchmark programs. The comparison results show that CP detection has the highest amount of overhead among the five detection techniques, although the detection capability of CP detection does not surpass that of FastTrack on our benchmarks. SimpleLock+ generated the lowest amount of runtime overhead among the hybrid detection techniques (Acculock, SimpleLock+, and Multilock-HB) on all benchmarks, which is 1.2 times that of FastTrack on average. Unlike Acculock, SimpleLock+ does not introduce additional false positives into Multilock-HB, but misses 3.6% of the true data races reported by Mutilock_HB. Therefore, SimpleLock+ can be a good option for the frequent detection of data races during the development process, and MultiLock-HB can be used for the late stages of development for a more thorough check. We believe that our performance comparison in various aspects of the program characteristics can provide useful information for further research to improve the efficiency of current data race detection techniques. [1] N.G. Leveson and C.S. Turner, "An Investigation of the Therac-25 Accidents," Comput., vol. 26, no. 7, July 1993, pp. 18-
The second REF focused on detection methods rather than tools, and compared five different algorithms: FastTrack, Acculock, Multilock-HB, SimpleLock+, and casually precedes (CP) detection.
Experimental Performance Comparison of Dynamic Data Race Detection Techniques
Etri Journal
Computer Science