Views

[szeiger]

Let's use this ticket for discussions about views. Some comments were already made in #7:

• Should mutable views be removed entirely?
• How about special mutable views for mutable collections?

My own 2ct on the topic so far: I never cared for mutable views (too confusing) but I like the ideas of views as reified iterator operations, as currently implemented here. These could be useful in the context of both, mutable and immutable collections. I would like to propose to take them one step further and make the evaluation order of view operations unspecified. If views are used as a lightweight abstraction for composing complex transformations, you don't generally care about side effects, but you always care about performance (otherwise you'd transform the underlying collections in multiple steps). Views could be a place where we allow operations to be fused for better performance.

[julienrf]

For reference, here is an example given by @Ichoran on gitter about fusion:

Just did a quick test and

def jmap(i: Iterator[Int], f: Int => Int, g: Int => Int) = i.map(f andThen g)

takes only 60% as long to run as does

def imap(i: Iterator[Int], f: Int => Int, g: Int => Int) = i.map(f).map(g)

because boxing is a lot of the overhead, and functions are specialized.

[DarkDimius]

@julienrf, it's not only because of boxing, it's also because of reduction total memory footprint by 2x.
If you try functions on non-primitives(which eliminates difference with boxing), you'll still see a speedup.

[julienrf]

Still quoting @Ichoran:

If I use objects and just switch references around to which object I have, the jmap variant takes 75% as long as imap, so still a nice little win.
But using List instead of iterator slows things down by 5x, so you're right that avoiding intermediate collections can be the big win.

[Ichoran]

Mutable views are nice to have for a variety of divide-and-conquer in-place algorithms. For instance, an in-place sort is easier to express if you don't have to worry about indices.

I don't think that dropping the order of evaluation is particularly useful for either mutable or immutable views. That is a different useful thing, but "I want to act on part of my collection without rebuilding it" is a different desire than "I want to parallelize my operations on this collection".

If we were to support only one of the two, we at least shouldn't call it a "view" because right now (and in most other languages I've seen) "view" means the former.

[SethTisue]

Mutable views are nice to have for a variety of divide-and-conquer in-place algorithms. For instance, an in-place sort is easier to express if you don't have to worry about indices

I think this is a niche, 0.1% use case and we should drop it and not worry about it.

I don't think that dropping the order of evaluation is particularly useful for either mutable or immutable views. That is a different useful thing, but "I want to act on part of my collection without rebuilding it" is a different desire than "I want to parallelize my operations on this collection".

Not sure, but I think you might be misunderstanding Stefan's suggestion? It isn't about parallelization. He isn't suggesting leaving iteration order unspecified — allowing element 4 to be operated on before element 3, as can happen with parallel collections. Rather, he's suggesting to allow fusion. If you do .map(a).filter(b), it would be unspecified whether all the elements get mapped before any of them get filtered.

[szeiger]

Also note that evaluation order of views in the current strawman is already different from evaluation order of operations on the underlying collections. If you wanted the same evaluation order you would have to build intermediate results but the whole point of views is to avoid that. I am only suggesting that we do not guarantee the same evaluation order as that of Iterators, either.

[Ichoran]

Ah, yes, I did misunderstand. I agree that views should be maximally flexible in that regard; unlike iterators which should promise to be as lazy as possible, views can do whatever is "best" with regards to evaluation of sequential operations.

And I don't think evaluation order should be the same save on Seqs and SortedWhatevers where there is already a natural evaluation order.

But I think the "niche, 0.1% use case" evaluation is only because we're making it so by providing no support for this way of working. Views are a key aspect of, for instance, image processing operations in ImageJ; the conceptual equivalent of views with indexed ranges are used all over the place both in Java (e.g. java.util.Arrays.sort(xs, i0, iN)) and elsewhere (e.g. it's exceedingly common in Matlab).

One of the weaknesses of the current collections library is that it has relatively poor support for mutating operations. We needn't necessarily improve this greatly (people are used to it not being there), but it doesn't mean that the potential use cases are rare.

For instance, if one has a list of files and one wants to replace all the missing ones by default file names, you would normally do this with immutable collections:

xs.map(f => if (f.exists) f else default)

But although you could reassign everything in place mutably:

xs.mapInPlace(f => if (f.exists) f else default)

in some ways it's more natural to define a filtered view and fill it:

xs.viewWhere(! _.exists).fill(default)

Again, I'm not saying it's really important for us to provide this kind of functionality, but I don't think we should view this as for niche applications even if we have immutable alternatives as the standard now. (Except inasmuch as anything mutable is a niche application.)

[SethTisue]

I think the "niche, 0.1% use case" evaluation is only because we're making it so by providing no support for this way of working

It isn't so much that I'm opposed to including support for it, the only thing I'm strongly opposed to is letting this class of use cases be something that drives top-level design decisions. If it can be accommodated without distorting the hierarchy+API, great. (Can it?)

[Ichoran]

I think that mutable views would just be a completely different thing than immutable views, so I don't think they'd impact the hierarchy. We could call them something else also.

[odersky]

I would like to propose to take them one step further and make the evaluation order of view operations unspecified.

I don't think that's necessary. The specified evaluation order of views already demands fusing. An unspecified evaluation order could give you some extra facility, for instance if you want to batch some ops into segments before fusing. But I don't think views are the right place for that.

[EDIT] I might be convinced otherwise by benchmarks that show that there's a big win to be had by automatic batching.

I am also betting that we will have much better techniques to reason about effects in the future, which would let us optimize without compromising semantics.

[odersky]

Regarding mutable views, one question is what operations would produce a view? If we do not want to re-index (and I think we should not), then it seems the only sensical operations are to change the start, the end, or the stride. So, instead of views we could use a general notion of slices. E.g., on mutable (indexed?) Seq[A]:

def slice(r: Range): Slice[A]

val xs: Array[Int] = ...
xs.slice(3 until xs.length)
xs.slice(5 to 1 by -2)

Normal, strict slices are collection transformers and would not be available on mutable collections. There's no danger of silently changing semantics because the new non-strict slice
takes a range as argument instead of two bounds.

WDYT?

[odersky]

I just noted that there is a source of confusion for arrays.

xs.slice(1, 3)   

creates a new, strict array, or at least it did so far. But xs.slice(1 until 3) creates a view. Not sure what to do about that one yet - deprecate old-style slice on Array maybe?

[julienrf]

@odersky Maybe we should suffix operations producing a view with “view” (e.g. xs.sliceView(1 to 5)), to make it clearer that further operations will be fused.

[odersky]

@julienrf I agree sliceView would be clearer but it would also be longer and harder to remember. Also, it should not be ...View since a slice is not a view, but supports different operations. Maybe some other name? But I am not sure which.