libera/#sicl - IRC Chatlog
Search
3:20:54
beach
hayley: I read your text. Can I assume that the detection of an obsolete instance is something similar to what SICL does, i.e., failure in generic dispatch due to old stamp, so that this failure results in the forwarding pointer being put in? And it seems you assume that the old object minus the forwarding pointer will be reclaimed by the GC, yes?
3:22:22
beach
If so, what happens if we have two threads, T1 that wants to access a slot, so it does two things: 1. It checks whether there is an indirection and sees that there is none. 2. It uses the offset of that slot to access the contents.
3:23:16
beach
Now between 1 and 2, T2 kicks in. Lots of things happen, the class changes, and the GC runs, so the rest of the old object is now reclaimed and perhaps reused.
3:25:32
moon-child
I recall in a paper about precise instruction-level stack maps for java, they had a similar problem: if the gc ran between performing a write barrier and performing the associated write, problems could ensue, so they had to account for that
3:25:42
beach
And one more remark. Your suggestion involves another read (to check the forwarding pointer) and a test. But with a permanent indirection there is also just one more read. So it would seem to me that all you gain by your suggestion is cache performance, hoping that the forwarding pointer is close to the other slots to be read.
3:26:44
hayley
Good question. One could "pin" the object and have the garbage collector refuse to reclaim the old object, while T1 is using the object.
3:27:27
moon-child
hayley: the issue is what counts as a use. And actually this seems like quite an insidious problem
3:27:43
beach
More generally, with the SICL technique, the rack is internally consistent, so several operations can be executed on it, as long as no externally observable event occurs.
3:27:55
moon-child
suppose you have an outer loop, where you hoisted a type check, then stashed the object on the stack, accessing the object every now and then
3:28:41
hayley
The first test (of the stamp) in the read barrier precedes checking the forwarding pointer, so most of the time we should not check the forwarding pointer at all.
3:28:56
moon-child
beach: I think this method can be seen as equivalent to sicl, except that the rack is optimistically expected to be stored in-line (and is in fact stored there almost all of the time)
3:29:26
beach
hayley: Oh, and thank you for indulging me by writing everything down. I was very lost after your description here.
3:29:37
moon-child
the additional load is performed only in the sad path. And I think checking whether there is a forwarding pointer can be folded into dispatch that had to be performed anyway
3:30:40
beach
OK, so the remaining issue is then that old object must not be reclaimed while being used.
3:31:26
hayley
moon-child: Sure. It is unfortunate that an object might be pinned for a long time, but it's not a correctness issue. Or we could request that the thread eventually deoptimises.
3:31:55
beach
hayley: Oh, I see. So the stamp is stored in the same part that is preserved when that part turns into a forwarding pointer?
3:32:23
moon-child
hayley: I realised now that this is probably not such a big issue in practice, because program-order has to be preserved, so if there are any opaque calls in the loop, then it can't hoist
3:32:37
moon-child
beach: I think that, if the gc uses register maps, information about what has to be kept alive can be folded in to them
3:33:02
hayley
The stamp is modified to indicate that the object has a forwarding pointer, which allows method dispatch to check if an object is forwarded.
3:35:14
moon-child
https://www.cs.tufts.edu/~nr/cs257/archive/james-stichnoth/p118-stichnoth.pdf section 2.3
3:35:24
hayley
Right, the stamp must be in the same place, but I don't see why the stamp cannot be part of the object that is reclaimed.
3:36:02
hayley
Instead I suggested to "pin" and not reclaim an old object, while it is referenced by the stack.
3:37:14
beach
hayley: If the first thing that is accessed is the stamp, then it has to be in the same part that contains the forwarding pointer. And that part must not be reclaimed by the GC when the old object is reclaimed.
3:37:40
hayley
moon-child: And section 3 shows how JSR is evil yet again. (An ongoing joke of mine in #lispcafe.)
3:38:58
hayley
The garbage collector also needs to rewrite references to the old object, to refer to the new object. (But this doesn't quite work for the call stack, hence pinning.)
3:39:47
moon-child
beach: I imaagine stealing a bit from the stamp to tell if there is a forwarding pointer or not
3:41:22
beach
moon-child: OK, so either you access the stamp first, or the forwarding pointer first. If the stamp can be either in the non-indirect object referred to directly by they pointer or in the indirect object referred to by the forwarding pointer, then you have to check the forwarding pointer first.
3:42:11
beach
moon-child: But then you lose the saving of a read, so you need to access the stamp first. So then, the stamp can not be in different places depending on whether the object is indirect or not.
3:43:05
moon-child
load the stamp; check if it is what you expect; if it is, then treat the pointer you have as the start of an (appropriate, self-consistent) rack for the layout identified by that stamp; else, follow the forwarding pointer and try again. In the happy path, the stamp is the only thing you ever have to access
3:43:40
beach
moon-child: So then, the stamp must be in a fixed place, whether the object is direct or indirect. So it must be in the first few words of the direct object, and that part must not be reclaimed when the direct object turns into a forwarding object.
3:45:40
moon-child
the object forwarded-to will have a different layout. If I change-class something from an a to a b, the old copy must have the stamp and slots of an a, and the new copy the stamp and slots of a b. Until it is known that the old copy is no longer reachable (at which point it is reclaimed). No?
3:49:41
beach
moon-child: As I understood it, the object does not change its identity. So when the class is redefined, and this is detected by generic dispatch. The direct object is turned into a forwarding object.
3:51:43
moon-child
yes but, due to concurrency issues, as you mentioned, it is necessary to keep its old incarnation around. In just the same fashion as, with the present sicl design, it may be necessary to keep multiple racks around, because somebody has sampled an old one
3:53:40
beach
All I am saying is that, if you access the stamp first, it must be in the same place whether the object is direct or indirect.
3:55:09
moon-child
associated with the 'old rack' should be in the same location regardless (but that will not be the same as the stamp associated with the 'new rack'). But what is the problem, then?
3:56:51
beach
I was stating a simple consequence of what hayley said (namely that the stamp is accessed first, and not the possible indirection, so as to save a read), which is that the location of the stamp can not depend on whether the object is direct or indirect.
4:00:01
beach
This was not obvious from the text that hayley wrote, and I was under the impression that the indirection had to be tested first.
4:00:52
beach
The text also doesn't say how the indirection is put in there, which is why I asked whether it is with a mechanism similar to the failure detection in SICL.
4:05:28
moon-child
one could reserve an extra word in the object, after the stamp. Another idea was to use the same word as the stamp--say, a low bit tells if the object is forwarded, and if it is, then the high bits are the forwarding pointer, and otherwise, they are the stamp. But we were not sure if that could cause problems
4:13:41
beach
hayley: I think I am lost again. So why does there have to be a separate test to determine whether the object is forwarded? Won't the stamp be enough? I think moon-child suggested that the forwarding information be encoded in the stamp, so that the generic dispatch would follow the indirection or not, depending on the stamp.
4:15:38
hayley
You're right, the stamp is enough. I mustn't have made it clear, probably due to jumping between Smalltalk and Common Lisp/SICL terminology
4:16:50
beach
I think if you fix the text with all this additional information, it will be a great suggestion. Perhaps it can turn into a paper.
4:18:43
moon-child
I think it's usual to dispatch on the type of an object if you're using it at all. It's rare to treat data obliviously (copy-seq being one counterexample)
4:18:56
beach
hayley: But your text suggested that the original paper required a test and a (predictable) conditional jump. If so, your text is an improvement.
4:19:26
moon-child
so: would it be possible to fold this partial read barrier into a gc barrier and enable concurrent relocation at no additional cost?
4:22:21
hayley
Okay, I retract that. I'm distracted while cooking, and will actually think about it later.
4:26:08
moon-child
in the case of something like gethash, the object is loaded, but never accessed. Presumably the caller is going to access it. Is it possible to make the caller perform the read barrier, then, without inlining gethash? Probably hard because of self-healing. On the other hand, gethash with simd is pretty small (at least the hot path), so maybe _should_ be inlined
4:26:55
hayley
beach: I don't think I said that my approach performs fewer operations. "Miranda and Béra, however, use a special class ID to represent if an object has been forwarded, which allows method dispatch itself to test if an object has been forwarded"
4:28:42
hayley
moon-child: You'd need to make sure the flip is atomic, and you'd want to un-forward eventually. So I don't think this technique helps for implementing concurrent relocation.
4:34:09
moon-child
hayley: I mean implement something like pauseless and friends, but put the colour in the stamp. Then, right after you load an object, the same check suffices both to implement the read barrier, perform method dispatch, and check for a redefined/changed class
4:35:41
moon-child
(I'm not sure if this works when not inline caching or otherwise having some idea of what you're going to get. Buuuuut leaving that aside)