http://d.puremagic.com/issues/show_bug.cgi?id=5282

           Summary: Use memcmp or other appropriate optimizations for
                    array comparison where possible
           Product: D
           Version: unspecified
          Platform: Other
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: jmdavisProg@gmx.com


--- Comment #0 from Jonathan M Davis <jmdavisProg@gmx.com> 2010-11-27 22:30:10 PST ---
This thread makes it fairly clear that in some cases, array comparisons in D are unnecessarily slow: http://www.mail-archive.com/digitalmars-d@puremagic.com/msg43150.html

What likely should be done is to use memcmp in cases where you don't actually
need to call opEquals() on the individual elements of the arrays - such as when
comparing arrays of primitives or arrays of structs where none of the struct's
member variables have opEquals() (be they primitives or structs without an
opEquals() and no member variables with opEquals()). strings would naturally be
among the types which would benefit from the optimization.

Other optimizations for speeding up array comparisons may be appropriate, but I do think that it's clear that array comparisons can be better optimized in many common cases. Obviously, this isn't a high priority, but I do think that this is an optimization which should be added at some point if we really want D to be as fast as it should be.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5282


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc


--- Comment #1 from bearophile_hugs@eml.cc 2010-11-28 03:20:18 PST ---
(In reply to comment #0)

> What likely should be done is to use memcmp in cases where you don't actually need to call opEquals() on the individual elements of the arrays

A simple solution for the string case:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=123044

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5282



--- Comment #2 from bearophile_hugs@eml.cc 2010-11-28 09:05:27 PST ---
The solution I suggest for this problem is: when DMD knows at compile-time the length of one of the two strings to equate, and such length is small (like < 6), then it may replace the string eq code like this:

(c == "TAC")

With code like:

(c.length == 3 && c[0] == 'T' && c[1] == 'A' && c[2] == 'C')

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5282


Stewart Gordon <smjg@iname.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |smjg@iname.com


--- Comment #3 from Stewart Gordon <smjg@iname.com> 2010-11-28 18:16:25 PST ---
The conditions for memcmp working as a way of comparing structs are:

- no opEquals of a compatible parameter type
- no holes due to alignment
- no members with reference semantics (dynamic arrays, AAs, classes)
- all of this applies recursively to any struct or union members

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5282


Rob Jacques <sandford@jhu.edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |performance
                 CC|                            |sandford@jhu.edu
            Summary|Use memcmp or other         |Optimize array comparison
                   |appropriate optimizations   |which use memcmp to
                   |for array comparison where  |something better and remove
                   |possible                    |unnecessary indirections.


--- Comment #4 from Rob Jacques <sandford@jhu.edu> 2010-11-28 21:59:20 PST ---
Here are two optimized routines for bit-wise comparing two arrays for equality, for both the dynamic/dynamic and dynamic/static case. These are significantly faster than memcmp (~2.5x) and D's built-in == operator (~3.3x) for the dynamic/dynamic case in a micro-benchmark. (The static case is naturally even faster) The difference between memcmp and '==' appears to be due to inlining: calling memcmp via a member function of a class (instead of from a free function) had approximately the same performance as D's '=='.

This seems to indicate that a) use of memcmp in druntime for equality tests should be replaced with the below routine and b) DMD should be calling free-function versions of these routines instead of using multiple indirections.

(By the way, does anyone know where array comparisons live in D? I tried modifying TypeInfo_Ag, but that didn't seem to work)

/// Returns: true if the contents of two arrays are bit-wise equal.
bool bitwiseEquality(T) (const T[] a, const T[] b) pure nothrow @trusted {
    if(a.length != b.length )
        return false;
    if(a.ptr is b.ptr)
        return true;
    size_t byte_length = a.length*T.sizeof;
    size_t alignment   = byte_length % ulong.sizeof;
    if(( (*(cast(ulong*)a.ptr) ^ *(cast(ulong*)b.ptr)) << 8 *
(ulong.sizeof-alignment) ))
        return false;
    alignment  += (!alignment) * ulong.sizeof;
    auto pa     = cast(ulong*)(cast(ubyte*)a.ptr + alignment);
    auto pb     = cast(ulong*)(cast(ubyte*)b.ptr + alignment);
    auto pa_end = cast(ulong*)(cast(ubyte*)a.ptr + byte_length);
    while (pa < pa_end)
        if(*pa++ != *pb++ )
            return false;
    return true;
}
/// Returns: true if the contents of two arrays are bit-wise equal.
bool bitwiseEquality(T, size_t N)(const T[] a, ref const T[N] b) pure nothrow
@trusted {
    static if(T.sizeof*N <= uint.sizeof) {
        return a.length == N && !( (*(cast(uint*)a.ptr)  ^ *(cast(uint*)b.ptr))
 & (uint.max >> 8*(uint.sizeof  - T.sizeof*N) ));
    } else static if(T.sizeof*N <= ulong.sizeof) {
        return a.length == N && !( (*(cast(ulong*)a.ptr) ^
*(cast(ulong*)b.ptr)) & (ulong.max>> 8*(ulong.sizeof - T.sizeof*N) ));
    } else { // Fall back to a loop
        if(a.length != N || (*(cast(ulong*)a.ptr) != *(cast(ulong*)b.ptr)) )
return false;
        enum alignment = T.sizeof*N % ulong.sizeof > 0 ? T.sizeof*N %
ulong.sizeof : ulong.sizeof;
        auto pa      = cast(ulong*)(cast(ubyte*)a.ptr + alignment);
        auto pb      = cast(ulong*)(cast(ubyte*)b.ptr + alignment);
        auto pa_end  = cast(ulong*)(cast(ubyte*)a.ptr + T.sizeof*N);
        while (pa < pa_end) {
            if(*pa++ != *pb++ ) return false;
        }
        return true;
    }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5282



--- Comment #5 from Rob Jacques <sandford@jhu.edu> 2010-11-28 22:17:11 PST ---
(In reply to comment #4)
P.S. The performance gain of bitwiseEquality does drop for very large files (as
things become more I/O bound), but it still maintains a ~1.5x advantage over
memcmp.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5282



--- Comment #6 from Stewart Gordon <smjg@iname.com> 2010-11-29 03:29:34 PST ---
(In reply to comment #3)
> The conditions for memcmp working as a way of comparing structs are:
> 
> - no opEquals of a compatible parameter type
> - no holes due to alignment
> - no members with reference semantics (dynamic arrays, AAs, classes)
> - all of this applies recursively to any struct or union members

Looks like I was wrong....
http://www.digitalmars.com/d/1.0/expression.html#CmpExpression
"Equality for struct objects means the bit patterns of the objects match
exactly (the existence of alignment holes in the objects is accounted for,
usually by setting them all to 0 upon initialization)."

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5282


Vladimir Panteleev <thecybershadow@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |thecybershadow@gmail.com


--- Comment #7 from Vladimir Panteleev <thecybershadow@gmail.com> 2013-04-02 00:50:30 EEST ---
I've written a patch to optimize the simple case of comparison of arrays of basic types (integral and void[]), which was merged yesterday:

http://d.puremagic.com/issues/show_bug.cgi?id=9477 https://github.com/D-Programming-Language/dmd/pull/1766

It uses the memcmp intrinsic. DMD currently does not do anything special if the array length is known at compile-time (i.e. at least one of the arrays is static), but I imagine smarter backends might take advantage of that and unroll it, as mentioned in comment #2.

It would be possible to expand it to structs, if someone could implement the checks as described in comment #3.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------