Re: [GHC] #913: instance Ord (StableName a)

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

Re: [GHC] #913: instance Ord (StableName a)

GHC - devs mailing list
#913: instance Ord (StableName a)
-------------------------------------+-------------------------------------
        Reporter:  ekarttun          |                Owner:  (none)
            Type:  feature request   |               Status:  closed
        Priority:  normal            |            Milestone:  6.10 branch
       Component:  libraries/base    |              Version:  6.4.2
      Resolution:  wontfix           |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by andrewthad):

 * failure:   => None/Unknown


Comment:

 Is there a reason this is currently marked as wontfix? It seems like
 adding a `compareStableNames#` primop would be easy and would solve this
 issue. I might be able to figure out how to do this and would be happy to
 give it a try if I knew it would be accepted.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/913#comment:8>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

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

Re: [GHC] #913: instance Ord (StableName a)

GHC - devs mailing list
#913: instance Ord (StableName a)
-------------------------------------+-------------------------------------
        Reporter:  ekarttun          |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:  6.10 branch
       Component:  libraries/base    |              Version:  6.4.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by bgamari):

 * cc: core-libraries-committee@… (added)
 * status:  closed => new
 * resolution:  wontfix =>


Comment:

 It sounds like we just weren't sure whether this was a desireable feature.
 Indeed this is a bit of a tricky question as it to some extent commits
 other implementations to also offer this functionality.

 Let's see what the Core Libraries Committee says.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/913#comment:9>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

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

Re: [GHC] #913: instance Ord (StableName a)

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#913: instance Ord (StableName a)
-------------------------------------+-------------------------------------
        Reporter:  ekarttun          |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:  6.10 branch
       Component:  libraries/base    |              Version:  6.4.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by andrewthad):

 When you say that it "to some extend commits other implementations to also
 offer this functionality", how do you mean that? StableName isn't part of
 the Haskell Report. But yes, I agree that checking with the CLC is a good
 step.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/913#comment:10>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

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

Re: [GHC] #913: instance Ord (StableName a)

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#913: instance Ord (StableName a)
-------------------------------------+-------------------------------------
        Reporter:  ekarttun          |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:  6.10 branch
       Component:  libraries/base    |              Version:  6.4.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by bgamari):

 Ahh, right, of course. I don't know why I thought it was in the Report.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/913#comment:11>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

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

Re: [GHC] #913: instance Ord (StableName a)

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#913: instance Ord (StableName a)
-------------------------------------+-------------------------------------
        Reporter:  ekarttun          |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:  6.10 branch
       Component:  libraries/base    |              Version:  6.4.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by ekmett):

 Up until now the fact that you can't care about the arbitrary ordering
 that the `StableName`s have has been viewed as a feature. Pragmatically,
 if you need to use them as keys in a container `unordered-containers`
 should properly treat them as `Hashable`, and rather explicitly considers
 the container "unordered".

 That said, one could argue that the same reasoning should apply to
 `Data.Unique` in that it should be `Hashable`/`Eq` only, and not provide
 the `Ord` instance it already does, so to your point there is at least an
 appearance of inconsistency between these two positions.

 There is some difference between those two scenarios though.

 It is worth noting that nothing in our current API says a `StableName#`
 gets any sort of actual _unique_ integer assigned to it during creation.
 It just lives on the heap. Pretending we can gives me pause. You can't
 compare pointers to them using an ordering, any more than you can compare
 `MutVar#`'s for `Ord` because GC can change the relative position of them,
 and we don't want to inflate them with a superfluous costs to support an
 operation that isn't fundamental to their existence.

 Now, we do have a `stableNameToInt#` operation, but it rather carefully
 doesn't claim to produce a unique name. Mind you it doesn't make this
 claim largely due to concerns about GC happening in the meantime, but
 we've had this degree of freedom for a long time, and could abuse it more
 in the internals without anybody actually being able to care.

 @simonmar's initial suggestion that we can use the `Ord` on the
 `stableNameToInt#` used by `hashStableName` to compare `StableName#`s
 seems a little racy to me: the integer isn't guaranteed to be unique due
 to the fact that `StableName` IDs can be reused, but due to the fact that
 I could construct two stable names, converting one to an integer through
 `stableNameToInt#`, have a gc happen in which the now 'dead' `StableName`
 gets recollected, have someone else get assigned to the same id, then
 force another stablename that was constructed in the meantime, which might
 resolve to the same id. While it seems like a reasonably far fetched
 scenario that that might go wrong, the chain of reasoning to prove that it
 always goes right is delicate. e.g. I don't see what prevents you from
 constructing the second stable name using an `unsafePerformIO` in between
 the unwrapping of the first and unwrapping the second, it would be
 constructed by the act of forcing the `StableName` data constructor. Do I
 think this will really happen in user code? Maybe not, but the fact that I
 could even see a path towards it, and Jan-Willem's experience report,
 combined with my previous efforts along these lines building the `intern`
 library and basically giving up on the cleanup once problems get large
 enough due to issues of this sort, gives me a great deal of pause.

 But there isn't really any particular reason other than the current
 implementation why these Ids are small unique numbers.

 In a different world, they could just be heap objects with some ID created
 during initialization, say, based on their initial allocation address.
 They could then be "moved" like any other heap object. The current API
 doesn't require uniqueness of keys, so this would pass everything about
 the `StableName` API, much like how my
 [https://github.com/ekmett/unique/blob/master/src/Control/Concurrent/Unique.hs#L38
 Control.Concurrent.Unique] matches the shape of the `Data.Unique` API, but
 can only supply `Hashable`, not `Ord`, as the integer of initial
 allocation location associated with each `Unique` value could be shared
 across several such `Unique` values. This has the benefit of avoiding
 _any_ coordination during allocation of these identifiers across threads
 and so scales better than our current `Data.Unique` system.

 I could see a world in which we'd want to refactor the internals of
 `System.Mem.StableName` at some point to offer a more efficient
 construction. The current API offers a lot of possible implementation
 approaches. Adding an `Ord` constraint limits those choices, and reasoning
 about its soundness takes us into relatively dubious territory as seen
 above.

 On a more theoretical basis, to phrase this another way, not everything
 that can be broken into equivalence classes breaks up into _ordered_
 equivalence classes. If these were merely unique objects on the heap, then
 merely being able to compare these for equality vs. having the power to
 sort them is analogous to the problem of 'pointer discrimination'
 mentioned by Fritz Henglein in
 [https://pdfs.semanticscholar.org/f425/7af9221ca7fe21dc84a049a8545a28a874ae.pdf
 Generic Top-down Discrimination for Sorting and Partitioning in Linear
 Time].

 All of these issues taken together leaves me inclined to let the old
 `wontfix` status of this issue stand.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/913#comment:12>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

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

Re: [GHC] #913: instance Ord (StableName a)

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#913: instance Ord (StableName a)
-------------------------------------+-------------------------------------
        Reporter:  ekarttun          |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:  6.10 branch
       Component:  libraries/base    |              Version:  6.4.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by andrewthad):

 I agree with your concern that an Ord instance limits future possibilities
 to modify the implementation.  I disagree with the concern about
 soundness.  As you point out, using  hashStableName to implement an Ord
 instance is unsound.  We do not use it in the Eq instance,  and it would
 be every bit as unsound in an Ord instance.  The path forward to
 implementing an Ord instance would be to introduce a new primop  for
 comparing StableName#.  It would basically be the same thing as
 eqStableName#.  After all, eqStableName#  is basically ( in the current
 implementation)  two calls to stableNameToInt#  with the guarantee that
 garbage collection cannot happen between them.  And this guarantee that
 garbage collection  doesn’t happen between the two calls  is exactly what
 you make the implementation you discuss above sound.

  But yes, it does constrain the possible available implementations. I
 certainly agree with that.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/913#comment:13>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

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

Re: [GHC] #913: instance Ord (StableName a)

GHC - devs mailing list
In reply to this post by GHC - devs mailing list
#913: instance Ord (StableName a)
-------------------------------------+-------------------------------------
        Reporter:  ekarttun          |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:  6.10 branch
       Component:  libraries/base    |              Version:  6.4.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by ekmett):

 Implemented as a custom prim so there is no risk of the gc gap? That'd fix
 the soundness concern. I'd for some reason mentally parsed Simon's
 suggestion as happening in "user land" as it were but that fixes it.

 I still think it falls into wontfix territory for the other reasons
 specified; I don't particularly _like_ our current implementation.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/913#comment:14>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

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