Low latency services such as credit-card fraud detection and website targeted advertisement rely on Big Data platforms (e.g., Lucene, Graphchi, Cassandra) which run on top of memory managed runtimes, such as the JVM. These platforms, however, suffer from unpredictable and unacceptably high pause times due to inadequate memory management decisions (e.g., allocating objects with very different lifetimes next to each other, resulting in memory fragmentation). This leads to long and frequent application pause times, breaking Service Level Agreements (SLAs). This problem has been previously identified and results show that current memory management techniques are ill-suited for applications that hold in memory massive amounts of middle to long-lived objects (which is the case for a wide spectrum of Big Data applications). Previous works try to reduce such application pauses by allocating objects off-heap or in special allocation regions generations, thus alleviating the pressure on memory management. However, all these solutions require a combination of programmer effort and knowledge, source code access, or off-line profiling, with clear negative impact on programmer productivity and or application performance. This paper presents ROLP, a runtime object lifetime profiling system. ROLP profiles application code at runtime in order to identify which allocation contexts create objects with middle to long lifetimes, given that such objects need to be handled differently (regarding short-lived ones). This profiling information greatly improves memory management decisions, leading to long tail latencies reduction of up to 51 for Lucene, 85 for GraphChi, and 60 for Cassandra, with negligible throughput and memory overhead. ROLP is implemented for the OpenJDK 8 HotSpot JVM and it does not require any programmer effort or source code access.
needs the calling context to profile objects at relevant allocation sites. Ball and Laurus @cite_33 compute a unique number for each possible path of a control flow graph inside a procedure. The computation is done offline and added to the source code. This is not suited for because modern workloads have many possible paths inside each routine, and the technique can not capture the inter-procedure path needed for to distinguish allocation sites. Bond and McKinley @cite_5 also compute a single value, but at runtime, to determine the sequence of active stack frames in a inter-procedural way. However, they need to maintain non-commutativity to differentiate call orders, such as calling methods @math and @math . This is not a requirement for and so we can have a smaller impact on code instrumentation, with low impact on the throughput. uses an adaptive solution to store allocation contexts, with a low ratio of collisions (as shown in Table ) while using fewer bits to store information.
@cite_5 @cite_33
2144300381 2101134669
We present a simple generation procedure which turns out to be an effective source of very hard cases for graph 3-colorability. The graphs distributed according to this generation procedure are much denser in very hard cases than previously reported for the same problem size. The coloring cost for these instances is also orders of magnitude bigger. This ability is issued from the fact that the procedure favors-inside the class of graphs with given connectivity and free of 4-cliques-the generation of graphs with relatively few paths of length three (that we call 3-paths). There is a critical value of the ratio between the number of 3-paths and the number of edges, independent of the number of nodes, which separates the graphs having the same connectivity in two regions: one contains almost all graphs free of 4-cliques while the other contains almost no such graphs. The generated very hard cases are near this phase transition, and have a regular structure, witnessed by the low variance in node degrees, as opposite to the random graphs. This regularity in the graph structure seems to confuse the coloring algorithm by inducing an uniform search space, with no clue for the search. Energy Efficient Ethernet, as defined by the IEEE 802.3az standard, has shown not to be as efficient as originally expected given the large values of the transition times between the active and sleep power modes. In fact, EEE performs nearly optimal only when the link load is either very low or very high, but never at medium loads. So, in order to achieve large power savings, then it is necessary to design a flow allocation algorithm that allocates traffic demands on links that avoid medium traffic loads on links, since these are far from optimal. This work defines EEE-FA, an energy-aware flow allocation algorithm that computes the best possible route in terms of energy consumption for a given network load condition. Essentially, EEE-FA computes the K-shortest paths for a given traffic demand and evaluates the consumption impact of allocating the traffic demand on each of them, in order to further select that route with minimum energy consumption impact for a given network status. This algorithm is compared with shortest path routing and it is shown that important energy savings may be achieved, however at the expense of increasing the global network traffic load and the average number of hops per demand as a consequence of using sub-optimal (in terms of distance) routes. A fast and scalable interprocedural escape analysis algorithm is presented.T he analysis computes a description of a subset of created objects whose lifetime is bounded by the lifetime of a runtime stack frame.T he analysis results can be used for many purposes, including stack allocation of objects, thread synchronization elimination, dead-store removal, code motion, and iterator reduction. A method to use the analysis results for transforming a program to allocate some objects on the runtime stack is also presented.F or non-trivial programs, typically 10 -20 of all allocated objects are placed on the runtime stack after the transformation. Calling context enhances program understanding and dynamic analyses by providing a rich representation of program location. Compared to imperative programs, object-oriented programs use more interprocedural and less intraprocedural control flow, increasing the importance of context sensitivity for analysis. However, prior online methods for computing calling context, such as stack-walking or maintaining the current location in a calling context tree, are expensive in time and space. This paper introduces a new online approach called probabilistic calling context (PCC) that continuously maintains a probabilistically unique value representing the current calling context. For millions of unique contexts, a 32-bit PCC value has few conflicts. Computing the PCC value adds 3 average overhead to a Java virtual machine. PCC is well-suited to clients that detect new or anomalous behavior since PCC values from training and production runs can be compared easily to detect new context-sensitive behavior; clients that query the PCC value at every system call, Java utility call, and Java API call add 0-9 overhead on average. PCC adds space overhead proportional to the distinct contexts stored by the client (one word per context). Our results indicate PCC is efficient and accurate enough to use in deployed software for residual testing, bug detection, and intrusion detection.