digitalmars.D.bugs - [Issue 5282] New: Use memcmp or other appropriate optimizations for array comparison where possible
- d-bugmail puremagic.com (31/31) Nov 27 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5282
- d-bugmail puremagic.com (12/14) Nov 28 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5282
- d-bugmail puremagic.com (11/11) Nov 28 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5282
- d-bugmail puremagic.com (14/14) Nov 28 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5282
- d-bugmail puremagic.com (70/70) Nov 28 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5282
- d-bugmail puremagic.com (9/9) Nov 28 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5282
- d-bugmail puremagic.com (11/17) Nov 29 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5282
- d-bugmail puremagic.com (19/19) Apr 01 2013 http://d.puremagic.com/issues/show_bug.cgi?id=5282
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 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: -------
Nov 27 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5282 bearophile_hugs eml.cc changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |bearophile_hugs eml.ccWhat 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 arraysA 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: -------
Nov 28 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5282 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: -------
Nov 28 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5282 Stewart Gordon <smjg iname.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |smjg iname.com 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: -------
Nov 28 2010
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. 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: -------
Nov 28 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5282 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: -------
Nov 28 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5282The 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 membersLooks 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: -------
Nov 29 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5282 Vladimir Panteleev <thecybershadow gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |thecybershadow gmail.com 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 would be possible to expand it to structs, if someone could implement the -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Apr 01 2013