Stable name equality

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Stable name equality

David Feuer
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?

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: Stable name equality

GHC - devs mailing list

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 <[hidden email]> On Behalf Of David Feuer
Sent: 19 August 2018 18:53
To: ghc-devs <[hidden email]>
Subject: Stable name equality

 

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?


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Stable name equality

David Feuer-2
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.
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Stable name equality

David Feuer
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.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: Stable name equality

GHC - devs mailing list
In reply to this post by David Feuer-2
|  > 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 <[hidden email]>
|  Sent: 20 August 2018 23:36
|  To: [hidden email]; Simon Peyton Jones <[hidden email]>
|  Cc: David Feuer <[hidden email]>; [hidden email]
|  Subject: Re: Stable name equality
|  
|  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.
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Stable name equality

David Feuer


On Tue, Aug 21, 2018, 3:39 AM Simon Peyton Jones <[hidden email]> wrote:

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.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: Stable name equality

GHC - devs mailing list

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 <[hidden email]>
Sent: 21 August 2018 09:25
To: Simon Peyton Jones <[hidden email]>
Cc: David Feuer <[hidden email]>; ghc-devs <[hidden email]>; [hidden email]
Subject: Re: Stable name equality

 

 

On Tue, Aug 21, 2018, 3:39 AM Simon Peyton Jones <[hidden email]> wrote:


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.


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Stable name equality

David Feuer


On Tue, Aug 21, 2018, 4:32 AM Simon Peyton Jones <[hidden email]> wrote:

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.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs