Parallel, multithreaded C and C++ programs such as web servers, database managers, news servers, and scientific applications are becoming increasingly prevalent. For these applications, the memory allocator is often a bottleneck that severely limits program performance and scalability on multiprocessor systems. Previous allocators suffer from problems that include poor performance and scalability, and heap organizations that introduce false sharing. Worse, many allocators exhibit a dramatic increase in memory consumption when confronted with a producer-consumer pattern of object allocation and freeing. This increase in memory consumption can range from a factor of P (the number of processors) to unbounded memory consumption.This paper introduces Hoard, a fast, highly scalable allocator that largely avoids false sharing and is memory efficient. Hoard is the first allocator to simultaneously solve the above problems. Hoard combines one global heap and per-processor heaps with a novel discipline that provably bounds memory consumption and has very low synchronization costs in the common case. Our results on eleven programs demonstrate that Hoard yields low average fragmentation and improves overall program performance over the standard Solaris allocator by up to a factor of 60 on 14 processors, and up to a factor of 18 over the next best allocator we tested.

The unmanageably large size of reference traces has spurred the development of sophisticated trace reduction techniques. In this paper we presenttwonew algorithms for trace reduction --- Safely Allowed Drop (SAD) and Optimal LRU Reduction (OLR). Both achieve high reduction factors and guarantee exact simulations for common replacement policies and for memories larger than a user-defined threshold. In particular, simulation on OLR-reduced traces is accurate for the LRU replacement algorithm, while simulation on SAD-reduced traces is accurate for the LRU and OPT algorithms. OLR also satisfies an optimality property: for a given trace and memory size it produces the shortest possible trace that has the same LRU behavior as the original for a memory of at least this size. Our approach has multiple applications, especially in simulating virtual memory systems

Despite the many replacement algorithms proposed throughout the years, approximations of Least Recently Used (LRU) replacement are predominant in actual virtual memory management systems because of their simplicity and efficiency.LRU, however, exhibits well-known performance problems for regular access patterns over more pages than the main memory can hold (e.g., large loops).In this paper we present Early Eviction LRU (EELRU).EELRU is a simple adaptive replacement algorithm, which uses only the kind of information needed by LRU-how recently each page has been touched relative to the others.It exploits this information more effectively than LRU, using a simple on-line cost/benefit analysis to guide its replacement decisions.In the very common situations where LRU is good, EELRU is good because it behaves like LRU.In common worst cases for LRU, EELRU is significantly better, and in fact close to optimal as it opts to sacrifice some pages to allow others to stay in memory longer.Overall, in its worst case, EELRU cannot be more than a constant factor worse than LRU, while LRU can be worse than EELRU by a factor almost equal to the number of pages in memory.In simulation experiments with a variety of programs and wide ranges of memory sizes, we show that EELRU does in fact outperform LRU, typically reducing misses by ten to thirty percent, and occasionally by much more-sometimes by a factor of two to ten.It rarely performs worse than LRU, and then only by a small amount.Overall, EELRU demonstrates several principles which could be widely useful for adaptive page replacement algorithms:(1) it adapts to changes in program behavior, distinguishing important behavior characteristics for each workload.In particular, EELRU is not affected by highfrequency behavior (e.g., loops much smaller than the memory size) as such behavior may obscure important largescale regularities;(2) EELRU chooses pages to evict in a way that respects both the memory size and the aggregate memory-referencing behavior of the program; (3) depending

We show that for 8 real and varied C and C++ programs, several conventional dynamic storage allocators provide near-zero fragmentation, once we account for overheads due to implementation details such as headers, alignment, etc. This substantially strengthens our previous results showing that the memory fragmentation problem has generally been misunderstood, and that good allocator policies can provide good memory usage for most programs. The new results indicate that for most programs, excellent allocator policies are readily available, and efficiency of implementation is the major challenge. While we believe that our experimental results are state-of-the-art and our methodology is superior to most previous work, more work should be done to identify and study unusual problematic program behaviors not represented in our sample.

Many useful programming language extensions and system support libraries require knowledge of the locations of fields within objects at run time. Examples include orthogonal persistent object stores, precise garbage collectors, data structure picklers, and parameter marshaling schemes.For clean and efficient implementation as libraries, these systems require run-time knowledge of in-memory layouts of data objects, which is unavailable in most traditionally compiled and linked programming languages, such as C, C++, and Ada. Even the recently standardized run-time type identification (RTTI) feature in C++ is insufficient, because it describes only language-level features of the type hierarchy and not the compiler-dependent object layout decisions.We present a facility for run-time type description, or RTTD, which extracts low-level layout information from debugging information generated by conventional compilers, and makes it available to user programs. We believe this to be the simplest and most portable approach to run-time type description, requiring no changes to existing compilers. In this paper, we describe the basic strategies and present details of our implementation for C++. We also sketch some extensions that we have implemented, including special treatment of C++'s virtual function table pointers to match persistent or foreign data objects with the actual code in a particular application.Our implementation of run-time type description is freely available. It is in regular use with multiple operating systems and compilers, in both free and commercial products, including a high-performance persistent object storage system for C++ and a real-time garbage collector.

Article Free Access Share on Effective "static-graph" reorganization to improve locality in garbage-collected systems Authors: Paul R. Wilson Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, Illinois Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, IllinoisView Profile , Michael S. Lam Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, Illinois Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, IllinoisView Profile , Thomas G. Moher Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, Illinois Electrical Engineering and Computer Science Dept., University of Illinois at Chicago, Box 4348 (m/c 154) Chicago, IllinoisView Profile Authors Info & Claims PLDI '91: Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementationMay 1991 Pages 177–191https://doi.org/10.1145/113445.113461Published:01 May 1991Publication History 83citation592DownloadsMetricsTotal Citations83Total Downloads592Last 12 Months39Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The Opportunistic Garbage Collector (OGC) is a generational garbage collector for stock hardware and operating systems. While incorporating important features of previous systems, the OGC includes several innovations. A new bucket brigade heap organization supports advancement thresholds between one and two scavenges, using only two or three spaces per generation, and without requiring per-object counts. Opportunistic scavenging decouples scavenging from the filling of available memory, in order to hide potentially disruptive scavenge pauses and improve efficiency. Card marking efficiently records which small areas of the heap may contain pointers into younger generations, and is supported by a refinement of the crossing map technique, to enable scanning of arbitrary cards.

Demonic memory is a form of reconstructive memory for process histories. As a process executes, its states are regularly checkpointed, generating a history of the process at low time resolution. Following the initial generation, any prior state of the process can be reconstructed by starting from a checkpointed state and re-executing the process up through the desired state, thereby exploiting the redundancy between the states of a process and the description of that process (i.e., a computer program).