如何利用iOS中的多个处理器核心来实现fastest/shortest循环访问共享数据的计算？

Question

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

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

我提供的示例中的意图：

我正在确定地图上的一条线（汽车行驶轨迹，每秒的纬度和经度）是否在某个预定义区域内，地图上的多边形（环绕整个区域的纬度和经度） ).为此，我有一个函数可以计算单个点是否在多边形内。我正在使用 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 核心数量，在 DispatchQueues 上将数组的大致相等部分安排到 for-loops 运行ning通过 OS.

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

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

我的代码：

    /**
    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[[=13=] ..< Swift.min([=13=] + 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 region/area: Link to json File

Answer 1

感谢社区，我解决了这个问题。本回答囊括了评论区带来的各种结果。

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

利用指针（注意：基本的"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: [=11=].latitude, y: [=11=].longitude)}
        let trackPoints = coordinates.compactMap {CGPoint(x: [=11=].latitude, y: [=11=].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 变体会变得更快。谁知道，对于这个特定问题，将两者结合起来可能会得到更好的结果。

如何利用iOS中的多个处理器核心来实现fastest/shortest循环访问共享数据的计算？

How to utilize multiple processor cores in iOS to achieve the fastest/shortest computation of a loop accessing shared data?

ios

swift

ios-multithreading