Free space calculation of heap

[Srinivas Ramakrishna]

Hi Bond --

Sorry for the delay in responding... I hadn't had the time to visit the CMS
code to check a few things.
I just did and can confirm that what i described earlier is exactly how the
computation of fragmentation is
done. Recall that the only block sizes that enter into the calculation are
those that are free blocks.
In that sense, the total size of the free space should have little direct
bearing on the fragmentation metric
except through coalition and allocation strategies that cause such a trend
to be exhibited by the heap.
Now, let's think about the two extremal cases here first.

The first is at the start of the JVM's life or immediately following a full
collection, when all of the free
space is in a single large free block. In this case Sum(b^2) == (Sum(b))^2,
so fragmemtation = 0.
Consider now the other extreme where the entire free space has become
maximally fragmented, so
that all of the free blocks in the heap are of minimal object size, i.e.
say 3 heapwords (in the case of
the 64-bit heap). In this case,  if the heap is composed of k blocks of
size b each, then the
fragmentation metric is 1 - (k.b^2)/(k.b)^2 = 1 - 1/k, which tends to 1 as
k tends to infinity, i.e.
maximal fragmentation. Basically, the metric reflects how fine the
granularity of the free blocks is
vis-a-vis the available free space.

Now I can imagine that the allocation and sweep/coalition heuristics are
such that as the free space
dwindles, the fragmentation does drop. This can be seen as a good thing in
a well-tuned system.
The free space lives in the smaller free blocks in the so-called indexed
(small size block) lists,
and in the so-called (large-size) binary tree dictionary. As we come close
to the GC triggering threshold,
we find that most of the smaller blocks have been used up. The sweep then
starts and frees up the
smaller blocks which are by now dead, and based on historical demand,
places them back into the free
lists that they came from. So the system shifts constantly between the
state immedicately following a
sweep when the smaller-sized block freelists are fully populated, and
there's some free space in the
form of a few very large blocks in the binary tree dictionary, and then
progressively reaches a state
where the smaller blocks are all used up. In the former state, the
fragmentation looks higher and in
the latter case lower. At least to me that seems like a reasonable
explanation of the behaviour you
are seeing. Does it make sense to you and others on the list as well, or is
my explanation perhaps
too simplistic?

-- ramki

On Tue, Jun 5, 2012 at 12:05 AM, Bond Chen <Bond.Chen at lombardrisk.com>wrote:

>  Hi Srinivas,
> I have grep all free heap words size and frag of old generation, like 2
> line ( free=314669364 frag=0.6797 , free=314669364 frag=0.6797) from the gc
> log clip pasted below, draw a line chart, found the fragrate have the
> exactly same momentum as free size except the very first time period.
> q1, Am I draw the right chart? if true can the counter(frag) can truely
> reflect the rate of fragementation?
>
>
>
> Regards,
> Bond
>
>
>
>
> /****gc log clip ****/
> : 1378638K->93316K(1523200K), 1.0308235 secs]
> 3397083K->2111761K(6000128K)After GC:
> Statistics for BinaryTreeDictionary:
> ------------------------------------
> Total Free Space: 277079438
> Max   Chunk Size: 178032428
> Number of Blocks: 42888
> Av.  Block  Size: 6460
> Tree      Height: 67
> Statistics for IndexedFreeLists:
> --------------------------------
> Total Free Space: 37589926
> Max   Chunk Size: 256
> Number of Blocks: 6367913
> Av.  Block  Size: 5
> free=314669364 frag=0.6797
>
> After GC:
> Statistics for BinaryTreeDictionary:
> ------------------------------------
> Total Free Space: 0
> Max   Chunk Size: 0
> Number of Blocks: 0
> Tree      Height: 0
> Statistics for IndexedFreeLists:
> --------------------------------
> Total Free Space: 0
> Max   Chunk Size: 0
> Number of Blocks: 0
> free=0 frag=0.0000
> , 1.0336722 secs] [Times: user=3.30 sys=0.02, real=1.03 secs]
> Heap after GC invocations=101430 (full 337):
> par new generation   total 1523200K, used 93316K [0xfffffd7e5ea10000,
> 0xfffffd7ec8e10000, 0xfffffd7ec8e10000)
>   eden space 1305600K,   0% used [0xfffffd7e5ea10000, 0xfffffd7e5ea10000,
> 0xfffffd7eae510000)
>   from space 217600K,  42% used [0xfffffd7eae510000, 0xfffffd7eb4031090,
> 0xfffffd7ebb990000)
>   to   space 217600K,   0% used [0xfffffd7ebb990000, 0xfffffd7ebb990000,
> 0xfffffd7ec8e10000)
> concurrent mark-sweep generation total 4476928K, used 2018445K
> [0xfffffd7ec8e10000, 0xfffffd7fda210000, 0xfffffd7fda210000)
> concurrent-mark-sweep perm gen total 524288K, used 429440K
> [0xfffffd7fda210000, 0xfffffd7ffa210000, 0xfffffd7ffa210000)
> }
> Total time for which application threads were stopped: 1.0355841 seconds
> Total time for which application threads were stopped: 0.0042883 seconds
> Total time for which application threads were stopped: 0.0052694 seconds
> {Heap before GC invocations=101430 (full 337):
> par new generation   total 1523200K, used 1398916K [0xfffffd7e5ea10000,
> 0xfffffd7ec8e10000, 0xfffffd7ec8e10000)
>   eden space 1305600K, 100% used [0xfffffd7e5ea10000, 0xfffffd7eae510000,
> 0xfffffd7eae510000)
>   from space 217600K,  42% used [0xfffffd7eae510000, 0xfffffd7eb4031090,
> 0xfffffd7ebb990000)
>   to   space 217600K,   0% used [0xfffffd7ebb990000, 0xfffffd7ebb990000,
> 0xfffffd7ec8e10000)
> concurrent mark-sweep generation total 4476928K, used 2018445K
> [0xfffffd7ec8e10000, 0xfffffd7fda210000, 0xfffffd7fda210000)
> concurrent-mark-sweep perm gen total 524288K, used 429440K
> [0xfffffd7fda210000, 0xfffffd7ffa210000, 0xfffffd7ffa210000)
> 2012-06-04T18:33:21.721+0800: 263877.362: [GC Before GC:
> Statistics for BinaryTreeDictionary:
> ------------------------------------
> Total Free Space: 277079438
> Max   Chunk Size: 178032428
> Number of Blocks: 42888
> Av.  Block  Size: 6460
> Tree      Height: 67
> Statistics for IndexedFreeLists:
> --------------------------------
> Total Free Space: 37589926
> Max   Chunk Size: 256
> Number of Blocks: 6367913
> Av.  Block  Size: 5
> free=314669364 frag=0.6797
> Before GC:
>
> Statistics for BinaryTreeDictionary:
> ------------------------------------
> Total Free Space: 0
> Max   Chunk Size: 0
> Number of Blocks: 0
> Tree      Height: 0
> Statistics for IndexedFreeLists:
> --------------------------------
> Total Free Space: 0
> Max   Chunk Size: 0
> Number of Blocks: 0
> free=0 frag=0.0000
> 263877.364: [ParNew-
>
> /***gc log clip ***/
>
> >>> Srinivas Ramakrishna <ysr1729 at gmail.com> 6/4/2012 3:05 PM >>>
> On Su
>
>
> n, Jun 3, 2012 at 11:16 PM, Bond Chen <
> Bond.Chen at lombardrisk.com>wrote:
>
>
> [BOND] YES, THAT'S HOW I CALC THE FREE SPACE.
> >
>
> Good -- hopefully the subsequent emails cleared up the mystery.
>
>
> 1 -   (Sum(b_1^2)/(Sum(b_i))^2)
>
> > [BOND]: (Sum(b_1^2)/(Sum(b_i))^2) , THE FIRST ONE IS b_i OR b_1 (one) ?
> >
>
> Right, a typo. It should have been b_i, not b_1.
>
>
> >
> > [BOND]: MY OPTION DIDN'T INCLUDE PrintFLSCensus, SHOULD BE ONE OF MY NEW
> > ADDED OPTIONS THIS TIME
> > PrintFLSStatistics=2 (CHANGE =1 to =2)
> > PrintPromotionFailure
> > PrintHeapAtGC
> >
>
> I can check the code and let you know unless you fin out for yourself or
> someone else answers first.
> It's been a while since i looked at these options.
>
> -- ramki
>
> This e-mail together with any attachments (the "Message") is confidential and may contain privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and delete this Message from your system.  Any unauthorized copying, disclosure, distribution or use of this Message is strictly forbidden.
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/hotspot-gc-use/attachments/20120609/dbbc30cd/attachment.html