{'fraction_non_alphanumeric': 0.031926520660809615, 'fraction_numerical': 0.012800033628988189, 'mean_word_length': 4.858761236300948, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
OJXPerf: Featherlight Object Replica Detection for Java Programs

Memory bloat is an important source of inefficiency in complex production software, especially in software written in managed languages such as Java. Prior approaches to this problem have focused on identifying objects that outlive their life span. Few studies have, however, looked into whether and to what extent myriad objects of the same type are identical. A quantitative assessment of identical objects with code-level attribution can assist developers in refactoring code to eliminate object bloat, and favor reuse of existing object(s). The result is reduced memory pressure, reduced allocation and garbage collection, enhanced data locality, and reduced re-computation, all of which result in superior performance. We develop OJXPerf, a lightweight sampling-based profiler, which probabilistically identifies identical objects. OJXPerf employs hardware performance monitoring units (PMU) in conjunction with hardware debug registers to sample and compare field values of different objects of the same type allocated at the same calling context but potentially accessed at different program points. The result is a lightweight measurement, a combination of object allocation contexts and usage contexts ordered by duplication frequency. This class of duplicated objects is relatively easier to optimize. OJXPerf incurs 9% runtime and 6% memory overheads on average. We empirically show the benefit of OJXPerf by using its profiles to instruct us to optimize a number of Java programs, including well-known benchmarks and real-world applications. The results show a noticeable reduction in memory usage (up to 11%) and a significant speedup (up to 25%).


Introduction
Memory bloat is a common problem in managed languages, such as Java and C#. The problem is particularly severe in large, production software, which employs layers of abstractions, third-party libraries, and evolves over time into complex systems not comprehendible by any single developer. Furthermore, these programs run for a long time (several months at a time), giving them an opportunity to grow their memory footprint and become a source of major problems in production environments often shared by several other programs.
An object that is not reclaimed by the garbage collector (GC) but neither read nor written any more is considered to be "leaked". A memory leak happens in managed languages because useless objects remain unreclaimed by the GC because of unnecessary references to them. Additionally, memory spikes occur in managed languages because of accumulated objects that are yet to be garbage collected. Memory bloat (whether due to leaks or GC) results in high memory pressure and poor performance. A lot of prior work exits to detect object leaks [21, 38, 57, 59-62, 64, 65] and improve GC [5,10,27,36,49,66].
However, there is another cause of memory bloat and inefficiency that has hardly been studied -replica objects -which is the focus of this paper. Two objects are replicas if their contents are identical. Two objects are shallow replicas if their fields are bitwise identical; and deep replicas if the transitive closure of the constituent objects and their respective fields values are bitwise identical. When two objects are bitwise identical (shallow replicas), their transitive closures are also the same. However, when two objects are not bitwise identical and the difference occurs on one or more fields that are object references, it becomes necessary to chase those references to disprove that the contents of those objects are not identical. After chasing all object references, if we can prove that their contents are identical, then such two objects are deep replicas.
There is a temporal aspect to replica objects: one may regard two objects as replicas either because they were identical at the time (or a window) of observation or for their entire lifetime. Two objects are mutable replicas if they are identical to each other, but they may independently evolve during their lifetimes; whereas two objects are immutable replicas if they are identical to each other and are also immutable during their lifetimes.
There are two performance dimensions to replica objects: total memory consumption and total number of memory accesses. On the one hand, an object may be large in size and replicated only a few times, and such replicas still contribute to the overall memory bloat; also, an object may be small in size but replicated many times, which also contributes to memory bloat; both these cases are worth optimizing to remove the replicas. On the other hand, an object may be small in size and replicated only a few times, but the program may be accessing these few replicated objects a lot of times; although this situation is not memory bloat, it can still have a significant consequence to the overall performance since it increases the memory footprint at the CPU cache level, squanders potential memory reuse [6], and often results in redundant re-computations [38,54].
Having described the landscape of object replication (deep vs. shallow, some time window vs. full lifespan, mutable vs. immutable, and memory size vs. access counts), we now scope this problem to a tractable subset driven by pragmatic tool-development factors. First, instrumenting every allocation and memory access to identify object replicas leads to excessive runtime overheads; we seek for a lightweight tool that can collect profiles in production rather than in test-only environments; we guarantee the analysis accuracy with the theoretical bounds of a sampling technique we use. Second, deep replica comparison is unachievable without running something analogous to the garbage collector, which can introduce high overheads and require runtime modifications, making it less adaptable; hence we restrict our tool to only shallow object comparison. Third, if two objects are not replicas for their entire life span, they are not easy to optimize, and hence we consider only those objects that are replicas for their entire duration. We do not enforce objects to be immutable for replica detection. Finally, our tool regards two or more objects as replicas only if they were allocated in the same calling context; the observation drives this restriction that it is significantly easy to refactor such code to optimize compared with optimizing replica objects allocated from myriad code locations. We emphasize that we want to be able to monitor replicas and prioritize them by their access frequency.
OJXPerf, developed to meet these factors, monitors object allocations and accesses at runtime via statistical sampling. The key differentiating aspect of OJXPerf, compared to a large class of existing profilers, is its ability to detect object replicas with minimal byte code instrumentation and no prior knowledge of programs makes it applicable in the production environment. A thorough evaluation of several real-world applications shows that pinpointing object replicas offers new avenues to understanding performance losses; aggregating replica objects into one or a few objects reduces the memory footprint, eliminates redundant computations, and enhances performance.

Observation
With the help of OJXPerf, Figure 1 quantifies the ratio of object replicas over the total number of objects in several real applications listed at [32] and two popular Java benchmark suites-Dacapo 9.12 [2] and Renaissance [44], showing that replicated objects are pervasive in modern Java software packages. Based on many case studies investigated in this paper, we observe that object replication is the symptom of the following kinds of inefficiencies.
Input-sensitive Inefficiencies. Repeatedly using the same input to instantiate a Java class shows up as repeatedly creating objects with the same content. Listing 1 shows a problematic method readNext from Parquet-MR [29], which contains the Java implementation of the Parquet format. This method is invoked in a loop, and in each invocation, it creates a new object bytes, shown on line 93, and initializes this object via input stream "in", as shown on line 94. We run Parquet-MR using Parquet-Column as its input. The Parquet-Column input is a columnar storage format for Hadoop; this format provides efficient storage and encoding of data. As line 94 in Listing 1 shows, each time the readNext method is invoked, it creates a copy of input contents (variable "in"), and uses this copy to initialize many objects "bytes" (object replication). None of the existing profilers, such as JXPerf [51] and LDoctor [50], can identify such object replicas since they are designed only to recognize the redundancies happening at the same memory location. Instead, objects bytes are allocated in disjoint memory regions.
Algorithmic Inefficiencies. Suboptimal choices of an algorithm often show up as object duplications. As a practical example, Findbugs [45] divides a graph into tiny-size blocks and creates an object for each block instead of creating a single object for the whole graph. Consequently, most of the created objects have the same content due to good value locality among adjacent blocks.
Data Structural Inefficiencies. Like suboptimal algorithms, poor data structures can easily introduce object replicas as well. For instance, in matrix multiplication, sparse matrices with a dense format can yield a high proportion of objects with the same content.
The major lessons that can be learned from this paper: • Object replicas are not uncommon in real Java applications.
• Sampling-based measurement based on hardware counters and debug registers can provide good insights and incur significant low overhead. • Developing OJXPerf that efficiently interacts with off-the-shelf JVM and Linux OS in the production environment requires careful design. • The call path of object allocation and source code attribution in a GUI are particularly useful for users to identify actionable optimization.

Paper Contributions
In this paper, OJXPerf makes the following contributions: • Develops a novel object-centric profiling technique. It provides rich information to guide optimizing object replicas in JVM-based programs, such as Java and Scala.  • Employs PMU in conjunction with hardware debug registers and minimal byte code instrumentation, which typically incurs 9% runtime and 6% memory overheads. • Quantifies the theoretical lower and upper bounds of replication ratios of OJXPerf's statistical approach. • Applies to unmodified Java (and languages based on JVM, e.g., Scala) applications, the off-the-shelf Java virtual machine, and Linux operating system, running on commodity CPU processors, which can be directly deployed in the production environment. • Provides intuitive optimization guidance for developers. We evaluate OJXPerf with popular Java benchmarks (Dacapo [35], NPB [16], Grande [9], SPECjvm2008 [14], and the most recent Renaissance [44]) and more than 20 real-world applications. Guided by OJXPerf, we are able to obtain significant speedups by eliminating object replicas in various Java programs. We have upstreamed some of the patches to the software repositories.

Paper Organization
The paper is organized as follows. Section 2 covers the related work and distinguishes OJXPerf. Section 3 offers some background knowledge. Section 4 depicts OJXPerf's methodology. Section 5 describes the implementation details of OJXPerf. Section 6 discusses the theoretical guarantee of OJXPerf's analysis accuracy. Section 7 evaluates OJXPerf's accuracy and overhead. Section 8 describes case studies of OJXPerf. Section 9 discusses the threats to validity. Finally, Section 10 presents our conclusions.

Redundancy detection
Cross-object analysis

Probabilistic analysis
Sampling with hardware support *OEP identifies mergeability of live objects while OJXPerf pinpoints object replicas regardless of their liveness.
Memoizelt [15] **We obtain the average overhead described in the paper of these tools.

Related Work
Performance profiling techniques abound in the Java community, which fall into two categories: hardware and software approaches. Each category can be further classified into hotspot and inefficiency analyses. We also compare the related Java tools in table 1.

Software Approaches
Hotspot Analysis. Netbeans Profiler [42], JProfiler [19], YourKit [24], VisualVM [13], and Oracle Developer Studio Performance Analyzer [11] are hotspot analysis profilers, which identify execution hotspots in CPU time or memory usage. They typically introduce negligible overhead by leveraging OS timers as the sampling engines to deliver periodic samples. The hotspot analysis is indispensable but fails to tell whether a resource is being used in a productive manner and contributes to a program's overall efficiencies. A hotspot does not need to be an inefficient code region and vice versa. Hence, a heavy burden is on users to make a judgment on whether the reported hotspots are actionable.
Inefficiency Analysis. Unlike hotspot analysis, inefficiency analysis tools identify code regions leading to resource wastage instead of resource usage. Cachetor [31] combines value profiling and dependence profiling to pinpoint operations that repeatedly generate an identical value. MemoizeIt [15] identifies methods that repeatedly perform identical computation. JOLT [48] identifies and optimizes object churn in a virtual machine. Toddler [39] identifies redundant memory load operations in loop nests. The follow-up work [50] applies a static-dynamic analysis to reduce Toddler's overhead. However, it identifies inefficiencies within a small number of suspicious loops instead of the entire program. Xu et al. [58] introduce copy profiling that optimizes data copies to remove the objects that carry copied values, and the method calls that allocate and populate these objects. Their follow-up work [63] develops practical static and dynamic analyses that identify inefficiently-used containers, such as overpopulated containers and underutilized containers. They also present a run-time technique [56] to identify reusable data structures to avoid frequent object allocations. OEP [37] identifies mergeability among live objects, which requires the measurement of object reachability. In contrast, OJXPerf analyzes objects allocated in the same call path regardless of their liveness. OEP leverages bytecode instrumentation, which incurs orders of magnitude of overhead compared to OJXPerf.
OJXPerf is a profiler but applies a hardware approach to address a different inefficiency problem -object replication.

Hardware Approaches
There are many hardware-assisted profilers. In this paper, we review only PMU-or debug register-assisted Java profilers.
Hotspot Analysis. Linux Perf [34], Async-profiler [43], and Oprofile [3] employ PMU as the sampling engines to deliver periodic samples. PMU-based hotspot profilers offer slightly better intuition than the OS timer-based ones since they can classify hotspots according to various forms of performance metrics collected from PMU, such as instruction numbers, cache misses, bandwidth, and many others. However, they are not panaceas; users still have to distinguish inefficient hotspots from efficient ones manually.
Inefficiency Analysis. Sweeney et al. [20] develop a system that provides a graphical interface to alleviate the difficulty in interpreting PMU results. Hauswirth et al. [25] present vertical profiling that captures and correlates performance problems across multiple execution layers (application, VM, OS, and hardware). Georges et al. [23] study methods exhibit similar and dissimilar behaviors by measuring the execution time for each method invocation using PMU. Lau et al. [33] present a technique that allows a VM to determine whether an optimization improved or degraded by measuring CPU cycles. Remix [18] employs PMU to identify inter-thread false sharing on the fly. JXPerf [51] detects redundant memory operations by using PMU to sample memory locations accessed by a program and using debug registers to monitor subsequent accesses to the same location.
Orthogonal to the aforementioned inefficiency analysis profilers, OJXPerf addresses a different inefficiency problem with a different usage of PMU and debug registers. To the best of our knowledge, OJXPerf is the first lightweight sampling-based profiler to pinpoint object replicas in Java.

Background
We introduce some essential facilities that OJXPerf leverages based on Java virtual machines (JVM) and CPU processors.
Java Virtual Machine Tool Interface (JVMTI). JVMTI, a native programming interface of the JVM, is loaded during the initialization of the JVM. JVMTI provides a VM interface for the full breadth of tools that need access to VM state, including but not limited to profiling, debugging, monitoring, thread analysis, and coverage analysis tools.
Hardware Performance Monitoring Unit (PMU). PMU is hardware built inside a processor to measure its performance parameters. We can measure parameters like instruction cycles, cache hits, cache misses, branch misses, and many others, depending on the supported hardware. PMU supports lightweight measurement.
Intel processors also support Precise Event-Based Sampling (PEBS) [30]. PEBS is a profiling mechanism that logs a snapshot of the processor state at the time of the event, allowing users to attribute performance events to actual instruction pointers (IPs). Also, PEBS provides an effective address (EA) at the time of the sample when the sample is for a memory load or store instruction. In PEBS, the event type may be chosen from an extensive list of performance-related events to monitor, e.g., cache misses, remote cache hits, branch mispredictions. AMD processors provide similar capabilities via instruction-based sampling.
Hardware Debug Register. Modern x86 processors provide debug facilities for developers in debugging code and monitoring system behaviors. Such debug support is accessed using hardware debug registers. Hardware debug registers [17,47] enable trapping the CPU execution for debugging when the program counter (PC) reaches an address (breakpoint) or an instruction accesses a designated address (watchpoint). Hardware debug registers allow programmers to selectively enable various debug conditions associated with a set of four debug addresses because our current x86 processors have four debug registers.

Methodology
As previously alluded, we restrict the definition of object replicas to those allocated in the same calling context. Definition 4.1. Object Replicas: 1 and 2 are two objects that have the same allocation context. If the contents of 1 and 2 are identical, 1 is a replica of 2 and ⟨ 1 , 2 ⟩ is an object replication pair.
A straightforward detection approach is monitoring every allocation context and comparing all fields of all object instances created at that allocation context at any use points. However, performing such whole-heap object tracing can introduce a prohibitively high overhead (70~300× slowdown reported in [26]).
Instead of exhaustive duplication detection, OJXPerf takes advantage of sampling to perform lightweight replica detection. We neither compare all objects allocated in the same context nor compare all fields when comparing two objects. Instead, our algorithm chooses random fields (offsets in terms of memory locations) at random points.
Example 1 shows an object replica detection example that keeps allocating an object inside a while loop. As the while loop iterates 4 times, the program allocates a sequence of objects { 1 , 2 , 3 , 4 }, which have the same allocation context and are sorted by the allocation timestamp during program execution. First, in each loop iteration, we intercept the allocation of the object on line 3. This interception offers two pieces of information: 1) the calling context of allocation, and 2) the memory address range occupied by each object. We maintain this information for future use.
For all objects allocated on line 3 in this example, the context is the same but the object addresses can be different 1 . Second, when the program accesses an object (use point), e.g., lines 5 and 7, we can obtain the effective address of the access and map the address to the object it belongs to; furthermore, we can easily derive the relative offset of the access from the start address of the object; this relative offset guides us where to monitor another object allocated in the same context. Third, when the program accesses an object, we can read the contents of the location accessed. Given the nature of sampling, let's assume that memory-access samples occur on line 5 in iteration 1 of the loop (while accessing object 1 ) and line 7 in iteration 3 (while accessing object 3 ), as shown in Figure 2. Assume, the sample in iteration 1 for 1 on line 5 happens at the relative offset Off 1 from the beginning of the object and the value at Off 1 is 1 ; OJXPerf remembers the triple -line 5, Off 1 , and 1 -for future use. For the next allocation, 2 , we probabilistically skip and do nothing. When 3 starts to be accessed, we decide to monitor its contents at offset Off 1 , and hence arm a watchpoint to trap on access to offset Off 1 from the beginning of 3 . This watchpoint traps when the program accesses 3 on line 5. Let the contents at 3 + Off 1 be ′ 1 when the trap happens. We compare 1 and ′ 1 and if they are the same, 1 and 3 contribute towards the number of equivalent objects allocated in context line 3; otherwise they contribute towards non-equivalent objects allocated in context line 3.
The next sample happens on line 7, for the same object 3 at offset Off 2 in iteration 3 of the loop. Let the value at Off 2 for 3 be 2 . We remember the triple -line 7, Off 2 , and 2 -for future use. When 4 starts to be accessed in iteration 4 of the loop, we arm a watchpoint at address Off 2 from the beginning of 4 . This watchpoint traps when the program accesses 4 on line 7. Let the value at the trapped location be ′ 2 . As before, depending on whether 2 and ′ 2 are the same or not, they contribute towards equivalent or non-equivalent objects allocated in context line 3. Figure 2 shows that 1 equals to ′ 1 (the blue star), which means that the values stored in an offset Off 1 of 1 and 3 are the same. Also, the red star in Figure 2 shows that the values stored in an offset Off 2 of 3 and 4 are different ( 2 doesn't equal to ′ 2 ), which means that 3 and 4 must be two objects that have different contents. 1 two objects of different size, e.g., arrays allocated in the same context are easily ruled out of duplication due to size difference  Off 1 (Off 2 ) presents memory offset with value 1 ( 2 ) for Object 1 (Object 3 ). When a watchpoint trap of memory access happens at offset Off 1 (Off 2 ), OJXPerf compares their corresponding values 1 and ′ 1 ( 2 and ′ 2 ).
As the program continues, OJXPerf performs the same redundancy checks for other samples taken from objects { 1 , 2 , 3 , 4 }. Finally, if most of the comparisons (>60%, obtained from our experiments) report identical values among all detection pairs, we believe objects { 1 , 2 , 3 , 4 } suffer from object replicas with a high probability, which is quantified with our theoretical analysis in Section 6.

Implementation
OJXPerf is a user-space tool with no need for any privileged system permission. OJXPerf requires no modification to hardware, OS, JVM, and monitoring applications, making it applicable to the production environment. Conceptually, OJXPerf consists of two components: data-centric analysis and duplication detection. These two components are implemented within two agents: a Java agent and a JVMTI agent. Figure 3 overviews the design of these two agents. The Java agent instruments Java byte code execution to obtain each object's memory interval and allocation context. The JVMTI agent subscribes to Java thread creation to enable PMU. Upon each PMU sample, OJXPerf obtains the effective address of the monitored memory access and associates it with the Java object enclosing this address. Moreover, to identify object replicas, the JVMTI agent programs the debug registers to subscribe to watchpoints.

Java Agent
The Java agent monitors object allocation, which leverages java.lang.instrument API and ASM framework. The Java agent inserts pre-and post-allocation hooks to intercept each object allocation. Then, a user-defined callback is invoked on each allocation to obtain the object information, such as the object pointer, type, and size. For a given Java class we want to instrument, the Java agent scans the byte code of this class, instruments new, newarray, anewarray, and multianewarray, and obtains the memory range of every object following an existing technique [1].  How to present an object allocation is a challenging question. We adopt a simple and perhaps the most intuitive approach that developers can identify with -the allocation context leading to the object allocation. A Java application can often create multiple object instances via a single allocation site in a loop. All those objects will be represented by a single call path, which naturally aggregates numerous objects with similar behavior. OJXPerf leverages the AsyncGetCallTrace() [40] API provided by Oracle Hotspot JVM to determine the calling contexts at any point during the execution. OJXPerf then inserts a ⟨ , ⟩ pair into a map M, where is the memory range and is the allocation context.

JVMTI Agent
Implementing Sampling with PMU. The JVMTI agent leverages PMU to sample memory accesses. It subscribes to MEM_UOPS_ RETIRED:ALL_LOAD, a PMU precise event to sample memory loads. We empirically choose a sampling period to ensure OJXPerf can collect 20-200 samples per second per thread, which yields a fair tradeoff between runtime overhead and statistical accuracy [52]. Moreover, the JVMTI agent captures the calling contexts for both PMU samples and object allocations described in Section 5.1. To minimize synchronization, each thread collects PMU samples independently and maintains a thread-local compact calling context tree (CCT) [7], which stores the calling contexts of PMU samples and merges all the common prefixes of given calling contexts.
Examining Object Contents with Watchpoints. OJXPerf leverages debug registers to set up watchpoints, which traps the program execution when the designated memory addresses are accessed. Assume 1 and 2 are two distinct objects that have the same allocation context and 1 is created prior to 2 . Moreover, 1 and 2 have the same accessing context, then 1 and 2 form a ( 1 , 2 ) as object replicas. OJXPerf uses queues 1 and 2 to store samples taken from objects 1 and 2 , respectively. Upon a sample taken from 1 , OJXPerf uses a tuple ⟨Off , ⟩ to represent it and adds this tuple to queue 1 , as shown in Figure 4a. Off is the offset between the sampled address (i.e., the address of the PMU sample) and the starting address of 1 , and is the value stored at the sampled memory address. Upon a sample taken from 2 ,   OJXPerf not only adds a tuple ⟨Off m , ⟩ to queue 2 , but also retrieves a sample (⟨Off n , ⟩) from queue 1 and uses a debug register to set up a watchpoint at the offset Off n of 2 , as shown in Figure 4b. OJXPerf compares values at the the same offset Off n of 1 and 2 when the watchpoint is triggered. Watchpoint can be removed when it is triggered, and watchpoints are used for a single access.

Limited Number of Debug Registers.
Hardware offers only a small number of debug registers, which becomes a limitation if the PMU delivers a new sample, but all watchpoints are armed with addresses obtained from prior samples. OJXPerf employs a reservoir sampling strategy [46], which uniformly chooses between old and new samples with no bias. The basic idea of reservoir sampling is to assign a probability to each debug register and perform a replacement policy based on the probability. Prior work [53,55] has shown that reservoir sampling guarantees the fairness of the measurement with a limited number of debug registers.

Offline Data Analyzer and GUI
To generate a compact profile, which is essential for analyzing a large-scale execution, the offline data analyzer merges profiles from different threads. Object allocation call paths coalesce across threads in a top-down way if they are identical. All memory accesses with their call paths to the same objects are merged as well. Metrics are also summed up when call paths coalesce. The offline procedure typically takes less than one minute in our experiments. Furthermore, OJXPerf integrates its analysis visualization in Microsoft Visual Studio Code, which is shown in Figure 6.

Discussions
As a sampling-based approach, OJXPerf may introduce false positives and false negatives, which are elaborated in Section 7.1. Our theoretical analysis to be described in the next section bounds the analysis accuracy.

Theoretical Analysis
Since OJXPerf does not exhaustively check every field of an object for replication due to the sampling, we compute the lower and upper bounds of the analysis to quantify the replication factor. Definition 6.1. Replication Factor (RF) : For a set of objects that suffer from object replication, the replication factor is the probability of last accessed object to be bit-wise same as the current accessed object. We define as the ratio of the number of times that an object accessed is equivalent to another object accessed previously, to the total accesses of this set of objects. (1) Assume 1 and 2 are a pair of object under object replica detection. If all memory locations sampled from 2 have the same values as the corresponding locations in 1 ( 2 = 1 ), it is possible that 2 and 1 are two objects that have the same contents ( 2 ≡ 1 ) or the different contents ( 2 1 ). Here, we have three scenarios and each with a specific probability: • 2 = 1 and 2 ≡ 1 , the probability is ; • 2 = 1 and 2 1 , the probability is ; • 2 ≠ 1 , so 2 1 , the probability is . Obviously, we have + + = 1.
Then, the can be rewritten using , , as: Furthermore, we define as the probability of 2 = 1 when 2 1 . Then can be denoted as: Combine Equation (2) and Inequality (3), we have: Assume there are objects { 1 , 2 , ..., } belonging to the same calling context. These objects are divided into groups. Inside each group, the objects are identical with each other. Every group contains objects (1 ≤ ≤ , =1 = ), and 1 , 2 , ..., are sorted in an ascending order by group size. Based on these objects, there are 2 object pairs. Among these 2 object pairs, there will be =1 2 identical object pairs. Considering we can estimate identical object pairs ratio by + + = and Inequality (4), we can state: can be derived as: Focusing on =1 ( ) 2 , we can reconstruct it as: Since Furthermore, combining (5), (6), (7), (8), we then obtain Because represents the largest identical objects group size ratio, we know that this ratio is lower bounded by − . Next we show the upper bound of . Based on equation 5, we have: Focusing on ( 2 ) ( 2 ) , we have: We also have: We then denote = and 1 −1 = , equation 10 can be rewritten as: Combining with equation 9, we have this in-equation: Solving this in-equation, we then have: Focusing on in equation 2 and 3, we have: Solving it, we then have: Based on the in-equation 14, we have: We show how the interval of the largest identical objects group size ratio guides our optimizations in Section 7. In the applications we evaluated, we have not seen an application with a very high (we compute for each application via exhaustively checking every field of objects), which we further discuss here. For an application with inequivalent objects 1 , 2 , ..., that belong to the same calling context, high indicates that most of the contents of these objects are the same and only a few contents are different, which means these objects are partially replicated. It is worth noting that partially replicated objects can warrant some optimization to move redundant computations, such as approximate computing or data compression; however, it is out of the scope of this paper.
The theoretical analysis influences the design decisions in two aspects: on the one hand, the theoretical bounds guarantee the analysis accuracy of OJXPerf's sampling technique; on the other hand, the bounds, as metrics, help users determine whether the object replicas are significant for optimization.

Evaluation
We evaluate OJXPerf on a 36-core Intel Xeon E5-2699 v3 (Haswell) CPU clocked at 2.3GHz running Linux 4.8.0. The memory hierarchy consists of a private 32KB L1 cache, a private 256KB L2 cache, a shared 46MB L3 cache, and 128GB main memory. OJXPerf is compatible with JDK 1.5 and any of its successors. We run all applications with JDK 1.8.0_161.
We run these applications with different real inputs released with them or the real inputs that we can find to our best knowledge; the inputs control the parallelism configuration.
Replication. Figure 1 shows the replication ratios for more than 50 Java programs obtained from OJXPerf. We can see that several Java programs suffer from significant object replications (replication ratio > 15%). We optimize some of them, as shown in Section 8 under the guidance of OJXPerf. For some Java applications (e.g., gaussmix, log-regression, page-rank, scala-kmeans) with high replication ratios, we only obtain trivial speedups because these applications do not have any hotspot object replicas. For example, the top five object replicas' accessing times in Renaissance benchmark gaussmix are less than three. In this case, it is reasonable that there is no benefit to optimize these replicated objects that are used very few. We focus on the hotspot object replicas, which at least are accessed dozens of times.
OJXPerf is able to pinpoint many object replicas that are not reported by existing profilers and guide optimization choices. Table 2 summarizes the new findings identified by OJXPerf, which we further elaborate in Section 8. In Table 2, we report replication factor , , and lower bound factor , which are defined in Section 6. Table 2 shows that ranges from 0% to 53% and ranges from 65% to 100%, respectively. As a result, the lower bound factor is usually > 15%, which means that these Java applications at least have 15% objects suffering from object replication.
Optimization. It is worth doing the optimization to decrease the creations of objects with the same contents. To guarantee optimization correctness, we ensure the optimized codes do not change semantics for any inputs and pass the validation tests. To avoid system noises, we run each application 30 times and use a 95% confidence interval for the geometric mean speedup to report the performance improvement, according to a prior approach [51].
From Table 2, we can see that we are able to obtain nontrivial speedups by removing object replicas. The performance improvement comes from the reduction of heap memory usage, cache misses, and executed instructions, which are measured with jmap [12] and perf [34]. We detected the object replicas as shown in Table 2 without much effort. Object replicas often concentrate around only a few calling contexts making investigation relatively simpler; for example, in all of our case studies, we found the top five objects (sorted by replication factor) account for ∼37% of wholeprogram object replicas on average.

False Positives and Negatives
As a sampling-based tool, OJXPerf can introduce false negativesmissing some object replicas. However, the statistics theory guarantees the high probability of capturing object replicas that occur frequently. The false negatives do not hurt the insights obtained from OJXPerf because optimizing infrequently occurred object replicas typically receives trivial speedups.
OJXPerf can also introduce false positives -reporting object replicas that are not replicated because OJXPerf uses sampling instead of exhaustive checking. The false positives occur when most elements of the two objects are the same, with only a few different elements not monitored. However, OJXPerf randomly Real-world Applications Soot [40] JGFSerialBench [9] Apache SAMOA [22] fj-kmeans [43] FindBugs-3.0.1 [44] Deeplearning4J AlphaGo Zero [4] Deeplearning4J SameDiff [28]    checks different fields with enough samples to minimize the false positives. We exhaustively check every field of the top five objects (i.e., objects associated with most samples) of all our investigated programs in Table 3. From the table, we can see that OJXPerf incurs 5.9% false positives.

Overhead Measurement
The runtime overhead (memory overhead) is the ratio of the runtime (peak memory usage) of the execution monitored by OJXPerf to the runtime (peak memory usage) of the native execution. To quantify the overhead, we apply OJXPerf to three well-known Java benchmark suites: Renaissance [44], Dacapo 9.12 [2], and SPECjvm2008 [14]. We run all benchmarks with four threads. We run every benchmark 30 times and compute the average and error bar. Figure 5 shows the overhead when OJXPerf is enabled at a sampling period of 5M. Some Renaissance and Dacapo benchmarks have higher time overhead (larger than 30%) because they allocate too many objects (e.g., more than 400 million allocations for mnemonics, par-mnemonics, scrabble, akka-uct, db-shootout, dec-tree, neo4j-analytics).

Case Studies
This section shows how OJXPerf pinpoints object replicas in real applications and guides the optimization. Our optimization guarantees the program's correctness via human inspection, and we have evaluated our transformed code with tests to ensure their correctness. It is worth noting that existing profilers may identify the same object allocation as a hotspot in memory usage; however, they do not know whether this allocation point creates multiple object replicas for potential optimization. OJXPerf, in contrast, quantifies the replication factors for the objects to provide intuitive optimization. We have submitted our optimization patches in several cases and gotten them confirmed or upstreamed, e.g., Soot and Findbugs.

Soot
Soot is a Java optimization framework, which uses containers extensively [41]. We run Soot-3.3.0 using the bytecode of the Da-Capo benchmark avrora as input. Figure 6 shows the snapshot of OJXPerf's Flame Graphs GUI in VSCode for intuitive analysis. The top pane of the GUI shows the Java source code; the bottom shows the flame graphs of object accesses in their full call stacks. In the flame graphs, the x-axis shows the accesses with their call stacks to object replicas, and the y-axis shows call stack depth, counting from zero at the top. Each rectangle represents a stack frame. The wider a stack frame is, the higher of replication factor of this stack frame.
The GUI in Figure 6 shows one problematic object st (highlighted in blue), which is accessed on line 84 in method getPhaseOptions of class PhaseOptions with many replicas (its replication factor is 83.9%, as shown in the top pane of the GUI). Soot's execution is divided into a number of phases, such as Jimple Body Creation (jb) phase, Java To Jimple Body Creation (jj) Figure 6: The Flame Graphs GUI of Soot shows a problematic object st with its accesses in full call stacks.
phase, Grimp Body Creation (gb) phase, etc. In the jb phase, the JimpleBodys are built by a phase called jb, which is itself comprised of subphases, such as the aggregation of local variables (jb.a), type assigner (jb.tr), dead assignment eliminator (jb.dae), etc. Each of these subphases that belong to jb phase has its own default option. By investigating the source code, we found that when the soot executes these subphases sequentially, the default option for different subphases is stored in the reported StringTokenizer st object, which keeps unchanged.
To eliminate these replicas, we only read the default option when its contents are changed; otherwise, we reuse the default option from the prior subphase. This optimization yields a (1.17 ± 0.02)× speedup to the entire program.

Eclipse Deeplearning4J -SameDiff
Eclipse Deeplearning4J integrates with Hadoop and runs on several backends [28]. We run Deeplearning4J using SameDiff, a TensorFlow/PyTorch-like framework for executing complex graphs. This framework is also the lower lever base API for running onnx and TensorFlow graphs. OJXPerf investigates the training phase and reports that the replication factor of the input array shapeInfo is 64.7%, indicating high redundancies in the computation on this array in method hasBitSet, which determines array types, as shown in Listing 2.
Deeplearning4J SameDiff builds a directed acyclic graph, whose nodes are differential functions used to compute gradients. In the SameDiffLayer (a base layer used for implementing Deeplearning4J layers with SameDiff), Deeplearning4J provides a set of operations named "Custom operations" designed for the SameDiff graph. To execute the "Custom operations" within graph, these operations are stored in a two-dimensional array. Then Deeplearning4J splits this two-dimensional array into different small partitions. Each partition has its own shape identifier array shapeInfo, which is used to determine four shape properties: SPARSE, COMPRESSED, EMPTY, and DENSE. We found that the adjacent partitions in the SameDiff graph 58  often have the same shape property due to the good locality among adjacent partitions.
To eliminate redundancies, we first check whether the shapeInfo in the current iteration has the same value as in the last iteration. If the shapeInfo is unchanged, we reuse the shape property memoized from the previous iteration, which saves the call to hasBitSet. This yields a (1.09 ± 0.02)× speedup to the entire program.

Eclipse Deeplearning4J -AlphaGo Zero
We also run Deeplearning4J using AlphaGo Zero model [4], which combines a neural network and Monte Carlo Tree Search in an elegant policy iteration framework to achieve stable reinforcement learning. OJXPerf studies the training stage and reports an object, Map<String, NDArrayCompressor> codecs, which is allocated on line 53 and accessed on line 57 in method loadCompressors of class BasicNDArrayCompressor with many replicas (its replication factor is 81.3%), as shown in Listing 3.
The reason for generated replicas is due to constructing the computational graph in the AlphaGo Zero model. To initialize the computational graph, the AlphaGo Zero model uses an existing array parameters for each layer. Given the topological order, the Al-phaGo Zero model constructs the computational graph by iterating each subset of array parameters. Since the array parameters is in compressed status, to obtain the elements of array parameters, the program needs to decompress it first. Deeplearning4J framework provides several different compression algorithms (compressor) based on the data type (e.g., FLOAT16, FLOAT8, INT16, etc). Since every subset of array parameters has the same data type, which means we don't need to load the new compressor and store it again in map codecs in a loop (line 69 of Listing 3). To avoid the redundant loading and storing compressor, we check whether the program is processing different subsets in the same array parameters. If so, we use the current compressor directly. This optimization yields a (1.15 ± 0.01)× speedup to the entire program.

FindBugs-3.0.1
FindBugs looks for code instances that are likely to be errors [45]. We run Find-Bugs on a real input Java chart library 1.0.19 (a widely used client-side chart library for Java). OJXPerf reports an object that has many replicas, BasicBlock block (an object with a user-defined type), which is accessed on the line 183 in method lookupOrCreateFact of class BasicAbstractDataflowAnalysis, as shown in Listing 4.
The replicas come from the algorithm of data-flow analysis used in FindBugs. Findbugs divides a data-flow graph into tiny-sized 58  blocks and creates an object for each block instead of creating a single object for the whole graph. Consequently, most created objects have the same content due to good value locality among adjacent blocks. OJXPerf finds that the method lookupOrCreateFact (line 182 of Listing 4) method is usually invoked with the same input BaiscBlock block. OJXPerf reports that the replication factor of the input block is 70.3%, indicating many replicas of this object. To avoid the redundant lookup and creation, we check whether a different block is produced in the current iteration. If the block is unchanged, we return fact obtained from the last invocation directly. This optimization yields a (1.25 ± 0.03)× speedup to the entire program.

fj-kmeans
fj-kmeans is a benchmark from Renaissance Suite, used to run the k-means algorithm [44]. We run fj-kmeans using the fork/join framework as input. OJXPerf reports an object that has many replicas, array result, which is allocated on line 5 in method findNearestCentroid and accessed on line 2 in method compute Directly of class JavaKMeans, as shown in Listing 5.
The generated replicas are due to the finding nearest centroid algorithm for many different sets of elements. This finding nearest centroid algorithm maintains a collection of centroids, and the distance between each centroid is significant. Then, during some computation periods, because different sets of elements have small distance, the program keeps generating the same centroids and put the centroids' indices into an array result (line 12 of Listing 5), which is the object with many replicas (the replication factor is 76.1%) reported by OJXPerf. Listing 5: OJXPerf pinpoints the result object with many replicas in fj-kmeans.
To eliminate efficiencies, we check the values in array result produced by findNearestCentroid. If result is unchanged, we reuse the return value of method collectClusters memoized from the last iteration, which avoids the redundant computation. This optimization yields a (1.08 ± 0.04)× speedup to the entire program.

Threats to Validity
The threats reside in validating OJXPerf's optimization guidance. The limited scope of replica detection and the sampling strategy does not reveal the ground truth of object replication. Any reported replication is input and execution specific. Different inputs can result in different profiles, and the effects of optimization on unseen inputs will remain unknown. In our studies, we use real inputs for the applications to ensure the optimization is valid. Finally, our optimization may sometimes break the program readability by inserting conditional checks. Developers need to decide whether to adopt our optimization given their priority on software performance.

Conclusions
In this paper, we design and develop OJXPerf, the first lightweight profiler to identify object replicas in Java applications. As a unique feature, OJXPerf combines the use of performance monitoring units, debug registers and lightweight byte code instrumentation for statistical object replica detection. With the evaluation of more than 50 Java applications, we show OJXPerf minimizes false positives and incurs 9% and 6% runtime and memory overheads, respectively. We further optimize several real-world applications guided by OJXPerf that result in a noticeable reduction in heap-memory demands and significant runtime speedups. Many optimization patches are confirmed or upstreamed by the software developers. OJXPerf is open source at https://github.com/Xuhpclab/jxperf.