Skip to content

BUG: Add size check for threaded array assignment - #24257

Merged
seberg merged 2 commits into
numpy:mainfrom
BrandonSmithJ:array-assign-shape-check
Sep 26, 2023
Merged

BUG: Add size check for threaded array assignment#24257
seberg merged 2 commits into
numpy:mainfrom
BrandonSmithJ:array-assign-shape-check

Conversation

@BrandonSmithJ

@BrandonSmithJ BrandonSmithJ commented Jul 25, 2023

Copy link
Copy Markdown
Contributor

Many small array assignments releasing the GIL can cause slowdowns, and in multithreaded environments, can cause significant thread contention.

Add a size check to array assignment such that only assignments that exceed a certain number of elements (512) will release the GIL.

Closes gh-24252.

@seberg

seberg commented Jul 25, 2023

Copy link
Copy Markdown
Member

I meant lets not set up benchmark with a threadpool. I think adding a benchmark with a huge number of small arrays or lists to concatenate would make sense. (I think we have concatenation benchmarks, so it may just be expanding those, or even checking that we do.)

I might think that integrating the size calculation into PyArray_PrepareTwoRawArrayIter could be nice, but not sure its worth it. This is also used in array_assign_scalar.c, if we change this, we should change the other one, too.

@BrandonSmithJ

BrandonSmithJ commented Aug 1, 2023 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

If I'm reading this right, array_assign_scalar.c actually already performs conditional threading based on a size threshold. I went ahead and just made array_assign_array.c symmetric with that implementation, and added another test class to bench_manipulate.py to specifically test concatenating / stacking a large number of small arrays.

Here's the relevant benchmark before/after:

Before size threshold 
[ 56.25%] ··· bench_manipulate.ConcatenateNestedArrays.time_concatenate_ax0                                                          ok
[ 56.25%] ··· ======== ========= ============ ============
               shape    narrays     ndtype
              -------- --------- ------------ ------------
               (1, 1)     1000      int16       274±5μs
               (1, 1)     1000     float16      273±7μs
               (1, 1)     1000      int32       269±5μs
               (1, 1)     1000     float32      271±3μs
               (1, 1)     1000      int64       275±4μs
               (1, 1)     1000     float64      276±5μs
               (1, 1)     1000    complex64     275±7μs
               (1, 1)     1000    longdouble    273±3μs
               (1, 1)     1000    complex128    269±2μs
               (1, 1)    100000     int16      32.2±0.5ms
               (1, 1)    100000    float16     32.2±0.6ms
               (1, 1)    100000     int32      32.6±0.6ms
               (1, 1)    100000    float32     32.9±0.4ms
               (1, 1)    100000     int64      32.2±0.3ms
               (1, 1)    100000    float64     32.4±0.2ms
               (1, 1)    100000   complex64    32.0±0.4ms
               (1, 1)    100000   longdouble    33.0±1ms
               (1, 1)    100000   complex128   33.3±0.7ms
              ======== ========= ============ ============

[ 62.50%] ··· bench_manipulate.ConcatenateNestedArrays.time_concatenate_ax1                                                          ok
[ 62.50%] ··· ======== ========= ============ ============
               shape    narrays     ndtype
              -------- --------- ------------ ------------
               (1, 1)     1000      int16       272±3μs
               (1, 1)     1000     float16      272±4μs
               (1, 1)     1000      int32       272±2μs
               (1, 1)     1000     float32      274±5μs
               (1, 1)     1000      int64       270±4μs
               (1, 1)     1000     float64      273±2μs
               (1, 1)     1000    complex64     272±3μs
               (1, 1)     1000    longdouble    275±4μs
               (1, 1)     1000    complex128    274±6μs
               (1, 1)    100000     int16      32.4±0.9ms
               (1, 1)    100000    float16     32.3±0.9ms
               (1, 1)    100000     int32      31.8±0.4ms
               (1, 1)    100000    float32     31.8±0.2ms
               (1, 1)    100000     int64      31.5±0.3ms
               (1, 1)    100000    float64     31.8±0.5ms
               (1, 1)    100000   complex64    32.3±0.4ms
               (1, 1)    100000   longdouble   31.8±0.7ms
               (1, 1)    100000   complex128   32.4±0.2ms
              ======== ========= ============ ============

[ 68.75%] ··· bench_manipulate.ConcatenateNestedArrays.time_stack_ax0                                                                ok
[ 68.75%] ··· ======== ========= ============ ============
               shape    narrays     ndtype
              -------- --------- ------------ ------------
               (1, 1)     1000      int16       570±7μs
               (1, 1)     1000     float16      588±10μs
               (1, 1)     1000      int32       576±7μs
               (1, 1)     1000     float32      578±6μs
               (1, 1)     1000      int64       570±9μs
               (1, 1)     1000     float64      578±9μs
               (1, 1)     1000    complex64     570±5μs
               (1, 1)     1000    longdouble    574±8μs
               (1, 1)     1000    complex128    566±6μs
               (1, 1)    100000     int16       75.2±1ms
               (1, 1)    100000    float16     74.8±0.8ms
               (1, 1)    100000     int32       75.8±2ms
               (1, 1)    100000    float32     75.9±0.5ms
               (1, 1)    100000     int64      74.6±0.8ms
               (1, 1)    100000    float64     74.8±0.8ms
               (1, 1)    100000   complex64    73.9±0.9ms
               (1, 1)    100000   longdouble   74.6±0.8ms
               (1, 1)    100000   complex128   75.3±0.9ms
              ======== ========= ============ ============

[ 75.00%] ··· bench_manipulate.ConcatenateNestedArrays.time_stack_ax1                                                                ok
[ 75.00%] ··· ======== ========= ============ ============
               shape    narrays     ndtype
              -------- --------- ------------ ------------
               (1, 1)     1000      int16       590±6μs
               (1, 1)     1000     float16      586±9μs
               (1, 1)     1000      int32       587±6μs
               (1, 1)     1000     float32      585±4μs
               (1, 1)     1000      int64       590±7μs
               (1, 1)     1000     float64      620±70μs
               (1, 1)     1000    complex64     597±2μs
               (1, 1)     1000    longdouble    589±10μs
               (1, 1)     1000    complex128    599±10μs
               (1, 1)    100000     int16      76.4±0.8ms
               (1, 1)    100000    float16     77.3±0.6ms
               (1, 1)    100000     int32      76.1±0.6ms
               (1, 1)    100000    float32      76.4±2ms
               (1, 1)    100000     int64       77.3±1ms
               (1, 1)    100000    float64     77.0±0.7ms
               (1, 1)    100000   complex64     76.0±1ms
               (1, 1)    100000   longdouble    77.2±1ms
               (1, 1)    100000   complex128    77.0±1ms
              ======== ========= ============ ============
After size threshold 
[ 56.25%] ··· bench_manipulate.ConcatenateNestedArrays.time_concatenate_ax0                                                          ok
[ 56.25%] ··· ======== ========= ============ ============
               shape    narrays     ndtype
              -------- --------- ------------ ------------
               (1, 1)     1000      int16       176±3μs
               (1, 1)     1000     float16      173±2μs
               (1, 1)     1000      int32       174±2μs
               (1, 1)     1000     float32      177±2μs
               (1, 1)     1000      int64       175±2μs
               (1, 1)     1000     float64      177±3μs
               (1, 1)     1000    complex64     172±3μs
               (1, 1)     1000    longdouble    183±8μs
               (1, 1)     1000    complex128    173±3μs
               (1, 1)    100000     int16      22.4±0.4ms
               (1, 1)    100000    float16     22.9±0.3ms
               (1, 1)    100000     int32      22.9±0.3ms
               (1, 1)    100000    float32     22.4±0.6ms
               (1, 1)    100000     int64      22.6±0.2ms
               (1, 1)    100000    float64     22.7±0.4ms
               (1, 1)    100000   complex64    22.0±0.6ms
               (1, 1)    100000   longdouble   22.4±0.4ms
               (1, 1)    100000   complex128   22.7±0.4ms
              ======== ========= ============ ============

[ 62.50%] ··· bench_manipulate.ConcatenateNestedArrays.time_concatenate_ax1                                                          ok
[ 62.50%] ··· ======== ========= ============ ============
               shape    narrays     ndtype
              -------- --------- ------------ ------------
               (1, 1)     1000      int16       169±3μs
               (1, 1)     1000     float16      169±2μs
               (1, 1)     1000      int32       169±2μs
               (1, 1)     1000     float32      172±4μs
               (1, 1)     1000      int64       169±2μs
               (1, 1)     1000     float64      170±2μs
               (1, 1)     1000    complex64     175±4μs
               (1, 1)     1000    longdouble    170±1μs
               (1, 1)     1000    complex128    175±5μs
               (1, 1)    100000     int16      21.9±0.5ms
               (1, 1)    100000    float16     21.7±0.4ms
               (1, 1)    100000     int32      22.2±0.5ms
               (1, 1)    100000    float32      22.0±1ms
               (1, 1)    100000     int64      22.0±0.6ms
               (1, 1)    100000    float64     22.2±0.5ms
               (1, 1)    100000   complex64    21.9±0.1ms
               (1, 1)    100000   longdouble   22.5±0.6ms
               (1, 1)    100000   complex128   22.6±0.7ms
              ======== ========= ============ ============

[ 68.75%] ··· bench_manipulate.ConcatenateNestedArrays.time_stack_ax0                                                                ok
[ 68.75%] ··· ======== ========= ============ ============
               shape    narrays     ndtype
              -------- --------- ------------ ------------
               (1, 1)     1000      int16       473±4μs
               (1, 1)     1000     float16      475±9μs
               (1, 1)     1000      int32       491±10μs
               (1, 1)     1000     float32      477±20μs
               (1, 1)     1000      int64       478±8μs
               (1, 1)     1000     float64      476±8μs
               (1, 1)     1000    complex64     467±8μs
               (1, 1)     1000    longdouble    478±8μs
               (1, 1)     1000    complex128    484±10μs
               (1, 1)    100000     int16      66.1±0.5ms
               (1, 1)    100000    float16     65.8±0.9ms
               (1, 1)    100000     int32      65.4±0.5ms
               (1, 1)    100000    float32     66.9±0.3ms
               (1, 1)    100000     int64      64.9±0.2ms
               (1, 1)    100000    float64      65.9±1ms
               (1, 1)    100000   complex64    64.3±0.9ms
               (1, 1)    100000   longdouble   65.3±0.7ms
               (1, 1)    100000   complex128    65.8±3ms
              ======== ========= ============ ============

[ 75.00%] ··· bench_manipulate.ConcatenateNestedArrays.time_stack_ax1                                                                ok
[ 75.00%] ··· ======== ========= ============ ============
               shape    narrays     ndtype
              -------- --------- ------------ ------------
               (1, 1)     1000      int16       494±10μs
               (1, 1)     1000     float16      489±5μs
               (1, 1)     1000      int32       490±8μs
               (1, 1)     1000     float32      493±7μs
               (1, 1)     1000      int64       491±10μs
               (1, 1)     1000     float64      489±8μs
               (1, 1)     1000    complex64     495±5μs
               (1, 1)     1000    longdouble    494±6μs
               (1, 1)     1000    complex128    494±10μs
               (1, 1)    100000     int16      66.9±0.7ms
               (1, 1)    100000    float16     66.3±0.5ms
               (1, 1)    100000     int32      66.7±0.8ms
               (1, 1)    100000    float32      67.1±1ms
               (1, 1)    100000     int64      66.1±0.2ms
               (1, 1)    100000    float64     66.2±0.5ms
               (1, 1)    100000   complex64    67.4±0.9ms
               (1, 1)    100000   longdouble   66.9±0.7ms
               (1, 1)    100000   complex128   67.1±0.7ms
              ======== ========= ============ ============

In summary, ~50% runtime reduction for concatenate with a large number of small arrays.

@BrandonSmithJ
BrandonSmithJ force-pushed the array-assign-shape-check branch from aec24a9 to c859917 Compare August 1, 2023 18:19
@seberg

seberg commented Aug 11, 2023

Copy link
Copy Markdown
Member

Close/reopen to rerun tests since so many failed when it was made. Probably a bit more benchmarks than necessary, but LGTM.

@seberg seberg closed this Aug 11, 2023
@seberg seberg reopened this Aug 11, 2023
@BrandonSmithJ BrandonSmithJ reopened this Sep 26, 2023
@BrandonSmithJ

BrandonSmithJ commented Sep 26, 2023

Copy link
Copy Markdown
Contributor Author

@seberg As far as I can tell, these errors aren't related to the pull request. Is there anything I need to do in order to get this wrapped up?

@seberg

seberg commented Sep 26, 2023

Copy link
Copy Markdown
Member

No, it would probably need a rebase to fix them up. I am OK with this, I had half hoped to calculate the size outside, but it seems worthwhile either way.

One interesting angle (if you are interested!); Reading the Cython mailing list, I saw that at least with Python 3.11+ (maybe 3.10) GIL locking/unlocking seems vastly faster and there might actually be a point to lower the threshold, but that probably shouldn't stop this.

So putting it in thanks, the biggest holdup was me being on vacation (and similar).

@seberg
seberg merged commit a412097 into numpy:main Sep 26, 2023
@BrandonSmithJ

BrandonSmithJ commented Sep 26, 2023

Copy link
Copy Markdown
Contributor Author

If I had the time, I'd love to optimize some more. Unfortunately my work is more application-driven at the moment, so it's only when I come across a specific issue like this that I can justify spending some time on it. Either way, contributing certainly helped with my familiarity of the process - so it should at least be easier for me to contribute in the future. Thanks for all the help throughout!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

00 - Bug

Projects

NumPy first-time contributor PRs
Status: Completed

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

BUG: Multiple threads introduce significant delays in numpy concatenate

2 participants

@BrandonSmithJ @seberg