Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Optimizing Swift Collection

Optimizing Swift Collection

potatotips 49

Twitter hashtag: #potatotips

Ryo Aoyama

March 13, 2018
Tweet

More Decks by Ryo Aoyama

Other Decks in Programming

Transcript

  1. Sample public struct Bag0<Element> { public struct Key: Equatable {

    fileprivate let value: UInt64 fileprivate init(value: UInt64) { self.value = value } public static func == (lhs: Key, rhs: Key) -> Bool { return lhs.value == rhs.value } } private var buffer = [(key: Key, element: Element)]() private var nextKey = Key(value: 0) public init() {} @discardableResult public mutating func add(_ element: Element) -> Key { let key = nextKey nextKey = Key(value: key.value &+ 1) buffer.append((key: key, element: element)) return key } @discardableResult public mutating func remove(for key: Key) -> Element? { if let index = buffer.indices.reversed().first(where: { buffer[$0].key == key }) { return buffer.remove(at: index).element } return nil } }
  2. Sample extension Bag0: RandomAccessCollection { public var startIndex: Int {

    return buffer.startIndex } public var endIndex: Int { return buffer.endIndex } public func index(after i: Int) -> Int { return i + 1 } public subscript(position: Int) -> Element { return buffer[position].element } }
  3. public struct Bag2<Element> { private var elements = ContiguousArray<Element>() private

    var keyRawValues = ContiguousArray<UInt64>() private var nextKey = Key(value: 0) @discardableResult public mutating func remove(for key: Key) -> Element? { if let index = elements.indices.reversed().first(where: { keyRawValues[$0] == key.value }) { keyRawValues.remove(at: index) return elements.remove(at: index) } return nil } ࠷దԽࡁΈͷstdlibΛͦͷ··ར༻͢Δ͜ͱͰࣗલ࣮૷ΑΓ ΋ߴ଎ԽͰ͖Δ৔߹͕͋Δ Keyͷ୅ΘΓʹ࣮ମͷUInt64Λ֨ೲ͢Δ ͜ͱͰൺֱʹUInt64.==Λ࢖͏
  4. extension Bag3: RandomAccessCollection { public var startIndex: Int { return

    elements.startIndex } public var endIndex: Int { return elements.endIndex } public subscript(index: Int) -> Element { return elements[index] } public func makeIterator() -> ContiguousArray<Element>.Iterator { return elements.makeIterator() } } σϑΥϧτͰ࣮૷͞ΕΔIndexingIterator<Bag>಺෦Ͱɺؔ਺ݺͼग़͠ʹίε τ͕͔͔Δ৔߹͕͋ΔͨΊContiguousArray<Element>.IteratorΛެ։͢Δ @_versioned, @_inlineable͕privateଐੑͰͳ͘ͳΕ͹ΑΓద੾ʹ࠷దԽ͞Ε Δ࣮૷͕Ͱ͖Δ͕... extension Bag0: RandomAccessCollection { public var startIndex: Int { return buffer.startIndex } public var endIndex: Int { return buffer.endIndex } public func index(after i: Int) -> Int { return i + 1 } public subscript(position: Int) -> Element { return buffer[position].element } }
  5. @discardableResult public mutating func remove(for key: Key) -> Element? {

    if let index = elements.indices.reversed().first(where: { keyRawValues[$0] == key.value }) { keyRawValues.remove(at: index) return elements.remove(at: index) } return nil } ReactiveSwiftͰ͸ɺ͋ͱ͔Β௥Ճ͞Εͨ΋ͷͷํ͕remove(for:)͞Ε΍͍͢ ͱ͍͏ߟ͑Ͱٯॱʹ૞ࡧ͍ͯͨ͠ͷΛݱࡏͷ༻్ʹ߹Θͤͯ΍ΊΔ ͜ͷΑ͏ʹɺར༻ํ๏ʹ͚ͩ͢͜͠าΈدΔͷ΋༗ޮ @discardableResult public mutating func remove(for key: Key) -> Element? { if let index = elements.indices.first(where: { keyRawValues[$0] == key.value }) { keyRawValues.remove(at: index) return elements.remove(at: index) } return nil }
  6. Iteration 1,000,000 elements func testBag0() { typealias Bag = Bag0

    let count = 1000_000 var bag = Bag<Object>() for _ in 0..<count { let object = Object() bag.add(object) } measure { var trash = [Object]() trash.reserveCapacity(count) for object in bag { trash.append(object) } XCTAssertEqual(trash.count, count) } }
  7. Add, Iteration, Remove 10,000 elements func testBag0() { typealias Bag

    = Bag0 let count = 10_000 measure { var bag = Bag<Object>() var keys = [Bag<Object>.Key]() for _ in 0..<count { let object = Object() let key = bag.add(object) keys.append(key) } var trash = [Object]() trash.reserveCapacity(count) for object in bag { trash.append(object) } for key in keys { bag.remove(for: key) } XCTAssertEqual(trash.count, count) XCTAssertEqual(bag.count, 0) } }