On Wednesday, 14 May 2014 at 14:54:57 UTC, David Nadlinger wrote:
On Wednesday, 14 May 2014 at 14:24:28 UTC, Damian Day wrote:
I've written some search functions, which are many times
faster, is it
worth making a pull request?
Generally, we strive to make the algorithms in Phobos as fast
as possible even in the general case. I didn't look at the
issue at hand in any detail, but if the "-O -release -inline"
performance when operating on Arrays is considerably worse than
when directly operating on the data, we have a problem, as it
likely to also impact other ranges.
In short, I don't think the best solution is to add this
special case to Array!T, but rather to figure out what exactly
is wrong with Array!T and/or find() and fix the problem at its
source. Could you post a short benchmark snippet explicitly
showing the problem?
Best,
David
"One" of the issue is the cost of repeatedly indexing Array, when
internally it is nothing more than an array. Adding a special
case "in" Array.Range allows bypassing the repeated indexing
costs, but at the very least, should be implemented "in terms of"
find itself, eg:
Range searchForward(E)(E needle)
if (isImplicitlyConvertible!(E, T))
{
assert(_outer._data.refCountedStore.isInitialized);
auto haystack = _outer._data._payload[_a .. _b];
haystack = haystack.find(needle);
return Range(this._outer, _b - haystack.length, _b);
}
