[Issue 5282] Optimize array comparison which use memcmp to something better and remove unnecessary indirections.

[d-bugmail at puremagic.com]

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


Rob Jacques <sandford at jhu.edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |performance
                 CC|                            |sandford at 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 at 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: -------