Why is array copy on write getting triggered in this code?

I'm learning Swift using Advent of Code 2020. From day 23, an ideal data structure is a linked list in an array. But the following code runs really slow with Swift 5.3 in Xcode 12.3 (12C33).

class LLInArray {
    
    var a = Array<Int>()
    var ex1: Int = 0
    var ex2: Int = 0
    var ex3: Int = 0
    
    var head = 0
    var tail = 0
    
    init(initial: [Int], size: Int) {
        a = Array(repeating: -1, count: size)
        
        var first = true
        for i in initial {
            if first {
                head = i - 1
                tail = i - 1
                first = false
            } else {
                a[tail] = i - 1
                tail = i - 1
            }
        }
        
        a[tail] = initial.count
        for i in initial.count..<size {
            a[i] = i + 1
        }
        tail = size - 1
        a[tail] = head
    }
    
    func extract() {
        var p = head
        var prev = tail
        
        p = a[p]
        prev = a[prev]
        ex1 = p + 1
        
        p = a[p]
        prev = a[prev]
        ex2 = p + 1

        p = a[p]
        prev = a[prev]
        ex3 = p + 1

        a[head] = a[p]
        a[prev] = a[head]
    }
    
    func insert(after: Int) {
        a[ex3 - 1] = a[after - 1]
        a[ex2 - 1] = ex3 - 1
        a[ex1 - 1] = ex2 - 1
        a[after - 1] = ex1 - 1
    }
    
    func rotate() {
        head = a[head]
        tail = a[tail]
    }
    
    func twoAfter1() -> (Int, Int) {
        return (a[0] + 1, a[a[0]] + 1)
    }
    
    func contains(_ i: Int) -> Bool {
        return (i - 1 == ex1) || (i - 1 == ex2) || (i - 1 == ex3)
    }
    
    var description: String {
        get {
            var s = ""
            var first = true
            var h = self.head
            repeat {
                if !first {
                    s += ","
                } else {
                    first = false
                }
                s += String(h+1)
                h = a[h]
            } while h != self.head
            return s
        }
    }
    
    var current: Int {
        get {
            return head + 1
        }
    }
}

public func day23problem2() {
    let cups = LLInArray(initial: [6, 4, 3, 7, 1, 9, 2, 5, 8], size: 1000000)
            
//    print(cups.description)
        
    for _ in 1...10000 /*000*/ {
//        print("round \(i)")
        cups.extract()

//        print("after pickup \(pickUp) is \(cups.description)")
//        let current = cups.current
        
        var target:Int = cups.current
        repeat {
            target = target - 1
            if target == 0 {
                target = 1000000
            }
        } while cups.contains(target)
        
        cups.insert(after: target)
        cups.rotate()
        
//        print("after round \(i) current \(current) picked up \(pickUp) inserted after \(target) got \(cups.description)")
    }
    
    print(cups.twoAfter1())
}

I have been unable to meaningfully simplify the code and still reproduce the behavior.

Profiling in Xcode 12.3 (12C33) with Instruments, I get the following, which looks like a copy on write is being triggered.

Weight	Self Weight		Symbol Name
9.81 s  100.0%	0 s	 	start
9.81 s  100.0%	0 s	 	 main
9.81 s  100.0%	0 s	 	  day23problem2()
6.57 s   66.9%	0 s	 	   LLInArray.extract()
3.27 s   33.3%	0 s	 	    specialized Array.subscript.modify
3.27 s   33.3%	0 s	 	     specialized Array._makeMutableAndUnique()
3.27 s   33.3%	1.00 ms	 	      specialized Array._createNewBuffer(bufferIsUnique:minimumCapacity:growForAppend:)
3.27 s   33.3%	0 s	 	       specialized _ArrayBuffer._copyContents(subRange:initializing:)
3.27 s   33.3%	0 s	 	        specialized _ContiguousArrayBuffer._copyContents(subRange:initializing:)
3.27 s   33.3%	0 s	 	         specialized UnsafeMutablePointer.initialize(from:count:)
3.27 s   33.3%	3.27 s	 	          _platform_memmove$VARIANT$Haswell
1.00 ms    0.0%	1.00 ms	 	       swift_retain
3.24 s   32.9%	0 s	 	    specialized Array.subscript.modify
3.24 s   32.9%	0 s	 	     specialized Array._makeMutableAndUnique()
3.24 s   32.9%	0 s	 	      specialized Array._createNewBuffer(bufferIsUnique:minimumCapacity:growForAppend:)
3.24 s   32.9%	0 s	 	       specialized _ArrayBuffer._copyContents(subRange:initializing:)
3.24 s   32.9%	0 s	 	        specialized _ContiguousArrayBuffer._copyContents(subRange:initializing:)
3.24 s   32.9%	0 s	 	         specialized UnsafeMutablePointer.initialize(from:count:)
3.24 s   32.9%	3.24 s	 	          _platform_memmove$VARIANT$Haswell
54.00 ms    0.5%	0 s	 	    _swift_release_dealloc
48.00 ms    0.4%	1.00 ms	 	     free_large
47.00 ms    0.4%	47.00 ms	 	      madvise
2.00 ms    0.0%	1.00 ms	 	     free
1.00 ms    0.0%	1.00 ms	 	      szone_size
1.00 ms    0.0%	1.00 ms	 	     madvise
1.00 ms    0.0%	1.00 ms	 	     large_entry_for_pointer_no_lock
1.00 ms    0.0%	1.00 ms	 	     _ContiguousArrayStorage.__deallocating_deinit
1.00 ms    0.0%	0 s	 	     swift_deallocClassInstance
1.00 ms    0.0%	0 s	 	      objc_destructInstance
1.00 ms    0.0%	1.00 ms	 	       _object_remove_assocations
1.00 ms    0.0%	1.00 ms	 	    DYLD-STUB$$pthread_getspecific
1.00 ms    0.0%	1.00 ms	 	    swift_beginAccess
1.00 ms    0.0%	1.00 ms	 	    pthread_getspecific
1.00 ms    0.0%	1.00 ms	 	    swift_endAccess
3.24 s   33.0%	0 s	 	   LLInArray.insert(after:)
3.21 s   32.6%	0 s	 	    specialized Array.subscript.modify
3.21 s   32.6%	0 s	 	     specialized Array._makeMutableAndUnique()
3.21 s   32.6%	0 s	 	      specialized Array._createNewBuffer(bufferIsUnique:minimumCapacity:growForAppend:)
3.21 s   32.6%	0 s	 	       specialized _ArrayBuffer._copyContents(subRange:initializing:)
3.21 s   32.6%	0 s	 	        specialized _ContiguousArrayBuffer._copyContents(subRange:initializing:)
3.21 s   32.6%	0 s	 	         specialized UnsafeMutablePointer.initialize(from:count:)
3.21 s   32.6%	3.21 s	 	          _platform_memmove$VARIANT$Haswell
1.00 ms    0.0%	0 s	 	       specialized _ContiguousArrayBuffer.init(_uninitializedCount:minimumCapacity:)
1.00 ms    0.0%	1.00 ms	 	        __swift_instantiateConcreteTypeFromMangledName
31.00 ms    0.3%	0 s	 	    _swift_release_dealloc
25.00 ms    0.2%	0 s	 	     free_large
25.00 ms    0.2%	25.00 ms	 	      madvise
2.00 ms    0.0%	0 s	 	     swift_deallocClassInstance
2.00 ms    0.0%	0 s	 	      objc_destructInstance
1.00 ms    0.0%	1.00 ms	 	       free
1.00 ms    0.0%	1.00 ms	 	       _object_remove_assocations
2.00 ms    0.0%	1.00 ms	 	     free
1.00 ms    0.0%	1.00 ms	 	      szone_size
1.00 ms    0.0%	0 s	 	     <Unknown Address>
1.00 ms    0.0%	1.00 ms	 	      szone_size_try_large
1.00 ms    0.0%	1.00 ms	 	     _ContiguousArrayStorage.__deallocating_deinit
3.00 ms    0.0%	2.00 ms	 	    swift_endAccess
1.00 ms    0.0%	1.00 ms	 	     pthread_getspecific
2.00 ms    0.0%	2.00 ms	 	    DYLD-STUB$$pthread_getspecific
1.00 ms    0.0%	0 s	 	   print(_:separator:terminator:)
1.00 ms    0.0%	0 s	 	    print(_:separator:terminator:)
1.00 ms    0.0%	0 s	 	     specialized _print<A>(_:separator:terminator:to:)
1.00 ms    0.0%	0 s	 	      _print_unlocked<A, B>(_:_:)
1.00 ms    0.0%	0 s	 	       Mirror.init(reflecting:)
1.00 ms    0.0%	0 s	 	        __swift_instantiateConcreteTypeFromMangledName
1.00 ms    0.0%	0 s	 	         swift_getTypeByMangledNameInContext
1.00 ms    0.0%	0 s	 	          swift::swift_getTypeByMangledName(swift::MetadataRequest, llvm::StringRef, void const* const*, std::__1::function<swift::TargetMetadata<swift::InProcess> const* (unsigned int, unsigned int)>, std::__1::function<swift::TargetWitnessTable<swift::InProcess> const* (swift::TargetMetadata<swift::InProcess> const*, unsigned int)>)
1.00 ms    0.0%	0 s	 	           swift_getTypeByMangledNameImpl(swift::MetadataRequest, llvm::StringRef, void const* const*, std::__1::function<swift::TargetMetadata<swift::InProcess> const* (unsigned int, unsigned int)>, std::__1::function<swift::TargetWitnessTable<swift::InProcess> const* (swift::TargetMetadata<swift::InProcess> const*, unsigned int)>)
1.00 ms    0.0%	0 s	 	            swift::swift_getTypeByMangledNode(swift::MetadataRequest, swift::Demangle::Demangler&, swift::Demangle::Node*, void const* const*, std::__1::function<swift::TargetMetadata<swift::InProcess> const* (unsigned int, unsigned int)>, std::__1::function<swift::TargetWitnessTable<swift::InProcess> const* (swift::TargetMetadata<swift::InProcess> const*, unsigned int)>)
1.00 ms    0.0%	0 s	 	             swift_getTypeByMangledNodeImpl(swift::MetadataRequest, swift::Demangle::Demangler&, swift::Demangle::Node*, void const* const*, std::__1::function<swift::TargetMetadata<swift::InProcess> const* (unsigned int, unsigned int)>, std::__1::function<swift::TargetWitnessTable<swift::InProcess> const* (swift::TargetMetadata<swift::InProcess> const*, unsigned int)>)
1.00 ms    0.0%	0 s	 	              swift::Demangle::TypeDecoder<(anonymous namespace)::DecodedMetadataBuilder>::decodeMangledType(swift::Demangle::Node*)
1.00 ms    0.0%	0 s	 	               (anonymous namespace)::DecodedMetadataBuilder::createBoundGenericType(swift::TargetContextDescriptor<swift::InProcess> const*, llvm::ArrayRef<swift::TargetMetadata<swift::InProcess> const*>, swift::TargetMetadata<swift::InProcess> const*) const
1.00 ms    0.0%	0 s	 	                _gatherGenericParameters(swift::TargetContextDescriptor<swift::InProcess> const*, llvm::ArrayRef<swift::TargetMetadata<swift::InProcess> const*>, swift::TargetMetadata<swift::InProcess> const*, llvm::SmallVectorImpl<unsigned int>&, llvm::SmallVectorImpl<void const*>&, swift::Demangle::Demangler&)
1.00 ms    0.0%	0 s	 	                 swift::_checkGenericRequirements(llvm::ArrayRef<swift::TargetGenericRequirementDescriptor<swift::InProcess> >, llvm::SmallVectorImpl<void const*>&, std::__1::function<swift::TargetMetadata<swift::InProcess> const* (unsigned int, unsigned int)>, std::__1::function<swift::TargetWitnessTable<swift::InProcess> const* (swift::TargetMetadata<swift::InProcess> const*, unsigned int)>)
1.00 ms    0.0%	0 s	 	                  swift::_conformsToProtocol(swift::OpaqueValue const*, swift::TargetMetadata<swift::InProcess> const*, swift::TargetProtocolDescriptorRef<swift::InProcess>, swift::TargetWitnessTable<swift::InProcess> const**)
1.00 ms    0.0%	0 s	 	                   swift_conformsToProtocolImpl(swift::TargetMetadata<swift::InProcess> const*, swift::TargetProtocolDescriptor<swift::InProcess> const*)
1.00 ms    0.0%	0 s	 	                    swift_conformsToSwiftProtocolImpl(swift::TargetMetadata<swift::InProcess> const*, swift::TargetProtocolDescriptor<swift::InProcess> const*, llvm::StringRef)
1.00 ms    0.0%	0 s	 	                     ConformanceState::cacheSuccess(void const*, swift::TargetProtocolDescriptor<swift::InProcess> const*, swift::TargetProtocolConformanceDescriptor<swift::InProcess> const*)
1.00 ms    0.0%	0 s	 	                      malloc
1.00 ms    0.0%	0 s	 	                       malloc_zone_malloc
1.00 ms    0.0%	0 s	 	                        szone_malloc_should_clear
1.00 ms    0.0%	1.00 ms	 	                         tiny_malloc_should_clear
1.00 ms    0.0%	0 s	 	   <Unknown Address>
1.00 ms    0.0%	1.00 ms	 	    swift_bridgeObjectRetain

From the profile, it looks like there are two copy on writes in the extract() function.

A simpler program that allocates an array and has two functions that mutate it called in a loop does not trigger the problem.

class HasArray {
    var a = [Int]()
    
    init(size: Int) {
        a = [Int](0..<size)
    }

    func mutate(_ i: Int) {
        a[i] = i + 1
    }
    
    func mutate2(_ i: Int) {
        a[i + 100] = i + 2
    }
}

func testHasArray() {
    let h = HasArray(size: 1000000)
    
    for i in 1...10000 {
        h.mutate(i)
        h.mutate2(i)
    }
}

Profiling this second program shows that it does not seem to copy the data, the only measurable time is spent in the initializer.

Weight	Self Weight		Symbol Name
7.00 ms   17.0%	0 s	 	start
7.00 ms   17.0%	0 s	 	 main
7.00 ms   17.0%	0 s	 	  testHasArray()
7.00 ms   17.0%	0 s	 	   HasArray.__allocating_init(size:)
7.00 ms   17.0%	0 s	 	    HasArray.init(size:)
7.00 ms   17.0%	0 s	 	     specialized Array.init<A>(_:)
7.00 ms   17.0%	0 s	 	      specialized protocol witness for Sequence._copyToContiguousArray() in conformance <> Range<A>
7.00 ms   17.0%	0 s	 	       specialized Collection._copyToContiguousArray()
7.00 ms   17.0%	0 s	 	        specialized _copyCollectionToContiguousArray<A>(_:)
7.00 ms   17.0%	0 s	 	         specialized protocol witness for Sequence._copyContents(initializing:) in conformance <> Range<A>
7.00 ms   17.0%	2.00 ms	 	          specialized Sequence._copyContents(initializing:)
4.00 ms    9.7%	4.00 ms	 	           specialized UnsafeMutablePointer.initialize(to:)
1.00 ms    2.4%	1.00 ms	 	           specialized UnsafeMutablePointer.initialize(to:)

Is copy on write getting triggered in the first program? Or is it something else?

This is clearly a bug. Changing it from class to struct fixes it. Also, here is the reduced version of the bug with a workaround. Please report the bug and post the bug number:

class Bug {
    var a = Array(repeating: -1, count: 1_000_000)
        
    func buggy() { a[2] = a[1] }
    
    func workaround() {
        let t = a[1]
        a[2] = t
    }
}

public func triggerBug() {
    let c = Bug()
    for _ in 1...10_000 { c.buggy() }
    print("Buggy Done")
}

public func useWorkaround() {
    let c = Bug()
    for _ in 1...10_000 { c.workaround() }
    print("Workaround Done")
}

triggerBug()
useWorkaround()

Hooman, thank you for reducing it.

Reported as: https://bugs.swift.org/browse/SR-14062

Terms of Service

Privacy Policy

Cookie Policy