The Experts below are selected from a list of 5679 Experts worldwide ranked by ideXlab platform
Erez Petrank - One of the best experts on this subject based on the ideXlab platform.
-
data structure aware Garbage Collector
International Symposium on Memory Management, 2015Co-Authors: Nachshon Cohen, Erez PetrankAbstract:Garbage collection may benefit greatly from knowledge about program behavior, but most managed languages do not provide means for the programmer to deliver such knowledge. In this work we propose a very simple interface that requires minor programmer effort and achieves substantial performance and scalability improvements. In particular, we focus on the common use of data structures or collections for organizing data on the heap. We let the program notify the Collector which classes represent nodes of data structures and also when such nodes are being removed from their data structures. The data-structure aware (DSA) Garbage Collector uses this information to improve performance, locality, and load balancing. Experience shows that this interface requires a minor modification of the application. Measurements show that for some significant benchmarks this interface can dramatically reduce the time spent on Garbage collection and also improve the overall program performance.
-
stopless a real time Garbage Collector for multiprocessors
International Symposium on Memory Management, 2007Co-Authors: Filip Pizlo, Erez Petrank, Daniel Frampton, Bjarne SteensgaardAbstract:We present Stopless: a concurrent real-time Garbage Collector suitable for modern multiprocessors running parallel multithreaded applications. Creating a Garbage-collected environment that supports real-time on modern platforms is notoriously hard,especially if real-time implies lock-freedom. Known real-time Collectors either restrict the real-time guarantees to uniprocessors only, rely on special hardware, or just give up supporting atomic operations (which are crucial for lock-free software). Stopless is the first Collector that provides real-time responsiveness while preserving lock-freedom, supporting atomic operations, controlling fragmentation by compaction, and supporting modern parallel platforms. Stopless is adequate for modern languages such as C# or Java. It was implemented on top of the Bartok compiler and runtime for C# and measurements demonstrate high responsiveness (a factor of a 100 better than previously published systems), virtually no pause times, good mutator utilization, and acceptable overheads.
-
an on the fly mark and sweep Garbage Collector based on sliding views
Conference on Object-Oriented Programming Systems Languages and Applications, 2003Co-Authors: Hezi Azatchi, Yossi Levanoni, Harel Paz, Erez PetrankAbstract:With concurrent and Garbage collected languages like Java and C# becoming popular, the need for a suitable non-intrusive, efficient, and concurrent multiprocessor Garbage Collector has become acute. We propose a novel mark and sweep on-the-fly algorithm based on the sliding views mechanism of Levanoni and Petrank. We have implemented our Collector on the Jikes Java Virtual Machine running on a Netfinity multiprocessor and compared it to the concurrent algorithm and to the stop-the-world Collector supplied with Jikes JVM. The maximum pause time that we measured with our benchmarks over all runs was 2ms. In all runs, the pause times were smaller than those of the stop-the-world Collector by two orders of magnitude and they were also always shorter than the pauses of the Jikes concurrent Collector. Throughput measurements of the new Garbage Collector show that it outperforms the Jikes concurrent Collector by up to 60%. As expected, the stop-the-world does better than the on-the-fly Collectors with results showing about 10% difference.On top of being an effective mark and sweep on-the-fly Collector standing on its own, our Collector may also be used as a backup Collector (collecting cyclic data structures) for the Levanoni-Petrank reference counting Collector. These two algorithms perfectly fit sharing the same allocator, a similar data structure, and a similar JVM interface.
-
a generational on the fly Garbage Collector for java
Programming Language Design and Implementation, 2000Co-Authors: Tamar Domani, Elliot K Kolodner, Erez PetrankAbstract:An on-the-fly Garbage Collector does not stop the program threads to perform the collection. Instead, the Collector executes in a separate thread (or process) in parallel to the program. On-the-fly Collectors are useful for multi-threaded applications running on multiprocessor servers, where it is important to fully utilize all processors and provide even response time, especially for systems for which stopping the threads is a costly operation. In this work, we report on the incorporation of generations into an on-the-fly Garbage Collector. The incorporation is non-trivial since an on-the-fly Collector avoids explicit synchronization with the program threads. To the best of our knowledge, such an incorporation has not been tried before. We have implemented the Collector for a prototype Java Virtual Machine on AIX, and measured its performance on a 4-way multiprocessor. As for other generational Collectors, an on-the-fly generationalCollector has the potential for reducing the overall running time and working set of an application by concentrating collection efforts on the young objects. However, in contrast to other generational Collectors,on-the-fly Collectors do not move the objects; thus, there is no segregation between the old and the young objects. Furthermore, on-the-fly Collectors do not stop the threads, so there is no extra benefit for the short pauses obtained by generational collection. Nevertheless, comparing our on-the-fly Collector with and without generations, it turns out that the generational Collector performs better for most applications. The best reduction in overall running time for the benchmarks we measured was 25%. However, there were some benchmarks for which it had no effect and one for which the overall running time increased by 4%.
-
PLDI - A generational on-the-fly Garbage Collector for Java
Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation - PLDI '00, 2000Co-Authors: Tamar Domani, Elliot K Kolodner, Erez PetrankAbstract:An on-the-fly Garbage Collector does not stop the program threads to perform the collection. Instead, the Collector executes in a separate thread (or process) in parallel to the program. On-the-fly Collectors are useful for multi-threaded applications running on multiprocessor servers, where it is important to fully utilize all processors and provide even response time, especially for systems for which stopping the threads is a costly operation. In this work, we report on the incorporation of generations into an on-the-fly Garbage Collector. The incorporation is non-trivial since an on-the-fly Collector avoids explicit synchronization with the program threads. To the best of our knowledge, such an incorporation has not been tried before. We have implemented the Collector for a prototype Java Virtual Machine on AIX, and measured its performance on a 4-way multiprocessor. As for other generational Collectors, an on-the-fly generationalCollector has the potential for reducing the overall running time and working set of an application by concentrating collection efforts on the young objects. However, in contrast to other generational Collectors,on-the-fly Collectors do not move the objects; thus, there is no segregation between the old and the young objects. Furthermore, on-the-fly Collectors do not stop the threads, so there is no extra benefit for the short pauses obtained by generational collection. Nevertheless, comparing our on-the-fly Collector with and without generations, it turns out that the generational Collector performs better for most applications. The best reduction in overall running time for the benchmarks we measured was 25%. However, there were some benchmarks for which it had no effect and one for which the overall running time increased by 4%.
Perry Cheng - One of the best experts on this subject based on the ideXlab platform.
-
real time music synthesis in java using the metronome Garbage Collector
International Computer Music Conference, 2007Co-Authors: Joshua S Auerbach, David F Bacon, Florian Bomers, Perry ChengAbstract:Automatic memory management via Garbage collection is the key to the safety, portability, and high productivity of modern programming languages like Java. However, until now no truly real-time Garbage Collector has existed for Java. As a result, the extreme real-time requirements of interactive music synthesis and processing have made it impossible to build such systems in Java. We have developed a hard real-time Garbage Collector, called Metronome, around which IBM has built a production real-time Java virtual machine running on a realtime variant of Redhat Enterprise Linux. In this paper we demonstrate the real-time capabilities of our virtual machine with a MIDI music synthesizer that we built entirely in standard Java using the full object-oriented feaures of the language. We show that even with the addition of another thread allocating 8 MB/second of data, our Garbage Collector is able to sustain error-free 44 KHz music synthesis down to buffer sizes of 1ms, achieving keyboard-to-speaker latencies of 5.0±0.75ms, comparable to a Kurzweil K2000R synthesizer (3.9±1ms) and suitable for high-fidelity interactive performance.
-
ICMC - REAL-TIME MUSIC SYNTHESIS IN JAVA USING THE METRONOME Garbage Collector
2007Co-Authors: Joshua S Auerbach, David F Bacon, Florian Bomers, Perry ChengAbstract:Automatic memory management via Garbage collection is the key to the safety, portability, and high productivity of modern programming languages like Java. However, until now no truly real-time Garbage Collector has existed for Java. As a result, the extreme real-time requirements of interactive music synthesis and processing have made it impossible to build such systems in Java. We have developed a hard real-time Garbage Collector, called Metronome, around which IBM has built a production real-time Java virtual machine running on a realtime variant of Redhat Enterprise Linux. In this paper we demonstrate the real-time capabilities of our virtual machine with a MIDI music synthesizer that we built entirely in standard Java using the full object-oriented feaures of the language. We show that even with the addition of another thread allocating 8 MB/second of data, our Garbage Collector is able to sustain error-free 44 KHz music synthesis down to buffer sizes of 1ms, achieving keyboard-to-speaker latencies of 5.0±0.75ms, comparable to a Kurzweil K2000R synthesizer (3.9±1ms) and suitable for high-fidelity interactive performance.
-
a parallel real time Garbage Collector
Programming Language Design and Implementation, 2001Co-Authors: Perry Cheng, Guy E BlellochAbstract:We describe a parallel, real-time Garbage Collector and present experimental results that demonstrate good scalability and good real-time bounds. The Collector is designed for shared-memory multiprocessors and is based on an earlier Collector algorithm [2], which provided fixed bounds on the time any thread must pause for collection. However, since our earlier algorithm was designed for simple analysis, it had some impractical features. This paper presents the extensions necessary for a practical implementation: reducing excessive interleaving, handling stacks and global variables, reducing double allocation, and special treatment of large and small objects. An implementation based on the modified algorithm is evaluated on a set of 15 SML benchmarks on a Sun Enterprise 10000, a 64-way UltraSparc-II multiprocessor. To the best of our knowledge, this is the first implementation of a parallel, real-time Garbage Collector. The average Collector speedup is 7.5 at 8 processors and 17.7 at 32 processors. Maximum pause times range from 3 ms to 5 ms. In contrast, a non-incremental Collector (whether generational or not) has maximum pause times from 10 ms to 650 ms. Compared to a non-parallel, stop-copy Collector, parallelism has a 39% overhead, while real-time behavior adds an additional 12% overhead. Since the Collector takes about 15% of total execution time, these features have an overall time costs of 6% and 2%.
-
PLDI - A parallel, real-time Garbage Collector
Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation - PLDI '01, 2001Co-Authors: Perry Cheng, Guy E BlellochAbstract:We describe a parallel, real-time Garbage Collector and present experimental results that demonstrate good scalability and good real-time bounds. The Collector is designed for shared-memory multiprocessors and is based on an earlier Collector algorithm [2], which provided fixed bounds on the time any thread must pause for collection. However, since our earlier algorithm was designed for simple analysis, it had some impractical features. This paper presents the extensions necessary for a practical implementation: reducing excessive interleaving, handling stacks and global variables, reducing double allocation, and special treatment of large and small objects. An implementation based on the modified algorithm is evaluated on a set of 15 SML benchmarks on a Sun Enterprise 10000, a 64-way UltraSparc-II multiprocessor. To the best of our knowledge, this is the first implementation of a parallel, real-time Garbage Collector. The average Collector speedup is 7.5 at 8 processors and 17.7 at 32 processors. Maximum pause times range from 3 ms to 5 ms. In contrast, a non-incremental Collector (whether generational or not) has maximum pause times from 10 ms to 650 ms. Compared to a non-parallel, stop-copy Collector, parallelism has a 39% overhead, while real-time behavior adds an additional 12% overhead. Since the Collector takes about 15% of total execution time, these features have an overall time costs of 6% and 2%.
Hezi Azatchi - One of the best experts on this subject based on the ideXlab platform.
-
an on the fly mark and sweep Garbage Collector based on sliding views
Conference on Object-Oriented Programming Systems Languages and Applications, 2003Co-Authors: Hezi Azatchi, Yossi Levanoni, Harel Paz, Erez PetrankAbstract:With concurrent and Garbage collected languages like Java and C# becoming popular, the need for a suitable non-intrusive, efficient, and concurrent multiprocessor Garbage Collector has become acute. We propose a novel mark and sweep on-the-fly algorithm based on the sliding views mechanism of Levanoni and Petrank. We have implemented our Collector on the Jikes Java Virtual Machine running on a Netfinity multiprocessor and compared it to the concurrent algorithm and to the stop-the-world Collector supplied with Jikes JVM. The maximum pause time that we measured with our benchmarks over all runs was 2ms. In all runs, the pause times were smaller than those of the stop-the-world Collector by two orders of magnitude and they were also always shorter than the pauses of the Jikes concurrent Collector. Throughput measurements of the new Garbage Collector show that it outperforms the Jikes concurrent Collector by up to 60%. As expected, the stop-the-world does better than the on-the-fly Collectors with results showing about 10% difference.On top of being an effective mark and sweep on-the-fly Collector standing on its own, our Collector may also be used as a backup Collector (collecting cyclic data structures) for the Levanoni-Petrank reference counting Collector. These two algorithms perfectly fit sharing the same allocator, a similar data structure, and a similar JVM interface.
Hansj Boehm - One of the best experts on this subject based on the ideXlab platform.
-
reducing Garbage Collector cache misses
International Symposium on Memory Management, 2000Co-Authors: Hansj BoehmAbstract:Cache misses are currently a major factor in the cost of Garbage collection, and we expect them to dominate in the future. Traditional Garbage collection algorithms exhibit relatively little temporal locality; each live object in the heap is likely to be touched exactly once during each Garbage collection. We measure two techniques for dealing with this issue: prefetch-on-grey, and lazy sweeping. The first of these is new in this context. Lazy sweeping has been in common use for a decade. It was introduced as a mechanism for reducing paging and pause times; we argue that it is also crucial for eliminating cache misses during the sweep phase. Our measurements are obtained in the context of a non-moving Garbage Collector. Fully copying Garbage collection inherently requires more traffic through the cache, and thus probably also stands to benefit substantially from something like the prefetch-on-grey technique. Generational Garbage collection may reduce the benefit of these techniques for some applications, but experiments with a non-moving generational Collector suggest that they remain quite useful.
-
simple Garbage Collector safety
Programming Language Design and Implementation, 1996Co-Authors: Hansj BoehmAbstract:A conservative Garbage Collector can typically be used with conventionally compiled programs written in C or C++. But two safety issues must be considered. First, the source code must not hide pointers from the Garbage Collector. This primarily requires stricter adherence to existing restrictions in the language definition. Second, we must ensure that the compiler will not perform transformations that invalidate this requirement.We argue that the same technique can be used to address both issues. We present an algorithm for annotating source or intermediate code to either check the validity of pointer arithmetic in the source, or to guarantee that under minimal, clearly defined assumptions about the compiler, the optimizer cannot "disguise" pointers. We discuss an implementation based on a preprocessor for the GNU C compiler (gcc), and give some measurements of program slow down.
-
PLDI - Simple Garbage-Collector-safety
Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation - PLDI '96, 1996Co-Authors: Hansj BoehmAbstract:A conservative Garbage Collector can typically be used with conventionally compiled programs written in C or C++. But two safety issues must be considered. First, the source code must not hide pointers from the Garbage Collector. This primarily requires stricter adherence to existing restrictions in the language definition. Second, we must ensure that the compiler will not perform transformations that invalidate this requirement.We argue that the same technique can be used to address both issues. We present an algorithm for annotating source or intermediate code to either check the validity of pointer arithmetic in the source, or to guarantee that under minimal, clearly defined assumptions about the compiler, the optimizer cannot "disguise" pointers. We discuss an implementation based on a preprocessor for the GNU C compiler (gcc), and give some measurements of program slow down.
Tony Printezis - One of the best experts on this subject based on the ideXlab platform.
-
visualising the train Garbage Collector
International Symposium on Memory Management, 2002Co-Authors: Tony Printezis, Alex GarthwaiteAbstract:This paper presents a novel method for visualising an incremental Garbage Collector, based on the well-known Train algorithm, that generates concise snapshots of its state and informative graphs of its operation over time. To obtain these visualisations we used GC-spy, a generic heap visualisation framework. We show how this easy-to-use tool provided a visualisation model that was effective in both confirming our pre-existing beliefs about the Collector's operation and, more interestingly, highlighting unexpected patterns in its behaviour. Based on this successful experience, we advocate the use of similar visualisation approaches to better understand and ultimately tune, profile, and improve other equally complex Garbage Collectors.
-
MSP/ISMM - Visualising the train Garbage Collector
Proceedings of the third international symposium on Memory management - ISMM '02, 2002Co-Authors: Tony Printezis, Alex GarthwaiteAbstract:This paper presents a novel method for visualising an incremental Garbage Collector, based on the well-known Train algorithm, that generates concise snapshots of its state and informative graphs of its operation over time. To obtain these visualisations we used GC-spy, a generic heap visualisation framework. We show how this easy-to-use tool provided a visualisation model that was effective in both confirming our pre-existing beliefs about the Collector's operation and, more interestingly, highlighting unexpected patterns in its behaviour. Based on this successful experience, we advocate the use of similar visualisation approaches to better understand and ultimately tune, profile, and improve other equally complex Garbage Collectors.
-
a generational mostly concurrent Garbage Collector
International Symposium on Memory Management, 2000Co-Authors: Tony Printezis, David DetlefsAbstract:This paper reports our experiences with a mostly-concurrent incremental Garbage Collector, implemented in the context of a high performance virtual machine for the Java™ programming language. The Garbage Collector is based on the “mostly parallel” collection algorithm of Boehm et al. and can be used as the old generation of a generational memory system. It overloads efficient write-barrier code already generated to support generational Garbage collection to also identify objects that were modified during concurrent marking. These objects must be rescanned to ensure that the concurrent marking phase marks all live objects. This algorithm minimises maximum Garbage collection pause times, while having only a small impact on the average Garbage collection pause time and overall execution time. We support our claims with experimental results, for both a synthetic benchmark and real programs.
-
ISMM - A generational mostly-concurrent Garbage Collector
Proceedings of the second international symposium on Memory management - ISMM '00, 2000Co-Authors: Tony Printezis, David DetlefsAbstract:This paper reports our experiences with a mostly-concurrent incremental Garbage Collector, implemented in the context of a high performance virtual machine for the Java™ programming language. The Garbage Collector is based on the “mostly parallel” collection algorithm of Boehm et al. and can be used as the old generation of a generational memory system. It overloads efficient write-barrier code already generated to support generational Garbage collection to also identify objects that were modified during concurrent marking. These objects must be rescanned to ensure that the concurrent marking phase marks all live objects. This algorithm minimises maximum Garbage collection pause times, while having only a small impact on the average Garbage collection pause time and overall execution time. We support our claims with experimental results, for both a synthetic benchmark and real programs.
