"in" everywhere

[Steven Schveighoffer]

On Thu, 07 Oct 2010 19:07:55 -0400, Rainer Deyke <rainerd at eldwood.com>  
wrote:

> On 10/7/2010 14:33, Steven Schveighoffer wrote:
>> On Thu, 07 Oct 2010 16:23:47 -0400, Rainer Deyke <rainerd at eldwood.com>
>> wrote:
>>> I can't say I've ever cared about the big-O complexity of an operation.
>>
>> Then you don't understand how important it is.
>
> Let me rephrase that.  I care about performance.  Big-O complexity can
> obviously have a significant effect on performance, so I so do care
> about it, but only to the extend that it affects performance.  Low big-O
> complexity is a means to an end, not a goal in and of itself.  If 'n' is
> low enough, then a O(2**n) algorithm may well be faster than an O(1)
> algorithm.

You'd be surprised at how important it is.  I remember competing on  
TopCoder when they just barely added C++ as a possible language.  I  
remember wondering "how are all the Java guys going to even compete with  
C++?"  But the big-O complexity was always way way more important than the  
performance differences of native vs. JVM'd code.

The thing about big-O complexity is that it gives you a good idea of how  
well your library will perform under defined circumstances.  And libraries  
must be completely aware and rigid about it, or else you have situations  
where things are nice and easy syntax-wise but perform horribly when  
actually used.  What you end up with when libraries don't care about it  
are "mysterious" slowdowns, or cases where people just start blaming the  
language for being so slow.

Imagine if a database backend developer said "you know, who cares about  
big-O complexity, I think linear performance is good enough, most people  
have small databases anyways" who would ever use that backend?  This is  
akin to how phobos needs to strive for the best performance.

>
> I also believe that, in the absence of a sophisticated system that
> actually verifies performance guarantees, the language and standard
> library should trust the programmer to know what he is doing.  The
> standard library should only provide transitive performance guarantees,
> e.g. this algorithm calls function 'f' 'n' times, so the algorithm's
> performance is O(n * complexity(f)).  If 'f' runs in constant time, the
> algorithm runs in linear time.  If 'f' runs in exponential time, the
> algorithm still runs.
>
>> big O complexity is very important when you are writing libraries.  Not
>> so much when you are writing applications -- if you can live with it in
>> your application, then fine.  But Phobos should not have these problems
>> for people who *do* care.
>>
>> What I'd suggest is to write your own function that uses in when
>> possible and find when not possible.  Then use that in your code.
>
> The issue is that algorithms may use 'in' internally, so I may have to
> rewrite large parts of Phobos.  (And the issue isn't about 'in'
> specifically, but complexity guarantees in general.)\

You have two options, define opIn how you want if you don't care about  
complexity guarantees (not recommended), or define a wrapper function that  
uses the best available option, which your code can use.

Despite phobos defining opIn to require lg(n) or better complexity, it  
does not restrict you from defining opIn how you want (even on arrays if  
you wish).  I personally find the tools phobos provides completely  
adequate for the tasks you would need to do.

-Steve