[SR-425] Indexable documents startIndex as O(1) but this isn't true for some lazy collections

[lilyball]

Previous ID	SR-425
Radar	None
Original Reporter	@lilyball
Type	Bug
Status	Closed
Resolution	Duplicate

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Bug
Assignee	None
Priority	Medium

md5: 44131a346b66e07109ccf34858455fc1

duplicates:

• SR-428 Implement new performance terminology in documentation

Issue Description:

Indexable documents the startIndex property as having a Complexity of O(1), but LazyFilterCollection and FlattenCollection don't obey this rule. Accessing the startIndex on either collection runs the predicate up until it finds the first included element. And it does this every time you access startIndex. So that makes it O(N) at least (and a pathological predicate that captures a copy of the same underlying collection can make it arbitrarily expensive).

Luckily endIndex should be able to remain O(1) because collections can use a constant sentinel value instead of actually calculating anything (I haven't checked but I assume the lazy collection types already use a sentinel value for this).

There's two ways this can be fixed:

1. Modify LazyFilterCollection and FlattenCollection to aggressively calculate the index of the first element when they're created. But I think this would be surprising to have lazy collections run the predicate immediately, so I'd rather go with
2. Change the documentation of Indexable.startIndex to say it's O(1) in most cases, but potentially O(N) for lazy collections.

[lilyball]

PR submitted as #824. I opted to modify the doc comment.

[dabrahams]

I don’t understand what you’re getting at with FlattenCollection, since there’s no predicate involved. As for the general approach, please see my remarks here #824.

[lilyball]

You're right, that's a little unclear. The FlattenCollection I was referring to is the result of flatMap. I didn't specify because a normal flatten() on a sequence that contains a bunch of empty sequences at the start is also not O(1).

[dabrahams]

Still no predicate, but I understand what you’re saying. I was well aware of the “O(1) only if you really stretch the definition” issues here when I added these adapters. As noted in the PR, we should handle this by documenting the components rather than by loosening other guarantees. In fact, we have to update the way performance guarantees and requirements are documented if for no other reason that NSArray subclass performance is un-constrained, and Array may wrap it. We have a radar somewhere about that containing a plan…

[lilyball]

Submitted a new PR #829 that updates the doc comments on LazyCollectionType, LazyFilterCollection, and FlattenCollection. I don't consider that to actually fix SR-425 (because it's still true that these collections violate the expected performance, and I think it's bad that we document performance we can't actually provide), but it does help.

[dabrahams]

Please see SR-428, which IMO should address the larger issue.

[lilyball]

@dabrahams I like SR-428. That sounds like a good plan. I'll go ahead and mark this as a duplicate.