Value of `underestimatedCount` for lazy sequences

Using Swift
1

I'm using the underestimatedCount computed property of sequences to reserve capacity of a container before operations such as map. The underestimatedCount is used in the same way in the standard library, such as the Array initializer that use a sequence as input:

let sequence = [1, 2, 3]
let result = Array(sequence)  // Internally use `underestimatedCount`
                              // to avoid reallocatinons

Some sequences forward the underestimatedCount, such as LazySequence:

let seq = [1, 2, 3].lazy
print(seq.underestimatedCount)  // Prints '3'

Moreover, the Collection default implementation is the collection's count value, so a ReversedCollection forward the underestimatedCount automatically:

let seq = [1, 2, 3].reversed()
print(seq.underestimatedCount)  // Prints '3'

However, I found that some sequences does not forward the underestimatedCount such as:

let seq = [1, 2, 3].enumerated()
print(seq.underestimatedCount)  // Prints '0'

And some other combinations neither:

let seq = [[1, 2], [3]].lazy.joined()
print(seq.underestimatedCount)  // Prints '0', removing `lazy` prints `3`

Is this intended behavior? This could lead to poorly efficient code causing many unnecessary array reallocations.

2

There are cases where underestimatedCounts are improved in the past. If you think there are reasonable (and fast) implementations, you can file a bug report or just straight up pr.

That said, the lazy.joined case returning 0 sounds about right.

1 Like
3

thanks for the answer, could you expand on why returning underestimatedCount = 0 is correct for a LazySequence<FlattenSequence<Base>> but not for a FlattenSequence<Base>?

To me this is counterintuitive, LazySequence forwards the underlying base sequence underestimatedCount, but when the base is a FlattenSequence it appears that it is not the case.

I tried to fill bug reports in the past (here and here) but I never had an answer (excepted an automatic response of a bot). Since I don't know for sure that this is a bug, I feel that discussing it here in Swift Forums is more appropriated, I don't want to waste the time of Swift developers for a potential mistake on my side.

4

Oh right, I forgot FlattenSequence does have non-zero underestimated counts, albeit it doesn’t look like an O(1) implementation. I’d suspect some generic shenanigans since the following code exhibits similar behaviour.

func x<T : Collection>(_ t: T) -> Int {
    t.underestimatedCount
}

x([[1, 2]].joined()) // 0