silly-stringsearch.swift

@inline(never)
func searchSlow(_ haystack: UnsafeBufferPointer<UInt8>, needle: UInt8) -> Int? {
    print(haystack)
    return haystack.firstIndex(of: needle)
}

@inline(never)
func searchFast16(_ ptr: UnsafeBufferPointer<UInt8>, needle: UInt8) -> Int? {
    assert(ptr.count % 16 == 0)

    var index = 0
    var wh = UInt16(0)
    while index < ptr.count {
        wh  = ptr[index &+ 15] == needle ? 1 << 0 : 0
        wh |= ptr[index &+ 14] == needle ? 1 << 1 : 0
        wh |= ptr[index &+ 13] == needle ? 1 << 2 : 0
        wh |= ptr[index &+ 12] == needle ? 1 << 3 : 0
        wh |= ptr[index &+ 11] == needle ? 1 << 4 : 0
        wh |= ptr[index &+ 10] == needle ? 1 << 5 : 0
        wh |= ptr[index &+ 9] == needle ? 1 << 6 : 0
        wh |= ptr[index &+ 8] == needle ? 1 << 7 : 0
        wh |= ptr[index &+ 7] == needle ? 1 << 8 : 0
        wh |= ptr[index &+ 6] == needle ? 1 << 9 : 0
        wh |= ptr[index &+ 5] == needle ? 1 << 10 : 0
        wh |= ptr[index &+ 4] == needle ? 1 << 11 : 0
        wh |= ptr[index &+ 3] == needle ? 1 << 12 : 0
        wh |= ptr[index &+ 2] == needle ? 1 << 13 : 0
        wh |= ptr[index &+ 1] == needle ? 1 << 14 : 0
        wh |= ptr[index &+ 0] == needle ? 1 << 15 : 0

        if wh != 0 {
            break
        }
        index = index &+ 16
    }
    if wh != 0 {
        return index + Int(wh.leadingZeroBitCount)
    } else {
        return nil
    }
}

@inline(never)
func vectoSearch(haystack: String, needle: UInt8) -> String.UTF8View.Index? {
    return haystack.utf8.withContiguousStorageIfAvailable { hPtr -> Int? in
        print("start", hPtr)
        if hPtr.count < 16 {
            return searchSlow(hPtr, needle: needle)
        } else {
            let leftovers = hPtr.count % 16
            if let firstIndex = searchFast16(UnsafeBufferPointer(rebasing: hPtr[0 ..< (hPtr.endIndex - leftovers)]),
                                            needle: needle) {
                return firstIndex
            } else {
                return searchSlow(UnsafeBufferPointer(rebasing: hPtr[(hPtr.endIndex - leftovers)...]), needle: needle)
            }
        }
    }!.map { (index: Int) -> String.UTF8View.Index in
        print("index", index)
        return haystack.utf8.index(haystack.utf8.startIndex, offsetBy: index)
    }
}

let length = Int.random(in: 100_000 ..< 100_001)
var string = String(repeating: "a", count: length)
string.append("b")
string.append("X")
string.append("Cccccccccccccccccccccccccccccccccccc")

let result = vectoSearch(haystack: string, needle: UInt8(ascii: "X"))
print("result", result.debugDescription)
print(result.map {
    string[$0]
}.debugDescription)