Add append_outer_iter

[kolstae]

We use sprs for large sparse matrices with dims > 250,000,000. Currently the options to build a matrix requires realizing a CsVecI or a dense vector, which is inefficient.

Adding append_outer_iter helps with this without adding much code. Makes e.g. filtering out a component from a large matrix much simpler and efficient.

[jlogan03]

Thanks for the writeup! I'm traveling for a couple of days, but I'll take a look and run some quick bench comparisons later in the week, if Magnus doesn't get to it first.

Looks good from a quick skim - I just want to check that the additional branch point inside the loop (which I agree is necessary since the provided iterator isn't guaranteed to be sorted) doesn't scare away any optimizations. Given that there is already a branch point in the loop, it's unlikely that there would be any change.

[kolstae]

Looks good from a quick skim - I just want to check that the additional branch point inside the loop (which I agree is necessary since the provided iterator isn't guaranteed to be sorted) doesn't scare away any optimizations. Given that there is already a branch point in the loop, it's unlikely that there would be any change.

Could we make a trait signaling and/or verifying it's already ordered? This could be implemented as a noop for Enumerated.

[mulimoen]

Could you add calls to reserve where applicable? size_hint should sometimes give this information

[kolstae]

How about this approach? Move the validation of order into an explicit struct.

The AssertOrderedIterator should probably be moved somewhere else, but stuck it there for convenience for now.

[mulimoen]

@kolstae I added a commit directly, does the unsafe keyword pose any difficulties for you?

[kolstae]

@kolstae I added a commit directly, does the unsafe keyword pose any difficulties for you?

No, not at all. unsafe's a better way so make things clear.

[mulimoen]

Thanks for adding this @kolstae!

[mulimoen]

A new version of sprs (0.11.1) is released containing this PR