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

34 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. 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.

    python training in bangalore
    aws training in bangalore
    artificial intelligence training in bangalore
    data science training in bangalore
    machine learning training in bangalore
    hadoop training in bangalore
    devops training in bangalore

    ReplyDelete
  3. Gaining Python certifications will validate your skills and advance your career.
    python certification

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. thanks for ur valuable information,keep going touch with us

    Scaffolding dealers in chennai

    ReplyDelete
  6. Great blog !It is best institute.Top Training institute In Velachery
    http://trainingsinvelachery.in/bi-bw-training-in-velachery/
    http://trainingsinvelachery.in/solidworks-training-in-velachery/
    http://trainingsinvelachery.in/autocad-training-in-velachery/
    http://trainingsinvelachery.in/ansys-training-in-velachery/
    http://trainingsinvelachery.in/revit-architecture-training-in-velachery/
    http://trainingsinvelachery.in/primavera-training-in-velachery/

    ReplyDelete
  7. Great blog !It is best institute.Top Training institute In chennai
    http://chennaitraining.in/oracle-dba-training-in-chennai/
    http://chennaitraining.in/sql-server-dba-training-in-chennai/
    http://chennaitraining.in/teradata-training-in-chennai/
    http://chennaitraining.in/sap-hr-training-in-chennai/
    http://chennaitraining.in/sap-fico-training-in-chennai/
    http://chennaitraining.in/sap-abap-training-in-chennai/

    ReplyDelete
  8. It is amazing and wonderful to visit your site.Thanks for sharing this information,this is useful to me...
    http://chennaitraining.in/bi-bw-training-in-chennai/
    http://chennaitraining.in/solidworks-training-in-chennai/
    http://chennaitraining.in/autocad-training-in-chennai/
    http://chennaitraining.in/ansys-training-in-chennai/
    http://chennaitraining.in/revit-architecture-training-in-chennai/
    http://chennaitraining.in/primavera-training-in-chennai/

    ReplyDelete
  9. It is amazing and wonderful to visit your site.Thanks for sharing this information,this is useful to me...
    http://chennaitraining.in/bi-bw-training-in-chennai/
    http://chennaitraining.in/solidworks-training-in-chennai/
    http://chennaitraining.in/autocad-training-in-chennai/
    http://chennaitraining.in/ansys-training-in-chennai/
    http://chennaitraining.in/revit-architecture-training-in-chennai/
    http://chennaitraining.in/primavera-training-in-chennai/

    ReplyDelete
  10. Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care
    http://chennaitraining.in/creo-training-in-chennai/
    http://chennaitraining.in/building-estimation-and-costing-training-in-chennai/
    http://chennaitraining.in/machine-learning-training-in-chennai/
    http://chennaitraining.in/data-science-training-in-chennai/
    http://chennaitraining.in/rpa-training-in-chennai/
    http://chennaitraining.in/blueprism-training-in-chennai/

    ReplyDelete
  11. Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care
    http://chennaitraining.in/php-training-in-chennai/
    http://chennaitraining.in/nodejs-training-in-chennai/
    http://chennaitraining.in/reactjs-training-in-chennai/
    http://chennaitraining.in/ccnp-training-in-chennai/
    http://chennaitraining.in/mcsa-training-in-chennai/
    http://chennaitraining.in/mcse-training-in-chennai/

    ReplyDelete
  12. 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
  13. hey if u looking best Current affair in hindi but before that what is current affair ? any thing that is coming about in earth political events. things that act on the meeting, if need this visit our website and get best Current affair in hindi

    ReplyDelete
  14. 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