CPU performance issues

[mihaho]

I am facing some issues when trying to upgrade from Composable Architecture v20 to a higher version. The problem is that the CPU starts spiking after the introduction of the Identified Collections package. I profiled the app and noticed that the largest stack trace was due to the equality checks. This drew my attention to the equality conformance of IdentifiedArray. The difference with the old version is that you now use elementsEqual instead of ==. I checked the difference in Swift's source code. elementsEqual always creates 2 iterators for each sequence and goes through all elements while == has some shortcuts.

Replacing lhs.elementsEqual(rhs) with lhs.elements == rhs.elements helps a lot. The app becomes responsive again and the CPU drops for about ~50%

Is elementsEqual needed? Any comments are welcome

[mihaho]

As expected, the biggest difference is when we compare equal elements. I have run a benchmark test which is attached below. If you agree, I will be happy to create a pull request.

Legend

Red line - current algorithm, where `elementsEqual` is replaced with `==`
Blue line - current algorithm, using `elementsEqual` (no changes)

Source code:

import CollectionsBenchmark
import CollectionsA // red line
import CollectionsB // blue line

struct DummyState: Equatable, Identifiable {
    
    let value: Int
    
    var id: Int {
        value
    }
    
    init(_ value: Int) {
        self.value = value
    }
}

var benchmark = Benchmark(title: "Benchmark-Equality")

benchmark.add(
    title: "Equality ==",
    input: ([Int]).self
) { input in
    return { timer in
        let values = input.map(DummyState.init)
        let copiedValues = values
        
        let d1 = CollectionsA.IdentifiedArray(uniqueElements: values)
        let d2 = CollectionsA.IdentifiedArray(uniqueElements: copiedValues)
        
        timer.measure {
            blackHole(d1 == d2)
        }
    }
}
benchmark.add(
    title: "Equality elementsEqual",
    input: ([Int]).self
) { input in
    return { timer in
        let values = input.map(DummyState.init)
        let copiedValues = values
        
        let d1 = CollectionsB.IdentifiedArray(uniqueElements: values)
        let d2 = CollectionsB.IdentifiedArray(uniqueElements: copiedValues)
        
        timer.measure {
            blackHole(d1 == d2)
        }
    }
}

benchmark.main()
                                        

[stephencelis]

@mihaho Thanks for looking into this and for creating that benchmark! We'd definitely take a PR to change the implementation to call == instead. Wanna submit one? Otherwise we'll try to get to this soon.

[mihaho]

@stephencelis, thanks for answering. Sure, I'll submit a PR

[maximkrouk]

Also, I noticed that a thing mentioned in inline docs that direct access for Identifiable.id is faster than using a KeyPath, maybe it's better to add init with an _id closure to public API to enable users to specify id keypath as a function explicitly?