"in" everywhere

[Jonathan M Davis]

On Saturday 09 October 2010 06:54:31 Stewart Gordon wrote:
> On 07/10/2010 15:22, Steven Schveighoffer wrote:
> <snip>
> 
> > The problem is with generic code. Generic code that accepts some type
> > that defines the "in" operator. What can that generic code expect for
> > performance when using "in"? As a general rule, generic programming must
> > always assume the worst case, and if we have no rules for 'in', the
> > worst case is linear. Which means generic code may not use 'in' when it
> > would be a fast operation. Same thing with indexing. Try sorting a
> > 'random access' range which uses a linear search on opIndex, and see
> > what the performance is.
> 
> <snip>
> 
> Surely, what matters most for generic code is that in has consistent
> _semantics_, rather than the computational complexity?
> 
> Stewart.

_Both_ matter.

Imagine, for instance, if we were to make Java's mistake of having List be an 
interface which ArrayList and LinkedList implement and that List has a get() 
function. Using ArrayList, get() has a complexity of O(1). Using LinkedList, it 
has a complexity of O(n). Now, imagine code written with List rather than 
ArrayList or LinkedList directly. If you use get(), then your code will vary 
considerably in how efficient is. In small cases, this won't matter, but with 
large lists, it could matter a lot. Your generic code which uses List _has_ to 
worry about the computational complexity of get() or it could become very 
inefficient. In this case, for most situations, that would mean using a foreach 
loop or iterators directly, but using get() is likely a _bad_ idea. You need to 
know the computational complexity of get() in order to use List efficiently.

To write efficient algorithms, you _must_ be able to rely on certain complexity 
guarantees for the operations that you use. So, regardless of what those 
complexity gurantees actually _are_, they need to be there.

- Jonathan M Davis