René Schwietzke

• Co-Founder and Managing Directory Xceptance
• Working with Java since version 1.0
• Performance Tester since 1999
•    @ReneSchwietzke

Optimizing Java by Evans/Gough/Newland

Aleksey Shipilëv: https://shipilev.net/

• There is no universal truth
• BUT these challenges are universal and apply to most languages
• Java makes things comfortable but comfort must be paid for

Or in other words

• Allocate (new)
• Access (your code)
• Move (OS + GC)
• Free (OS + GC)

• Default stack on 64 bit Linux is 1024KB
• Heap can be sized with initial and max size, Java will determine the use of this large area mostly on its own
• Meta space (non-heap) can be sized as well, especially when a lot of classes are loaded, by default unlimited and growth as needed
• Initial code cache is 245,760 Kb, max is 251,658,240 Kb (PrintFlagsFinal does not match -XX:+PrintCodeCache)

        
final static FastRandom r = new FastRandom(7L);
int a; int b;

@Setup
public void setup()  {
    a = r.nextInt(1000) + 128;
    b = r.nextInt(1000) + 128;
}

@Benchmark
public int newInteger() {
    Integer A = new Integer(a);
    Integer B = new Integer(b);
    
    return A + B;
}

@Benchmark
public int integerValueOf() {
    Integer A = Integer.valueOf(a);
    Integer B = Integer.valueOf(b);
    
    return A + B;
}

@Benchmark
public int ints() {
    int A = a;
    int B = b;
    
    return A + B;
}

Benchmark                                Mode  Cnt    Score       Error   Units
newInteger                               avgt    3   24.187 ±    29.639   ns/op
newInteger:·gc.alloc.rate.norm           avgt    3   32.000 ±     0.001    B/op

integerValueOf                           avgt    3    5.778 ±    10.026   ns/op
integerValueOf:·gc.alloc.rate.norm       avgt    3    ≈ 10⁻⁶               B/op

ints                                     avgt    3    5.145 ±     2.536   ns/op
ints:·gc.alloc.rate.norm                 avgt    3    ≈ 10⁻⁶               B/op

ints()
0x...fbcc: mov    0x10(%rsi),%eax
0x...fbcf: add    0xc(%rsi),%eax   ; - ints@12 (line 55)

integerValueOf()
0x...264c: mov    0x10(%rsi),%eax  ; - integerValueOf@-1 (line 44)
0x...264f: add    0xc(%rsi),%eax   ; - integerValueOf@24 (line 47)

No out-of-thin-air reads: Each read of a variable must see a value written by a write to that variable.

Benchmark            (size)  Mode  Cnt       Score   Units
safe                      1  avgt    5      38.608   ns/op
safe                    100  avgt    5      71.374   ns/op
safe                  1,000  avgt    5     552.221   ns/op
safe                 10,000  avgt    5   4,571.595   ns/op
safe              1,000,000  avgt    5 853,938.677   ns/op

unsafe                    1  avgt    5      98.436   ns/op
unsafe                  100  avgt    5      91.668   ns/op
unsafe                1,000  avgt    5     148.716   ns/op
unsafe               10,000  avgt    5     127.362   ns/op
unsafe            1,000,000  avgt    5     156.854   ns/op

unsafeInitialized         1  avgt    5     158.442   ns/op
unsafeInitialized       100  avgt    5     173.470   ns/op
unsafeInitialized     1,000  avgt    5     437.876   ns/op
unsafeInitialized    10,000  avgt    5   2,570.801   ns/op
unsafeInitialized 1,000,000  avgt    5 387,303.491   ns/op

        
Benchmark               (size) Mode  Cnt       Score    Units
safe:·gc.alloc.rate         1  avgt    5     144.246   MB/sec
safe:·gc.alloc.rate       100  avgt    5   1,550.342   MB/sec
safe:·gc.alloc.rate     1,000  avgt    5   3,854.734   MB/sec
safe:·gc.alloc.rate    10,000  avgt    5   5,459.355   MB/sec
safe:·gc.alloc.rate 1,000,000  avgt    5   2,995.923   MB/sec

Benchmark                           Mode Cnt  Score     Units
step1                               avgt   2  41,528    ns/op
step1:CPI                           avgt           0.866 #/op
step1:IPC                           avgt           1.154 #/op
step1:L1-dcache-load-misses         avgt       6,062     #/op
step1:L1-dcache-loads               avgt      96,620     #/op
step1:LLC-load-misses               avgt           2     #/op
step1:LLC-loads                     avgt          32     #/op
step1:cycles                        avgt     100,055     #/op
step1:instructions                  avgt     115,507     #/op

step16                              avgt   2  12,636    ns/op
step16:CPI                          avgt           1.244 #/op
step16:IPC                          avgt           0.804 #/op
step16:L1-dcache-load-misses        avgt       6,132     #/op
step16:L1-dcache-loads              avgt       6,181     #/op
step16:LLC-load-misses              avgt           0     #/op
step16:LLC-loads                    avgt       4,111     #/op
step16:cycles                       avgt      30,922     #/op
step16:instructions                 avgt      24,855     #/op
                                                     
step32                              avgt   2   6,993    ns/op
step32:CPI                          avgt           1.375 #/op
step32:IPC                          avgt           0.727 #/op
step32:L1-dcache-load-misses        avgt       3,047     #/op
step32:L1-dcache-loads              avgt       3,122     #/op
step32:LLC-load-misses              avgt           0     #/op
step32:LLC-loads                    avgt       2,808     #/op
step32:cycles                       avgt      17,244     #/op
step32:instructions                 avgt      12,542     #/op

step1Reverse                        avgt   2  41,657    ns/op
step1Reverse:CPI                    avgt           0.760 #/op
step1Reverse:IPC                    avgt           1.316 #/op
step1Reverse:L1-dcache-load-misses  avgt       6,153     #/op
step1Reverse:L1-dcache-loads        avgt      97,628     #/op
step1Reverse:LLC-load-misses        avgt           1     #/op
step1Reverse:LLC-loads              avgt          42     #/op
step1Reverse:cycles                 avgt     102,766     #/op
step1Reverse:instructions           avgt     135,300     #/op

• It costs 100 to 200 cycles when we have to go to main memory
• Hence Java and the CPU avoid main memory access at all cost
• Java doesn't give you the notion of a memory location, hence you cannot directly influence it
• Things will change with project Valhalla and its inline classes that brings primitive data type performance to "objects"

• Object header: markword, classword
• classword: the reference to the class
• markword: metainfo about the object

64 bits:
--------
unused:25 hash:31 -->| unused:1   age:4    biased_lock:1 lock:2 (normal object)
JavaThread*:54 epoch:2 unused:1   age:4    biased_lock:1 lock:2 (biased object)
PromotedObject*:61 --------------------->| promo_bits:3 ----->| (CMS promoted object)
size:64 ----------------------------------------------------->| (CMS free block)

unused:25 hash:31 -->| cms_free:1 age:4    biased_lock:1 lock:2 (COOPs && normal object)
JavaThread*:54 epoch:2 cms_free:1 age:4    biased_lock:1 lock:2 (COOPs && biased object)
narrowOop:32 unused:24 cms_free:1 unused:4 promo_bits:3 ----->| (COOPs && CMS promoted object)
unused:21 size:35 -->| cms_free:1 unused:7 ------------------>| (COOPs && CMS free block)

• References can only be stored with 4 byte alignment (32 bit) or 8 byte (64 bit)
• Full objects can only be stored with 8 byte (64 bit) alignment to each other
• Full 64 bit values can also only be stored fully aligned (double, long)

class A 
{
    String s1;
    boolean b1;
    // int i1;

    String s2;
    boolean b2;
    long i2;
}

=== Instance Layout ====================================
org.jol.A object internals:
 OFFSET  SIZE               TYPE DESCRIPTION                               
      0     4                    (object header)                           
      4     4                    (object header)                   
      8     4                    (object header)                       
     12     1            boolean A.b1                                      
     13     1            boolean A.b2                                      
     14     2                    (alignment/padding gap)                  
     16     8               long A.i2                                      
     24     4   java.lang.String A.s1                                      
     28     4   java.lang.String A.s2                                      
Instance size: 32 bytes
Space losses: 2 bytes internal + 0 bytes external = 2 bytes total

public class GCAndAccessSpeed 
{
    private final static int SIZE  = 100_000;
    private final List<String> STRINGS = new ArrayList<>();
    private final List<String> ordered = new ArrayList<>();
    private final List<String> nonOrdered = new ArrayList<>();
    
    @Param({"false", "true"}) boolean gc;
    @Param({"1", "10"})       int COUNT;
    @Param({"false", "true"}) boolean drop;
    
    @Setup
    public void setup() throws InterruptedException
    {
        final FastRandom r = new FastRandom(7);
        for (int i = 0; i < COUNT * SIZE; i++)
        {
            STRINGS.add(RandomUtils.randomString(r, 1, 20));
        }
        
        for (int i = 0; i < SIZE; i++)
        {
            ordered.add(STRINGS.get(i * COUNT));
        }
        nonOrdered.addAll(ordered);
        Collections.shuffle(nonOrdered, new Random(r.nextInt()));
        
        if (drop)
        {
            STRINGS.clear();
        }
        
        if (gc) 
        {
            for (int c = 0; c < 5; c++) 
            {
                System.gc();
                TimeUnit.SECONDS.sleep(2);
            }
        }
    }
    
    @Benchmark
    public int walk[Ordered|NonOrdered]()
    {
        int sum = 0;
        for (int i = 0; i < [ordered|nonOrdered].size(); i++)
        {
            sum += [ordered|nonOrdered].get(i).length();
        }
        return sum;
    }
}

• Heap is split into four resizable areas
• Eden: All allocations happen here, also known as "New"
• Survivor S0: Space for objects to live a little longer
• Survivor S1: Similar to S0, but only one is in active use at the time
• Tenured: Where surviving objects continue to live and where large allocations are made, also known as "Old"

• Let's allocate some objects
• To simplify things, we ignore the size for now
• Important: If the object is too big, it will be allocated in Tenured directly

• TLAB - Thread Local Allocation Buffer
• To avoid Eden contention, we split up Eden
• Area per thread exclusively assigned
• No synchronization needed
• Thread just bumps the pointer
• TLABs are resized dynamically
• Allocation is almost O(1) now

Eden becomes full

• When the next allocation fails, Eden will be gc-ed
• Either all memory is allocated...
• ... or the next allocation request is bigger than free space
• Depending on algorithm, we either already marked objects or we stop and mark
• Unreferenced objects are discarded
• Referenced objects are hibernated in S0
• If the object does not fit, it goes to Tenured directly
• Eden has 0' now, the object that caused the GC

Do another round

• Let's fill up Eden again and GC
• Assume that we have only two generations in S0/S1 so we move some to Tenured

Assume we Eden GCed for a while...

• Now Tenured becomes full
• Either we reach a set limit or we cannot accommodate any new direct allocations or S0/S1 survivors
• CMS and ParallelGC start to mark live objects in parallel to running threads
• If your Tenured cannot accept survivors anymore, you have a Stop-the-World (STW) aka you run behind
• If you allocate large objects directly, your Tenured might be too fragmented, hence you STW to get compaction (CMS does not compact, ParallelGC does, it is STW all the time)

• Objects that don't fit Eden or TLAB section of Eden go directly to Tenured
• Many surviving objects might skip Survivor space because the Survivor size is too small
• Tenured has to finish quickly to avoid being the bottleneck when Eden has to copy through or allocate directly

• Tenured: Where the old objects live
• Long living objects, several seconds to minutes
• Humongous: Where the large objects live
• They get their own(!) regions when they are larger than 50% of region size
• Can span several regions
• Unused space is wasted
• Collected during Young
• Allocation of a humongous object triggers a mixed GC cycle

• -XX:+G1ReclaimDeadHumongousObjectsAtYoungGC (default)
• Instead of reclaiming humongous late we try to do it during Young collection now
• Still waste and fragmentation are a burden (first tuning target)

When Eden is full

• Eden is full (5% of heap initially)
• Scan all Eden regions
• Copy live objects to a survivor region
• Copy live objects from existing survivor regions (increment counter)
• No Eden is used anymore
• Calculate new statistics to tune Eden count

When Eden is full again

• Survivors are older aka count is up
• Some Survivors become Tenured

• When we are at 45% total usage, we start marking in parallel
• Snapshot-at-the-beginning (SATB) and marking if objects are live or dead
• Objects created after SATB are not considered, aka always live
• We are calculating the liveness per region continuously
• Start a young cycle first after marking
• After that we do a old collection
• Collect most "dead" regions first hence the name Garbage First Collector
• Not all Tenured will be collected, count is based on target pause time and adjusted frequently

Young Collection

Tenured Collection

• -XX:MaxGCPauseMillis=200
• Desired pause goal in milliseconds
• Not guaranteed to be achieved

• Tuning would fill another training
• Main goals: Avoid humongous objects and running into to-space exhaustion
• Besides that: Only no garbage is good garbage.

• In between two bytecodes or automatically inserted into compiled code
  • Return from a method
  • Each loop operation
• Automatically when blocked on monitor
• Automatically when in native code

• OS memory can be fragmented due to the slow transition from virtual to RSS
• Use -XX:+AlwaysPreTouch to avoid that, but you need the physical memory or OS will start paging when the JVM comes up
• With a lot of rarely accessed Tenured objects and no GC, a GC on Tenured can cause the OS to page
• Pre-G1 GC often touched all of in use memory and caused heavy paging when memory is scarce
• Theoretically G1 touches more memory more often

• G1 is NUMA-aware aka memory closer to a CPU is used
• Might deliver up to 30% more performance
• Java fully manages the memory in use, not the OS (off-heap allocations excluded)