If two dynamic arrays point to the same place in memory, is it fast to compare them for equality? or does every element still have to be compared?

On 04/03/2014 09:03 AM, dnspies wrote:
> If two dynamic arrays point to the same place in memory, is it fast to
> compare them for equality? or does every element still have to be compared?

Equals will first check for memory location.
This is from the runtime:

bool opEquals(Object lhs, Object rhs)
{
    // If aliased to the same object or both null => equal
    if (lhs is rhs) return true;

    // If either is null => non-equal
    if (lhs is null || rhs is null) return false;

    // If same exact type => one call to method opEquals
    if (typeid(lhs) is typeid(rhs) || typeid(lhs).opEquals(typeid(rhs)))
        return lhs.opEquals(rhs);

    // General case => symmetric calls to method opEquals
    return lhs.opEquals(rhs) && rhs.opEquals(lhs);
}

On Thursday, 3 April 2014 at 07:16:53 UTC, simendsjo wrote:
> On 04/03/2014 09:03 AM, dnspies wrote:
>> If two dynamic arrays point to the same place in memory, is it fast to
>> compare them for equality? or does every element still have to be compared?
>
> Equals will first check for memory location.
> This is from the runtime:
>
> bool opEquals(Object lhs, Object rhs)
> {
>     // If aliased to the same object or both null => equal
>     if (lhs is rhs) return true;
>
>     // If either is null => non-equal
>     if (lhs is null || rhs is null) return false;
>
>     // If same exact type => one call to method opEquals
>     if (typeid(lhs) is typeid(rhs) || typeid(lhs).opEquals(typeid(rhs)))
>         return lhs.opEquals(rhs);
>
>     // General case => symmetric calls to method opEquals
>     return lhs.opEquals(rhs) && rhs.opEquals(lhs);
> }

But this only applies to objects with a class type.  A dynamic array isn't an object with a class type, it's a builtin type.  Does it use this opEquals?  Can a dynamic array even be cast to an Object?  I don't see that "lhs is rhs" will return true since the array startptr-length pairs may still occupy different places in memory even if the contents of those arrays occupy the same place.

On Thursday, 3 April 2014 at 07:03:26 UTC, dnspies wrote:
> If two dynamic arrays point to the same place in memory, is it fast to compare them for equality? or does every element still have to be compared?

Depends how you test for equality.

If you use "is", the "opEquals" will straight up check that the slices are the actual same slice (point to same memory, same length).

If you use "==" or "[] == []" (which is equivalent), then it will check the lengths, then the pointers, and finally, the elements.

On 04/03/2014 09:23 AM, dnspies wrote:
> On Thursday, 3 April 2014 at 07:16:53 UTC, simendsjo wrote:
>> On 04/03/2014 09:03 AM, dnspies wrote:
>>> If two dynamic arrays point to the same place in memory, is it fast to
>>> compare them for equality? or does every element still have to be
>>> compared?
>>
>> Equals will first check for memory location.
>> This is from the runtime:
>>
>> bool opEquals(Object lhs, Object rhs)
>> {
>>     // If aliased to the same object or both null => equal
>>     if (lhs is rhs) return true;
>>
>>     // If either is null => non-equal
>>     if (lhs is null || rhs is null) return false;
>>
>>     // If same exact type => one call to method opEquals
>>     if (typeid(lhs) is typeid(rhs) || typeid(lhs).opEquals(typeid(rhs)))
>>         return lhs.opEquals(rhs);
>>
>>     // General case => symmetric calls to method opEquals
>>     return lhs.opEquals(rhs) && rhs.opEquals(lhs);
>> }
>
> But this only applies to objects with a class type.  A dynamic array
> isn't an object with a class type, it's a builtin type. Does it use this
> opEquals?  Can a dynamic array even be cast to an Object?  I don't see
> that "lhs is rhs" will return true since the array startptr-length pairs
> may still occupy different places in memory even if the contents of
> those arrays occupy the same place.

If the arrays have different lengths, they are obviously not equal.
Here's a quick test of the semantics of is on arrays.

    auto a = [1, 2];
    auto b = a;
    assert(a is b);
    b = a[0..$];
    assert(a is b);
    b = a[0..1];
    assert(a !is b);
    assert(a.ptr == b.ptr);

On Thursday, 3 April 2014 at 08:27:38 UTC, simendsjo wrote:
> On 04/03/2014 09:23 AM, dnspies wrote:
>> On Thursday, 3 April 2014 at 07:16:53 UTC, simendsjo wrote:
>>> On 04/03/2014 09:03 AM, dnspies wrote:
>>>> If two dynamic arrays point to the same place in memory, is it fast to
>>>> compare them for equality? or does every element still have to be
>>>> compared?
>>>
>>> Equals will first check for memory location.
>>> This is from the runtime:
>>>
>>> bool opEquals(Object lhs, Object rhs)
>>> {
>>>    // If aliased to the same object or both null => equal
>>>    if (lhs is rhs) return true;
>>>
>>>    // If either is null => non-equal
>>>    if (lhs is null || rhs is null) return false;
>>>
>>>    // If same exact type => one call to method opEquals
>>>    if (typeid(lhs) is typeid(rhs) || typeid(lhs).opEquals(typeid(rhs)))
>>>        return lhs.opEquals(rhs);
>>>
>>>    // General case => symmetric calls to method opEquals
>>>    return lhs.opEquals(rhs) && rhs.opEquals(lhs);
>>> }
>>
>> But this only applies to objects with a class type.  A dynamic array
>> isn't an object with a class type, it's a builtin type. Does it use this
>> opEquals?  Can a dynamic array even be cast to an Object?  I don't see
>> that "lhs is rhs" will return true since the array startptr-length pairs
>> may still occupy different places in memory even if the contents of
>> those arrays occupy the same place.
>
> If the arrays have different lengths, they are obviously not equal.
> Here's a quick test of the semantics of is on arrays.
>
>     auto a = [1, 2];
>     auto b = a;
>     assert(a is b);
>     b = a[0..$];
>     assert(a is b);
>     b = a[0..1];
>     assert(a !is b);
>     assert(a.ptr == b.ptr);

Ok, I accept that for dynamic arrays, the "is" keyword appears to be overloaded. (I still haven't found documentation for "is" as you can see from one of my other forum posts.  I'm having trouble figuring out where to look)

But I still don't see how this opEquals which takes two Objects could possibly accept dynamic arrays instead.  Object is a class-type so its instances can only be accessed by reference (which is only a single pointer internally).  Thus the size of the parameters to this function is two pointers.  But a dynamic array is a pointer paired with a length (which is the same size as two pointers) meaning the size of the parameters two any function taking two arrays would have to be four pointers.  So it seems like any function which would work on both would have to be templated (but this one isn't).  Are you sure that this is the opEquals that gets used with dynamic arrays and not a different one somewhere else?

On Thursday, 3 April 2014 at 16:05:27 UTC, dnspies wrote:
> But I still don't see how this opEquals which takes two Objects could possibly accept dynamic arrays instead.

It doesn't. The link you were given was not relevent.

> Object is a class-type so its instances can only be accessed by reference (which is only a single pointer internally).  Thus the size of the parameters to this function is two pointers.  But a dynamic array is a pointer paired with a length (which is the same size as two pointers) meaning the size of the parameters two any function taking two arrays would have to be four pointers.  So it seems like any function which would work on both would have to be templated (but this one isn't).  Are you sure that this is the opEquals that gets used with dynamic arrays and not a different one somewhere else?

It's not the one for dynamic arrays. AFAIK, the one for arrays is fully compiler generated, so you won't find it anywhere.