OpenMP Groupby any/all
State: closed

Seems to give a small boost with our current test suite, though this could depend on the shape of the input data:

```sh
       before           after         ratio
     [824fc830]       [f7d33366]
     <main>           <parallel-shift>
-      46.3±0.4μs       41.6±0.4μs     0.90  groupby.GroupByMethods.time_dtype_as_group('datetime', 'any', 'direct', 5)
-     1.26±0.01ms      1.13±0.01ms     0.89  groupby.GroupByMethods.time_dtype_as_field('object', 'any', 'transformation', 5)
-     1.21±0.05ms      1.07±0.02ms     0.89  groupby.GroupByMethods.time_dtype_as_field('int', 'any', 'transformation', 5)
```

For the openmp link arg meson should have a much better facility for auto-detecting that which we can leverage

Cython dev docs have been updated with more info on parallelization:

https://github.com/cython/cython/blob/master/docs/src/tutorial/parallelization.rst

Labels:

Comments:
I tried this recently ish with libalgos.nancorr and couldn’t get it working on Mac. Would be awesome if you can figure it out!
Assuming this link is true looks like the macOS bundled llvm just doesn't support llvm:

https://stackoverflow.com/a/60043467/621736

Meson should help us compared to setuptools - will rebase after that goes into main and see
@h-vetinari wondering if you have any experience with distributing openmp linked libraries via conda and pip. Not sure how the presence of this on the build system may affect downstream users
Not sure. It definitely is the easiest way for us to parallelize things via Cython (where applicable), but I can't claim to have experience with using it otherwise. 

The packaging seems like the riskiest piece. Maybe we have to turn it off for wheels but enable for conda environments where openmp can be ensured?

Are there other huge downsides anyone is aware of?
In general, you don't want to parallelize at multiple levels of your code. E.g. a workflow that uses up all cores via multiprocessing a workflow and then trying to use all cores within each process will suffer from context switches.

Another case is in a large shared server were you want to ensure you aren't over utilizing resources.
> @h-vetinari wondering if you have any experience with distributing openmp linked libraries via conda and pip. Not sure how the presence of this on the build system may affect downstream users

TL;DR: It works fine with conda, not fine with pip.

In more detail, conda-forge has all the required bits & pieces to make this work (and we [ship](https://github.com/conda-forge/openblas-feedstock/blob/main/recipe/meta.yaml#L27) openmp-support in openblas for example), though windows has the wrinkle that the `intel-openmp` and `llvm-openmp` implementations are different and cannot be co-installed. We've been wanting to switch to `llvm-openmp` also on windows (see e.g. [here](https://github.com/conda-forge/openblas-feedstock/pull/115), but that's been blocked on some Fortran infrastructure work that's still pending).

As a concrete example, scipy has [not allowed](https://github.com/scipy/scipy/issues/10239#issuecomment-795030817) a hard dependence on OpenMP for various reasons, primarily related to the limitations of PyPI's distribution model. @rgommers was & is heavily involved in this, and also did a [write-up](https://pypackaging-native.github.io/key-issues/native-dependencies/blas_openmp/) about this very subject in the context of the pypackaging-native initiative. From a (somewhat-)recently-added cross-reference on that scipy-issue, I see that a bunch of familiar faces already [discussed](https://github.com/Quansight-Labs/nasa-roses-2020/issues/27) this in the wider PyData context, including pandas.
FWIW numba seems to "select a threading layer if already available" instead of requiring one https://numba.pydata.org/numba-doc/latest/user/threading-layer.html#selecting-a-named-threading-layer

> you don't want to parallelize at multiple levels of your code

Yeah numba specifically detects and disallows this when jitting which might be hard to do on our side
> As a concrete example, scipy has [not allowed](https://github.com/scipy/scipy/issues/10239#issuecomment-795030817) a hard dependence on OpenMP for various reasons, primarily related to the limitations of PyPI's distribution model. @rgommers was & is heavily involved in this, and also did a [write-up](https://pypackaging-native.github.io/key-issues/native-dependencies/blas_openmp/) about this very subject in the context of the pypackaging-native initiative. From a (somewhat-)recently-added cross-reference on that scipy-issue, I see that a bunch of familiar faces already [discussed](https://github.com/Quansight-Labs/nasa-roses-2020/issues/27) this in the wider PyData context, including pandas.

Wow thanks these are great resources. But I think the last link might be private? I get a 404 trying to access
> But I think the last link might be private? I get a 404 trying to access

My bad, sorry, I'm not used to being a member of non-public GH orgs 😅

(i.e. when GH shows me an xref, I wrongly assume from habit that everyone else sees it too; in this case, the write-up I linked is more recent and more complete anyway) 
I am -1 on randomly adding parallelizable that is 

- not external controllable (via keyword and env variable)
- requires non standard things (openmp is standard but not generally available)
- defaults to anything hut False

this needs comprehensive policies otherwise you end up with multiple of layers of parallelism which is almost always bad

point is that this needs substantial testing and validation and tbh we may want to punt completely at the pandas level on this
I'm open to a "needs more thought" argument, but on a lot of fronts we've done a pretty good job with optimization so performance gains are going to _have_ to come from parallelism
Yea sounds like generally applying has some caveats. A conservative approach to start could be to add `-Duse-omp=ON` as a meson option, but set the default to false. That would give people building from source an easy way to opt in, if they don't plan on using pandas in a multiprocessing environment
+1 to @jreback's points. I'll note that @thomasjpfan put quite some thought into this topic and wrote up a design proposal for enabling parallelism across core PyData packages in a careful fashion: https://thomasjpfan.github.io/parallelism-python-libraries-design/ (also going to be a SciPy'23 talk I believe).
Awesome links thanks for sharing. So I see in the section: https://thomasjpfan.github.io/parallelism-python-libraries-design/#proposal-2

That there are three things being proposed:

  1. Detect combination of libgomp + fork call
  2. Detect when llvm openmp + intel openmp are loaded together
  3. Use openMP pypi wheel

2 seems feasible, 3 looks like the pre-cursor PR is merged, so I'm guessing just a matter of time (I see Intel OpenMP wheels already but likely not what the proposal refers to).

For number 1 I'm not sure if that would be possible for pandas to tackle, especially if we just rely on the Cython-generated OpenMP code. Guessing that is something we may want Cython to tackle?
Let's close this - I don't plan on taking any more immediate action. I think this is a good reference for any future discussion of the topic
Looking over the concerns from this PR, I can see the following path forward for pandas + OpenMP:

1. Let the default be **single threaded**.
2. Pass a keyword argument from the Python layer all the way down to `Cython`'s prange. This makes it harder to engage in nested parallelism in pandas code.
3. Have OpenMP be configurable with a compile time flag. This allows Pyodide to build with OpenMP off and conda to build with it on. As noted in https://github.com/pandas-dev/pandas/pull/53149#issuecomment-1541009510, conda has a better story around packaging OpenMP.
4. Be ready for issues. Even without nested parallelism, there will be performance issues when there are multiple threadpools. Pandas will need to have some documentation warning users about configuring threads >= 2.
5. If pandas wants OpenMP support in the near-term, be prepared to ship a PyPI wheel with an OpenMP binary.

### Alternative path forward

An alternative to OpenMP is to go with SciPy's solution, which developed their own [pthreads based solution](https://github.com/scipy/scipy/blob/762a349b62e59316617252c1d50371bab6fbee19/scipy/fft/_pocketfft/pocketfft_hdronly.h). It has the benefit of being a standard and avoids some of the issues with OpenMP.

@thomasjpfan can you comment on the pros/cons of the scipy solution, particularly for those of us with limited c++ experience
For reference, SciPy has discussed the topic of adding OpenMP and decided on pthreads: https://github.com/scipy/scipy/issues/10239 At a high level the pros and cons unique to SciPy's pthreads solution:

#### Pros
- Portable: pthreads is a POSIX standard
- None of the OpenMP headaches when libraries load different versions of OpenMP
- Easier to build. (No need to vendor OpenMP for wheels)

#### Cons
- As seen in SciPy's solution, pthreads needs a little more work to get going. OpenMP has higher level abstractions, which makes it easier to work with.
- Need to maintain a custom solution. (Although, if many libraries want to go down this route, we can wrap a C/C++ solution with a nice Cython frontend)
- Depending on how one implements the custom solution, you can still end up with CPU contention: https://github.com/xianyi/OpenBLAS/issues/4033