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.
