Why does adding conformance to RandomAccessCollection cause a performance regression?

[sbromberger]

I'm not sure I did this right, but here you go:

Dropbox - File Deleted

Dropbox - File Deleted

I note that when I build the project in Xcode, it runs much more quickly than when I build it using swiftc, even with -O.

[Jens]

@sbromberger

I note that when I build the project in Xcode, it runs much more quickly than when I build it using swiftc , even with -O .

If you compile more than one swift file, be sure to use -O -whole-module-optimization.

[Jens]

@Joe_Groff

It'd also be interesting to compare the -dump-ast output with and without the RandomAccessCollection conformance. It's likely that it's influencing overload resolution somewhere here in a way that's bad for performance; maybe it's picking a "better" overload that isn't really better in this case.

I did this for the code example of this post (commenting out the two @_transparent).

The ast dump files are about 2000 lines, I could put them in a gist but I guess it's almost as easy for anyone interested to just copy paste the code example and dump the two ast files from it (commenting and uncommenting the conformance to RandomAccessCollection), anyway, below is the diff

diff ast-with-conformance.txt ast-without-conformance.txt

in case it might be of interest on its own:

13c13
<       (func_decl implicit 'anonname=0x7fbe2719ca00' interface type='(BitVector) -> () -> Array<Int>' access=private getter_for=bits
---
>       (func_decl implicit 'anonname=0x7fbb562715d0' interface type='(BitVector) -> () -> Array<Int>' access=private getter_for=bits
21c21
<       (func_decl implicit 'anonname=0x7fbe2719cc70' interface type='(inout BitVector) -> (Array<Int>) -> ()' access=private setter_for=bits
---
>       (func_decl implicit 'anonname=0x7fbb562718c0' interface type='(inout BitVector) -> (Array<Int>) -> ()' access=private setter_for=bits
31c31
<       (func_decl implicit 'anonname=0x7fbe2719d550' interface type='(inout BitVector) -> (Builtin.RawPointer, inout Builtin.UnsafeValueBuffer) -> (Builtin.RawPointer, Builtin.RawPointer?)' access=private materializeForSet_for=bits
---
>       (func_decl implicit 'anonname=0x7fbb562721a0' interface type='(inout BitVector) -> (Builtin.RawPointer, inout Builtin.UnsafeValueBuffer) -> (Builtin.RawPointer, Builtin.RawPointer?)' access=private materializeForSet_for=bits
37c37
<     (func_decl implicit 'anonname=0x7fbe2719ca00' interface type='(BitVector) -> () -> Array<Int>' access=private getter_for=bits
---
>     (func_decl implicit 'anonname=0x7fbb562715d0' interface type='(BitVector) -> () -> Array<Int>' access=private getter_for=bits
45c45
<     (func_decl implicit 'anonname=0x7fbe2719cc70' interface type='(inout BitVector) -> (Array<Int>) -> ()' access=private setter_for=bits
---
>     (func_decl implicit 'anonname=0x7fbb562718c0' interface type='(inout BitVector) -> (Array<Int>) -> ()' access=private setter_for=bits
55c55
<     (func_decl implicit 'anonname=0x7fbe2719d550' interface type='(inout BitVector) -> (Builtin.RawPointer, inout Builtin.UnsafeValueBuffer) -> (Builtin.RawPointer, Builtin.RawPointer?)' access=private materializeForSet_for=bits
---
>     (func_decl implicit 'anonname=0x7fbb562721a0' interface type='(inout BitVector) -> (Builtin.RawPointer, inout Builtin.UnsafeValueBuffer) -> (Builtin.RawPointer, Builtin.RawPointer?)' access=private materializeForSet_for=bits
66c66
<       (func_decl implicit 'anonname=0x7fbe2722a7c0' interface type='(BitVector) -> () -> Int' access=private getter_for=blockSize
---
>       (func_decl implicit 'anonname=0x7fbb562f1160' interface type='(BitVector) -> () -> Int' access=private getter_for=blockSize
74c74
<     (func_decl implicit 'anonname=0x7fbe2722a7c0' interface type='(BitVector) -> () -> Int' access=private getter_for=blockSize
---
>     (func_decl implicit 'anonname=0x7fbb562f1160' interface type='(BitVector) -> () -> Int' access=private getter_for=blockSize
192c192
<       (func_decl 'anonname=0x7fbe270c6230' interface type='(BitVector) -> () -> Int' access=internal getter_for=startIndex
---
>       (func_decl 'anonname=0x7fbb558c6230' interface type='(BitVector) -> () -> Int' access=internal getter_for=startIndex
204c204
<     (func_decl 'anonname=0x7fbe270c6230' interface type='(BitVector) -> () -> Int' access=internal getter_for=startIndex
---
>     (func_decl 'anonname=0x7fbb558c6230' interface type='(BitVector) -> () -> Int' access=internal getter_for=startIndex
222c222
<       (func_decl 'anonname=0x7fbe270c6620' interface type='(BitVector) -> () -> Int' access=internal getter_for=endIndex
---
>       (func_decl 'anonname=0x7fbb558c6620' interface type='(BitVector) -> () -> Int' access=internal getter_for=endIndex
238c238
<     (func_decl 'anonname=0x7fbe270c6620' interface type='(BitVector) -> () -> Int' access=internal getter_for=endIndex
---
>     (func_decl 'anonname=0x7fbb558c6620' interface type='(BitVector) -> () -> Int' access=internal getter_for=endIndex
255c255
<       (func_decl 'anonname=0x7fbe270c6c50' interface type='(BitVector) -> (Int) -> Bool' access=internal getter_for=subscript(_:)
---
>       (func_decl 'anonname=0x7fbb558c6c50' interface type='(BitVector) -> (Int) -> Bool' access=internal getter_for=subscript(_:)
316c316
<       (func_decl 'anonname=0x7fbe270c76c0' interface type='(inout BitVector) -> (Bool, Int) -> ()' access=internal setter_for=subscript(_:)
---
>       (func_decl 'anonname=0x7fbb558c76c0' interface type='(inout BitVector) -> (Bool, Int) -> ()' access=internal setter_for=subscript(_:)
394c394
<       (func_decl implicit 'anonname=0x7fbe2722af60' interface type='(inout BitVector) -> (Builtin.RawPointer, inout Builtin.UnsafeValueBuffer, Int) -> (Builtin.RawPointer, Builtin.RawPointer?)' access=internal materializeForSet_for=subscript(_:)
---
>       (func_decl implicit 'anonname=0x7fbb562f1900' interface type='(inout BitVector) -> (Builtin.RawPointer, inout Builtin.UnsafeValueBuffer, Int) -> (Builtin.RawPointer, Builtin.RawPointer?)' access=internal materializeForSet_for=subscript(_:)
401c401
<     (func_decl 'anonname=0x7fbe270c6c50' interface type='(BitVector) -> (Int) -> Bool' access=internal getter_for=subscript(_:)
---
>     (func_decl 'anonname=0x7fbb558c6c50' interface type='(BitVector) -> (Int) -> Bool' access=internal getter_for=subscript(_:)
462c462
<     (func_decl 'anonname=0x7fbe270c76c0' interface type='(inout BitVector) -> (Bool, Int) -> ()' access=internal setter_for=subscript(_:)
---
>     (func_decl 'anonname=0x7fbb558c76c0' interface type='(inout BitVector) -> (Bool, Int) -> ()' access=internal setter_for=subscript(_:)
540c540
<     (func_decl implicit 'anonname=0x7fbe2722af60' interface type='(inout BitVector) -> (Builtin.RawPointer, inout Builtin.UnsafeValueBuffer, Int) -> (Builtin.RawPointer, Builtin.RawPointer?)' access=internal materializeForSet_for=subscript(_:)
---
>     (func_decl implicit 'anonname=0x7fbb562f1900' interface type='(inout BitVector) -> (Builtin.RawPointer, inout Builtin.UnsafeValueBuffer, Int) -> (Builtin.RawPointer, Builtin.RawPointer?)' access=internal materializeForSet_for=subscript(_:)
554c554
<       (func_decl implicit 'anonname=0x7fbe271c1680' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> T' access=internal getter_for=src
---
>       (func_decl implicit 'anonname=0x7fbb56285990' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> T' access=internal getter_for=src
562c562
<     (func_decl implicit 'anonname=0x7fbe271c1680' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> T' access=internal getter_for=src
---
>     (func_decl implicit 'anonname=0x7fbb56285990' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> T' access=internal getter_for=src
576c576
<       (func_decl implicit 'anonname=0x7fbe271c1a60' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> T' access=internal getter_for=dst
---
>       (func_decl implicit 'anonname=0x7fbb56285d70' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> T' access=internal getter_for=dst
584c584
<     (func_decl implicit 'anonname=0x7fbe271c1a60' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> T' access=internal getter_for=dst
---
>     (func_decl implicit 'anonname=0x7fbb56285d70' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> T' access=internal getter_for=dst
614c614
<       (func_decl 'anonname=0x7fbe270c8cd0' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> Edge<T>' access=internal getter_for=ordered
---
>       (func_decl 'anonname=0x7fbb558c8cd0' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> Edge<T>' access=internal getter_for=ordered
647c647
<     (func_decl 'anonname=0x7fbe270c8cd0' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> Edge<T>' access=internal getter_for=ordered
---
>     (func_decl 'anonname=0x7fbb558c8cd0' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> Edge<T>' access=internal getter_for=ordered
686c686
<       (func_decl 'anonname=0x7fbe270c9370' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> Edge<T>' access=internal getter_for=reverse
---
>       (func_decl 'anonname=0x7fbb558c9370' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> Edge<T>' access=internal getter_for=reverse
701c701
<     (func_decl 'anonname=0x7fbe270c9370' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> Edge<T>' access=internal getter_for=reverse
---
>     (func_decl 'anonname=0x7fbb558c9370' interface type='<T where T : BinaryInteger> (Edge<T>) -> () -> Edge<T>' access=internal getter_for=reverse
725c725
<       (func_decl implicit 'anonname=0x7fbe2723d5f0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Array<T>' access=internal getter_for=rowidx
---
>       (func_decl implicit 'anonname=0x7fbb562870f0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Array<T>' access=internal getter_for=rowidx
733c733
<     (func_decl implicit 'anonname=0x7fbe2723d5f0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Array<T>' access=internal getter_for=rowidx
---
>     (func_decl implicit 'anonname=0x7fbb562870f0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Array<T>' access=internal getter_for=rowidx
752c752
<       (func_decl implicit 'anonname=0x7fbe2723c320' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Array<Array.Index>' access=internal getter_for=colptr
---
>       (func_decl implicit 'anonname=0x7fbb563081f0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Array<Array.Index>' access=internal getter_for=colptr
760c760
<     (func_decl implicit 'anonname=0x7fbe2723c320' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Array<Array.Index>' access=internal getter_for=colptr
---
>     (func_decl implicit 'anonname=0x7fbb563081f0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Array<Array.Index>' access=internal getter_for=colptr
774c774
<       (func_decl 'anonname=0x7fbe270c9e50' interface type='<T where T : BinaryInteger> (Graph<T>.Type) -> () -> Any.Type' access=internal type getter_for=eltype
---
>       (func_decl 'anonname=0x7fbb558c9e50' interface type='<T where T : BinaryInteger> (Graph<T>.Type) -> () -> Any.Type' access=internal type getter_for=eltype
783c783
<     (func_decl 'anonname=0x7fbe270c9e50' interface type='<T where T : BinaryInteger> (Graph<T>.Type) -> () -> Any.Type' access=internal type getter_for=eltype
---
>     (func_decl 'anonname=0x7fbb558c9e50' interface type='<T where T : BinaryInteger> (Graph<T>.Type) -> () -> Any.Type' access=internal type getter_for=eltype
798c798
<       (func_decl 'anonname=0x7fbe270ca250' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> T' access=internal getter_for=nv
---
>       (func_decl 'anonname=0x7fbb558ca250' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> T' access=internal getter_for=nv
824c824
<     (func_decl 'anonname=0x7fbe270ca250' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> T' access=internal getter_for=nv
---
>     (func_decl 'anonname=0x7fbb558ca250' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> T' access=internal getter_for=nv
856c856
<       (func_decl 'anonname=0x7fbe270ca7e0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Int' access=internal getter_for=ne
---
>       (func_decl 'anonname=0x7fbb558ca7e0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Int' access=internal getter_for=ne
876c876
<     (func_decl 'anonname=0x7fbe270ca7e0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Int' access=internal getter_for=ne
---
>     (func_decl 'anonname=0x7fbb558ca7e0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> Int' access=internal getter_for=ne
904c904
<       (func_decl 'anonname=0x7fbe270cad00' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> StrideTo<T>' access=internal getter_for=vertices
---
>       (func_decl 'anonname=0x7fbb558cad00' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> StrideTo<T>' access=internal getter_for=vertices
941c941
<     (func_decl 'anonname=0x7fbe270cad00' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> StrideTo<T>' access=internal getter_for=vertices
---
>     (func_decl 'anonname=0x7fbb558cad00' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> StrideTo<T>' access=internal getter_for=vertices
1648c1648
<       (func_decl 'anonname=0x7fbe270d27b0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> String' access=internal getter_for=description
---
>       (func_decl 'anonname=0x7fbb558d27b0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> String' access=internal getter_for=description
1664c1664
<     (func_decl 'anonname=0x7fbe270d27b0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> String' access=internal getter_for=description
---
>     (func_decl 'anonname=0x7fbb558d27b0' interface type='<T where T : BinaryInteger> (Graph<T>) -> () -> String' access=internal getter_for=description
1680,1685d1679
<   (extension_decl BitVector inherits: RandomAccessCollection
<     (typealias implicit "Element" interface type='BitVector.Element.Type' access=internal type='Bool')
<     (typealias implicit "Index" interface type='BitVector.Index.Type' access=internal type='Int')
<     (typealias implicit "SubSequence" interface type='BitVector.SubSequence.Type' access=internal type='Slice<BitVector>')
<     (typealias implicit "Indices" interface type='BitVector.Indices.Type' access=internal type='CountableRange<Int>')
<     (typealias implicit "Iterator" interface type='BitVector.Iterator.Type' access=internal type='IndexingIterator<BitVector>'))

[Joe_Groff]

Thanks @Jens and @sbromberger. The diff doesn't indicate anything obviously different between the two forms.

[sbromberger]

Is there anything else I can try to help narrow down the source of this problem?

[Joe_Groff]

We should be able to investigate with the information in @Jens' post. I filed [SR-7713] Adding redundant `RandomAccessCollection` conformance mysteriously causes code to be less optimized · Issue #50253 · apple/swift · GitHub to investigate this.

[sbromberger]

Thank you!