eqStableName# is not currently defined as pointer equality. Is there some reason for this? My understanding is that there is a one-to-one correspondence between stable name objects and active stable name table entries, so pointer equality should be sufficient. Am I missing something?
I defer to SimonM but IIRC each stable name corresponds to an entry in the stable-name table; the index in the table is the “stable” thing in a stable name. So I bet that comparison compares these indices.
If two stable names are pointer-equal, they presumably contain the same index into the table.
But is the reverse true? That is, can we be sure that two pointer-distinct stable name objects contain different indices?
Simon
From: ghc-devs
On Monday, August 20, 2018 11:56:44 AM EDT Simon Peyton Jones via ghc-devs wrote:
I defer to SimonM but IIRC each stable name corresponds to an entry in the stable-name table; the index in the table is the “stable” thing in a stable name. So I bet that comparison compares these indices.
If two stable names are pointer-equal, they presumably contain the same index into the table.
But is the reverse true? That is, can we be sure that two pointer-distinct stable name objects contain different indices?
I believe so, yes. Each stable name table entry has a pointer to the linked stable name object. Calling makeStableName# checks whether the passed pointer already has a stable name, and, if so, returns the linked stable name object. The design seems a bit surprising to me, but it looks like that's actually how it works, at least for now. Each call locks the stable name table, so it shouldn't be possible to miss entry creation.
I had another thought. If we want, I believe we can make the stable name mechanism considerably more compact by giving up on a flat array representation for the stable name table. The flat representation means that enlarging the table moves all its entries. Suppose we instead choose some shallow tree representation that can grow without moving (an array of arrays comes to mind, where each array is null or twice the size of the last; index calculations should be pretty simple). I believe we can then play some nice tricks: 1. Lay out each entry in the stable name table like a heap object. 2. Make each StableName# a pointer directly to its stable name table entry. So instead of a stable name object and a stable name table entry that points to it, we'd just have the stable name entry. I believe we could run the free list through the "heap object" headers.
| > But is the reverse true? That is, can we be sure that two pointer-
| distinct stable name objects contain different indices?
|
| I believe so, yes. Each stable name table entry has a pointer to the
| linked stable name object. Calling makeStableName# checks whether the
| passed pointer already has a stable name, and, if so, returns the linked
| stable name object.
Actually I'm confused. Currently we have
data StableName a = StableName (StableName# a)
I believe (but there is no documentation to state) that the (StableName# a)
* Has kind (TYPE UnliftedRep)
* Is the index of the entry in the Stable Name Table
But if it's the index, why isn't it an IntRep? UnliftedRep is for pointers?
Moreover eqStableName# :: StableName# a -> StableName# b -> Bool
is directly implemented in the code generator (StgCmmPrim) by an equality
comparison.
If these things are correct, it would be great to write them down in a Note.
And if they are right, I'm now lost about what you question is. Equality is
/already/ implemented by direct equality comparison, no?
Simon
| -----Original Message-----
| From: David Feuer
On Tue, Aug 21, 2018, 3:39 AM Simon Peyton Jones
Actually I'm confused. Currently we have
data StableName a = StableName (StableName# a)
I believe (but there is no documentation to state) that the (StableName# a) * Has kind (TYPE UnliftedRep) * Is the index of the entry in the Stable Name Table
But if it's the index, why isn't it an IntRep? UnliftedRep is for pointers?
That's explained in the paper. A StableName# is a pointer to a stable name object in the heap that *contains* an index into the stable name table. Basically, the garbage collector needs to know whether a stable name is alive or not, so it can work out when to clear it from the table.
Moreover eqStableName# :: StableName# a -> StableName# b -> Bool is directly implemented in the code generator (StgCmmPrim) by an equality comparison.
If these things are correct, it would be great to write them down in a Note.
And if they are right, I'm now lost about what you question is. Equality is /already/ implemented by direct equality comparison, no?
It's currently implemented by an equality test on the indices stored in the stable name objects, rather than the pointers to those objects, if I'm not very much mistaken.
That's explained in the paper. A StableName# is a pointer to a stable name object in the heap that *contains* an index into the stable name table. Basically, the garbage collector needs to know whether a stable name is alive or not, so it can work out when to clear it from the table.
Very good. But could it be explained in a Note too? The paper is from a long time ago, contains lots of surrounding explanation, and might well be out of date (even if it in fact is not out of date).
So the entry in the table /also/ points to the same, heap-allocated StableName#? Doesn’t that keep it alive? Or is this akin to the treatment of weak pointers? (Which is part of the same paper.)
Do we anywhere keep a pointer to the object that this is a stable name of?
Simon
From: David Feuer
On Tue, Aug 21, 2018, 4:32 AM Simon Peyton Jones
That's explained in the paper. A StableName# is a pointer to a stable name object in the heap that *contains* an index into the stable name table. Basically, the garbage collector needs to know whether a stable name is alive or not, so it can work out when to clear it from the table.
Very good. But could it be explained in a Note too? The paper is from a long time ago, contains lots of surrounding explanation, and might well be out of date (even if it in fact is not out of date).
Certainly there should be a note, but as I mentioned in this thread, I think we can probably actually do better than we presently do.
So the entry in the table /also/ points to the same, heap-allocated StableName#? Doesn’t that keep it alive? Or is this akin to the treatment of weak pointers? (Which is part of the same paper.)
The stable name table is not in the root set. All its references are weak.
Do we anywhere keep a pointer to the object that this is a stable name of?
Yes. That's in the stable name table entry. It's also the key for the stable name hash table.
participants (3)
-
David Feuer -
David Feuer -
Simon Peyton Jones