ENH: avoid allocations in getmaskarray by eric-wieser · Pull Request #8910 · numpy/numpy

eric-wieser · 2017-04-07T13:43:36Z

Public API still has to return a full array, but we can avoid a lot of copying and memory by returning np.broadcast_to(np.zeros((), dtype), shape) instead of np.zeros(dtype, shape) when arr.mask is nomask.

This seems to add 2us overhead for small arrays, and starts to break even at around 10000 elements

Most of the time here is lost to the ndarray constructor, when really all we want to do is modify ->strides and ->shape without checking

eric-wieser · 2017-04-07T13:46:11Z

+
+        # duplicate it using zero strides
+        # like np.lib.stride_tricks.as_strided, but faster
+        return np.ndarray(


This is faster than np.lib.stride_tricks.as_strided and np.broadcast_to, surprisingly.

It's still pretty darn slow though, when all we really want to do is directly write to the shape and stride attributes.

Could np.zeros acquire a readonly kwarg, to do this C-side?

not using keyword arguments for ndarray() should be significantly faster.

You're right, it is. Using buff = b'\0' instead of np.ma.nomask is also faster.

With both optimizations in place, this breaks even at shape (2000,).

For small n, this line by itself is worse by a factor of 2 (600ns)

For n = 100000, this is better by a factor of 8.

np.zeros(..., bool) really is alarmingly fast

want to update the PR?

juliantaylor · 2017-04-09T14:41:01Z

interesting idea, readonly one element arrays from ones/zeros/full
not too sure about how useful it really is, though if it is easy to do it might be worth a shot

concerning this, the boolean bitwise functions do currently not have scalar specializations so this could actually harm performance. But that can be fixed.

eric-wieser · 2017-04-09T14:52:34Z

concerning this, the boolean bitwise functions do currently not have scalar specializations

Not sure I understand how this is relevant - how do ufuncs behave on zero strides? Do they not still iterate over the full array? "readonly one element arrays" isn't quite the right description - they're multi-element backed by a single element's-worth of buffer

There's a more interesting idea here which would be to maintain 0 strides, so that an addition like:

array(shape=(10,1), strides=(0,0)) + array(shape=(1,10), strides=(10,1))

would result in array(shape=(10,10), strides=(0,1)). So basically, if you can keep sharing memory for elements, do so.

This could be implemented as an extra flag field on the arrays, ALLOW_STRIDE_COLLAPSING or something - this would have to be opt-in, as it would break code that tries to assign to the result

juliantaylor · 2017-04-09T15:15:44Z

bitwise_and/or use SSE2 code for contiguous arrays but not if one of the operands is a scalar.
So array & array is actually faster than array & scalar.
There wasn't really a compelling reason to add it as the operation does not make a lot of sense to explicitly write.
But if our masked arrays end up creating these scalar mask arrays more often its probably worth the extra code, its basically just using memset/memcpy.

the arrays still would be readonly so generalizing it to ufuncs doesn't sound that useful.

eric-wieser · 2017-04-09T15:20:17Z

bitwise_and/or use SSE2 code for contiguous arrays but not if one of the operands is a scalar.

This is what is confusing me. Why are you talking about one of the operands being a scalar? As far as I can tell, this patch does not introduce this. Feel like I'm missing something here

juliantaylor · 2017-04-09T15:23:49Z

In the ufunc loops a scalar is just a memory block with stride zero, like the arrays you are creating here.

what actually happens if you do return a scalar in _viewmaskarray?

eric-wieser · 2017-04-09T15:29:39Z

In the ufunc loops a scalar is just a memory block with stride zero

Can you point me to the bit of code that special cases zero strides then?

what actually happens if you do return a scalar in _viewmaskarray?

I'm assuming you mean an array with .shape ()? It doesn't produce masks of the "right" shape when broadcasting. Ie:

in0.data.shape = (10, 1)
in0.mask.shape = ()
in1.data.shape = (1, 10)
in1.mask.shape = (1, 10)

out = f(in0, in1)

out.data.shape = (10, 10)
out.data.shape = (1, 10)  #oops

Of course, this comes down to what "right" is defined as, but this would definitely be incompatible with the current behaviour, and it becomes harder to implement __index__ when the shapes don't match.

juliantaylor · 2017-04-09T15:55:50Z

it are just the loops in loops.c.src
see https://github.com/juliantaylor/numpy/tree/scalar-bool for an example how it could be done

eric-wieser · 2017-04-09T16:10:14Z

Oh right, I see what you're getting at now - scalars are promoted to arrays with strides = (0,0,...) by the ufunc machinery, so doing that promotion by hand beforehand is equivalent.

That looks like a pretty straightforward patch, and probably would offer some performance improvement.

Although we could do even better if the ufunc was allowed to do scalar & array -> scalar for things like 0 & arr or 1 | arr.

Also, could this be taken further to work for any case of ufunc(ufunc.identity, x)?

Regarding my remark about collapsing strides - I was envisaging something like this:

in0 = view(in0)
in1 = view(in1)

old_shape = out.shape

if in0.strides[i] == in1.strides[i] == 0:
   # don't bother iterating over this dimension, as we know it aliases to a single memory location
    in0.shape[i] = 1
    in1.shape[i] = 1
    out.shape[i] = 1
    out.strides[i] = 0

doit(in0, in1, out)

out.shape = old_shape  # re-broadcast over the dimensions we skipped/

juliantaylor · 2017-04-10T12:00:54Z

do you have a benchmark for this?

eric-wieser · 2017-04-10T12:05:17Z

@juliantaylor: Not one that shows an improvement. I suspect there would be one with your patch included though.

Do you want me to add one anyway?

The actual goal here was to make calling _viewmaskedarray cheap enough that it can be called inside __getitem__, because then it can be used to determine whether the return value should be a scalar

* Avoid named arguments to ndarray * Avoid getting a buffer from bool_ when we can construct that buffer directly

eric-wieser · 2017-04-11T12:32:14Z

Ok, updated with some micro-optimizations.

make_mask_none((N,), readonly=True) and make_mask_none((N,), readonly=False) have equal timings at N = 750. Obviously dropping the kwarg with a default value in the second case speeds things up a little

However, the timings become absolutely terrible when you do boolean operations on the readonly arrays, as you pointed out

mhvk

Overall, I quite like it. Especially if you follow my suggestion of making _viewmaskarray the routine that does the actual work, I would go ahead and replace getmaskarray with _viewmaskarray in other places where this is the logical choice.

mhvk · 2017-04-11T16:55:25Z

        If None, use a MaskType instance. Otherwise, use a new datatype with
        the same fields as `dtype`, converted to boolean types.
+    readonly : bool
+        If True, return a read-only array that uses less memory.


Maybe try to be a bit more explicit about what is actually done. E.g., "return a readonly array scalar that is broadcasted over the shape and thus uses less memory"

As noted above, I'd suggest calling this writable (which here should default to True for backward compatibility)

mhvk · 2017-04-11T17:03:54Z



-def getmaskarray(arr):
+def getmaskarray(arr, nomask_as_readonly=False):


My own sense would be not to add an argument here, which is used by _viewmaskarray, but rather have this call _viewmaskarray with a new argument; that way the rest of the code is not slowed down by another function call.

I'd also suggest to make the argument writable=True, ie., it states what kind of view is required.

Flipping the call stack around sounds sensible. Do you still think there should be an argument here to expose the behaviour publicly?

I'd also suggest to make the argument writable=True

I went for readonly because that's consistent with np.lib.stride_tricks._broadcast_to, but I guess you're right, making the name match the flags makes more sense.

Done in make_mask_none.

The real meaning in this function though is require_to_be_writeable, which I thought was better spelt allow_readonly.

allow_readonly definitely describes the intent, so 👍 on that.

mhvk · 2017-04-11T17:05:05Z

+            readonly=nomask_as_readonly)
    return mask

+def _viewmaskarray(arr):


So, in my view this would become

def _viewmaskarray(arr, writable=False): mask = getmask(arr) if mask is nomask: make_mask_none(np.shape(arr), dtype=getattr(arr, 'dtype', None), writable=writable)

The problem I have with that is that _viewmaskarray(arr, writable=False).writable == False does not always hold, which might be a little surprising.

I had actually not thought so much about the flags, but more that writable=True indicated the array had to be writable. Maybe we can be even more direct and make it broadcast_if_possible=True?

That seems to expose unnecessary implementation details. The important thing is whether the consumer is ok with mask.writeable == False. Everything else is just an optimization.

eric-wieser · 2017-04-11T17:44:08Z

I would go ahead and replace getmaskarray with _viewmaskarray in other places where this is the logical choice.

I thought I already did this in my second commit. Did I miss some obvious ones?

mhvk · 2017-04-11T19:42:34Z

I thought I already did this in my second commit. Did I miss some obvious ones?

It is just that if one reverses the order _viewmaskarray becomes faster, so it might as well be used whenever you only need to read the mask. But no big deal.

eric-wieser · 2017-04-11T20:27:27Z

I was already under the impression that I replaced every internal use with _viewmaskarray where I was sure a readonly array was sufficient.

It is just that if one reverses the order _viewmaskarray becomes faster

I doubt this is actually true right now - there's more overhead due to a lack of #8924 right now than there is due to one level of function call overhead. Also, there's a little too much overhead in calling the ndarray ctor, it seems.

eric-wieser · 2017-04-11T23:59:24Z

Arguments against a writeable kwarg - we are bad at spelling it!

it seems there is no agreed upon way to write this ._.

You could say it's not particular... writeable.

In numpy we should write it writeable, because arr.flags.writeable is part of the public API.

The internal function should have the shallower callstack, for speed.

juliantaylor · 2017-04-12T10:57:49Z

        Input `MaskedArray` for which the mask is required.
+    allow_readonly : bool, optional
+        If True, allow this function to produce a readonly array when doing so
+        would increase performance. The default is False.


this and the one in make_mask_none need a .. versionadded:: tag

mhvk · 2017-04-12T20:14:50Z

I was already under the impression that I replaced every internal use with _viewmaskarray where I was sure a readonly array was sufficient.

I clearly looked at an earlier version... Anyway, still found one. I changed this branch directly, but feel free to just make this part of your single commit.

eric-wieser · 2017-04-12T20:23:33Z

        out = out.view(MaskedArray)
        out._mask = np.array([tuple(flatten_sequence(d.item()))
-                              for d in getmaskarray(a)])
+                              for d in _viewmaskarray(a)])


Yeah, I saw this and thought the whole function looked broken, so didn't touch it. But I was wrong, this is fine

eric-wieser · 2017-04-17T16:21:06Z

Marked with "Needs work" since I do not think this should be merged while it causes a performance hit.

homu · 2017-06-09T18:27:10Z

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

eric-wieser added 2 commits April 7, 2017 14:20

ENH: allow expanding nomask without memory allocation

5db1131

ENH: Don't use getmaskarray internally to avoid copies

76cad4f

eric-wieser added component: numpy.ma masked arrays 01 - Enhancement labels Apr 7, 2017

eric-wieser changed the title ~~ENH: avoiding copies in getmaskarray to avoid allocations~~ ENH: avoid allocations in getmaskarray Apr 7, 2017

eric-wieser commented Apr 7, 2017

View reviewed changes

MAINT: Improve performance

99d68c8

* Avoid named arguments to ndarray * Avoid getting a buffer from bool_ when we can construct that buffer directly

juliantaylor mentioned this pull request Apr 11, 2017

ENH: add scalar special cases for boolean logical loops #8924

Closed

mhvk reviewed Apr 11, 2017

View reviewed changes

eric-wieser mentioned this pull request Apr 11, 2017

BENCH: Masked array benchmarks #8929

Merged

eric-wieser force-pushed the faster-getmaskarray branch from 0e0fba1 to acbc218 Compare April 11, 2017 23:55

eric-wieser commented Apr 11, 2017

View reviewed changes

MAINT: Rename parameters, and flip callstack

d0d4ed5

The internal function should have the shallower callstack, for speed.

eric-wieser force-pushed the faster-getmaskarray branch from acbc218 to d0d4ed5 Compare April 12, 2017 00:15

juliantaylor reviewed Apr 12, 2017

View reviewed changes

MAINT: one more getmaskarray that can be replaced.

341b984

eric-wieser commented Apr 13, 2017

View reviewed changes

eric-wieser added the 55 - Needs work label Apr 17, 2017

Base automatically changed from master to main March 4, 2021 02:03

charris added the 52 - Inactive Pending author response label Apr 6, 2022

charris closed this Apr 6, 2022



		def getmaskarray(arr):
		def getmaskarray(arr, nomask_as_readonly=False):

Uh oh!

Conversation

eric-wieser commented Apr 7, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

juliantaylor Apr 10, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

eric-wieser Apr 10, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

juliantaylor commented Apr 9, 2017

Uh oh!

eric-wieser commented Apr 9, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

juliantaylor commented Apr 9, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

eric-wieser commented Apr 9, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

juliantaylor commented Apr 9, 2017

Uh oh!

eric-wieser commented Apr 9, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

juliantaylor commented Apr 9, 2017

Uh oh!

eric-wieser commented Apr 9, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

juliantaylor commented Apr 10, 2017

Uh oh!

eric-wieser commented Apr 10, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

eric-wieser commented Apr 11, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mhvk left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

eric-wieser Apr 11, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

eric-wieser commented Apr 11, 2017

Uh oh!

mhvk commented Apr 11, 2017

Uh oh!

eric-wieser commented Apr 11, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

juliantaylor Apr 10, 2017 •

edited

Loading

eric-wieser Apr 10, 2017 •

edited

Loading

eric-wieser commented Apr 9, 2017 •

edited

Loading

juliantaylor commented Apr 9, 2017 •

edited

Loading

eric-wieser commented Apr 9, 2017 •

edited

Loading

eric-wieser commented Apr 9, 2017 •

edited

Loading

eric-wieser commented Apr 9, 2017 •

edited

Loading

eric-wieser commented Apr 10, 2017 •

edited

Loading

eric-wieser commented Apr 11, 2017 •

edited

Loading

eric-wieser Apr 11, 2017 •

edited

Loading

eric-wieser commented Apr 11, 2017 •

edited

Loading