[GHC] #13908: sameMutableArray equivalent for Array
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Sometime it is useful to compare reference equality for immutable arrays, for example when comparing vectors which are slices of arrays, we may want to know if two vectors are slices of the same array. But currently we only have `sameMutableXXXArray` primitives. A workaround may look like this: {{{ sameArray :: Array a -> Array a -> Bool sameArray arr1 arr2 = runST (do marr1 <- unsafeThawArray arr1 marr2 <- unsafeThawArray arr2 return (sameMutableArray marr1 marr2) ) }}} But the problem is for boxed arrays, this code will push an unchanged array to mutable list if it's already on older generations. Next GC will have to scan it(at least will scan its card table). I can see two solutions here, first one is to add `sameXXXArray` for all array types. The second one is somehow more complex: Currently we simply rewrite array's header to `MUT_ARR_PTRS_FROZEN0/SMALL_MUT_ARR_PTRS_FROZEN0` when we do `unsafeFreeze`. But for mutable array with no write happend, e.g. the ones with `MUT_ARR_PTRS_CLEAN/SMALL_MUT_ARR_PTRS_CLEAN` header. we can safely rewrite the header to `MUT_ARR_PTRS_FROZEN/SMALL_MUT_ARR_PTRS_FROZEN`, so that we can keep it from next GC. Then to fix previous code, we can add a freeze before returning. Of course we can do these two solutions all together ; ) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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 winter): In fact the code in the issue report is even problematic: if we thaw an array without freezing it. we may leave it on the mutable list forever. So we have to add it anyway. But currently doing that won't save us from next GC. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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 winter): I just come up a third solution to this problem: {{{ sameArray :: Array a -> Array a -> Bool sameArray arr1 arr2 = runST (do return (sameMutableArray (unsafeCoerce arr1) (unsafeCoerce marr2)) }}} Does this code safe? do i have to use unboxed version, e.g. unsafeCoerce# with array#? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 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): I believe that should be fine. Afterall, `sameMutableArray#` is really just a pointer comparison. However, you are right that we probably ought to have a primop for this. I'm not sure why this was overlooked. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3697 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch * differential: => Phab:D3697 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3697 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: => 8.4.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D3697 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): I'm really not sure about this. Mutable arrays have ''identity'' so it makes sense to ask if they are "the same". Immutable arrays do not. Are the two lists `[2,3]` and `[2,3]` "the same"? Would it make a difference if you let-bound it `let x = [2,3] in sameList x x`? We have `unsafePtrEq` and `reallyUnsafePtrEq`. Maybe use them instead? The danger is that legitimate compiler optimisations might change behaviour. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.0.1 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): Phab:D3697 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => closed * resolution: => wontfix @@ -8,1 +8,1 @@ - {{{ + {{{#!hs New description: Sometime it is useful to compare reference equality for immutable arrays, for example when comparing vectors which are slices of arrays, we may want to know if two vectors are slices of the same array. But currently we only have `sameMutableXXXArray` primitives. A workaround may look like this: {{{#!hs sameArray :: Array a -> Array a -> Bool sameArray arr1 arr2 = runST (do marr1 <- unsafeThawArray arr1 marr2 <- unsafeThawArray arr2 return (sameMutableArray marr1 marr2) ) }}} But the problem is for boxed arrays, this code will push an unchanged array to mutable list if it's already on older generations. Next GC will have to scan it(at least will scan its card table). I can see two solutions here, first one is to add `sameXXXArray` for all array types. The second one is somehow more complex: Currently we simply rewrite array's header to `MUT_ARR_PTRS_FROZEN0/SMALL_MUT_ARR_PTRS_FROZEN0` when we do `unsafeFreeze`. But for mutable array with no write happend, e.g. the ones with `MUT_ARR_PTRS_CLEAN/SMALL_MUT_ARR_PTRS_CLEAN` header. we can safely rewrite the header to `MUT_ARR_PTRS_FROZEN/SMALL_MUT_ARR_PTRS_FROZEN`, so that we can keep it from next GC. Then to fix previous code, we can add a freeze before returning. Of course we can do these two solutions all together ; ) -- Comment:
Mutable arrays have identity so it makes sense to ask if they are "the same".
That is a fair point. I suppose this is a sensible reason for this asymmetry. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.0.1 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): Phab:D3697 Wiki Page: | -------------------------------------+------------------------------------- Comment (by winter): Sounds reasonable. I will go with unsafeCoerce#. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13908: sameMutableArray equivalent for Array -------------------------------------+------------------------------------- Reporter: winter | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.0.1 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): Phab:D3697 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Actually, in its current form I realized that `reallyUnsafePtrEquality#` doesn't really fit the bill: it's type is `Type -> Type -> Int#` whereas `ByteArray#` is of kind `TYPE 'UnliftedPtrRep`. This means that you would first need to coerce the `ByteArray#` to a lifted type before being able to do the comparison, which seems quite ugly. Ideally we would be able to make the type of `reallyUnsafePtrEquality#` `TYPE ('PtrRep levity) -> TYPE ('PtrRep levity) -> Int#`, abstracting over levity. In the short term we could also introduce a `reallyUnsafeUnliftedPtrEquality# :: TYPE 'UnliftedPtrRep -> TYPE 'UnliftedPtrRep -> Int#`, but frankly I think the `unsafeCoerce#` is probably a reasonable 80% solution for the time being. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13908#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC