BUG: Multiple threads introduce significant delays in numpy concatenate

[BrandonSmithJ]

Describe the issue:

The observation is that using np.concatenate with multiple threads uses more CPU, more than 4x peak memory, and takes ~5x longer than using an explicit for loop to concatenate:

from concurrent.futures import ThreadPoolExecutor
import numpy as np
import time, psutil

N_ELE = 5e5


def concat1(x):
    return np.concatenate(x, dtype=np.int64)

def concat2(x):
    total = np.r_[0, np.cumsum(list(map(len, x)))]
    y = np.empty(total[-1], dtype=np.int64)
    for i, n in enumerate(x):
        y[total[i]:total[i+1]] = n
    return y 

def mwe(concat, nest_type=list):
    a = [nest_type([1,1])] + [nest_type([1])]*int(N_ELE)
    return concat( np.array(a, dtype=object) )

def multithread(f, concat, workers, jobs=6):
    label = f'{concat.__name__} using {workers} workers'
    with ThreadPoolExecutor(max_workers=workers) as pool:
        proc = psutil.Process()
        start = time.time()
        psutil.cpu_percent()
        list(pool.map(f, [concat] * jobs))
        print(f'{label} finished in {time.time()-start:.1f} seconds')
        print(f'CPU usage: {psutil.cpu_percent()}%')
        print(f'Mem usage: {proc.memory_info().peak_wset/1e6:,.1f} MB\n')

# Function combinations generate the same result
assert((mwe(concat1) == mwe(concat2)).all())

# 1 worker vs 6 workers
multithread(mwe, concat2, 1)
multithread(mwe, concat1, 1)
print()

multithread(mwe, concat2, 6)
multithread(mwe, concat1, 6)
print()

Output:

concat2 using 1 workers finished in 1.8 seconds
CPU usage: 13.3%
Mem usage: 119.6 MB

concat1 using 1 workers finished in 1.9 seconds
CPU usage: 13.9%
Mem usage: 140.2 MB


concat2 using 6 workers finished in 1.8 seconds
CPU usage: 13.4%
Mem usage: 140.2 MB

concat1 using 6 workers finished in 9.9 seconds
CPU usage: 24.6%
Mem usage: 560.1 MB

I've tried to minimize the comparisons here, but one other observation is that by using list as the nest_type I observe the above. If I use np.array however (which produces a nested object array of arrays rather than lists), I find that the problem exists for both concat1 and concat2 - implying there's something happening with the array representation specifically that's causing an issue, and not necessarily with concatenate.

Runtime information:

System:
    python: 3.10.12 | packaged by Anaconda, Inc. | (main, Jul  5 2023, 19:09:20) [MSC v.1916 64 bit (AMD64)]
executable: env_crest\python.exe
   machine: Windows-10-10.0.19045-SP0

Python dependencies:
      sklearn: 1.2.1
          pip: 23.1.2
   setuptools: 67.8.0
        numpy: 1.24.3
        scipy: 1.10.1
       Cython: None
       pandas: 1.5.3
   matplotlib: 3.7.1
       joblib: 1.2.0
threadpoolctl: 2.2.0

Built with OpenMP: True

threadpoolctl info:
       filepath: env_crest\Library\bin\mkl_rt.2.dll
         prefix: mkl_rt
       user_api: blas
   internal_api: mkl
        version: 2023.1-Product
    num_threads: 6
threading_layer: intel

       filepath: env_crest\vcomp140.dll
         prefix: vcomp
       user_api: openmp
   internal_api: openmp
        version: None
    num_threads: 12

Context for the issue:

Maybe tangentially related to this issue.

[seberg]

arr1d[slice] = 1_d_list side-steps full array creation. That isn't the reason though, the reason is that that path never releases the GIL (I guess if arrays are embedded it will), while the other always releases it, which isn't ideal in this case.

That can be changed, its just that raw_array_assign_array does release the GIL. In many places we only do that if there above a certain threshold (typically 512), here, that isn't the case.

[seberg]

In other words: The "fast" path isn't threaded at all, which is why it is fast (releasing the GIL takes time) and uses much more memory: clearly you need more memory if you do more things at once.

[BrandonSmithJ]

Okay, I think I understand. So to sum up:

• arr[slice] = 1d_array is slow above because it releases the GIL many times in the for loop
• arr[slice] = 1d_list is fast because it never releases the GIL, so the concat is essentially forcing single-threaded

Then, np.concatenate is slow in both cases because it does release the GIL regardless of it being 1d_array or 1d_list, but...also releases it independently for each item in the parent array? For example, running concatenate with nest_type=list results in:

concat1 using 6 workers finished in 9.6 seconds
CPU usage: 24.0%
MEM usage: 559.1MB

And running concatenate with nest_type=np.array results in:

concat1 using 6 workers finished in 8.4 seconds
CPU usage: 25.8%
MEM usage: 125.5MB

Which means the memory usage is now on par with the single-threaded version, but still takes 4x as long to run. The memory and slight time difference I assume is because it converts each list object into a new array before insertion, but I'm not exactly clear where the additional extra time comes from over the single-threaded version.

[seberg]

also releases it independently for each item in the parent array

Yes, also within concatenate it is the individual arr[slice] = other_array that releases the GIL. This is the change that would avoid it:

diff --git a/numpy/core/src/multiarray/array_assign_array.c b/numpy/core/src/multiarray/array_assign_array.c
index 7aee7d6e9..99699ea13 100644
--- a/numpy/core/src/multiarray/array_assign_array.c
+++ b/numpy/core/src/multiarray/array_assign_array.c
@@ -132,7 +132,8 @@ raw_array_assign_array(int ndim, npy_intp const *shape,
     if (!(flags & NPY_METH_NO_FLOATINGPOINT_ERRORS)) {
         npy_clear_floatstatus_barrier((char*)&src_data);
     }
-    if (!(flags & NPY_METH_REQUIRES_PYAPI)) {
+    if (!(flags & NPY_METH_REQUIRES_PYAPI)
+            && PyArray_MultiplyList(shape_it, ndim) > 512) {
         NPY_BEGIN_THREADS;
     }

Might be nice to refactor a bit to calculate the shape elsewhere. Won't complain about a PR, especially if it includes a test (no point for multi-threading).
I probably have removed such a change at least once from a PR because it wasn't quite related ;).

[BrandonSmithJ]

While I would genuinely like to contribute back to a project that has given me a lot of benefit over the years, I don't have a whole lot of time to do so at the moment. Still, I've opened a pull request with the change you suggested (which does indeed fix the issue), and I can potentially add a brief test to it.

With regard to the test though, I'm not exactly sure what you mean by "no point for multi-threading". I'm happy to add a cleaner version of the reproducer above as a test, but I'm not sure that's what you had in mind - and my C is a bit too rusty at the moment for me to be confident dropping down to that level to write a test.

In any case, for anyone that comes across this issue later on that needs a high-level fix for whatever reason, here's what I'm currently using to recover performance in a multithreaded setting for both list and array nested types:

def concat3(x):
    return np.fromiter((y[i] for y in x for i in range(len(y))), dtype=np.int64)

concat3 using 1 workers finished in 1.0 seconds
CPU usage: 18.2%
Mem usage: 119.4 MB

concat3 using 6 workers finished in 1.0 seconds
CPU usage: 16.6%
Mem usage: 119.4 MB