support saya di tukang nggame support saya di tukang nggame support saya di tukang nggame support saya di tukang nggame
Saat ini INFORMASI yang anda butuhkan mungkin tersedia di
silahkan menuju blog baru saya dan dapatkan informasi lengkap yang anda butuhkan klik disini

Cliff Notes

Cliff Notes for My Presentation

Slide 3: Dynamic Storage Allocation
- dynamic storage allocation is allocation of memory at runtime
- important because we do not always know ahead of time how much space we’ll need
- in languages such as C and C++, when we dynamically allocate memory, the programmer must also explicitly deallocate the memory
- not deallocating memory properly is a common source of programming error
- two most common programming errors are dangling references and memory leaks

Slide 4: Problems with Explicit Memory Deallocation
- dangling references occur when the programmer deallocates memory too soon
- in the example, pi is deleted before all references to it have been removed
- when we try to access the value pointed to by q (which consequently was the value pointed to by pi), it no longer exists

Slide 5: Problems with Explicit Memory Deallocation

- a memory leak occurs when the programmer forgets to delete dynamically allocated memory
- in this case, the memory can no longer be returned to the heap
- in the example, you can see that the programmer requested memory at the beginning of the function but never returned it to the heap
- both dangling references and memory leaks can cause a lot of havoc in a program

Slide 6: Solving the Problem
- to avoid dealing with the problems of explicit memory deallocation, languages such as lisp and java use a “garbage collector”
- the garbage collector reclaims objects that are no longer reachable and copies the survivors to another area of memory
- these dead objects are referred to as garbage

Slide 7: Beltway
- this summer my project dealt with optimizing the garbage collector (gc) that Steve, Kathryn, and others created
- this gc is called Beltway and follows the following 5 key ideas of copying gc
1. “most objects die young”
- statistics show that between 80-95% of objects die before the next
megabyte of heap has been allocated
2. “give objects time to die”
- we do not want to collect the youngest objects because they are likely
to still be alive
3. “Avoid collecting old objects”
- not as likely to be dead
4. “incrementality improves responsiveness”
- breaking down amount that needs to be collected at one time
increases response time
5. “copying gc can improve locality”
- reduces amount of fragmentation
- when survivors are copied, they are copied contiguously in memory

Slide 8: Organizational Terms
- before looking at an example of Beltway, there are two terms you must know: belts and increments
- the beltway collector is made up of what we call “belts”
- and the belts are made up of “increments” (which are independently collectible regions of memory)
- both belts and increments can be collected independently

Slide 9: A Simple Example

Slide 10: A More Interesting Example

Slide 11: So What’s the Problem?
- you might be asking yourself this very question – so what’s the problem?
- the beltway examples I showed you follow the 5 principles of copying gc and the beltway gc seems to be a great new collector
- unfortunately, Steve and Kathryn found they could not get FIFO in the nursery without a significant performance hit
- this is the problem we tried to solve this summer
- to understand the reasons behind this problem, we must first look at how pointers are handled in beltway

Slide 12: Pointers and Write Barriers
- pointers whose source and target are in the same increment are called “intra-increment” pointers and are ignored
- pointers whose source and target are in different increments need only be remembered if the target could be collected before the source
- these are old-young pointers (pointers going from an object in an older increment to an object in a younger increment)
- pointers are tested by a write barrier
- the write barrier also has the function of remembering old-young pointers
- to understand how a write barrier works, we need to look at a diagram of a heap

Slide 13: What are Write Barriers?
- if we implement two write barriers (the gray lines), the heap is divided into 3 increments
- if we say that the leftmost increment is the youngest increment (meaning we collect from left to right), we now need to remember only those pointers that cross a barrier from right to left
- this eliminates the need to remember all pointers in the heap
- pointers “to remember” in grey (left) are the pointers the write barrier would have to remember if we were collecting increment 1
- pointers “to remember” in red (middle) are the pointers the write barriers would have to remember if we were collecting increment 2
- pointers “to remember” in gray (right) are the pointers the write barrier would have to remember if we were collecting increment 3
- write barrier benefits us by: giving us better performance, targeted collection, and shorter pause times (less time spent in gc)
- the write barrier sounds like a good idea but it does not come without its cost

Slide 14: Overhead of the Write Barrier
- overhead of the write barrier comes in two forms:
- fast path: does the pointer cross a write barrier?
- slow path: if so, does the pointer need to be remembered?
- as stated, the fast path is cheap (we use a mask and XOR for this) and the slow path is expensive
- now getting back to the problem of the performance hit from a FIFO nursery

Slide 15: Motivation for Optimization
- Steve and Kathryn found that the expensive slow path was being evaluated a lot
- having a FIFO nursery requires many look-ups to determine whether a pointer needs to be remembered
- the quick solution Kathryn and Steve found was to remove the FIFO behavior from the nursery
- to remove the FIFO behavior, two rules needed to be implemented: there could only be a single nursery and it always had to be collected first
- however this made beltway more specific case and Kathryn wanted the gc to be more general
- also without a FIFO nursery, they could not reap the benefits of OF (the idea that we should “give objects time to die”)

Slide 16: Why was Slow Path Evaluated A lot?
- the final clue to the performance hit puzzle was to determine why the slow path was being evaluated so much
- Steve and Kathryn hypothesized that it was because of pointer to TIBs
- TIB stands for “type information block”
- Important things to know about TIBs:
- created when a class is loaded
- declared as an array of object references and allocated into the
nursery (just like all other objects)
- stores information about the class such as methods, virtual
methods, etc
- every object has a pointer to the TIB in its header

Slide 17: The TIB Write Barrier
- because pointers to the TIBs are in the object header, they are not seen by the normal write barrier
- Steve and Kathryn implemented a TIB write to remember pointers to TIBs if necessary
- however the TIB write barriers account for most of write barrier activity
furthermore, it is never necessary to remember pointers to TIBs
- so if we removed the TIB write barrier we thought we could decrease the number of slow path evaluations, thus solving the problem of the performance hit in the nursery
- but we can only remove w/b if we move all TIBs to a “special” place in memory

Slide 18: Optimizations for Beltway
- Here’s what we did
- we implemented an immortal space for TIBs to live for the duration of the program
- the immortal space will never be collected
- turned off the TIB write barrier

Slide 19: A Simple Case First
- but before we could implement these optimizations, we wanted to look at a simpler case to get an idea of how they would affect performance
- so we implemented these changes in an Appel generational copying collector

Slide 20: Appel Generational Copying GC
- objects are grouped into 2 generations according to their “age”
- age is determined by the amount of the heap allocated since the object was created
- generation 0 is called the nursery and generation 1 is called the older generation
- objects are allocated into the nursery
- when the nursery fills, we collect it and promote survivors to the older generation
- we continue allocation into the nursery and the cycle continues
- when the older generation fills, we collect both the older generation and the nursery
- pointers are handled as in beltway (i.e. intra-generational pointers are ignored and old-young intergenerational pointers must be remembered)

Slide 21: Appel Facts to Remember
- nursery is always collected before the older generation
- collection is not FIFO
- nursery is collected most often following the hypothesis that “most objects die young”
- note that this hypothesis is one of the principles of copying gc

Slide 22: Optimizations for Appel
- just like our optimization for Beltway, in Appel we created an immortal space for TIBs and removed the tib write barrier
- the only difference with the tib write barrier is that in Appel the tib write barrier only has a fast path
- this fast path does both tests (does a pointer cross a boundary and if so does it need to be remembered)

Slide 23/24: Results for Appel
- Notice that removing the TIB write barrier (green line and aqua line) causes a significant decrease in runtime (as much as 10% in some places) as compared to Appel without the optimizations
- putting the TIBs in an immortal space does not have much affect on the run-time
- javac: Sun JDK Java compiler compiling jess (another benchmark which is a system shell)
- pseudojbb: emulates a 3-tier transaction processing system

Slide 25: Results for Beltway
- we do not have any results for beltway yet (they are running on the computer as we speak)
- however based on the results from Appel, we expect that removing the TIB write barrier will lower the run-time (probably more so than in Appel)
- we also do not believe that putting the TIBs into the immortal space will have much of an effect on run-time (as in Appel)

Comments :

0 komentar to “Cliff Notes”

Posting Komentar


profil me

collection tutorials

Name :   Ridwan Syarif
location: Medan

ideals I want to continue to learn and run the internet



website pendidikan ilmu dan belajar gratis desain grafis tutorial photoshop Tutorials and reference guides for the Java Programming Lanugage Complete tutorial from that covers from basics up to object oriented programming. adalah tempat belajar pembuatan website dari mulai programing This tutorial introduces the reader informally Python language and system. Artikel komputer, tips dan trik, windows, tutorial, trouble shooting Click Here for Tutorial Basics. Test Drive RefWorks Cara membuat blog website gratis tutorial blogger indonesia Directory of tutorials for software programs such as MS Excel lists tens of thousands of tutorials for Photoshop Learn how to take and edit digital photographs using tutorials Three tutorials, two half-day (3 hours) and one full day (6 hours) Tutorial Photoshop, gudangnya tutorial photoshop Articles & Tutorials. Deploying a Mashup as a Google Gadget EuroBSDCon 2008 Tutorials. Schedule. Thursday - October 16th 2008 LexisNexis AU · Subscribe Now · What's new · 7 Day Trial Even if you hate images of text on the web, this tutorial This is a collection of just about all the tutorials and docs I know any example code contained in any of these Java Tutorials pages United States Searches valuation by website links to websites tutorial tutorial home jobs function type returned Video Conferencing Equipment Online games tutorial Net What is your portal fun tutorial games training program designed tutorial Learn tie internet Magazine featuring collection Alexa Site collection bandwidth collection Art sale hundreds Online gallery of artists Official site includes updates collection what information collection Horror movies entertainment classifieds leading European supplier collection instituciĆ³n financiera Web standards resources collection automobiles is the net's largest collection Managed Hosting software's official homepage Welcome to Yahoo Get product information search engine optimization Business from Asia to Europe. Search Engine Submission - AddMe free search engine website submission top optimization

Search Engine Optimization and SEO Tools
Submit Your Site To The Web's Top 50 Search Engines for Free! Join My Community at MyBloglog! Add to Technorati Favorites Add to Technorati Favorites Directories Blogs - BlogCatalog Blog Directory