Feature request: Incremental bincount and axis argument

I have an application that requires to generate multiple histograms from a (25000,5000) array using bincount with 2^16 bins (16 bit values) each, e.g. the result would be a (65536,5000) array. The application first generates the initial histogram with apply_along_axis and then updates it up to 4000 times. Applying bincount along the axis is relatively fast, but adding the resulting (65536,5000) arrays is very slow.

My application would significantly improve, if bincount would be able to update a previous array returned by bincount, e.g. if it could run incremental and if it could be applied along an axis similar to the sum or mean functions instead of using apply_along_axis.

I think this is an interesting idea. Would having a non-overwritten out argument help here, as was proposed in #7998? See also the discussion in #8495. It does seem time something got implemented! If you have time...

Note that np.add.at(out, to_count, 1) already has the desired incremental behaviour, at the cost of efficiency.

Is there anything special about bincount that makes it more efficient than a hypothetical np.increment.at(out, inds) ufunc which has a trivial inner loop of *out = *in + 1?

Of course, that only solves the first half of the problem - I can't see an obviously sensible way to define an axis argument in at - once again, we end up wanting to support the #8708-style indexing

I think generally you actually want the weights, so np.increment may not be that much use. But, yes, bincount is much more efficient -- in part because it can avoid the problem that the normal iterator is not all that suited for at (if I recall correctly, it ends up calling the inner add loop with chunks of size 1).

I'm not sure I understand the original problem. You're doing something like

data = [np.zeros((25000, 5000)) for _ in range(4000)]
total_binned = np.zeros((65536, 5000))
for arr in data:
    binned = np.apply_along_axis(np.bincount, arr)
    total_binned += binned

? And the problem is that the total_binned += binned line is taking a really long time?

That seems odd to me. I'd expect the += to be within a factor of two of the bincount calls, because they're not touching that much more memory, and their access pattern is more regular.

Is this a good sketch of your problem? And if so, just how slow are these summations?

Yes, this is exactly my problem! I'm postprocessing the measurements from an oscilloscope which generates 25000 very similar power traces with 5000 sample points each. Overall, the distribution of an individual point is quite narrow and hence only a few of the 65536 bins are used. That means that the actual binned data is sparse, i.e. most bins are zero. I guessed, that the addition is taking much longer than the binning, because most of the time the addition after the binning is only adding zeros, while the binning itself is mostly accessing the same data. I can get some benchmarks later today, but if I recall correctly, the binning was less than 2 seconds, while the following addition took about 6 seconds on my system

@jungkb

Adding an axis= argument would be a pretty involved change. And I don't think we have yet agreed on what the meaning of it would be if either list or weights are broadcast to a new shape, e.g. what should this return:

np.bincount([0, 0, 0, 1, 1], weights=[[2.0], [3.0]], axis=0)

The arrays have shapes (5,) and (2, 1), so their broadcast shape is (2, 5):

list = [[0, 0, 0, 1, 1],  weights = [[2.0, 2.0, 2.0, 2.0, 2.0],
        [0, 0, 0, 1, 1]]             [3.0, 3.0, 3.0, 3.0, 3.0]]

Should axis= refer to the broadcast shape and return [4.0, 4.0, 6.0, 6.0, 6.0]? Or should it refer to an existing axis of the first input, and return [[6.0, 4.0], [9.0, 6.0]]?

Adding an out= argument is more straightforward, but it also has some challenging semantics:

What happens if both minlength= and out= are specified? I'm guessing an error is in order if minlength > len(out), but perhaps also if minlength != len(out)?
What happens if the input array has indices beyond the size of out=? Should they be silently discarded? Should the user be warned? Should an error be raised?
What happens if the out= array doesn't have the right type, i.e. np.intp or np.double, depending on whether weights are specified? I think the viable options without lots of complexity are to raise, or do a cast that may lose precision, so that e.g.:
```
>>> out = np.array([3.1, 1.2])
>>> np.bincount([0, 0, 0, 1, 1], out=out)
[6.0, 3.0]
```
or do the accumulation on a new array of the right type, then add the result to out, but that would negate the performance benefit for sparse histograms that you are after.

I would be in favor of a very restrictive approach that raises in all three cases, which would support your use case, but I'm not sure if it breaks other people's expectations.

So here's my offer, @jungkb, if you can bring the mailing list to an agreement over these points, I will implement an out= argument for you. Deal?

It would be great, and the restrictions would not break my expectations at least. But indeed good to pass by the mailing list.

From my point of view a conservative approach is best, because it protects users from unexpected behaviour, especially, if it is failing silently:

I would always raise an exception, if the shapes or value ranges are incompatible or if minlength and the out array shape do not match. Both actually feel to me to be very likely to be user errors.
I would also raise an exception, if the data types do not match.

I guess the main usage of such an out parameter is to repeatedly accumulate data of the dame shape and type and hence, I think the types and shapes should all match.

I don't have an opinion on the weights issue.

You would have to document very clearly that the out array needs to be zeroed out if you want it to be a clean result. Unlike other functions, what would be in the out array actually matters. Might even consider to not call it out.

I was thinking I'd be slightly less strict on the type of out - anything compatible with the type of weight should be OK - but then I noticed that weights are always cast to double -- so while I think it should be OK to have float32 for both weights and out, that would be for another time.

My thoughts, mostly echoing other comments upthread:

out implies overwriting semantics, which would defeat the utility here. I don't have a good suggestion on a different name, unfortunately.
If minlength is given, we should enforce minlength == len(out).
Any bins that don't fit in out should raise an exception.
We should check np.can_cast(weight.dtype, out.dtype, casting='safe'), rather than strict dtype equality.

PTAL at #9424. Testing, comments and reviews are very welcome!

#13166 would be fixed if bincount had an axis argument. Obviously its needed for the fast histogram route, and its going to be hard to add axis to histogram without first having it here.

Cross reference: #8495

Navigation Menu

Repository navigation

Feature request: Incremental bincount and axis argument #9397

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Feature request: Incremental bincount and axis argument #9397

Description

Activity

mhvk commented on Jul 10, 2017

eric-wieser commented on Jul 10, 2017

eric-wieser commented on Jul 10, 2017

mhvk commented on Jul 10, 2017

njsmith commented on Jul 11, 2017

jungkb commented on Jul 11, 2017

jaimefrio commented on Jul 13, 2017

mhvk commented on Jul 13, 2017

jungkb commented on Jul 13, 2017

seberg commented on Jul 13, 2017

mhvk commented on Jul 13, 2017

perimosocordiae commented on Jul 13, 2017

jaimefrio commented on Jul 14, 2017

GregoryMorse commented on Dec 2, 2019

WarrenWeckesser commented on Apr 27, 2020

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions