Array!T and find are slow

[monarch_dodra via Digitalmars-d-learn]

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);
}