http://d.puremagic.com/issues/show_bug.cgi?id=5282
Rob Jacques <sandf...@jhu.edu> changed:
What |Removed |Added
----------------------------------------------------------------------------
Keywords| |performance
CC| |sandf...@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 <sandf...@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: -------
