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.

On Wednesday, 14 May 2014 at 17:20:37 UTC, David Nadlinger wrote:
> On Wednesday, 14 May 2014 at 15:42:13 UTC, Damian Day wrote:
>> On Wednesday, 14 May 2014 at 14:54:57 UTC, David Nadlinger wrote:
>>
>>> Could you post a short benchmark snippet explicitly showing the problem?
>>
>> Benchmark found here:
>> http://dpaste.dzfl.pl/0058fc8341830
>
> Unfortunately, I don't have the time to look at the details right now, but https://github.com/D-Programming-Language/phobos/pull/1713 might have improved the situation somewhat.
>
> David

That pull shows that the previous behaviour was to use enforce?
Isn't this very expensive, particularly considering that enforce
uses lazy non-scope arguments?

On Wednesday, 14 May 2014 at 21:20:06 UTC, Kapps wrote:
> That pull shows that the previous behaviour was to use enforce?
> Isn't this very expensive, particularly considering that enforce
> uses lazy non-scope arguments?

Yes.

On Wed, 14 May 2014 20:54:19 +0000
monarch_dodra via Digitalmars-d-learn
<digitalmars-d-learn@puremagic.com> wrote:

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

We should avoid it where it doesn't gain us much, but the standard library needs to be fast, so if there's a definite performance gain to be made in adding overloads, we should. That being said, I agree that we should be trying to make ranges in general faster rather than optimizing for individual range types such as Array's range type. Still, if there's a significant performance gain to be made in adding an overload for find to Array's range type, we should at least consider it. UFCS should then make it just work. But that solution should be reserved for if there's a fundamental reason why it would be faster to create a specialization for Array's range type rather than just because ranges aren't optimized well enough by the compiler or because std.algorithm.find itself needs improvement. If we can speed up ranges in general, then we gain everywhere, and if we can speed up std.algorithm.find, then it's sped up for many types rather than just making it faster for Array's range type.

- Jonathan M Davis

On Wed, 14 May 2014 21:20:05 +0000
Kapps via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> wrote:

> That pull shows that the previous behaviour was to use enforce? Isn't this very expensive, particularly considering that enforce uses lazy non-scope arguments?

Yeah, much as Andrei would hate to hear it (enforce was his idea, and he quite likes the idiom), the fact that lazy is so inefficient makes it so that it's arguably bad practice to use it in high performance code. We really need to find a way to make it so that lazy is optimized properly so that we _can_ safely use enforce, but for now, it's not a good idea unless the code that you're working on can afford the performance hit.

Honestly, in general, I'd avoid most anything which uses lazy (e.g. that's why I'd use explict try-catch blocks rather than use std.exception.assumeWontThrow - like enforce, it's a nice idea, but it's too expensive at this point).

- Jonathan M Davis

On Wednesday, 14 May 2014 at 22:32:01 UTC, Jonathan M Davis via Digitalmars-d-learn wrote:
> Yeah, much as Andrei would hate to hear it (enforce was his idea, and he quite
> likes the idiom), the fact that lazy is so inefficient makes it so that it's
> arguably bad practice to use it in high performance code. We really need to
> find a way to make it so that lazy is optimized properly so that we _can_
> safely use enforce, but for now, it's not a good idea unless the code that
> you're working on can afford the performance hit.
>
> Honestly, in general, I'd avoid most anything which uses lazy (e.g. that's why
> I'd use explict try-catch blocks rather than use
> std.exception.assumeWontThrow - like enforce, it's a nice idea, but it's too
> expensive at this point).
>
> - Jonathan M Davis

On the topic of lazy, why *is* it so slow, exactly? I thought it was just shorthand for taking a function that evaluates the expression, and wrapping said expression in that function at the call site. That is, I thought that:

int doSomething(lazy int n)
{
    return n();
}

Was more or less equivalent to:

int doSomething(int function(int) n)
{
    return n();
}

On Wednesday, 14 May 2014 at 23:50:34 UTC, Meta wrote:
> On the topic of lazy, why *is* it so slow, exactly? I thought it was just shorthand for taking a function that evaluates the expression, and wrapping said expression in that function at the call site. That is, I thought that:
>
> int doSomething(lazy int n)
> {
>     return n();
> }
>
> Was more or less equivalent to:
>
> int doSomething(int function(int) n)
> {
>     return n();
> }

It's more equivalent to:

int doSomething(int delegate(int) n)
{
    return n();
}

And (I could be very likely wrong here), I believe that it's expensive because it's not scope and possibly requires a closure. Again, very likely may be wrong.

On Thu, 15 May 2014 01:29:23 +0000
Kapps via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> wrote:

> On Wednesday, 14 May 2014 at 23:50:34 UTC, Meta wrote:
> > On the topic of lazy, why *is* it so slow, exactly? I thought it was just shorthand for taking a function that evaluates the expression, and wrapping said expression in that function at the call site. That is, I thought that:
> >
> > int doSomething(lazy int n)
> > {
> >     return n();
> > }
> >
> > Was more or less equivalent to:
> >
> > int doSomething(int function(int) n)
> > {
> >     return n();
> > }
>
> It's more equivalent to:
>
> int doSomething(int delegate(int) n)
> {
>      return n();
> }
>
> And (I could be very likely wrong here), I believe that it's expensive because it's not scope and possibly requires a closure. Again, very likely may be wrong.

Yeah. It generates a delegate. You even use the value internally as a delegate. So, that's definitely part of the problem, though IIRC, there were other issues with it. However, I don't remember at the moment. The big one IIRC (which may be due to its nature as a delegate) is simply that it can't be inlined, and in many cases, you very much what the code to be inlined (enforce would be a prime example of that).

enforce(cond, "failure");

really should just translate to something close to

if(!cond) throw new Exception("failure");

but it doesn't do anything close to that. And as long as it doesn't, enforce is of questionable value in any code that cares about efficiency.

- Jonathan M Davis

On Thursday, 15 May 2014 at 04:37:16 UTC, Jonathan M Davis via Digitalmars-d-learn wrote:
> enforce(cond, "failure");
>
> really should just translate to something close to
>
> if(!cond) throw new Exception("failure");
>
> but it doesn't do anything close to that. And as long as it doesn't, enforce
> is of questionable value in any code that cares about efficiency.
>
> - Jonathan M Davis

As a workaround, I'm sure we could specialize enforce without lazy for built-in types?

BTW: Why *is* enforce lazy again? I don't really see it. I makes more sense for things like "collectException" I guess, but I don't see it for enforce.

On Thu, 15 May 2014 05:53:45 +0000
monarch_dodra via Digitalmars-d-learn
<digitalmars-d-learn@puremagic.com> wrote:

> As a workaround, I'm sure we could specialize enforce without lazy for built-in types?

No. I don't think that that would work. The problem is that you'd have to be
able to overload between stuff like "error message" and
format("error message: %s", foo), because you don't want the first one to be
lazy, whereas you do want the second one to be lazy.

> BTW: Why *is* enforce lazy again? I don't really see it. I makes more sense for things like "collectException" I guess, but I don't see it for enforce.

It's lazy so that the second argument isn't evaluated. That might not be obvious in the example

enforce(cond, "failure");

but if you have

enforce(cond, format("failure: %s", foo));

or

enforce(cond, new BarException("blah"));

then it would definitely be costing you something if the second parameter weren't lazy - and in theory, the cost of it not being lazy could be arbitrarily large, because you can pass it arbitrarily complex expressions just so long as their result is the correct type. Now, given how slow lazy is, maybe it would actually be faster to just have it be strict instead of lazy, but in theory, it's saving you something. And if lazy were actually properly efficient, then it would definitely be saving you something. Regardless, using an explicit if statement is definitely faster, because then you don't have the lazy parameter to worry about _or_ the potentially expensive expression, since the expression would only be encountered if the condition failed.

- Jonathan M Davis