Time to kill T() as (sometimes) working T.init alias ?

[Jonathan M Davis]

On Sunday, December 09, 2012 21:21:10 Mehrdad wrote:
> On Sunday, 9 December 2012 at 20:14:18 UTC, Jonathan M Davis
> 
> wrote:
> > Algorithms end up copying all the time
> 
> Hmm... like which ones, and copying what kinds of objects?

Just calling front on a range is going to copy the element, and it's not 
uncommon for front to be called multiple times within a range-based function. 
Calls to front should probably minimized anyway, because front could be 
calculating front instead of simply returning it, but that's often not 
accounted for like it should be. But even if it _is_ accounted for, if front 
is being called in a loop (as it has to be while iterating), then it's going 
to be called over and over again. And if making a copy is O(n), then those 
calls to front end up being O(n) instead of O(1) like they're supposed to be, 
and calling in a loop becomes O(n * m) instead of O(n). And plenty of 
algorithms have to do further stuff on front, which may or may not result in 
further copies.

The fact that copying can be worse than O(1) is actually pretty devastating to 
performance in general. But I don't see how it can be avoided other than 
advising people that it's a bad idea to declare types where copying them is 
worse than O(1) (which would mean that types where copying would be worse 
should try being COW types or reference types). Trying to write algorithms in 
a way which minimizes copying helps to be sure, but sometimes copying is 
necessary, and it's very easy to introduce unnecessary copying accidentally - 
copying whose cost would only become evident with types where copying is 
expensive, and most unit testing is done with primitive types or simple user-
defined types. And most unit testing does not involve any sort of timing or 
benchmarking (which is part of why Andrei wants to push for std.benchmark), so 
the cost wouldn't even necessarily be evident if unit tests _did_ use types 
which were expensive to copy.

So, I totally sympathize with Andrei and Walter wanting to say that copying 
must be O(1). I just don't think that it's realistic to expect that that's 
really going to be the case in the general case. At best, it's something that 
should be considered best practice.

- Jonathan M Davis