Garbage Collection - Compiler Design, Computer Science & Engineering Video Lecture - Computer Science Engineering (CSE)

welcome to the lecture on garbage
collection this is going to be a lecture
on the application of static analysis to
garbage collection so static analysis
for identifying and allocating clusters
of four immortal objects so why do we
really need to do garbage collection
this we have already discussed in one of
the previous lectures on memory
management so garbage collection is a
necessity in modern object-oriented
languages it hides the problems of
memory management from the programmer
that is very briefly put what GC is all
about so basically when we create
dynamic data structures the nodes of the
dynamic data structure such as tree or
linked list would be deleted as per the
program requirements and instead of
placing the burden of you know returning
the deleted nodes to the memory pool it
is possible to arrange the garbage
collected collect such deleted and then
used nodes and return them to the memory
pool however there is a performance
penalty due to garbage collection and
this has been addressed by many methods
so for example generational garbage
collection and concurrent garbage
collection or two methods by which we
try to reduce the overhead of garbage
collection so what is generational GC we
are going to see a little more of this
in the in the near future basically we
try to arrange objects into many
generations that is according to their
eh so some objects live very long some
objects live a very short life so if
they are arranged according
their life then the younger generations
that is the generations which store
younger or short lifetime objects can be
garbage collected frequently whereas the
older generations need not be garbage
collected so frequently so this in turn
reduces the overheads of garbage
collection concurrent garbage collection
is you know is now the way GC is done
basically garbage you know when we run a
thread and that does all the garbage
collection we are really not coming in
the way of the main program so the main
program is not stopped but at the same
time garbage collection keeps happening
so this is a little more challenging
when exactly should we stop the main
program and how long is the question
that a concurrent garbage collector has
to authorize it now cluster allocation
reduces the number of collections and
makes each collection more effective so
what is cluster location so basically if
we look at very long living objects and
if we are able to collect all of them
together in one bunch we do not allocate
memory to those in the same you know
heap that is used for other objects then
you know it is generational in nature so
what only thing is we need to do this
cluster location separately it is not
exactly the same as generational because
in generational collection the aged
objects are moved to older generation
but in cluster location allocation
itself is done in a slightly different
way in a different heap structural what
is the cost of a tracing garbage
collector a tracing garbage collector
really goes through the memory and then
copy subjects and so on and so forth so
the overall elapsed time and then it
consists of two
parts garbage collection time and the
main program time so here we have in the
GC time we have passed time tracing time
and cash miss time etcetera etcetera so
basically past time is the time for
which the main program is stopped racing
time is the time needed to go through
the memory completely and determine what
is garbage what is not and so on and
cache miss time is because of mrs. in
the cache in the program time of course
cache miss time is a factor mutator time
is the actual program running time
allocation time is the memory allocator
time and barrier time is the
synchronization of threads iterative
there is a system over at all these
comprise the program time so when we
talk about the effectiveness of a
garbage collector we are not definitely
going to look at the overall elapsed
time for the program but we will also
look at the past time because how many
times is the main program stopped in
between and how long that is the past
time that becomes very important what
are the past approaches to reduce cost
of garbage collection so as we discussed
just now generational collection small
going on we collect smaller areas at a
time so the older areas are collected
infrequently younger areas are corrected
frequently so this definitely reduces
the cost of garbage collection
concurrent garbage collection also
reduces it then there is something
called opportunistic collection in which
the programmer is supposed to identify
what are known as key objects and these
key objects are the roots of trees or
headers of link lace etcetera when the
whole data structure is not very useful
then you know the key or if we we can
say all the objects pointed to by the
key object can be garbage collected so
then we can schedule the collection of
such key objects when the program
activity is low but this has to be done
carefully and there is a programmer
intervention rather program
specification of key objects which is
quad compiler assistance for garbage
collection so there is something called
region collection so you take the
regions of 4 program so within that
region a data structure may be created
used and then this post off so if we are
able to detect regions of this kind then
garbage collection can be based on that
region and escape analysis and stack
allocation also are very helpful here we
intend to find out which objects
actually are confined to procedures or
functions and they are not visible
outside so such analysis called escape
analysis is useful in determining
objects which can be allocated on the
stack instead of on the heap so if they
are allocated on the stack as soon as a
activation record or dies the the space
for that particular object also gets
collected so now coming back to our
scheme we said we want to detect
clusters of long living objects so let
us see what is the effect of long living
objects on garbage collection on various
benchmark programs so scavenging long
life objects accounts for a significant
part of garbage collection time so what
is indicated here for many benchmarks is
the amount of time that is needed to
scavenge such long living objects so as
you can see this is a fairly large
amount of time for some programs and
very small for some other programs so
the indication is some programs have
long living objects and some programs
don't in such a case it is necessary
that the compiler detect whether the
program has long living objects or it
doesn't how do we reduce scavenge time
in garbage collection so we have to go
through the entire memory find out what
is garbage what is not etcetera etcetera
so compute the lifetimes of objects and
bind them to the activation record of a
method that uses them lost so in other
words
once we know the lifetime of objects
there are many methods which use this
object so the last one which uses that
object is can also be responsible for
disposing of the object and return it to
the memory pool so that is the basic
idea this can handle volatile objects
well but not long living objects because
long living objects you know may live
through the entire program so the if
they are allocated on the same heap as
any other object then we would be really
going through the memory which need not
be disposed of every time that is the
long living objects will be scanned
every time whereas if we allocate such
long living objects in a separate memory
area then we do not have to go through
them during garbage collection then
stack allocation instead of heap
allocation is a possibility for some of
the objects but definitely long living
objects do not benefit so much from this
so it is possible that we want to use
both techniques that is stack allocation
wherever possible and heap allocation
for wherever possible and clusters
allocation wherever possible we cannot
handle related objects that refer to
each other in this stack allocation
methodology so for example dynamic data
structures so they may refer to each
other but they died together so such
objects cannot be you know allocated on
the stack they will have to be located
on him but if we detect that these are
long living objects then and the
compiler helps in such detection then
they can be allocated in a separate area
so the basic principle as I have been
stressing till now is detect long living
clusters and locate them separately so
let us look at some highlights of our
scheme so identify clusters of long
living objects so this identification is
basically done using compiler analysis
so allocate clusters in a separate
mature object space that is what we call
them
neither on the runtime stack nor on the
normal heap it is a separate area no
garbage collection on mature object
space require whole space at method
termination time so you find out all the
methods which actually use it use this
mature object space or a part of mature
object space and then once all of them
terminate the last one in that sequence
will collect the end you know will
return that entire area to the memory
pool so it is possible again that we
have long living objects which lived
through the entire program time
execution time or they actually leave
for one small part of the program so
either way is possible it avoids
stressing and comping the long living
objects through garbage during garbage
collection so this is the obvious then
allocating such long living objects in
mature object space also reduces the
heap time so heap will now contain
objects with shorter lifetimes so and
makes collections even more effective
and faster so since you know short
lifetime objects are now on the heap
garbage collection now takes much lesser
time trample our analysis to identify
clusters has no runtime overheads but it
is conservative in other words within
the cluster there may be some garbage so
that means there is wastage of memory
and allocating them separately may not
help in certain situations because the
usage is not tight the memory
requirement of the program also may
increase but that would be only for
certain types of programs what is our
approach it uses information about
lifetime of objects to construct a what
is known as a points to escape rough pte
graph so this PT graph is well known
literature and it is based on the
compositional pointer and escape
analysis framework which was proposed by
valley and Reiner a couple of years ago
so when we construct this points to
escape graph it gives us a lot of
information so let us see what
information goes into this graph and how
it is used so longest-living methods
that contribute to long living clusters
are identified using profiling so first
of all we need to do some profiling on
the program find out which methods are
long living okay so and we also have to
find out what is their contribution to
long living clusters both are necessary
the methods have to live long and also
the clusters to which they refer should
be long living object the you know
long-living clusters are identified
using the speedy graph and also this
profiling objects that do not escape the
longest-living methods or the roots of
clusters so basically these long living
methods refer to some data structures
and what we mean by escaping is the they
are used within the long living methods
and they are not actually passed out of
this method they died when the long
living method dies that is the idea of
escape so all objects are reachable from
the roots of clusters belong to the
clusters so once we know what the roots
of these clusters are and we just do it
that first search on the PT graph and
identify all the objects which are
reachable and those are all in the same
cluster roots of click clusters are the
key objects that I talked about so key
objects can also be identified by our
method
so all cluster objects are statically
allocated in a separate mature object
space so this space is separate from
either the stack or the heap okay and
this is not collected by the garbage
collector routinely so we actually
allocate on the mature object space and
we release the mature object space part
when the method rate are no dice okay so
the long living method dies then that
area is also released so there is no
garbage collection on the mature object
space when the method binding the
lifetime of the root objects returns the
entire cluster is garbage and can be
reclaimed in its entirety so that is
what i was saying so evaluation of our
approach was done using a baseline
garbage collector that can run in the
stop the world and concurrent modes so
what is the stop the world GC so they
stop the world GC does not have a thread
running I know which runs the garbage
collector there is only one program that
is the main program it is running when
it runs out of memory as usual the
garbage collector is called then the
program is halted you know it does not
currently proceed with the garbage
collector so now the garbage collector
freezes the program corrects garbage
returns all that garbage to the memory
pool and then reinvest program are
restarts the program from the point
where it was frozen so this is the stop
the world program in the garbage
collector and concurrent of course I
already mentioned that the garbage
collector runs in France has a thread
concurrently with the main program so
we had a garbage collector rather we
built a garbage collector that could be
run in stop the world mode and it could
be run in concurrent mode and these were
implemented in the rotor shared source
you know common language interface which
is available in rotor so both cluster
and stack allocation methods have been
implemented compared and evaluated so we
could run the stack allocation and we
could run the cluster a location we
could run without any of these as well
and then compare the results that is
what we really did so what is
compositional pointer and escape
analysis so it is very difficult to
either out of scope of this lecture to
provide a complete algorithm for
compositional pointer and escape
analysis but let me try to give you a
flavor of what exactly this compiler
analysis is all about it determines for
a very allocation side a the method yemm
who's stack frame will outlive the
object created d so we are looking at
allocation sites in the method or in the
program so for each one of these memory
allocation sites such as camel walk or
you know new we are going to determine
the method whose track frame will
outlive the object created it that
particular a so it may if it is as if
allocation is done inside a method then
it is possible that the object is used
within the method and does not end ice
within the method it is not useful after
that that is what I mean it is also
possible that this method calls a
different method okay and there is a
series of such methods which are called
then there is a return to the original
method
so in that sequence somewhere you know
the object that has been created
originally will not be useful anymore so
that is the method iam that we are
trying to find out so this is the method
iam who stack frame will outlive the
object created it a so each one of these
methods you know em some m1 calls m2m to
cause IM 3 etcetera m1 will use a the
object created a TA it calls him to
possibly then you know mm2 also uses it
and so on it returns to m1 and then to
em maybe then again m3 is called so m1
and m2 actually are the methods that we
are looking for because a is used beyond
the methods m1 and m2 as well it is
still used in m3 so what we want is an
object p escapes a method iam that is
what we want to define so when does it
escape it is a formal parameter so it is
passed to some other method so we do not
know what happens to it it is going
outside a reference to P is written into
a static variable so again we do not
know who reads the static variable in
what is done with it a reference to P is
passed to one of the Collies of em SE n
and we do not know what ended to pee so
a reference was passed and then
something happens to it again we do not
know and um returns the object p so in
all these cases we say that the object B
escapes a method so we are trying to
find out the you know when you know if
and when the an object escapes a method
that is the idea behind this
compositional pointer and escape
analysis if none of the above then M
captures P and P does not leave um so P
can be allocated on the stack of em so
this is what i was saying so if there is
a chain of methods you want to find out
whether this
object allocated to site a really goes
beyond the methods are lies within the
method so this pte requires both intra
procedural and interprocedural analysis
it is not possible to do this analysis
in pure intra procedural way we have not
seen interprocedural analysis so far we
will do that in one of the future
lectures so creates the this algorithm
creates the points to escape graph so
that is what it does so what are the
nodes and objects I know edges of this
particular graph so allocated objects
are nodes and references between objects
are the edges so as simple as that so we
allocate an object and then you know one
object refers to another objects through
you know various possible pointer
mechanisms these are the edges so there
are two types of nodes and two types of
edges so there are inside nodes and
outside nodes there are inside edges and
outside edges so inside nodes are
objects created within the currently
analyzed region so as simple as that so
you are run lysing let us say a method
we let us say create the object within
that method then it is a corresponds to
an inside node what is an inside edge
these are references created within the
currently and ice region so again we are
creating a reference to an object within
a method so that would be an inside edge
what is an outside method node objects
created outside the currently unless
region are outside nodes and of course
what are outside edges there are
references created outside the currently
analyzing
it is possible that nodes could become
outside nodes because of their axis why
I an outside edge so outside edge comes
first and then you know because of that
the node could become an outside node so
an intra procedural algorithm for a
method m for escape analysis of course
incrementally computes the pte graph for
em in a statement by statement manner so
it goes through statements finds out
whether they are related to memory
allocation or memory reference object of
allocation or object reference and then
these are the statements which
contribute to the PT graph other
statements do not contribute to the PT
graph pte graphs of some of the called
methods may not be available at this
stage so remember we are doing
intrapersonal analysis so we are not
going to analyze parameters trace other
methods and so on and so forth so when
we are doing this analysis obviously
some information will be missing just
like you know in a when you are doing
data flow analysis for reaching
definitions or something like that if
there is a subroutine call or procedure
call within that control flow graph we
have to maybe LOL firm ation about what
that procedure called us we will have to
make some worst-case assumptions saying
ok it kills all reaching definitions or
something like that so that is the part
that we are talking about so since some
of the PT graphs of the called methods
may not be available you either say we
will not do any interprocedural analysis
are we simply say this information will
be filled in a little later so in turn
we actually fill in the information a
little later after when we do
interprocedural analysis so what is the
interpersonal algorithm it composes
individual
method pte graphs with those of the
methods called from millenium to form
the complete pte graph so basically it
patches together these graphs of various
methods in the cold sequence and then
you know builds the bigger pte graph
that is the interprocedural algorithm it
is not possible to explain the complete
construction of pte for example for an
example program it suffices to know the
structure of these PT graphs so there is
a program called anagram which has many
of these functions methods inside so
these black one nodes are all outside
nodes and the white nodes are all inside
nodes then there are some return nodes
so the solid edges are inside edges and
the dot dash edges are the outside edges
so this is the structure here there are
only inside edges then oh and then there
are outside edges here and here and so
on and so forth and suppose this node is
identified as the root of a cluster then
we trace all these in an intra
procedural manner interprocedural manner
and find that these are all reachable so
this entire set of objects forms a
single cluster for this particular
program so that is how we actually
determine clusters so we are how is
cluster identification done we apply
profiling and get a list of methods that
have a long life and are close to the
main program so from the main program we
are going to actually call many methods
and those we do not really you know want
methods which are deep inside the call
chain remain but we are close to the
n method so emphasis is on those methods
that live long and allocate objects that
are potential routes of clusters so
first of all the methods must leave
wrong so in other words when they return
to main the we assume that there will be
a call chain from Maine you know which
calls say method a a may call many other
methods so we are really looking at the
calls which are made from Maine so
because a make several calls but a will
live until all its calls are completed
so a will be long living in that sense
so the is a heuristic of course and then
not only that the objects allocated
inside these methods the long living
methods are potential routes of these
clusters they are possibly are long
living objects so they will be because
they are going to live until this long
living method which is called from Maine
leaves so in the PT graph nodes with no
incoming edges are possible routes so if
they are actually attached to some of
these long living methods then they
become actually roots then the first
search from the pd graphs is used to
identify clusters so only edges
corresponding to new statements are
considered new is the allocation
statement and all objects created by
such statements are allocated using say
some other procedure called new one
instead of the regular procedure new
placing them in a separate mature object
space so instead of trying to pass
information to new and overloaded we
statically replace the new statement by
statement new one which allocates the
space on that mature object space rather
than on the regular heap so now let us
look at the garbage collector and its
structure finally look at how
these clusters have affected the garbage
collection process so the concurrent
garbage collector for rotor so this is
the baseline garbage collector that we
are using the existing rotor GC is a
stop the world GC so it actually has
very large pastimes whereas ours is a
generational concurrent garbage
collection so it permits the mutator
that is the application program and the
garbage collector GC to run concurrently
so that is precisely what the
concurrency is all about so GC is yet
another threat and it is based on the
algorithm of nettles and O'Toole so this
is a fairly well-known concurrent
garbage collector so that is what we are
using and we are using only two
generations one is the young generation
and the other is the old generation so
young generation stores recent objects
most of which would become garbage very
quickly so the lifetime of these objects
which reside in young actually is very
small that is the basic idea so we
possibly temporary objects which are
created or possibly nodes which are
created in a linked list and get deleted
very quickly and so on and so forth the
old generation stores permanent objects
so in other words relatively permanent
they are long living objects and when I
say long living it is not the cluster
the time talking about the long living
object is relative to the young so as I
said in a generational garbage collector
as the objects mature they become older
and they are not deleted or released by
the program they become older and they
will be moved to this permanent object
space it has the same garbage collector
interface as rotor garbage collector so
interfacing was easy
so here is a picture this is the young
generation and this is the old
generation so young generation holds
objects with low left lifetimes so it
gets filled up quickly and then it is a
it can be collected very quickly as well
so all most of the objects would be
deleted and only a small portion of the
objects are not deleted and those are
all transferred to the older generation
so if they live through one cycle of one
or two cycles of garbage collection then
they are transferred to the older
generation there is a threshold set here
so if the memory availability goes below
this particular threshold then the
garbage collector is activated on the
young generation so again let me repeat
that if some nodes actually survive the
garbage collection they are considered
as old and they are transferred to the
older generation so the hope is that
they would be leaving for some more time
and therefore they actually impede the
garbage collection process in this by
raising the overheads so why not
transfer them to the other generation
where all its colleagues are also
slightly longer living objects so again
let me repeat that this is not the
mature object space mature object space
will be separate okay it is further
separate from any of these areas within
the old generation we have actually two
parts one is the from half space as it
is called and the other is the two half
space so one of them is active at any
point in allocation okay so when we
transfer the objects which are which
survive garbage collection here they are
transferred to the from space let us say
to begin with so this is called as a
minor collection so what we do on this
particular young generation is called as
a minor collection
and the living objects there are
transferred to this from half space
obviously the the objects which we have
transferred to this from half space may
not live for the entire duration of the
program they may become garbage at
various times within the running runtime
of the program so since if we do not do
anything to delete some of the areas
here you know nodes rather release some
of the nodes here and move them to the
memory pool this phase will also become
full so when it be grow goes below this
particular threshold availability of
memory bit goes below this threshold
there is a garbage collection which is
invoked on this from space so that is
known as a major garbage collection so
the objects which actually are still
living here are all now transferred to
the two space objects which have died
here and have become garbage are all
going to be released okay so now the
trick is every time you have long living
objects here they are transferred to the
to collection and its entire from space
now becomes free the same is true for
this young generation as well since all
the surviving objects are transferred to
this from half space this entire young
generation becomes free after a garbage
collection process so now this entire
thing is free and there are some objects
which are living here so again you know
transfer from this particular young
generation keeps happening so again we
do garbage collection once in a while
keep transferring objects to the to half
space after some time the two half space
may also become full and it may actually
invoke garbage collector on the to half
space so now the roles are now reversed
the two half space becomes from space
and the from space becomes the two space
so all the long living objects from two
are now transferred to from and this
entire two is freed so from the one all
location for older objects happens on
this to space so this is how the
concurrent garbage collector really
works so let us look at the performance
of the concurrent garbage collector so
first let us look at the pause and
collection times okay so this is the
impact of pause impact on pause and
correction time okay in percentage so
what we have shown here in blue is the
the stop the world pause versus rotor
pass so it is very clear I know that
this blow in in general okay is it is
about twenty percent here minus thirty
percent here and so on and so forth then
the yellow bar really shows software the
stop the world collection versus rotor
collection and then the brown bar shows
concurrent pass vs the rotor pass so let
us take the last one that is a
concurrent pass vs the original rotor
pass so you can see that the concurrent
past time has really reduced to more
than you know in some cases it has
reduced up to eighty-five percent and in
some cases it has reduced by about
fifteen percent or even five percent but
in general all of them have reduced so
that is the indication when the bars are
on the negative side so the concurrent
garbage collector it really improves the
first time you know it reduces the past
time so there by the program does not
stall for long time whereas in the stop
the world garbage collector program
stops for quite a few you know of quite
a bit of duration so that is why most of
the bars are on the positive side of the
the axis okay so whereas the concurrent
garbage collector reduces the past time
so the bars are all on the negative side
so what about the impact on the elapsed
time okay so here again the blue bars
correspond to stop the world garbage
collector and the brown bars correspond
to the concurrent garbage collector so
impact on the elapsed time in percentage
is shown on this side so in many cases
ok so the concurrent garbage collector
requires you know a little more time
than the other one ok so the elapsed
time impact is a little high on this
compared to the stop the world collector
because the concurrent garbage collector
keeps running all the time ok so there
we are assuming that there is a thread
running corresponding to concurrent
garbage collector but there is a single
processor that we have assumed so it is
being shared by the main program and
also by the garbage collector so
eventually if the concurrent garbage
collector thread runs for a long time it
will actually stop the main program from
running so inside some of the cases the
concurrent garbage collector has a
little more overhead than the stop the
world collector for example here here
here here and in some other cases in
this for example here the it is much
lesser you know so stop the world has
more effect on the elapsed time than the
concurrent garbage collector here also
the other way ok so these are equivalent
this is slightly better so the model
love for the previous two graphs is the
past time of the concurrent garbage
collector is you know improved that is
reduced whereas the elapsed time of the
concurrent garbage occurs before the
curb concurrent garbage
I increases the program completion time
a little bit what about the performance
of clustering itself so this was what we
studied was for the general garbage
collector that we have implemented now
let us introduce clustering and then
stack allocation and see what happens
heap and mature object space so we have
done this for analysis for about five
programs we are comparing the young
generation versus the old generation
with no clustering so young generation
was given two megabytes rather required
two megabytes and the old generation
required eight megabytes for this
particular program it was one and ten
for the second 11 and 44 third 1.8 and
1.6 for the four and four and eight for
the last the way we have to read this is
the maximum amount of space that was
required by the old generation or the N
generation that is to run the program
without any core dumps and things of
that kind so with the clustering where
is this phenomenal improvement so the
young generation now required only point
7 mb and the old generation instead of
eight required only 1.4 mb and it is not
as if this is magic it is just that a
large number of objects in the old space
old generation who are long living and
now they have moved to the cluster space
that is the mature object space so the
maximum cluster size that we have
detected is also about 3.8 mb so even if
we add 3.8 and 1.4 we still are lower
than 8 mb instead of 10 mb we require
two mb in the second program and then
the cluster size was 2.5 so still we
have gained a lot
whereas here is the one and 40.7 and 1.4
and 12.7 so the gain is pro phenomenal
point 18 1.6 did not deal anything in
fact it made worse because the cross
suicide is 3.6 and it adds to the old
generation space four and eight became
point one nine point three eight and 1.4
so there is a lot of gain so in general
the average reduction in heap
requirement is 12 point six percent
otherwise program specifically they can
be even more than that so by introducing
the mature object space and clustering
we have reduced the sizes of the young
and old generation that we require so
the heap size requirement has come down
drastically so this is regarding the
memory space requirement what about the
performance of clustering so fraction of
bytes allocated in the mature object
space so the so for example the if you
look at the total amount of space memory
space 88.4 seven percent for anna was
allocated on the mature object space
whereas the for PO one point eight five
percent was allocated on the mature
object space in general for a very large
number of programs the cluster
relegation astrology has helped a lot so
the average you know benefit is really
51.5 seven percent because of cluster
allocation what about these programs
which have very little benefit basically
they benefit from stack allocation in
other words if we do a locust escape
analysis determine that the objects die
within the method then allocating those
objects in the stack instead of in the
heap gives a large amount of benefit so
that is what we have found piwo WTSP and
dar g will benefit from stack allocation
after an escape analysis
the inter-regional answers from young to
old old young etcetera etcetera also
reduced drastically so for these
programs total number of cluster to heap
references 12 6 and three total
intelligent us without and with
clustering they reduce from 6-9 16 to 14
447 31 to 39,000 403 thousand to 160
9001 63,000 to 293 so percentage
reduction is very high in the number of
intrusion pointers these inter region
pointers really affect you know I make
the updating of these older generations
very slow so that is where the problem
is and if something is writing into
cluster from the old or young etcetera
etcetera there is synchronization
etcetera etcetera needed so this slow
down the updating of the objects and
that is where the intelligent reference
has become very important so because of
clustering the inter-regional has
reduced a lot they will remain within
the mature object space or within the
young space etcetera etcetera and the
flip side of it there was garbage within
the cluster which show and since
clusters are not garbage collected they
remain forever so 11.2 percent of the
cluster in the first program was garbage
nineteen percent in the second
thirty-three percent in the third and in
redress actually hundred percent was
really garbage and therefore it did not
give any benefit either if you recall
raters did not give a much benefit in
other cases also but this is a special
program so performance of clustering
reduction in allocation time so let us
look at this you know the yellow part so
it really says that by using both stack
allocation and clustering okay so we are
able to reduce by using only
clustering we are able to reduce so much
all right by using both clustering and
stack allocation we are really able to
use reduce so much okay so for example
this let us take one with all three so
with the just stack allocation we are
able to reduce so much and then with
just cluster we are able to reduce so
much and if we use both then we actually
reduce so much okay so allocation time
was down drastically if we really use
both stack allocation and you know
clustering so because stack allocation
does not require allocation call at all
and only clustering requires allocation
call so if we combine stack allocation
and mcclure string then the allocation
time reduction happens quite a bit so do
too just stack allocation there is a
twelve percent reduction just clustering
this is fourteen percent reduction and
with both there is a general average
reduction of twenty percent in
allocation time impact on the number of
collections so again if you look at only
stack allocation there is a 75 percent
reduction in allocation this is a large
number because we really do not do garba
affection if it is stack allocation
clustering you 66.5 percent improvement
on its own again this is because we do
not do correction garbage collection on
the cluster and if you deploy both then
the total collection time comes down
drastically number of collection comes
down drastically by ninety percent or
more so in some cases like this okay so
the number of Corrections is very large
because our techniques may not be very
helpful in such cases whereas in other
cases about a collection time the number
of Corrections has come down drastically
reduction in collection time again in
the you know stack allocation alone
reduces the collection time by about
sixty percent clustering reduces it
again by sixty percent and
both reduce it by about seventy nine
percent so the way we have to look at it
this is one hundred percent collection
time so what is the contribution of the
baseline it is so much and what is the
contribution of the stack that is so
much and together this hundred percent
reduction happens so this you know we
have to look at this blue okay and the
violet and yellow okay so this is so
baseline had so much and then we have
the stack contributing so much
correction time and this cluster
contributes so much and if you have
everything then it becomes hundred
percent so it is best if we really use
both the techniques of stack allocation
in clustering in order to reduce the
collection time pass time again reduces
considerably a stack allocation itself
reduces sixty-three percent clustering
reduces it by sixty-two percent and both
of them together reduce it by about
seventy nine percent on the average so
the impact on elapsed time stack
allocation the increase is average
reduction in the Raps time is about 1.75
percent because of clustering it is just
point four four percent and if we deploy
both then the average reduction is one
percent so in other words there is not
much impact on the elapsed time just
because of clustering okay so it is the
past time and the number of collections
etc etcetera that really reduce static
compilation time because we change the
program by introducing new 1 etcetera
etcetera there is some increase in the
static compilation time of six to seven
percent but this is not really something
that we need to worry about because
unless they are in twenty to thirty
percent range we do not have to worry
about compilation time increase there
are limitations on the clustering
algorithm for example analysis
static and hence very conservative it
cannot handle dynamically growing data
structures they must be size limited
otherwise growing ones cannot be handled
and it cannot handle allocation site
homogeneity so for example if there is
if then else the only one of them is
really allocated a dot F for B dot f but
it cannot really take care of such
difficulties so concluding clustering
optimization reduces the number of
collections considerably it reduces the
number of the individual collection
times and pastimes by a reasonable
amount and it reduces the number of
inter region pointers elapsed time is
not affected much so there is neither
reduction or increase reduces the total
memory requirement and produces even
better results when applied along with
the stack optimization so that is the
end of my lecture thank you very much
you