Complexity: O(1) if the collection conforms to RandomAccessCollection; otherwise, O(k), where k is the specified number of elements.
The UTF view performance is great, which isn't very surprising, but the Substring and Substring.UnicodeScalarView performance discrepancy is quite surprising to me. Given that removeFirst() is O(1), and removeFirst(1) is O(1), shouldn't the performance be the same or at least close to the same?
O(1) means the function perform in constant time, whatever the string length is, it does not tell anything about the function performance. A function that constantly take a minute to execute is complexity O(1).
That said, the removeFirst(1) case should probably be optimised to match removeFirst(). The discrepancy is surprising.
Sure. I didn't mean to imply that they are equal here, just that the operations are similar (in the case of 1 the operation is the same) so I'd expect a much smaller discrepancy. On large strings it seems that:
for _ in 1...n { s.removeFirst(n) }
Is way more performant than:
s.removeFirst(n)
Till n hits a "large"-ish number. (In my example it's when n > 5000 or so.)
The removeFirst(_:) implementation for self-slicing types checks that k <= count, which would convert this into an O(n) operation for a non-random-access collection. That'd be my bet about what's happening here:
If we calculated the new start using index(_:offsetBy:limitedBy:), we'd keep the O(1)/O(k) performance.
I don't think we could do that without an Evolution proposal, since that would change the observed behavior of the API: removeFirst(k) where k > count should reliably trap rather than silently return an empty collection.
We could just delete the precondition and let the trapping happen on calling index(_:offsetBy:). I think that's a viable change, but I haven't thought it through.
FWIW, the removeFirst(_:) API does document the correct complexity:
Complexity: O(1) if the collection conforms to RandomAccessCollection; otherwise, O(k), where k is the specified number of elements.
I would have PRed to have the precondition use index(_:offsetBy:limitedBy:) for its check instead, though if things trap later it seems fine to just delete the precondition.
Are you sure? k is the specified number of elements, not the number of elements in the array.
- _precondition(count >= k,
+ _precondition(index(startIndex, offsetBy: k, limitedBy: endIndex) != nil,
"Can't remove more items from a collection than it contains")
.)