Short-term Memory for Self-collecting Mutators
image/svg+xml
Short-term Memory for Selfcollecting Mutators
##
/
##
MASTER SLIDE
Google Tech Talk, London, September 2011
Short-term Memory for Self-collecting Mutators
Martin Aigner, Andreas Haas, Christoph M. Kirsch, Michael Lippautz, Ana Sokolova, Stephanie Stroka, Andreas Unterweger
University of Salzburg
Short-term Memory
for
Self-collecting Mutators
new memory modelfor heap management
new explicit heap management system
time 5
5
6
7
time 6
6
7
heap
time 7
7
heap
heap
expired
expired
time
time advance
time advance
Each memory object allocated in short-term memoryhas an expiration date
When an object expires, its memory may be reused
real time possible
no memory leaks as long as time advances
programmer-defined time: "tick()-calls"
multiple timelines supported in the latest software distribution
premature expirationmay create danglingpointers
Extend the expiration date of an object by refreshing
5
6
7
time 5
heap
time 5
9
8
7
heap
refresh(4)
refresh(1)
refresh(3)
new expiration date = max
current time + extension
current expiration date
9 = 5 + 4
8 = 5 + 3
7 > 5 + 1
State what happens when expired objects are refreshed.
Expiration extensions do not accumulate
Objects may be refreshed multiple times as long as they have not expired
needed
reachable
heap
not-needed
unreachable
garbage collected by a GC
explicit deallocation
object
object
object
last reference deleted
last use
relevant forthe application
expired
needed
heap
not expired
object
conservativerefresh
conservativeexpiration
objects expire later
refreshing ofnot-needed objects
relevant forthe application
time
allocation
last use
last referenceis deleted
correct deallocation
correct expiration
no upper bound for correct expiration
Conservative lifetime approximations possible in short-term memory
May be easier to determine
Explicit heap management based on short-term memory
Heap management hybrid
Offers refresh- and time-advance-facilities
Explicit deallocation or garbage collection as default
Short-term memory as option
No additional threads for memory management
Possibly unsafe
explicit heap management systembased on short-term memory
heap management hybrid
no additional threads for memory management
explicit refresh
explicit time advance
can be unsafe
explicit deallocation or garbage collection as default
short-term memoryas option
backwardcompatibility
hence the name
fully scalable
object = malloc(size);
refresh(object, 3);
tick();
.....
.....
object
8
time = 5
time = 6
allocates memory with one additional header word
counts expiration dates
creates an expiration date for the object
object is short-term: deallocation-calls are ignored
0
8
1
3
increments time
multiple expiration datesfor efficiency
time isthread-local
only point of synchronization
port an applicationwithout removingfree-calls
8
9
9
expiration dates are managed in buffers
buffers arethread-local
all buffer operationsare performed inconstant time
hybrid heap management: the object can be deallocated hereexplicitly
an object expires when all its expiration dates have expired
9
10
11
12
time
8
object
8
8
8
9
8
3
0
1
8
expired
expired
expired
expired
collected
collected
collected
eager collection:collect all expirationdates at time advance
lazy collection:collect one expirationdate at a time
maximal throughput -minimal memory consumption
one per memory management operation -maximal incrementality
takes constant time
an object is deallocatedwhen all is expiration datesare collected
2
3
time advance
time advance
currenttime
currenttime
currenttime
collection strategiesbetween lazy and eagercollection possible-not done yet
ease of use
performance
lines of code
difficulty of placing code
total execution time (throughput)
execution time per operation(latency)
memory consumption
C
mpg123
x264
based on ptmalloc2
Java
Monte Carlo
in Jikes RVM
Go
tree benchmark
webserver
in the 6g runtime
16043 LoC
1 tick-call
refresh all objectsright after allocation
in the paper
1450 LoC
1 tick-call
refresh all short-living objects right after allocation
to make allshort-living objectsshort-term
1 tick-call
61722 LoC
single refresh: refresh all frames after allocationwith a conservative expiration date
continuous refresh: refresh all needed frames before time advance with extension '1'
or
2 tick-calls in the multi- threaded version
0
5
10
15
20
25
30
0
50
100
150
200
250
300
memory consumption in MB
(lower is better)
number of frames
original with pool allocation
original without pool allocation
SCM single refresh
SCM continuous refresh
original with pool allocation
original without pool allocation
SCM single refresh
SCM continuous refresh
Bounded memory overhead
Easier to use than explicit deallocation (no reference counting)
0
50
100
150
200
250
300
350
0
20
40
60
80
100
memory consumption in KB (lower is better)
number of allocations
tick
tick
tick
original
eager-SCM
lazy-SCM
original mpg123
eager-SCMcollect all expired objects at time advance
lazy-SCMcollect one objectper operation
tick
Bounded memory overhead
No additional latency withlazy collection
Easier to use (like onefree for all objects)
Same throughput
0
20
40
60
80
100
0
500
1000
1500
2000
2500
1
10
100
1000
10000
memory consumption in MB (lower is better)
loop execution time in microseconds
(logarithmic) (lower is better)
loop iteration
GEN memory consumption
MS memory consumption
SCM memory consumption
GEN loop execution time
MS loop execution time
SCM loop execution time
loop execution time
garbage collection
memory consumption
Low latency at the expense of safety
memory overheadof self-collecting mutators
dead start-up memory
mark-sweep garbage collector
self-collecting mutators
generationalgarbage collector
Future work (embedded software community)
Time as first class citizen: capture execution progress relevant for memory management
Future work (memory management community)
Efficiency: integrate short-term memory into other allocators
Correctness: make short-term memory safe
Get the code from here:
http://tiptoe.cs.uni-salzburg.at/short-term-memory/
Thank You
http://tiptoe.cs.uni-salzburg.at/short-term-memory/