Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#13908 closed bug (wontfix)

sameMutableArray equivalent for Array

Reported by: winter Owned by:
Priority: normal Milestone: 8.4.1
Component: Compiler Version: 8.0.1
Keywords: Cc:
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:

Description (last modified by bgamari)

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 ; )

Change History (9)

comment:1 Changed 2 years ago 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.

comment:2 Changed 2 years ago by winter

I just come up a third solution to this problem:

sameArray :: Array a -> Array a -> Bool
sameArray arr1 arr2 = 
    sameMutableArray (unsafeCoerce arr1) (unsafeCoerce arr2)

Does this code safe? do i have to use unboxed version, e.g. unsafeCoerce# with array#? I think the unboxed version might work, since primitive array references are like MutVar#: they have identities.

Last edited 2 years ago by winter (previous) (diff)

comment:3 Changed 2 years ago 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.

comment:4 Changed 2 years ago by bgamari

Differential Rev(s): Phab:D3697
Status: newpatch

comment:5 Changed 2 years ago by bgamari

Milestone: 8.4.1

comment:6 Changed 2 years ago 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.

comment:7 Changed 2 years ago by bgamari

Description: modified (diff)
Resolution: wontfix
Status: patchclosed

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. Given that we have reallyUnsafePtrEq I suppose the status quo is fine.

Last edited 2 years ago by bgamari (previous) (diff)

comment:8 Changed 2 years ago by winter

Sounds reasonable. I will go with unsafeCoerce#.

comment:9 Changed 2 years ago 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.

Note: See TracTickets for help on using tickets.