[Issue 10403] memchr optimization for std.algorithm.find

[d-bugmail at puremagic.com]

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



--- Comment #2 from Tommi <tommitissari at hotmail.com> 2013-06-19 14:48:56 PDT ---
(In reply to comment #1)
> (In reply to comment #0)
> > Add an optimization for:
> > 
> > R find(alias pred = "a == b", R, E)(R haystack, E needle);
> > 
> > ...to use the c function memchr when pred is the default "a == b" and...
> > 
> > CASE 1:
> > All of the following are true:
> > 
> > 1) R is an array of elements of type char, byte, ubyte or an enum type whose
> > base type is one of those.
> > 2) E is integral
> > 3) For the element type of R:
> > alias Elem = ElementType!R;
> > ...the following is true:
> > (Elem.min <= needle && needle <= Elem.max)
> > This is important because memchr only cares about bitwise equality. If the
> > value of needle is beyound the limits of possible values for type Elem, then we
> > know needle cannot be found within haystack and the function can just return
> > early without searching.
> > 
> > CASE 2:
> > All of the following are true:
> > 
> > 1) R is an array of elements of type E
> > 2) E.sizeof == 1
> > 3) For type E equality means bitwise equality
> 
> I'm just about finished implementing the above, along with quite a few other
> tricks, and I'm getting some 'great' performance improvements.
> 
> I implemented "CASE 2".
> 
> However, I don't think it is worth implementing "CASE 1": I think the case of
> searching for an element that is simply outside of the possible values of the
> range's element type should be a very rare case. I mean, who would write:
> find(myRangeOfBytes, 5000);
> ???
> I come to the conclusion that the cost of checking the condition all the time
> just to reduce the time of a special case is not worth it.
> 
> It's kind of like of the "opAssign check for self assignment" issue. If you can
> write the code in such a case that the common case goes faster, but self is
> more costly, then that is better.
> 
> So yeah, I implemented "CASE 2".

Checking for (Elem.min <= needle && needle <= Elem.max) is not an optimization,
it's there for code correctness sake. It's the memchr that is the optimization.
And checking for (Elem.min <= needle && needle <= Elem.max) is needed only when
it's possible that it might be true, i.e. only when the signedness of Elem is
different from the signedness of the type of needle.

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