PERF: GH10213 kth_smallest GIL release
State: closed

One tiny part of #10213 

```
import timeit

setup_seq = '''
import pandas
import numpy
numpy.random.seed(1234)
x = numpy.random.randn(10000000)
a = x.copy()
b = x.copy()

def f(s):
    pandas.algos.kth_smallest(s, 500000)

def seq():
    f(a)
    f(b)
'''

setup_parallel = '''
import pandas
import numpy
import threading
numpy.random.seed(1234)
x = numpy.random.randn(10000000)
a = x.copy()
b = x.copy()

def f(s):
    pandas.algos.kth_smallest(s, 500000)

def parallel():
    thread1 = threading.Thread(target=f, args=(a,))
    thread2 = threading.Thread(target=f, args=(b,))
    thread1.start()
    thread2.start()
    thread1.join()
    thread2.join()
'''

print(min(timeit.repeat(stmt='seq()', setup=setup_seq, repeat=100, number=1)))
print(min(timeit.repeat(stmt='parallel()', setup=setup_parallel, repeat=100, number=1)))
```

On master

```
0.15268295999976544
0.15424678300041705
```

On branch

```
0.1544521670002723
0.08813380599985976
```

Testing of `nsmallest`/`nlargest`/`median` (I don't think `median` calls `kth_smallest` though)

```
import pandas, numpy
from pandas.util.testing import test_parallel
n = 1000000
k = 50000
numpy.random.seed(1234)
s = pandas.Series(numpy.random.randn(n))

def f():
    s.nlargest(k)

def seq():
    f()
    f()

@test_parallel(num_threads=2)
def g():
    f()
```

Master `nsmallest`

```
In [2]: %timeit f()
10 loops, best of 3: 42.4 ms per loop

In [3]: %timeit g()
10 loops, best of 3: 79.9 ms per loop

In [4]: %timeit seq()
10 loops, best of 3: 84.9 ms per loop
```

Branch `nsmallest`

```
In [10]: %timeit f()
10 loops, best of 3: 42.8 ms per loop

In [11]: %timeit g()
10 loops, best of 3: 68.6 ms per loop

In [12]: %timeit seq()
10 loops, best of 3: 91.2 ms per loop
```

Master `nlargest`

```
In [2]: %timeit f()
10 loops, best of 3: 47.5 ms per loop

In [3]: %timeit g()
10 loops, best of 3: 86 ms per loop

In [4]: %timeit seq()
```

Branch `nlargest`

```
In [10]: %timeit f()
10 loops, best of 3: 48.1 ms per loop

In [11]: %timeit g()
10 loops, best of 3: 71 ms per loop

In [12]: %timeit seq()
10 loops, best of 3: 95.7 ms per loop
```

Master `median`

```
In [2]: %timeit f()
100 loops, best of 3: 15.4 ms per loop

In [3]: %timeit g()
10 loops, best of 3: 20.7 ms per loop

In [4]: %timeit seq()
10 loops, best of 3: 30.7 ms per loop
```

Branch `median`

```
In [12]: %timeit f()
100 loops, best of 3: 15 ms per loop

In [13]: %timeit g()
10 loops, best of 3: 21.5 ms per loop

In [14]: %timeit seq()
10 loops, best of 3: 30 ms per loop
```

Results are pretty in line with expectations -- `nsmallest` does quite a bit more than `kth_smallest`, such as copying and indexing. 


Labels:
name: Performance
description: Memory or execution speed performance

Comments:
can you add a asv benchmark (note that #10928 ) changes this so will merge this after.

This _should_ affect `median`, `nlargest`, `nsmallest`. So those would be nice to test.

Further use the `test_parallel` decorator to show the perf changes.

You can also add this issue to the GIL release issues in the whatsnew.

OK, I will update after 10928.  I had looked at `test_parallel`, but wasn't sure how to make it work for this function. 

The function alters the state of the array, so I needed one set-up per iteration (hence `repeat=n` and `number=1`), but obviously didn't want that to be included in the timing.  In-place sorting and functions that drop stuff should have the same problem, so maybe there's machinery to deal with this that I don't know about.  Plus `test_parallel` has a function level import, which I thought might skew the timing for this one. 

I will check what asv has. 

@kawochen can you update

Will do.  I haven't been able to get the `asv` benchmarks to match the improvement I saw, even when I add class attributes like `number` and `repeat`.  `asv` does use a different default timer, but it looked more like `number` and `repeat` are ignored.  I will update tonight.

Updated. `asv` has a million gotchas!

@kawochen ahh ok, when you have time can you expand the doc section on `asv` would be appreciated.thxs.

thanks!

asv `repeat` does not actually re-run setup each time, which probably should be considered a bug. (If you want to elaborate on the other million gotchas, that could also be useful)

@pv forgive my hyperbole! It's a great package :smile:   I looked at the code before and saw that repeat is passed into `timeit`, but you are saying it actually doesn't quite work?  Is there an open issue for this?  I'll be more constructive and translate some of what I think are gotchas into feature requests. 

Repeat is indeed passed to timeit, but the setup function is not run by timeit, but is done separately.
cf https://github.com/spacetelescope/asv/pull/316