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

Question

我有很多非常大的矩阵 AFeatures，我正在与其他一些非常大的矩阵 BFeatures 进行比较，两者的形状都是 (878, 2, 4, 15, 17, 512)，使用欧几里得距离。我正在尝试并行化此过程以加快比较速度。我在 Conda 环境中使用 Python 3，我的原始代码在 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, :])

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

使用多处理

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% 使用。我尝试了很多不同的进程，进程越多越慢。

这是一种略有不同的方法，我使用 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

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

创建进程是一项非常昂贵的系统操作。操作系统必须重新映射很多页面（程序、共享库、数据等），以便新创建的进程可以访问初始进程的页面。 multiprocessing 包还使用进程间通信来共享进程之间的工作。这也很慢。更不用说所需的最终连接操作了。为了高效（即尽可能减少开销），使用多处理包的 Python 程序应该共享少量数据并执行昂贵的计算。在你的例子中，你不需要 multiprocessing 包，因为你只使用 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 使用 threads 而不是进程，线程与进程相比更轻（即更便宜）。 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的实现是多线程的，那么多处理代码会慢很多。事实上，每个进程都会在一台有 N 个内核的机器上创建 N 个线程。因此 N*N 线程将是运行。这种情况称为 over-subscription 并且已知效率低下（由于抢占式多任务处理，尤其是上下文切换）。检查这个假设的一种方法是简单地查看创建了多少线程（例如，在 Posix 系统上使用 hwloc 工具）或简单地监视处理器使用情况。

Answer 2

关于这个问题，我只是快速更新一下。我发现在计算不同的高维向量之间的欧氏距离时，我确实在 Anaconda 中使用 numpy 获得了最佳结果。在此之上使用多处理并没有取得任何显着的改进。

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

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

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

python

performance

numpy

multiprocessing

numexpr