Sunday, July 28, 2013

What drives Full GC duration ?

Its obvious that, the more memory allocated, the longer a full GC pause will be. However a GC has to track references, so I want to find out if primitve fields (like int, long) also increase Full GC duration. Additionally I'd like to find if the structure of an object graph has impact on GC duration.

The Test

I am creating a number of instances of the following classes:
    static class GCWrapper {
        GCWrapper(Object referenced) {
            this.referenced = referenced;
        }
        Object referenced;
    }
    static class GCWrapperMiddle {
        int a,b,c,d,e,f,g,h,i,j,k,l;
        GCWrapperMiddle(Object referenced) {
            this.referenced = referenced;
        }
        Object referenced;
    } 
    static class GCWrapperFat {
        int a,b,c,d,e,f,g,h,i,j,k,l;
        long aa,ab,ac,ad,ae,af,ag,ah,ai,jj,ak,al;
        GCWrapperFat(Object referenced) {
            this.referenced = referenced;
        }
        Object referenced;
    }
they all hold exactly one reference. But "Middle" and "Fat" additionally contain primitive fields, which increases their memory consumption a lot.
I am chaining those objects after creation to a linked list. For locality tests, the reference is pointed to a random other "GCWrapper" Object to create "far" references.
Additionally I am using the class below to test effects of "many references", a highly interlinked Object graph:
    static class GCWrapperLinked {
        GCWrapperLinked(Object referenced) {
            this.r1 = referenced;
        }
        Object r1,r2,r3,r4,r5;
    }
After instantiation, the test does 5 GC's using System.gc() and takes the last value (~3 calls are required until time stabilizes). 
Tests are done on an Intel i7 4 core 8 threads mobile processor with a somewhat outdated JDK 7 u 21, as I am in vacation currently with a pretty bad internet connection ...

What has more impact, Memory Size or Number of Object (-References) ?


The test was done with all collectors and different number of Objects on the Heap. Objects were allocated in  a linked List like
        GCWrapperMiddle res = new GCWrapperMiddle(null);
        for ( int i = 0; i < len; i++ ) {
            res = new GCWrapperMiddle(res);
        }
        return res;

The result shows clear linear dependency inbetween the number of Objects and Full GC duration.
Please don't conclude Default GC (ParOldGC) is slowest from the results, because
a) subsequent calls to system.gc() without mutation may enable Collectors to cut corners
b) they might choose to use fewer/more threads during collection

I test all Collectors just to ensure that observed interdependencies are present for all collectors.

Now let's compare effects of Object size on Full GC durations. As described above, I pumped up object size by adding int and long fields to them. Those fields cannot contain references to other objects (no need to scan them) but still consume space. The test creates 6 million objects of the classes shown above. Heap consumption is:

  • 163 Mb for 'small'
  • 427 Mb for 'middle'
  • 1003 Mb for 'large'
Now that's interesting:
Object size has a minor impact on Full GC duration (the differences observed can be attributed mostly to CPU cache misses, i assume). Main driver of FullGC duration is the number of object (-references). 


Does GC duration depend on number of objects or the number of object-references ?


To test this, I create an object graph where each gcwrapper object points to another randomly choosen gcwrapper object.
        GCWrapper res[] = new GCWrapper[len];
        for ( int i = 0; i < len; i++ ) {
            res[i] = new GCWrapper(null);
        }
        for ( int i = 0; i < len; i++ ) {
            res[i].referenced = res[((int) (Math.random() * len))];
        }
        return res;
and ('5 refs')
        GCWrapperLinked res[] = new GCWrapperLinked[len];
        for (int i = 0; i < res.length; i++) {
            res[i] = new GCWrapperLinked(null);
        }
        for (int i = 0; i < res.length; i++) {
            res[i].r1 = res[((int) (Math.random() * len))];
            res[i].r2 = res[((int) (Math.random() * len))];
            res[i].r3 = res[((int) (Math.random() * len))];
            res[i].r4 = res[((int) (Math.random() * len))];
            res[i].r5 = res[((int) (Math.random() * len))];
        }
        return res;


Oops, now that's surprising. It's strange, that DefaultGC (ParOldGC) actually gets faster for objects containing *more* references to (random) other objects !! This is not a test error and reproducable.
You probably now, that todays CPU's have a multi stage cache and that access to main memory is extremely expensive compared to cache hits, so locality (memory wise) is pretty important. Its obvious this also hit's Full GC when iterating the live set of objects.
(see http://www.akkadia.org/drepper/cpumemory.pdf for more information you'd probably want to read about caches ;-) ).

In contradiction to the CMS collector, ParOldGC ('DefaultGC') is able to compact the heap during Full GC. It seems it does this in a way optimizing the randomly linked object graph by moving objects close to objects referencing them (that's my speculative explanation, others are welcome ..).

This observation leads to the following test:
A comparion of FullGC of 6 million GCWrapper object graphs. One setup as linked list (linked in allocation order) and one with randomly choosen referenced objects.

        GCWrapper res = new GCWrapper(null);
        for ( int i = 0; i < len; i++ ) {
            res = new GCWrapper(res);
        }
        return res;
vs
        GCWrapper res[] = new GCWrapper[len];
        for ( int i = 0; i < len; i++ ) {
            res[i] = new GCWrapper(null);
        }
        for ( int i = 0; i < len; i++ ) {
            res[i].referenced = res[((int) (Math.random() * len))];
        }
        return res;
Boom ! The impact of locality is massive. This will also have a strong impact on performance of a java application accessing those data structures.

Conclusion:

Full GC duration depends on the number of objects allocated and the locality of their references. It does not depend that much on actual heap size.


Questionable design patterns regarding (OldGen) GC and overall locality


I think one can safely assume, that objects allocated at the same time have a high chance to be "near" each other (Note: CMS heap fragmentation may behave different if the application fragments the heap). So whenever statically allocated data is updated by refering to a newly allocated Object, chance is, that the new Object is far away from the referencee, which will cause cache misses. Especially the massive use of Immutables as favoured by many designs and (newer VM-based languages) actually is deadly regarding locality and OldGen GC.
  • Lazy initialization/instantiation
  • Value classes. E.g. GC-wise its better to use a primitive long instead of Date.
  • Immutables (except preallocated Flyweight's)
  • Fine grained class design 
  • Preferring Composition over Subclassing (many wrapper, delegate Objects)
  • JDK's HashMap uses entry objects. Use open addressed Hashmaps instead
  • Use of Long,Integer,Short instead of primitives in static data (unfortunately Java's Generics encourage this). Even if the VM does some optimization here (e.g. internal caching of Integer's), one can verify easily that these objects still have severe impact on GC duration

31 comments:

  1. 1. Especially the massive use of Immutables as favoured by many designs and (newer VM-based languages) actually is deadly regarding locality and OldGen GC.

    OldGenGCs won't see many of those objects anyway - furthermore Hotspot features a technique called "object explosion" driven by knowledge gathered during the escape analysis pass.

    2. you create a single giant linked list:
    - this eliminates the possibility for generational GCs to only process a bit of your workload.
    - this eliminates any possibility for parallization


    long story short: it isn't that easy.

    ReplyDelete
    Replies
    1. دانلود آهنگ قدیمی
      Devops is not a Tool.Devops Is a Practice, Methodology, Culture or process used in an Organization or Company for fast collaboration, integration and communication between Development and Operational Teams. In order to increase, automate the speed of productivity and delivery with reliability.
      دانلود آهنگ غمگین

      Delete
    2. Hello your post is very helpful, thanks for wonderful information sharing. When you go about Find information and tips on Coffee Culture Around the World.
      Hello your post is very helpful, thanks for wonderful information sharing. When you go about Find information and tips on left breast
      Hello your post is very helpful, thanks for wonderful information sharing. When you go about Find information and tips on tongue scraper
      Hello your post is very helpful, thanks for wonderful information sharing. When you go about Find information and tips on blogger outreach
      Hello your post is very helpful, thanks for wonderful information sharing. When you go about Find information and tips on thick toenail
      Hello your post is very helpful, thanks for wonderful information sharing. When you go about Find information and tips on High da guest post
      Hello your post is very helpful, thanks for wonderful information sharing. When you go about Find information and tips on Women's Unstitched Summer Lawn Collection
      Hello your post is very helpful, thanks for wonderful information sharing. When you go about Find information and tips on Kamar Dard Ka ilaj

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. It is amazing and wonderful to visit your site.Thanks for sharing this information,this is useful to me...
    http://chennaitraining.in/etl-testing-training-in-chennai/
    http://chennaitraining.in/java-training-in-chennai/
    http://chennaitraining.in/python-training-in-chennai/
    http://chennaitraining.in/r-programming-training-in-chennai/
    http://chennaitraining.in/salesforce-developer-training-in-chennai/
    http://chennaitraining.in/sap-hana-training-in-chennai/

    ReplyDelete
  4. A Chatbot Development is a product program for reproducing wise discussions with human utilizing rules or man-made brainpower. Clients connect with the Chatbot development service by means of conversational interface through composed or spoken content. Chatbots can live in informing stages like Slack, Facebook Messenger bot developer and Telegram and fill some needs – requesting items, thinking about climate and dealing with your fund in addition to other things. As a Chatbot development company advancement organization our competency let you find happiness in the hereafter by taking care of clients all the more intelligently to accomplish wanted outcome. As a Chatbot companies we can streamline a large portion of your dreary undertakings, for example, voice bot advancement and client service, online business advices and so on

    ReplyDelete
  5. Thanks for provide great informatic and looking beautiful blog, really nice required information & the things i never imagined and i would request, wright more blog and blog post like that for us. Top 10 Makeup Artists in Kolkata

    ReplyDelete
  6. Thanks for sharing with us. I just loved your way of presentation. I enjoyed reading this .Thanks for sharing and keep writing. It is good to read blogs like this. Clinical Research Courses

    ReplyDelete
  7. Nice blog, I really appreciate the hard efforts you would have taken while creating this informational blog. Rubix Market Research

    ReplyDelete
  8. I'm hoping you have some insight for me. I very sincerely appreciate your time. Perhaps this topic may be a good one to blog about. I imagine I'm not the only one trying to figure this out. Plus, with the fires in Northern California, seems like a lot of guys are getting back into construction after having let their licenses expire.

    thetechiefinds.com
    thetechmagazines.com
    thetechiefind.com
    thetechtrending.com

    ReplyDelete
  9. با برنامه ریزی کمپین تبلیغات در تلگرام به صورت گسترده تبلیغات کنید.

    ReplyDelete
  10. Women choose sarees above other traditional attire in order to create a fashion statement. Finding the right hairstyle for a saree might be difficult. Just take a look at simple indian hairstyle for saree

    ReplyDelete
  11. Best Digital Marketing courses | Web development training institute in Chennai,chennai - Learnfella
    Learnfella Offers Digital Marketing, Web and mobile app development, Machine learning,
    Video editing and animation course Training in Shenoynagar, Anna nagar, Padi, Ambattur,
    Kilpauk, Arumbakam, Chennai with Learnfella. Get the best training with live interactive classes, real-world case studies, and expert trainers.
    Digital Marketing Course in chennai,
    Digital Marketing Training in chennai,
    best Digital Marketing Training in chennai,
    best Digital Marketing institute in chennai,
    Digital Marketing classes in chennai,

    ReplyDelete
  12.  اصطلاح "فیلر لب" یک کلمه پرطرفدار است که بسیاری از جوانان علاقه بیشتری به این روش نشان می دهند. تزریق فیلر لب یک درمان بی خطر است که پزشک متخصص ژل حاوی اسید هیالورونیک را مستقیماً به لب ها تزریق می کند.
    در کلینیک دکتر خلیلی بهترین برند های دنیا با روشی بدون درد تزریق میشوند.
    کلینیک دکتر خلیلی

    ReplyDelete
  13. Great, I like to read your article! Here is the best java training courses in Delhi that you should learn if you want to be a Java expert.

    ReplyDelete
  14. "Great article! I appreciate the in-depth information on your article. Keep up the good work."

    Python fullstack training in hyderabad

    ReplyDelete