www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Array!T and find are slow

reply "Damian Day" <damianroyday gmail.com> writes:
I've found bench-marking my program that std.algorithm.find is
very slow on Array!T, due to the fact it iterates on a range
instead of a plain array.

I've written some search functions, which are many times faster, 
is it
worth making a pull request?

http://dpaste.dzfl.pl/63b54aa27f35#
May 14 2014
next sibling parent reply "David Nadlinger" <code klickverbot.at> writes:
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
May 14 2014
next sibling parent reply "Damian Day" <damianroyday gmail.com> writes:
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
May 14 2014
next sibling parent reply "David Nadlinger" <code klickverbot.at> writes:
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
May 14 2014
parent reply "Kapps" <opantm2+spam gmail.com> writes:
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?
May 14 2014
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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.
May 14 2014
prev sibling parent reply Jonathan M Davis via Digitalmars-d-learn writes:
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
May 14 2014
parent reply "Meta" <jared771 gmail.com> writes:
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(); }
May 14 2014
next sibling parent reply "Kapps" <opantm2+spam gmail.com> writes:
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.
May 14 2014
parent reply Jonathan M Davis via Digitalmars-d-learn writes:
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
May 14 2014
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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.
May 14 2014
parent reply Jonathan M Davis via Digitalmars-d-learn writes:
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
May 14 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 15 May 2014 at 06:52:44 UTC, Jonathan M Davis via 
Digitalmars-d-learn wrote:
 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.
Oh... right. It's the *second* parameter that's lazy. Arguably, the compiler should be able too "see" if the argument passed is a value or an expression though, and optimize accordingly.
May 15 2014
prev sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
On 5/15/14, 1:31 AM, Jonathan M Davis via Digitalmars-d-learn wrote:
 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.
Isn't there a way in D to just expand: enforce(cond, "failure"); (or something with a similar syntax) to this, at compile-time: if(!cond) throw new Exception("failure"); I thought D could do this, so enforce should do this instead of using lazy arguments.
May 15 2014
parent reply Jonathan M Davis via Digitalmars-d-learn writes:
On Thu, 15 May 2014 08:04:59 -0300
Ary Borenszweig via Digitalmars-d-learn
<digitalmars-d-learn puremagic.com> wrote:

 Isn't there a way in D to just expand:

 enforce(cond, "failure");

 (or something with a similar syntax) to this, at compile-time:

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

 I thought D could do this, so enforce should do this instead of using
 lazy arguments.
No. enforce is a function, and the only other things that it could be with that syntax would be other callables (e.g. a lambda, delegate, or functor). Mixins are the only constructs that can completely replace themselves with another construct. So, I suppose that you could have a function called enforce that returned a string and be able to do something like mixin(enforce("cond", `"failure"`)); and you could probably do something similar with a template mixin. mixin(enforce!(cond, "failure")); might be possible if both of the template parameters were alias parameters. But there's no way to take one piece of code and completely translate it into another piece of code without mixins. To do that probably would have meant using some kind of macros, or that was specifically avoided in D's design. And conceptually, using lazy for enforce is a perfect fit. The problem is with the current implementation of lazy. - Jonathan M Davis
May 16 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 16 May 2014 11:36:44 -0400, Jonathan M Davis via  
Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:

 On Thu, 15 May 2014 08:04:59 -0300
 Ary Borenszweig via Digitalmars-d-learn
 <digitalmars-d-learn puremagic.com> wrote:

 Isn't there a way in D to just expand:

 enforce(cond, "failure");

 (or something with a similar syntax) to this, at compile-time:

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

 I thought D could do this, so enforce should do this instead of using
 lazy arguments.
No. enforce is a function, and the only other things that it could be with that syntax would be other callables (e.g. a lambda, delegate, or functor).
I think it *could* optimize properly, and that would be an amazing improvement to the compiler, if someone wants to implement that. Essentially, you need to be able to inline enforce (not a problem since it's a template), and then deduce that the lazy calls can just be moved to where they are used, in this case, only once. This would make a logging library even better too. -Steve
May 16 2014
parent reply Jonathan M Davis via Digitalmars-d-learn writes:
On Fri, 16 May 2014 11:51:31 -0400
Steven Schveighoffer via Digitalmars-d-learn
<digitalmars-d-learn puremagic.com> wrote:

 On Fri, 16 May 2014 11:36:44 -0400, Jonathan M Davis via
 Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:

 On Thu, 15 May 2014 08:04:59 -0300
 Ary Borenszweig via Digitalmars-d-learn
 <digitalmars-d-learn puremagic.com> wrote:

 Isn't there a way in D to just expand:

 enforce(cond, "failure");

 (or something with a similar syntax) to this, at compile-time:

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

 I thought D could do this, so enforce should do this instead of
 using lazy arguments.
No. enforce is a function, and the only other things that it could be with that syntax would be other callables (e.g. a lambda, delegate, or functor).
I think it *could* optimize properly, and that would be an amazing improvement to the compiler, if someone wants to implement that. Essentially, you need to be able to inline enforce (not a problem since it's a template), and then deduce that the lazy calls can just be moved to where they are used, in this case, only once. This would make a logging library even better too.
Sure, the compiler could be improved to optimize enforce such that enforce(cond, "failure"); becomes if(!cond) throw new Exception("failure"); And I think that that's what needs to be done. However, what I understood the question to be was whether there was a construct in the language that we could use where enforce(cond, "failure"); would be automatically converted to if(!cond) throw new Exception("failure"); without the compiler having to do optimizations to make it happen. The closest to that would be mixins, but they can't do it with the same syntax. You'd be required to write something more complex to use mixins to do the job. But I think that the correct solution is to improve the compiler with regards to lazy. The fact that lazy is so slow is a serious problem, and enforce is just one manifestation of it (albeit the worst because of how often it's used). - Jonathan M Davis
May 17 2014
parent "w0rp" <devw0rp gmail.com> writes:
On Saturday, 17 May 2014 at 20:06:03 UTC, Jonathan M Davis via 
Digitalmars-d-learn wrote:
 But I think that the correct solution is to improve the 
 compiler with regards
 to lazy. The fact that lazy is so slow is a serious problem, 
 and enforce is
 just one manifestation of it (albeit the worst because of how 
 often it's
 used).

 - Jonathan M Davis
I haven't been bitten by the performance of lazy myself, but I'd +1 that, because of how easy it can make writing code.
May 17 2014
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 May 2014 19:50:33 -0400, Meta <jared771 gmail.com> wrote:

 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?
Last time I remember, the issue is that functions with lazy parameters will never be inlined. -Steve
May 15 2014
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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
FYI, that implementation is wrong: Array.Range keeps `_a` and `_b`, which represents the "internal" bounds of the payload proper (and not "low" and "length"). You want something along the lines of: Range searchForward(E)(E needle) if (isImplicitlyConvertible!(E, T)) { assert(_data.refCountedStore.isInitialized); auto haystack = _data._payload[_a .. _b]; immutable len = _b - _a; for (size_t index = 0; index < len; ++index) { if (haystack[index] is needle) return Range(this, _b - len, _b); } return Range(this, _b, _b); } But even then, as I suggested above, while I think having searchForward could improve the situation, implementing it "in terms of" find would be better: This way, you'd still benefit from some of the highly optimized cases in find.
May 14 2014
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Damian Day:

 Benchmark found here:
 http://dpaste.dzfl.pl/0058fc8341830
Perhaps it's a problem of missed dmd inlining. So I suggest to run the benchmark with ldc2. Bye, bearophile
May 14 2014
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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); }
May 14 2014
parent reply "David Nadlinger" <code klickverbot.at> writes:
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. 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
May 14 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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.
May 14 2014
parent Jonathan M Davis via Digitalmars-d-learn writes:
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
May 14 2014
prev sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 14 May 2014 at 14:24:28 UTC, Damian Day wrote:
 I've found bench-marking my program that std.algorithm.find is
 very slow on Array!T, due to the fact it iterates on a range
 instead of a plain array.

 I've written some search functions, which are many times 
 faster, is it
 worth making a pull request?

 http://dpaste.dzfl.pl/63b54aa27f35#
BTW, this is a more "general" issue: Given a generic algorithm "std.foo", how can I write my own (better optimized) "object.foo", and make sure *that* is called instead? I initially filed the issue for "retro", while indeed mentioning that "find" was also open to the improvement: https://issues.dlang.org/show_bug.cgi?id=12583 This spawned the thread: http://forum.dlang.org/thread/op.xeuot6g2eav7ka stevens-macbook-pro-2.local Unfortunately, nothing came of it.
May 14 2014
parent "Damian Day" <damianroyday gmail.com> writes:
On Wednesday, 14 May 2014 at 17:57:30 UTC, monarch_dodra wrote:
 BTW, this is a more "general" issue: Given a generic algorithm 
 "std.foo", how can I write my own (better optimized) 
 "object.foo", and make sure *that* is called instead?

 I initially filed the issue for "retro", while indeed 
 mentioning that "find" was also open to the improvement:
 https://issues.dlang.org/show_bug.cgi?id=12583

 This spawned the thread:
 http://forum.dlang.org/thread/op.xeuot6g2eav7ka stevens-macbook-pro-2.local

 Unfortunately, nothing came of it.
It's an interesting problem to solve. Would having a specialized container range, which has search, removal, etc primitives work better?
May 14 2014