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
