Faster random.shuffle via static typing. by anntzer · Pull Request #6776 · numpy/numpy

anntzer · 2015-12-06T04:51:35Z

This patch modifies random.shuffle so that (when working on a ndarray) an array
of indices is shuffled and then elements are take()n from that array in that
order. This allows the inner loop to be statically typed (it turns out this
is not so easy to write a generic shuffling code using Cython fused types) and
thus much faster (~6x for me), at the expense of a threefold increase in memory
use (I guess take() needs to create a copy, and an additional array of indices
is created.).

See #5514.

njsmith · 2015-12-06T05:37:16Z

To reduce the overhead in common cases, you could write a single loop for
64-bit integers, and then at the top level either call this directly (if
the input is int64), view-cast and then call this (if the input is e.g.
float64), or else allocate an index array and shuffle it.
On Dec 5, 2015 8:51 PM, "Antony Lee" [email protected] wrote:

This patch modifies random.shuffle so that (when working on a ndarray) an
array
of indices is shuffled and then elements are take()n from that array in
that
order. This allows the inner loop to be statically typed (it turns out this
is not so easy to write a generic shuffling code using Cython fused types)
and
thus much faster (~6x for me), at the expense of a threefold increase in
memory
use (I guess take() needs to create a copy, and an additional array of
indices
is created.).

See #5514 #5514.

You can view, comment on, or merge this pull request online at:

#6776
Commit Summary

Faster random.shuffle via static typing.

File Changes

M numpy/random/mtrand/mtrand.pyx
https://github.com/numpy/numpy/pull/6776/files#diff-0 (31)

Patch Links:

https://github.com/numpy/numpy/pull/6776.patch

https://github.com/numpy/numpy/pull/6776.diff

—
Reply to this email directly or view it on GitHub
#6776.

anntzer · 2015-12-06T06:02:05Z

Indeed, this shaves off another 10% or so to the runtime (in the case where itemsize is the same as intp.itemsize).

Side question: currently, building numpy (via setup.py or runtests.py) fails (even after git clean -xf) with

Building, see build.log...
Running from numpy source directory.
Traceback (most recent call last):
  File "setup.py", line 263, in <module>
    setup_package()
  File "setup.py", line 247, in setup_package
    from numpy.distutils.core import setup
  File "/home/antony/src/numpy/numpy/distutils/__init__.py", line 21, in <module>
    from numpy.testing import Tester
  File "/home/antony/src/numpy/numpy/testing/__init__.py", line 12, in <module>
    from . import decorators as dec
  File "/home/antony/src/numpy/numpy/testing/decorators.py", line 21, in <module>
    from .utils import SkipTest
  File "/home/antony/src/numpy/numpy/testing/utils.py", line 18, in <module>
    from numpy.core import float32, empty, arange, array_repr, ndarray
  File "/home/antony/src/numpy/numpy/core/__init__.py", line 58, in <module>
    from numpy.testing import Tester
ImportError: cannot import name 'Tester'

Build failed!

which I can locally solve by first importing numpy.core in setup.py (to break the circular dependency), but is that a known issue?

seberg · 2015-12-06T06:43:18Z

I doubt np.take does not work in-place or checks this. Which means the result can be corrupted by memory layout. I think you have to create a copy unfortunately.
Depends a bit on the shape, but unless your array is (N, m) with m being quite small, indexing is probably faster, but does not matter much.

If mode is the default 'raise', it always allocates an intermediate buffer, so that if an error in the indexing is detected, and an error has to be raised, the output array is left unchanged. If you set it to 'clip' or 'wrap' then yes, you would start seeing all kind of funny things if you tried to do the operation in place.

Ah ok, then take is nicer in that regard. Hopefully we have cipy on overlap at some point in indexing....

On Sun Dec 6 09:54:39 2015 GMT+0100, Jaime wrote:

with self.lock:

while i > 0:

j = rk_interval(i, self.internal_state)

buf[...] = x[j]

x[j] = x[i]

x[i] = buf

i = i - 1

if isinstance(x, np.ndarray):

if x.ndim == 1 and x.dtype.itemsize == np.dtype(np.intp).itemsize:

# Directly shuffle the array if possible.

self._shuffle_intpsized(x.view(np.intp))

else:

# Take from a shuffled range to benefit from static typing.

idxs = np.arange(n, dtype=np.intp)

self._shuffle_intpsized(idxs)

x.take(idxs, 0, out=x)

If mode is the default 'raise', it always allocates an intermediate buffer, so that if an error in the indexing is detected, and an error has to be raised, the output array is left unchanged. If you set it to 'clip' or 'wrap' then yes, you would start seeing all kind of funny things if you tried to do the operation in place.

Reply to this email directly or view it on GitHub:
https://github.com/numpy/numpy/pull/6776/files#r4676812

anntzer · 2015-12-09T17:22:44Z

There's a test failure on 2.6, due to MaskedArrays not supporting the buffer protocol there. To be honest I don't really understand how the buffer protocol works on maskedarrays (how exactly is the mask information propagated?), moreover buffer(MaskedArray(...)) works fine on 2.6. I'll probably make the code conditional on the version of Python, given that 2.6 is expected to be dropped in a few versions.
Thoughts?

njsmith · 2015-12-09T17:41:11Z

Does cython know how to compile this down to a C for loop?

Yes (and I much prefer this to range(n-1, 0, -1) which I always find slightly confusing).

njsmith · 2015-12-09T17:42:05Z

Actually I suspect that your implementation is broken for masked arrays in
all versions, because cython doesn't know about masks and will shuffle the
data array but not the masks. It would be good to add a test at a minimum.
On Dec 9, 2015 9:22 AM, "Antony Lee" [email protected] wrote:

There's a test failure on 2.6, due to MaskedArrays not supporting the
buffer protocol there. To be honest I don't really understand how the
buffer protocol works on maskedarrays (how exactly is the mask information
propagated?), moreover buffer(MaskedArray(...)) works fine on 2.6. I'll
probably make the code conditional on the version of Python, given that 2.6
is expected to be dropped in a few versions.
Thoughts?

—
Reply to this email directly or view it on GitHub
#6776 (comment).

anntzer · 2015-12-09T18:38:01Z

Indeed, the current test suite does not cover this case. In fact the current implementation messes up the underlying array (i.e masking, shuffling and unmasking reveals that masked values have been overwritten by unmasked values), which should probably be considered a bug too.

Both issues are fixed by the new patch (which simply shuffle masked arrays by indexing with a shuffled index array).

njsmith · 2015-12-10T00:54:08Z

I guess to be safer we might as well make it type(x) is np.ndarray to disallow all subclasses (since there's no guarantee that MaskedArray is the only weird subclass)

njsmith · 2015-12-10T00:56:02Z

I think that as written this code should be safe WRT not changing the random stream. But can you make sure that we have tests for that, that cover all the different branches, and add them if they're missing?

njsmith · 2015-12-10T01:05:59Z

Aside from the minor nits above, the one thing I'm wary of is the memory overhead in the take path -- it's the sort of thing where we might well get users complaining that we totally broke their processing pipeline because they were shuffling some 10 gigabyte array and now... :-/.

One idea: would it be easy to use fused types to at least generate u8, u16, u32, u64 versions of _shuffle_intps, and use the view trick for other types that have exactly those sizes? then pretty much all the simple easy fast cases would be really fast, and we could stick to the old low-memory-overhead code for multidimensional and structured arrays.

anntzer · 2015-12-10T08:50:22Z

This latest commit should handle all the issues you mentioned. I added tests for various sizes of items.

ghost · 2015-12-10T22:02:14Z

There should also be some special handling of object arrays, because these can't be viewed as int. You could branch on dtype.hasobject, but structured arrays with object members still pose a problem. These are bugged even in the current release:

np.random.shuffle(np.ones(3, 'i4, O'))
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-38-67e839c634c1> in <module>()
----> 1 np.random.shuffle(np.ones(3, 'i4, O'))
mtrand.pyx in mtrand.RandomState.shuffle (numpy\random\mtrand\mtrand.c:30002)()
mtrand.pyx in mtrand.RandomState.shuffle (numpy\random\mtrand\mtrand.c:29939)()
ValueError: Setting void-array with object members using buffer.

anntzer · 2015-12-11T00:03:51Z

FWIW, I realized that you can bypass the checks in view by using np.frombuffer instead. A scary(ish) side note is that this opens a segfault possibility:

np.frombuffer(np.array(None), np.int64)[0] = 1

This handles the object array case but not the struct-with-object-fields case, which is arguably a bug in ndarray.__setitem__ (and isn't a regression anyways):

In [23]: a = np.ones(3, 'i4, O')

In [24]: a[0] = a[1]
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-24-5ef5a6077ce6> in <module>()
----> 1 a[0] = a[1]

ValueError: Setting void-array with object members using buffer.

homu · 2016-01-03T22:32:05Z

☔ The latest upstream changes (presumably #6910) made this pull request unmergeable. Please resolve the merge conflicts.

This patch modifies random.shuffle so that (when working on a ndarray) an array of indices is shuffled and then elements are take()n from that array in that order. This allows the inner loop to be statically typed (it turns out this is not so easy to write a generic shuffling code using Cython fused types) and thus much faster (~6x for me), at the expense of a threefold increase in memory use (I guess take() needs to create a copy, and an additional array of indices is created.). See numpy#5514.

This avoids the memory overhead of allocating an index array and take()ing from the original array when possible.

Also ensure that the masked data is preserved upon shuffling, which was not the case before.

Do not rely on take(), which for non-standard sized arrays, thus ensuing the previous memory performance at the expense of speed. Also get rid of the guarantee that shuffling masked arrays maintains the masked values as well, which should probably be handled on np.ma's side anyways.

anntzer · 2016-01-04T01:35:46Z

Superseded by #6933.

Only for 1d-ndarrays exactly, as subtypes (e.g. masked arrays) may not allow direct shuffle of the underlying buffer (in fact, the old implementation destroyed the underlying values of masked arrays while shuffling). Also handles struct-containing-object 1d ndarrays properly. See numpy#6776 for an earlier, less general (but even faster: ~6x) improvement attempt, numpy#5514 for the original issue.

Apparently gcc only specializes one branch (the last one) so I went for another 33% performance increase (matching numpy#6776) in what's likely the most common use case.

Only for 1d-ndarrays exactly, as subtypes (e.g. masked arrays) may not allow direct shuffle of the underlying buffer (in fact, the old implementation destroyed the underlying values of masked arrays while shuffling). Also handles struct-containing-object 1d ndarrays properly. See numpy#6776 for an earlier, less general (but even faster: ~6x) improvement attempt, numpy#5514 for the original issue.

Apparently gcc only specializes one branch (the last one) so I went for another 33% performance increase (matching numpy#6776) in what's likely the most common use case.

anntzer mentioned this pull request Dec 6, 2015

np.random.choice without replacement or weights is less efficient than random.sample? #2764

Closed

anntzer force-pushed the fastshuffle branch from 86f808c to 92698a1 Compare December 6, 2015 05:08

seberg reviewed Dec 6, 2015
View reviewed changes

charris added 01 - Enhancement component: numpy.random labels Dec 6, 2015

njsmith reviewed Dec 9, 2015
View reviewed changes

njsmith reviewed Dec 10, 2015
View reviewed changes

This was referenced Dec 11, 2015

setting entry in struct array with object field #6806

Closed

frombuffer segfault #6811

Open

anntzer force-pushed the fastshuffle branch from ef611e9 to 1c4cc5d Compare January 3, 2016 23:35

anntzer added 4 commits January 3, 2016 15:38

Specialize shuffling for intp-sized 1d arrays.

2d9ff3c

This avoids the memory overhead of allocating an index array and take()ing from the original array when possible.

Fix shuffling of masked arrays.

a535de8

Also ensure that the masked data is preserved upon shuffling, which was not the case before.

anntzer mentioned this pull request Jan 4, 2016

memcpy-based fast, typed shuffle. #6933

Merged

charris closed this Jan 4, 2016

anntzer mentioned this pull request Jun 10, 2016

RandomState.shuffle has a terrible overhead for NumPy arrays #5514

Closed

anntzer deleted the fastshuffle branch January 23, 2017 02:13

Uh oh!

Uh oh!

Conversation

anntzer commented Dec 6, 2015

Uh oh!

njsmith commented Dec 6, 2015

See #5514 #5514.

Uh oh!

anntzer commented Dec 6, 2015

Uh oh!

seberg Dec 6, 2015

Choose a reason for hiding this comment

Uh oh!

jaimefrio Dec 6, 2015

Choose a reason for hiding this comment

Uh oh!

seberg Dec 6, 2015

Choose a reason for hiding this comment

Uh oh!

anntzer commented Dec 9, 2015

Uh oh!

njsmith Dec 9, 2015

Choose a reason for hiding this comment

Uh oh!

anntzer Dec 9, 2015

Choose a reason for hiding this comment

Uh oh!

njsmith commented Dec 9, 2015

Uh oh!

anntzer commented Dec 9, 2015

Uh oh!

njsmith Dec 10, 2015

Choose a reason for hiding this comment

Uh oh!

njsmith commented Dec 10, 2015

Uh oh!

njsmith commented Dec 10, 2015

Uh oh!

anntzer commented Dec 10, 2015

Uh oh!

ghost commented Dec 10, 2015

Uh oh!

anntzer commented Dec 11, 2015

Uh oh!

homu commented Jan 3, 2016

Uh oh!

anntzer commented Jan 4, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants