Performance of "removeFirst()" vs "removeFirst(1)"?

When working with a mutable substring, I was surprised to see that removeFirst() and removeFirst(1) had drastically different performance.

I've pushed a benchmark here, which runs removeFirst() and removeFirst(1) on a bunch of different string types:

And here's a sample run from my machine:

name                                        time          std        iterations
-------------------------------------------------------------------------------
String.removeFirst()                        81679174.0 ns ±   1.64 %         16
String.removeFirst(1)                       81369569.0 ns ±   2.42 %         17
Substring.removeFirst()                          132.0 ns ± 274.18 %    1000000
Substring.removeFirst(1)                    93850715.0 ns ±   2.25 %         15
Substring.UnicodeScalarView.removeFirst()        109.0 ns ± 241.26 %    1000000
Substring.UnicodeScalarView.removeFirst(1)  18106959.0 ns ±   5.49 %         66
Substring.UTF8View.removeFirst()                 117.0 ns ± 313.89 %    1000000
Substring.UTF8View.removeFirst(1)                118.0 ns ± 287.76 %    1000000
Substring.UTF16View.removeFirst()                108.0 ns ± 323.84 %    1000000
Substring.UTF16View.removeFirst(1)               126.0 ns ± 330.52 %    1000000

The documentation has this to say:

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?

Is this a bug?

4 Likes

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.)

What happens when you put the test string in a separate module so that the operation definitely can't be constant-folded away?

I originally ran the benchmark against a string loaded from disk and the performance was the same. (Didn't want to include a 10MB file in the repo :smile:.)

1 Like

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.

8 Likes

Are you planning on making that change or is it something I should PR?

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.

Never mind: brainfart. I forgot that the limitedBy: API returns nil; it'd all be equivalent.

Yeah, oops: that's not quite right.

This seems to improve things:

-    _precondition(count >= k,
+    _precondition(index(startIndex, offsetBy: k, limitedBy: endIndex) != nil,
       "Can't remove more items from a collection than it contains")
name                                       time     std        iterations
-------------------------------------------------------------------------
Substring.removeFirst()                    107.0 ns ± 407.56 %    1000000
Substring.removeFirst(1)                    90.0 ns ± 185.21 %    1000000
Substring.UnicodeScalarView.removeFirst()  102.0 ns ± 426.49 %    1000000
Substring.UnicodeScalarView.removeFirst(1)  95.0 ns ± 282.41 %    1000000
Substring.UTF8View.removeFirst()           105.0 ns ± 180.93 %    1000000
Substring.UTF8View.removeFirst(1)           89.0 ns ± 351.59 %    1000000
Substring.UTF16View.removeFirst()          105.0 ns ± 367.93 %    1000000
Substring.UTF16View.removeFirst(1)         102.0 ns ± 177.51 %    1000000

Edit: opened a PR here:

9 Likes
Terms of Service

Privacy Policy

Cookie Policy