Importance of Relevant Evidence in Erasmus+ Policy Solutions
Policy solutions in Erasmus+ benefit greatly from evidence-based approaches to address complex challenges effectively. Prof. Jarosław Grnia from the Centre for Evaluation and Analysis of Public Policies at Jagiellonian University emphasizes the significance of utilizing relevant evidence for informed decision-making and impactful outcomes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Comparing GCs and Allocation Richard Jones, Antony Hosking and Eliot Moss 2012 Presented by Yarden Marton 18.11.14
Outline Comparing between different garbage collectors. Allocation methods and considerations.
Comparing GCs What is the best GC? When we say best do we mean: - Best throughput? - Shortest pause times? - Good space utilization? - Compromised combination?
Comparing GCs More to consider: Application dependency Heap space availability Heap size
Comparing GCs - Aspects Throughput Pause time Space Implementation
Comparing GCs - Aspects Throughput Pause time Space Implementation
Throughput Primary goal for batch applications or for systems experiencing delays. Does a faster collector means faster application? Not necessarily. Mutators pay the cost
Throughput Algorithmic complexity Mark-sweep: - cost of tracing and sweeping phases. - Requires visiting every object Copying: - cost of tracing phase only - Requires visiting only live objects
Throughput Is Copying collection faster? Not necessarily: - Number of instructions executed to visit an object - Locality - Lazy sweeping
Comparing GCs - Aspects Throughput Pause time Space Implementation
Pause Time Important for interactive applications, transaction processors and more. stop-the-world collectors Immediate attraction to reference counting However: - Recursive reference count is costly - Both improvements of reference count reintroduce a stop-the-world pause
Comparing GCs - Aspects Throughput Pause time Space Implementation
Space Important for: - Tight physical constraints on memory - Large applications All collectors incur space overhead: - Reference count fields - Additional heap space - Heap fragmentation - Auxiliary data structures - Room for garbage
Space Completeness reclaiming all dead objects eventually. - Basic reference counting is incomplete Promptness reclaiming all dead objects at each collection cycle. - Basic tracing collectors (but with a cost) Modern high-performances collectors typically trade immediacy for performance.
Comparing GCs - Aspects Throughput Pause time Space Implementation
Implementation GC algorithms are difficult to implement, especially concurrent algorithms. Errors can manifest themselves long afterwards Tracing: - Advantage: Simple collector-mutator interface - Disadvantage: Determining roots is complicated Reference counting: - Advantage : Can be implemented in a library - Disadvantage : Processing overheads and correctness essentiality of all reference count manipulation. In general, copying and compacting collectors are more complex than non-moving collectors.
Adaptive Systems Commercial system often offer a choice between GCs, with a large number of tuning options. Researchers have developed systems that adapts to the enviroment: - Java run-time (Soman et al [2004]) - Singer et al [2007a] - Sun s Ergonomic tuning
Advice For Developers Know your application: - Measure its behavior - Track the size and lifetime distributions of the objects it uses. Experiment with the different collector configurations on offer.
A Unified Theory of GC Considered two styles of collection: Direct, reference counting. Indirect, tracing collection. Next: An abstract framework for a wide variety of collectors.
Abstract GC GC can be expressed as a fixed point computation that assigns reference counts (n) to nodes n Nodes. Nodes with non-zero count are retained and the rest should be reclaimed. Use of abstract data structures whose implementations can vary. W a work list of objects to be processed. When empty, the algorithms terminate.
Abstract Tracing GC Algorithm atomic collectTracing(): rootsTracing(W) scanTracing(W) sweepTracing() //find root objects //mark reachable objects //free dead objects rootsTracing(R): for each fld in Roots ref *fld if ref null R R + [ref] scanTracing(W): while not isEmpty(W) src remove(W) (src) (src)+1 if (src) = 1 for each fld in Pointers(src) ref *fld if ref null W W + [ref]
Abstract Tracing GC Algorithm (Continued) sweepTracing(): for each noed in Nodes if?(node) = 0 free(node) else ?(node) 0 New(): ref allocate() if ref = null collectTracing() ref allocate() if ref = null error Out of memory ?(ref) 0 return ref
Roots A B C D A B C D 0 0 0 0 W
Roots A B C D A B C D 0 0 0 0 W B C
Roots A B C D A B C D 0 1 0 0 W C
Roots A B C D A B C D 0 1 1 0 W A B
Roots A B C D A B C D 1 1 1 0 W B
Roots A B C D A B C D 1 2 1 0 W
Roots A B C D A B C D 0 0 0 0 W
Abstract reference counting GC Algorithm atomic collectCounting(I,D): applyIncrements(I) scanCounting(D) sweepCounting() //free dead objects //increase necessary //decrease reqursivaly applyIncrements(I): while not isEmpty(I) ref remove(I) (ref) (ref)+1 scanCounting(W): while not isEmpty(W) src remove(W) (src) (src)-1 if (src) = 0 for each fld in Pointers(src) ref *fld if ref null W W + [ref]
Abstract reference counting GC Algorithm (Continued) sweepCounting(): for each node in Nodes if?(node) = 0 free(node) New(): ref allocate() if ref = null collectCounting() ref allocate() if ref = null error Out of memory ?(ref) 0 return ref
Abstract reference counting GC Algorithm (Continued) inc(ref): if ref null I I + [ref] dec(ref): ifref null D D + [ref] Atomic Write(src, i, dst): inc(dst) dec(src[i]) src[i] dst
atomic collectCounting() applyIncrements(I) Roots A B C D A B C D 0 0 0 0 I A B A D B C B D A D
atomic collectCounting() applyIncrements(I) Roots A B C D A B C D 1 0 0 0 I B A D B C B D A D
atomic collectCounting() applyIncrements(I) Roots A B C D A B C D 2 3 1 1 I D A D
atomic collectCounting() applyIncrements(I) scanCounting(D) Roots A B C D A B C D 1 3 1 0 I D B
atomic collectCounting() applyIncrements(I) scanCounting(D) Roots A B C D A B C D 1 2 1 0 I D
atomic collectCounting() applyIncrements(I) scanCounting(D) sweepCounting() Roots A B C D A B C D 1 2 1 0 I D
Abstract deferred reference counting GC Algorithm Atomic collecDrc(I,D): rootsTracing(I) applyIncrements(I) scanCounting(D) sweepCounting() rootsTracing(D) applyDecrements(D) //add root objects to I //increase necessary //decrease reqursively //free dead objects //keep invariant New(): ref allocate() if ref = null collecDrc(I,D) ref allocate() if ref = null error Out of memory (ref) 0 return ref
Abstract deferred reference counting GC Algorithm (Continued) Atomic Write(src, i, dst): if src Roots inc(dst) dec(src[i]) src[i] dst applyDecrements(D): while not isEmpty(D) ref remove(D) ?(ref) ?(ref)-1
atomic collectDrc() rootsTracing(I) Roots A B C D A B C D 0 0 0 0 I A B A D B D A D
atomic collectDrc() rootsTracing(I) applyIncrements(I) Roots A B C D A B C D 0 0 0 0 I A B A D B B C D A D
atomic collectDrc() rootsTracing(I) applyIncrements(I) scanCounting(D) Roots A B C D A B C D 2 3 1 1 I D A D
atomic collectDrc() rootsTracing(I) applyIncrements(I) scanCounting(D) sweepCounting() Roots A B C D A B C D 1 2 1 0 I D
atomic collectDrc() rootsTracing(I) applyIncrements(I) scanCounting(D) sweepCounting() rootsTracing(D) Roots A B C D A B C D 1 2 1 0 I D
atomic collectDrc() rootsTracing(I) applyIncrements(I) scanCounting(D) sweepCounting() rootsTracing(D) applyDecrements(D) Roots A B C A B C 1 2 1 I D B C
atomic collectDrc() rootsTracing(I) applyIncrements(I) scanCounting(D) sweepCounting() rootsTracing(D) applyDecrements(D) Roots A B C A B C 1 1 0 I D
Comparing GCs Summary GCs performance depends on various aspects - Therefore, no GC has an absolute advantage on the others. Garbage collection can be expressed in an abstract way. - Highlights similarity and differences
Allocation Three aspects to memory management: - Allocation of memory in the first place - Identification of live data - Reclamation for future use Allocation and reclamation of memory are tightly linked Several key differences between automatic and explicit memory management, in terms of allocating and freeing: - GC free space all at once - A system with GC has more information when allocating - With GC, users tends to write programs in a different style.
