为什么多处理会降低嵌套for循环的速度？

Question

我有很多非常大的矩阵AFeatures，我正在与其他一些非常大的矩阵BFeatures进行比较，它们的形状都是(878, 2, 4, 15, 17, 512)，使用欧几里德距离。我试图将这个过程并行化，以加速比较。 我在Conda环境中使用Python3，我的原始代码在100%的速度下平均使用两个CPU核：

    per_slice_comparisons = np.zeros(shape=(878, 878, 2, 4))
    
    for i in range(878):
        for j in range(878):
            for k in range(2):
                for l in range(4):
                    per_slice_comparisons[i, j, k, l] = np.linalg.norm(AFeatures[i, k, l, :] - BFeatures[j, k, l, :])

我尝试了两种加速代码的方法

1. 使用多重处理

   def fill_array(i):
       comparisons = np.zeros(shape=(878, 2, 4))
   
       for j in range(878):
           for k in range(2):
               for l in range(4):
                   comparisons[j, k, l] = np.linalg.norm(AFeatures[i, k, l, :] -BFeatures[j, k, l, :])
            comparisons[j, k, l] = 0
   
            return comparisons
   
   pool = Pool(processes=6)
   list_start_vals = range(878)
   per_slice_comparisons = np.array(pool.map(fill_array, list_start_vals))
   pool.close()
   

这种方法将运行时间增加了5%左右，尽管所有8个CPU内核现在都以100%的速度使用。我已经尝试了许多不同的过程，越多，速度就越慢

1. 这是一种稍微不同的方法，我使用numexpr库来执行更快的linal.norm操作。对于单个操作，此方法将运行时间减少10倍

    os.environ['NUMEXPR_MAX_THREADS'] = '8'
    os.environ['NUMEXPR_NUM_THREADS'] = '4'
    import numexpr as ne
   
    def linalg_norm(a):
        sq_norm = ne.evaluate('sum(a**2)')
        return ne.evaluate('sqrt(sq_norm)')
   
    per_slice_comparisons = np.zeros(shape=(878, 878, 2, 4))
        for i in range(878):
            for j in range(878):
                for k in range(2):
                    for l in range(4):
                        per_slice_comparisons[i, j, k, l] = linalg_norm(AFeatures[i, k, l, :] - BFeatures[j, k, l, :])
   

但是，对于嵌套for循环，这种方法将总执行时间增加了3倍。我不明白为什么简单地将这个操作放在嵌套的for循环中会显著降低性能？如果有人对如何解决这个问题有任何想法，我将非常感激

Answer 1

我只是简单介绍一下这个问题。我发现，在计算不同的高维向量之间的欧几里德距离时，我确实在Anaconda中使用numpy获得了最好的结果。在此基础上使用多处理并没有取得任何显著的改进

但是，我后来通过一个代码示例（https://github.com/QVPR/Patch-NetVLAD）找到了最近的Faiss库。Faiss（https://anaconda.org/pytorch/faiss-gpu）是一个用于聚类和计算不同向量之间距离的库，可用于计算余弦和欧氏距离。简单地说，使用这个库可以实现的速度是巨大的，远远超过了比较大量高维矩阵的速度的100倍。对于我的研究来说，它完全改变了游戏规则，我强烈推荐它，尤其是在比较大型神经网络描述器时

Answer 2

Why does multi-processing slow down a nested for loop in python?

创建进程是一项非常昂贵的系统操作。操作系统必须重新映射大量页面（程序、共享库、数据等），以便新创建的进程可以访问初始进程的页面。多处理包还使用进程间通信，以便在进程之间共享工作。这也很慢。更不用说所需的最终联接操作了。为了提高效率（即尽可能减少开销），使用多处理包的Python程序应该共享少量数据并执行昂贵的计算。 在您的情况下，您不需要多处理软件包，因为您只使用Numpy数组（请参阅下文）

This is a slightly different approach where I use the numexpr library to do a faster linal.norm operation. For a single operation this approach reduces runtime by a factor of 10.

Numexpr使用线程，而进程和线程比进程轻（即更便宜）。Numexpr还使用积极优化尽可能加快计算表达式的速度（CPython没有做到这一点）

I don't understand why simply putting this operation in a nested for loop would decrease performance so dramatically?

Python的默认实现是CPython，它是一个解释器。口译员通常非常慢（尤其是CPython）。CPython几乎不执行代码优化。如果您想要快速循环，那么您需要将它们编译为本机代码或JIT的替代方法。您可以使用Cython或Numba进行此操作。这两种方法可以提供简单的并行化程序的方法。在您的案例中，使用Numba可能是最简单的解决方案。您可以从查找example programs开始

---

更新：如果Numpy的实现是多线程can，那么多处理代码可能会慢得多。实际上，每个进程将在一台有N个内核的机器上创建N个线程。因此，将运行N*N个线程。这种情况称为过度订阅，已知效率低下（由于抢占式多任务处理，尤其是上下文切换）。检查这一假设的一种方法是简单地查看创建了多少线程（例如，在Posix系统上使用hwloc工具），或者简单地监视处理器的使用情况