Faster cumsum & cumprod. Fixes #7342.

[timholy]

Should we export cumsum! and cumprod!?

Note if you include the copy operation that would have been needed in #7342 (comment), this implementation is actually a little faster because it only needs to make one pass through the data rather than two.

[JeffBezanson]

That was fast! 👏 🍸

[lindahua]

@timholy You probably want a special path for cases where dim = 1.

[lindahua]

I agree with exporting cumsum! and cumprod!.

[ViralBShah]

Yes, we should probably export cumsum! and cumprod!.

[JeffBezanson]

I'm never in favor of the ! functions, but we certainly have tons of them already so if you insist, I guess why not.

[ViralBShah]

If only the code without ! was magically as fast...

[JeffBezanson]

Well, this PR makes cumsum 10x faster. The ! does not add much on top of that. Exporting so many of these will make it harder to get rid of them in the future.

[timholy]

Right, once we have a faster gc the ! will only make a difference for small arrays. With our current gc, when testing in a loop even for size 5000x800, gc accounts for ~30% of the time!

EDIT: Of course, the bigger benefit in principle arises with SharedArrays or mmapped arrays---the ! form provides a natural mechanism to exploit parallelism or do things that might otherwise exhaust your memory. Though currently we lack a good framework for automatically generating SharedArray variants of functions.

[timholy]

You probably want a special path for cases where dim = 1

True enough. Not as important as for reductions, because you still have to access each element again to store the result, but it does save one array-access per element. See if this is better (~20% additional speedup for dim = 1).

[lindahua]

I understand that we don't want too many !-functions. However, cumsum is the kind of functions that the inplace version is often needed.

[lindahua]

@timholy I am happy with the latest commit. This fix comes amazingly fast!

[ViralBShah]

@JeffBezanson I don't think that exporting matters. Even if something is not exported, but is widely used, it is just as difficult to take it away. I am hoping we will get things to be fast enough so that we can at least unexport the ! functions by 1.0.

[ViralBShah]

Also, in a perverse way, now that this is 10x faster, it is all the more important to have the ! version. Before, cumsum! would have only been 5% faster and not worthwhile, but now it is much faster than cumsum.

[tkelman]

I'm confused, what's the motivation behind not liking the in-place versions of functions? Unless there are plans afoot to somehow make them unnecessary for performance, in which case I don't understand how that would be possible. A standardized mechanism for doing things in-place by default and automating the copying definitions would be good, of course.

[jakebolewski]

Well if you switch to array view semantics instead of copy be default then the in place method performance difference will likely be less dramatic. It is still nice to have an escape hatch if you don't want the overhead of creating even a lightweight view object.

[lindahua]

@jakebolewski I am afraid that I don't see how the array views are relevant to the discussions here.

Even with array views, you still need inplace functions to avoid creating temporary arrays.

[StefanKarpinski]

I definitely think they should be exported – these are quite useful.

On Jun 21, 2014, at 6:47 PM, Dahua Lin notifications@github.com wrote:

I agree with exporting cumsum! and cumprod!.

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

[GunnarFarneback]

I'm biased by Matlab to prefer a default of 1 but don't have a strong feeling about it for the multidimensional case. For the vector case, however, having to explicitly specify dim 1 is just annoying.

[timholy]

Yes, you're right about handling vectors. To me that's by far the strongest argument in favor of defaulting to 1 for all arrays.