libera/#sicl - IRC Chatlog
Search
4:57:51
hayley
Silly thought, would an overhead of one word per object in a thread-local nursery be too much space overhead? The worst-case behaviour that we found for the original thread-local GC design could be avoided if we could update the allocation points which produce objects that (frequently) escape, so that the points would allocate into the global heap instead. The extra word per object would be used to store a "backpointer" to information about the
5:02:48
beach
I don't understand what it means for an object to "escape". And I don't know what an "allocation point" is. And I don't know what it means for an allocation point in the nursery to allocate in the global heap.
5:06:39
hayley
I had meant to write "objects that (frequently) escape to the global heap", and an "allocation point" is some code which performs an allocation, such as in the function CONS.
5:08:46
hayley
"allocation point" is seemingly a term that is only used in documentation on the Memory Pool System.
5:12:36
beach
Then, why not just allocate the object directly in the global heap? What is the word in the nursery good for?
5:13:23
hayley
The idea is that any code which might allocate from the nursery has a flag associated with it, and the allocation code first tests if the flag has been set. If the flag is set, then allocate in the global heap. If the flag is still not set, then allocate in the nursery.
5:14:24
beach
OK. So what determines whether the flag is set or not? And what is the word in the nursery for?
5:15:50
hayley
The word per object is used as part of a feedback mechanism: the additional word contains information about the allocation code, including the associated flag. If an object escapes to the global heap, the flag associated with the allocation code which allocated that object is set.
5:17:01
hayley
The end result is that an allocation point will not repeatedly allocate objects in the nursery, only for those objects to escape to the global heap.
5:21:20
beach
How will the word be found? If it is associated with a previous object allocated at some allocation point, how will some subsequent execution of the code at the allocation point find the word that was associated with the object previously allocated?
5:22:19
beach
An, what makes us believe that the allocation point itself determines whether the object is likely to escape, rather than the entire execution history that called that allocation point?
5:22:58
beach
I mean, there are typically only two allocation points in the entire system: In CONS and in ALLOCATE-INSTANCE, unless you always inline those of course.
5:25:09
hayley
We could consider each named call to CONS and ALLOCATE-INSTANCE as an allocation point instead.
6:04:39
beach
OK, so you are at some allocation point and you need to decide where to allocate, in the nursery or in the global heap. The flag that will give you this information is in a slot of some object. But which object? And how do you find it?
6:08:17
moon-child
at compile-time, a cell could be allocated for every named call to CONS, which cell would be passed to CONS
6:10:15
moon-child
at the point when you migrate an object to the global heap, you need to figure out where it was allocated, so you can mark that location as more likely to allocate into the global heap
6:14:19
beach
So the basic idea is that the best place to allocate an object is determined by the allocation point. And that this information is determined at run time, based on whether the object is migrated to the global heap as a result of it being written into the slot of an older object. Yes?
6:14:59
moon-child
‘what makes us believe that the allocation point itself determines whether the object is likely to escape, rather than the entire execution history that called that allocation point?’ the latter would probably be a _better_ indicator. But it seems reasonably likely that just knowing the allocation point would be a decent indicator. E.G. I believe languages with inline caching for method
6:16:08
beach
So the first step would be to try to instrument some code to determine whether this assumption is true.
6:18:32
beach
I'll be very distracted today. First I will go buy food in half an hour or so. Then, I will prepare lunch for my favorite coauthor who is coming in 5 hours or so. And of course, I will spend time with her and my (admittedly small) family over lunch for a significant amount of time.
6:34:15
hayley
moon-child: Thanks for handling that. I had to disappear for a bit, and my phone ran out of power.
6:35:43
hayley
Right, the flag is per call site, and a slot in each object in the nursery points to the flag for the relevant allocation point.
6:39:45
hayley
I suspect that higher order functions such as MAPCAR produce objects with more unpredictable lifetimes though.
6:43:03
hayley
I got the idea from a paper on optimistic stack allocation in Java <https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.3766&rep=rep1&type=pdf>, which includes simulation results using the feedback technique I tried to describe, and also considering the calling method while making a decision. The latter is closer to considering the entire execution history.