Parallel memory allocator employing liveness metrics
A liveness-based memory allocation module operating so that a program thread invoking the memory allocation module is provided with an allocation of memory including a reserve of free heap slots beyond the immediate requirements of the invoking thread. The module receives a parameter representing a thread execution window from an invoking thread; calculates a liveness metric based upon the parameter; calculates a reserve of memory to be passed to the invoking thread based upon the parameter; returns a block of memory corresponding to the calculated reserve of memory. Equations, algorithms, and sampling strategies for calculating liveness metrics are disclosed, as well as a method for adaptive control of the module to achieve a balance between memory efficiency and potential contention as specified by a single control parameter.
1. A non-transitory, computer readable storage medium encoding a memory allocation module, the memory allocation module including instructions executable by a processor unit to perform:
(1) receiving a parameter representing a length of a thread execution window from an invoking thread;
(2) calculating a liveness metric for the invoking thread, the liveness metric representing heap slot reuse or a number of live data objects within the thread execution window, based upon the parameter;
(3) calculating a reserve of memory to be provided to the invoking thread based upon the parameter and the liveness metric; and
(4) returning a pointer to an allocation of memory corresponding to the calculated reserve of memory, the allocation containing one or more chunks of memory that can be traversed via the pointer,
whereby a program thread invoking the memory allocation module is provided with an allocation of memory including a reserve of free heap slots beyond the immediate requirements of the invoking thread.
2. The storage medium of claim 1 , wherein the liveness metric represents, for a time window with a length specified by the parameter, the average number of times that local heap slots which were holding live objects at the start of the time window were freed and then allocated to hold new objects within the span of the time window, for multiple possible windows of the length.
3. The storage medium of claim 1 , wherein the liveness metric is calculated according to:
reuse
(
k
)
=
∑
i
=
1
m
I
(
e
i
-
s
i
≤
k
)
(
min
(
n
-
k
,
s
i
)
-
max
(
k
,
e
i
)
+
k
+
1
)
n
-
k
+
1
,
where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied,
where n is the current logical time, and
where function I is a predicate equal to 1 if the condition (e i −s i ≤k) is true or else 0.
4. The storage medium of claim 1 , wherein the liveness metric is calculated according to:
reuse
(
k
)
=
X
(
k
)
-
Y
(
k
)
+
Z
(
k
)
n
-
k
+
1
where X (1)=Σ i=1 m I ( e i −s i =1) s i
X ( k )= X ( k− 1)−Σ i=1 m I ( s i ≥n −( k− 1))+Σ i=1 m I ( e i −s i =k )min( n−k,s i ), for k> 1
Y (1)=Σ i=1 m I ( e i −s i =1) e i
Y ( k )= Y ( k− 1)−Σ i=1 m I ( e i ≤k− 1)+Σ i=1 m I ( e i −s i =k )max( k,e i ), for k> 1
Z (1)=2Σ i=1 m I ( e i −s i =1)
Z ( k )= Z ( k− 1)+Σ i=1 m I ( e i −s i ≤k )+ kΣ i=1 m I ( e i −s i =k ), for k> 1
where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied,
where n is the current logical time, and
where function I is a predicate equal to 1 if the respective parenthetical condition is true or else 0.
5. The storage medium of claim 4 , wherein the liveness metric is calculated during a plurality of burst periods, each burst period being separated from a next-in-time burst period by a hibernation period.
6. The storage medium of claim 1 , wherein the liveness metric represents, for a time window with a length specified by the parameter, the number of live objects in a local heap existing within the time window plus the number of objects in the local heap newly allocated within the time window, averaged over multiple possible windows of the length.
7. The storage medium of claim 1 , wherein the liveness metric is calculated according to:
live
(
k
)
=
∑
i
=
1
m
min
(
n
-
k
+
1
,
e
i
)
-
∑
i
=
1
m
max
(
k
,
s
i
)
+
m
k
n
-
k
+
1
where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied, and
where n is the current logical time.
8. The storage medium of claim 1 , wherein the liveness metric is calculated according to:
live
(
1
)
=
∑
i
=
1
m
e
i
-
∑
i
=
1
m
s
i
+
m
n
and
live
(
k
>
1
)
=
n
×
live
(
1
)
n
-
k
+
1
-
cumu_deallocations
(
n
-
k
+
2
)
+
cumu_allocations
(
k
-
1
)
n
-
k
+
1
where cumu _allocations( k )=Σ i=1 m I ( s i ≤k ) and
cumu _deallocations( k )=Σ i=1 m I ( e i ≥k )
where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied, and
where n is the current logical time.
9. The storage medium of claim 1 , wherein the liveness metric is calculated according to:
live
(
n
,
k
)
=
∑
e
n
-
k
+
1
+
(
m
-
#
e
n
-
k
+
1
)
(
n
-
k
+
1
)
-
(
#
s
k
k
-
∑
s
n
-
∑
s
k
)
+
mk
n
-
k
+
1
where k is the parameter,
where Σe k is the sum of free times before time k,
where #e k is the number of frees before time k,
where Σs k is the sum of allocation times before k,
where #s k is the number of allocations before time k, and
where m is the number of currently allocated objects at time n.
10. A computer system comprising:
a processor unit;
a memory for the storage of executable program code and data; and
a memory allocation module stored in the memory for execution by the processor unit, the memory allocation module containing executable instructions to carry out:
(1) receiving a parameter representing a length of a thread execution window from an invoking thread;
(2) calculating a liveness metric for the invoking thread, the liveness metric representing heap slot reuse or a number of live data objects within the thread execution window, based upon the parameter;
(3) calculating a reserve of memory to be provided to the invoking thread based upon the parameter and the liveness metric; and
(4) returning a pointer to an allocation of memory corresponding to the calculated reserve of memory, the allocation containing one or more chunks of memory that can be traversed via the pointer,
whereby a program thread invoking the memory allocation module is provided with an allocation of memory including a reserve of free heap slots beyond the immediate requirements of the invoking thread.
11. The computer system of claim 10 , wherein the liveness metric represents, for a time window with a length specified by the parameter, the average number of times that local heap slots which were holding live objects at the start of the time window were freed and then allocated to hold new objects within the span of the time window, for multiple possible windows of the length.
12. The computer system of claim 10 , wherein the liveness metric is calculated according to:
reuse
(
k
)
=
∑
i
=
1
m
I
(
e
i
-
s
i
≤
k
)
(
min
(
n
-
k
,
s
i
)
-
max
(
k
,
e
i
)
+
k
+
1
)
n
-
k
+
1
,
where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied,
where n is the current logical time, and
where function I is a predicate equal to 1 if the condition (e i −s i ≤k) is true or else 0.
13. The computer storage medium of claim 10 , wherein the liveness metric is calculated according to:
reuse
(
k
)
=
X
(
k
)
-
Y
(
k
)
+
Z
(
k
)
n
-
k
+
1
where X (1)=Σ i=1 m I ( e i −s i =1) s i
X ( k )= X ( k− 1)−Σ i=1 m I ( s i ≥n −( k− 1))+Σ i=1 m I ( e i −s i =k )min( n−k,s i ), for k> 1
Y (1)=Σ i=1 m I ( e i −s i =1) e i
Y ( k )= Y ( k− 1)−Σ i=1 m I ( e i ≤k− 1)+Σ i=1 m I ( e i −s i =k )max( k,e i ), for k> 1
Z (1)=2Σ i=1 m I ( e i −s i =1)
Z ( k )= Z ( k− 1)+Σ i=1 m I ( e i −s i ≤k )+ kΣ i=1 m I ( e i −s i =k ), for k> 1
where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied,
where n is the current logical time, and
where function I is a predicate equal to 1 if the respective parenthetical condition is true or else 0.
14. The computer storage medium of any of claim 13 , wherein the liveness metric is calculated during a plurality of burst periods, each burst period being separated from a next-in-time burst period by a hibernation period.
15. The computer of claim 10 , wherein the liveness metric represents, for a time window with a length specified by the parameter, the number of live objects in local heaps existing but not feed within the time window plus the number of objects in local heaps newly allocated within the time window, averaged over multiple possible windows of the length.
16. The computer system of claim 10 , wherein the liveness metric is calculated according to:
live
(
k
)
=
∑
i
=
1
m
(
min
(
n
-
k
+
1
,
e
i
)
-
∑
i
=
1
m
max
(
k
,
s
i
)
+
m
k
)
n
-
k
+
1
where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied, and
where n is the current logical time.
17. The computer system of claim 10 , wherein the liveness metric is calculated according to:
live
(
1
)
=
∑
i
=
1
m
e
i
-
∑
i
=
1
m
s
i
+
m
n
and
live
(
k
>
1
)
=
n
×
live
(
1
)
n
-
k
+
1
-
cumu_deallocations
(
n
-
k
+
2
)
+
cumu_allocations
(
k
-
1
)
n
-
k
+
1
where cumu _allocations( k )=Σ i=1 m I ( s i ≤k ) and
cumu _deallocations( k )=Σ i=1 m I ( e i ≥k )
where k is the parameter,
where s i and e i are a time interval logical start time and end time, respectively, during an i one of m free intervals in which a thread-local heap slot is free, unallocated, and unoccupied, and
where n is the current logical time.
18. The computer system of claim 10 , wherein the liveness metric is calculated according to:
live
(
n
,
k
)
=
∑
e
n
-
k
+
1
+
(
m
-
#
e
n
-
k
+
1
)
(
n
-
k
+
1
)
-
(
#
s
k
k
-
∑
s
n
-
∑
s
k
)
+
mk
n
-
k
+
1
where k is the parameter,
where Σe k is the sum of free times before time k,
where #e k is the number of frees before time k,
where Σs k is the sum of allocation times before k,
where #s k is the number of allocations before time k, and
where m is the number of currently allocated objects at time n.
19. A method of adaptively controlling the memory allocation module of claim 10 , the method comprising:
setting the parameter equal to a target time interval between invocations of the memory allocation module to request memory;
invoking memory allocation module to fetch a memory allocation based upon the parameter;
setting the parameter equal to an adaptive time interval to be sought before a next fetch operation whereby, if correctly predictive of the time of the next fetch operation, a long term average time interval between fetch operations approaches the target time interval; and
reinvoking the memory allocation module to fetch a memory allocation based upon the adaptive-time-interval-valued parameter.
20. The method of claim 19 further comprising:
upon an local free operation, checking whether the length of a local heap free list is greater than twice the calculated reserve of memory; and
if the check is true, invoking the memory allocation module to return free heap slots from the local heap.