ios - 如何利用 iOS 中的多个处理器内核来实现访问共享数据的循环的最快/最短计算？

Question

在 iOS 上运行的 Swift 中对数组运行 for 循环时，我想利用整个 CPU，因为我觉得这在理论上应该可以加快计算速度。然而，我的结果恰恰相反，在单个 DispatchQueue 而不是多个 DispatchQueue 上运行所有内容，实际上执行得更快。我将提供一个示例，并想知道为什么单线程方法更快，如果可能的话，我仍然可以通过正确利用多个 cpu 内核来减少计算所需的时间？

对于那些只想查看我的意图代码的人可以跳过，因为下一节仅阐述我的意图和方法。

示例中我的意图:

我正在确定 map 上的一条线(汽车行驶轨迹、每秒的纬度和经度)是否在某个预定义区域内、 map 上的多边形(环绕整个区域的纬度和经度)。为此，我有一个函数可以计算单个点是否在多边形内。我正在使用 for 循环来遍历汽车行驶轨迹中的每个位置，并使用该功能检查该点是否在多边形内。如果每个跟踪的位置都在多边形内，则整个跟踪的汽车行驶发生在所述区域内。

我将 iPhone X 用于开发目的，并利用整个 CPU 来加速此计算。

我的方法:

在提供的示例中，我有 3 个变体，导致计算所需的时间如下(以秒为单位):

Time elapsed for single thread variant: 6.490409970283508 s.
Time elapsed for multi thread v1 variant: 24.076722025871277 s.
Time elapsed for multi thread v2 variant: 23.922222018241882 s.

第一种方法是最简单的，即不使用多个 DispatchQueue。

第二种方法使用 DispatchQueue.concurrentPerform(iterations: Int)。我觉得这可能是满足我需求的最佳解决方案，因为它已经实现并且似乎是为我的确切目的而设计的。

第三种方法是我自己的，它根据操作系统报告的事件 CPU 内核数量，将数组的大致相等部分调度到在 DispatchQueue 上运行的 for 循环。

我也尝试过使用 inout 参数的变体(通过引用调用)但无济于事。时间保持不变，因此我没有提供更多代码来混淆问题。

我也知道，只要我发现一个点不在多边形内，我就可以返回函数，但这不是这个问题的一部分。

我的代码:

    /**
    Function that calculates wether or not a 
    single coordinate is within a polygon described
    as a pointlist. 
    This function is used by all others to do the work.
    */
    private static func contains(coordinate: CLLocationCoordinate2D, with pointList: [CLLocationCoordinate2D]) -> Bool {
        var isContained = false
        var j = pointList.count - 1
        let lat = coordinate.latitude
        let lon = coordinate.longitude
        for i in 0 ..< pointList.count {

            if (pointList[i].latitude > lat) != (pointList[j].latitude > lat) &&
                (lon < (pointList[j].longitude - pointList[i].longitude) * (lat - pointList[i].latitude) / (pointList[j].latitude - pointList[i].latitude) + pointList[i].longitude) {
                isContained.toggle()
            }
            j = i
        }
        return isContained
    }

///Runs all three variants as are described in the question
    static func testAllVariants(coordinates: [CLLocationCoordinate2D], areInside pointList: [CLLocationCoordinate2D]) {
        var startTime = CFAbsoluteTimeGetCurrent()
        var bool = contains_singleThread(coordinates: coordinates, with: pointList)
        var timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        print("Time elapsed for single thread variant: \(timeElapsed) s.")

        startTime = CFAbsoluteTimeGetCurrent()
        bool = contains_multiThread_v1(coordinates: coordinates, with: pointList)
        timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        print("Time elapsed for multi thread v1 variant: \(timeElapsed) s.")

        startTime = CFAbsoluteTimeGetCurrent()
        bool = contains_multiThread_v2(coordinates: coordinates, with: pointList)
        timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        print("Time elapsed for multi thread v2 variant: \(timeElapsed) s.")
    }

    private static func contains_singleThread(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        var bContainsAllPoints = true
        for coordinate in coordinates {
            if !contains(coordinate: coordinate, with: pointList) {
                bContainsAllPoints = false
            }
        }
        return bContainsAllPoints
    }

    private static func contains_multiThread_v1(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        let numOfCoordinates = coordinates.count
        var booleanArray = Array(repeating: true, count: numOfCoordinates)
        DispatchQueue.concurrentPerform(iterations: numOfCoordinates) { (index) in
            if !contains(coordinate: coordinates[index], with: pointList) {
                booleanArray[index] = false
            }
        }
        return !booleanArray.contains(false)
    }

    private static func contains_multiThread_v2(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        let numOfCoordinates = coordinates.count
        let coreCount = ProcessInfo().activeProcessorCount

        func chunk<T>(array: [T], into size: Int) -> [[T]] {
            return stride(from: 0, to: array.count, by: size).map {
                Array(array[$0 ..< Swift.min($0 + size, array.count)])
            }
        }

        let segments = chunk(array: coordinates, into: numOfCoordinates/coreCount)

        let dg = DispatchGroup()
        for i in 0..<segments.count {
            dg.enter()
        }

        var booleanArray = Array(repeating: true, count: segments.count)

        for (index, segment) in segments.enumerated() {
            DispatchQueue.global(qos: .userInitiated).async {
                for coordinate in segment {
                    if !contains(coordinate: coordinate, with: pointList) {
                        booleanArray[index] = false
                    }
                }
                dg.leave()
            }
        }

        dg.wait()
        return !booleanArray.contains(false)
    }

示例数据

我已经为那些希望有数据来运行测试的人上传了两个 json 文件。这与导致我记录时间的输入相同。

被追踪的乘车路线:Link to json File地区/区域:Link to json File

Answer 1

感谢社区，我解决了这个问题。这个答案包含了评论部分带来的各种结果。

有两种方式，一种是使用指针，这是比较通用的方式。另一个更具体地针对我的问题，它利用 GPU 来查看多个点是否在预定义的多边形内。无论哪种方式，这里都有两种方式，因为代码胜于 Eloquent ；)。

利用指针(注意:基本的“contains/containsWithPointer”函数可以在问题中找到):

private static func contains_multiThread(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        let numOfCoordinates = coordinates.count
        var booleanArray = Array(repeating: true, count: numOfCoordinates)
        let coordinatePointer: UnsafeBufferPointer<CLLocationCoordinate2D> = {
            return coordinates.withUnsafeBufferPointer { pointer -> UnsafeBufferPointer<CLLocationCoordinate2D> in
                return pointer
            }
        }()
        let pointListPointer: UnsafeBufferPointer<CLLocationCoordinate2D> = {
            return pointList.withUnsafeBufferPointer { pointer -> UnsafeBufferPointer<CLLocationCoordinate2D> in
                return pointer
            }
        }()
        let booleanPointer: UnsafeMutableBufferPointer<Bool> = {
            return booleanArray.withUnsafeMutableBufferPointer { pointer -> UnsafeMutableBufferPointer<Bool> in
                return pointer
            }
        }()

        DispatchQueue.concurrentPerform(iterations: numOfCoordinates) { (index) in
            if !containsWithPointer(coordinate: coordinatePointer[index], with: pointListPointer) {
                booleanPointer[index] = false
            }
        }

    return !booleanArray.contains(false)
}

利用 GPU:

private static func contains_gpu(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        let regionPoints = pointList.compactMap {CGPoint(x: $0.latitude, y: $0.longitude)}
        let trackPoints = coordinates.compactMap {CGPoint(x: $0.latitude, y: $0.longitude)}

        let path = CGMutablePath()
        path.addLines(between: regionPoints)
        path.closeSubpath()

        var flag = true
        for point in trackPoints {
            if !path.contains(point) {
                flag = false
            }
        }

        return flag
    }

哪个函数更快取决于系统、点数和多边形的复杂性。我的结果是多线程变体大约快 30%，但是当多边形相当简单或点数达到数百万时，差距就会缩小，最终 gpu 变体会变得更快。谁知道，对于这个特定问题，将两者结合起来可能会得到更好的结果。