swift - 是否有可能使多线程代码效率更高？ (双循环 O(n^2))

Question

我使用最小编辑距离算法来查找相似的字符串。

我的代码主题是在输入数据中找到爱好最接近的夫妇。

Hobby type
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

// * All of the person have 10 hobby. 
// * Hobby can not be duplicated.

// Input Data format
// 1000.txt
1000                   // number of data
N D R P Y X V B M T    // each line is person's hobbies
P J Z E X W H S M N
F U G L C T Q S O P
A D Q S F E N P Y G
K P D F G Q U I V H
D E I S N L C K H G
D I R K J V Q H M Z
Y A R D F T N P W O
R A G Z F M J K I Y
P E K W H S F Z G R
U J O T I B R Y E H
M A Z N S J H X T P
...
...

// This is Couple Model
struct Couple {
  let firstIdx: Int
  let firstArray: String

  let secondIdx: Int
  let secondArray: String

  let value: Int
}

// This function finds the couple with the closest hobbies among the input data.
func findCouple() {
    guard
      // Utility.makeData's return value is purified Input data. ex) N D R P Y X V B M T -> BDMNPRTVYX
      let data = Utility.makeData(using: "1000") 
      let count = Int(data[0]) else { return }

    var couples = [Couple]()
    var min = data[1].count

    // make GCD Group for handle each queue.
    let group = DispatchGroup()  

    for i in 1..<count {
      // Pivot for hobby compare
      let hobby = data[i]

      // make custom queue for multi-threading
      let queue = DispatchQueue(label: "idx.\(i).queue", attributes: .concurrent)

      queue.async(group: group) {
        for j in (i + 1)..<data.count {
          // This is the subject of comparison.
          let hobby2 = data[j]

          // Calculate for find similarly string
          let newMin = hobby.minimumEditDistance(other: hobby2)

          queue.async(group: group, qos: .userInitiated, flags: .barrier) {
            // If find more similarly string bundle
            if min >= newMin {
              min = newMin
              // Store the couple
              couples.append(
                Couple(firstIdx: i, firstArray: hobby, secondIdx: j, secondArray: hobby2, value: min)
              )
            }
          }
        }
      }
    }

    group.notify(queue: DispatchQueue.global()) {
      let similarCouples = couples.filter({$0.value == min}
      // I want to print like
      // 1-3 : index of persons
      // ASDFZXCVNM : 1 persons's hobby
      // ASDFXCVBJK : 2 persons's hobby
    }
}

如果输入数据的大小足够大(10000 或更多)，我的功能的性能最差。(非常慢)

请让我知道是否有任何改进。

Answer 1

毫无疑问，您可以在初次尝试时大大提高。坦率地说，尽管看起来令人惊讶，但您当前的再现甚至可能比非并行版本的效率更低，这是一个严重的风险。对两者进行基准测试并进行比较。

关于这些问题，它们是多方面的:

有更多async通话并不总是更好。肆无忌惮async电话将引入各种低效率。首先，工作线程的数量非常有限(目前为 64)。其次，无论如何，超过设备上可用内核的数量没有任何用处。

而不是这些async电话，我们经常联系concurrentPerform .这通常是并行化 for 的最有效方式。环形。这永远不会超过硬件允许的可用并发线程数。

因此，考虑非并行再现:

for i in 0 ..< 9_999 {
    for j in i+1 ..< 10_000 {
        ...
    }
}

我们将它简单地并行化:

DispatchQueue.concurrentPerform(iterations: 9_999) { i in
    for j in i+1 ..< 10_000 {
        ...
    }
}

而且，因为 concurrentPerform阻塞你调用它的线程，你可能会将整个事情分派(dispatch)到后台队列:

DispatchQueue.global().async {
    DispatchQueue.concurrentPerform(iterations: 9_999) { i in
        for j in i+1 ..< 10_000 {
            ...
        }
    }

    DispatchQueue.main.async {
        // now update UI with the results of the above
    }
}

注意，我没有使用任何 async concurrentPerform 内调用，因为它完成了外部 for 的所有并行化为我们循环。无论如何，在这种模式下，我有效地进行了 10,000 次异步调用(而不是 50m 次)。和concurrentPerform确保在执行此操作时不会发生线程爆炸。

但坦率地说，即使是 10,000 次迭代也太多了。每个线程没有足够的工作，每个线程的开销会增加。事实上，并行化例程的好处将被所有这些开销所抵消。

典型的解决方案是“跨越”计算。例如，对于 10,000 次迭代，对于 i 的 50 个值，一个人可能会跨越，进行 200 次迭代。每个，或类似的东西。例如:

let stride = 50
DispatchQueue.concurrentPerform(iterations: 200) { iteration in
    let startIndex = iteration * stride
    let endIndex = min(9_999, startIndex + stride)
    for i in startIndex ..< endIndex {
        for j in i+1 ..< strings.count {
            ...
        }
    }
}

因此，之前从 50m async 下降调用 concurrentPerform 的 10k 次迭代，我们现在只有 200 次迭代。这足以实现巨大的并行性能提升，但开销可以忽略不计。

您的代码不是线程安全的。您正在更新 min和 couples从多个线程。是的，您正在使用屏障，但每个循环都有自己的队列，并且屏障仅针对当前队列，而不是跨队列。你有一个数据竞赛。您必须同步对这些变量的访问。

因为同步存在相关开销，我可能建议您更进一步，弄清楚如何最小化所需的同步。例如，每个分派(dispatch)的 block 可能会计算自己的本地最小距离值，然后在 block 的末尾，您才应该检查本地最小距离与主最小距离。

这些是帮助您最大化并行计算性能的一些技巧。在我的 MacBookPro 上，上面的计算结果比非并行渲染快 9.9 倍。