[Pitch] `Distinguishable` protocol for Quick Comparisons

Evolution Pitches
47

I believe there are benefits of having a distinct entry point that could give quick positive or negative comparison results in O(1) time and return "can't determine" when it can't.

A simple test 
protocol QuickEquatable: Equatable {
    func quickEqual(_ rhs: Self) -> Bool?
}

struct S: QuickEquatable {
    var payload: [Int]
    func quickEqual(_ rhs: Self) -> Bool? {
        if payload.count != rhs.payload.count {
            return false
        }
        precondition(MemoryLayout<Self>.size == MemoryLayout<Int>.size)
        if unsafeBitCast(self, to: Int.self) == unsafeBitCast(rhs, to: Int.self) {
            return true
        }
        return nil
    }
}

extension Array where Element: QuickEquatable {
    func quickContains(_ element: Element) -> Bool {
        var notEqualCount = 0
        
        for v in self {
            if let equal = element.quickEqual(v) { // O(1)
                if equal { // identical, thus equal
                    // quick path -> yes
                    return true
                } else { // quick not equal
                    notEqualCount += 1
                }
            }
        }
        if notEqualCount == count {
            // quick path -> no
            return false
        }
        
        // slow path
        return contains(element)
    }
}

func test() {
    let payloadSize = 100000
    let arraySize = 1000
    
    var s = S(payload: [Int](repeating: 0, count: payloadSize))
    s.payload[s.payload.count - 1] = 1
    
    var array = (0 ..< arraySize).map { _ in
        S(payload: [Int](repeating: 0, count: payloadSize))
    }
    array.append(s)
    
    let (quickResult, quickTime) = measure {
        array.quickContains(s)
    }
    let (normalResult, normalTime) = measure {
        array.contains(s)
    }
    precondition(quickResult == normalResult)
    print("normalTime: \(normalTime), quickTime: \(quickTime), ratio: \(normalTime / quickTime)")
    print()
}

// normalTime: 0.07006704807281494, quickTime: 0.0003390312194824219, ratio: 206.66842475386778

Compared to normal contains, quickContains first tries to find the element quickly. Only when it fails to find the element quickly it does normal (potentially slower) comparing.

1 Like