Array!T and find are slow

[monarch_dodra via Digitalmars-d-learn]

On Wednesday, 14 May 2014 at 20:29:52 UTC, David Nadlinger wrote:
> On Wednesday, 14 May 2014 at 17:36:35 UTC, monarch_dodra wrote:
>> 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:
>
> Shouldn't the extra indirection just vanish into thin air once 
> opIndex or what have you is inlined? I don't see a conceptual 
> reason for overhead in this case.

Maybe. That said, currently, find doesn't use indexing for RA 
ranges. It simply uses a front/popFront for loop, so *that's* 
extra work.

I just tried a RA/hasLength/hasSlicing case in find. It improves 
the situation by a factor of 2 on my machine (with dmd), but it 
is still somewhat slower than extracting the array directly.

I'm usually reluctant to add extra code when the generic case 
works, but I feel we should make an exception for find.

I don't know if the optimizer can optimize away the indirection 
entirely, when the code for front also does indexing, with bounds 
checking...

Array comes with deterministic memory management, as well as 
non-invalidating range when relocation occurs. Extra overhead is 
to be expected.

> Of course, the compiler probably wouldn't be able to infer any 
> of the memchr/… optimizations find does for the array case, but 
> Damian's alternative version doesn't do any of that either.
>
> David

The memchr optimization would only trigger for ubyte/byte and 
char (although a bug prevents Array from working with char 
https://issues.dlang.org/show_bug.cgi?id=8824)

But more importantly, there are more flavors of find, such as 
with predicate, or range/range find. Having an implementation 
provide a thin wrapper might be acceptable. Reimplementation 
isn't.