transforming one's views on mixin composition

It would be nice in some cases to not have to extend, to only use with.
Jon

On Wed, Mar 9, 2011 at 1:11 PM, Paul Phillips <paulp@improving.org> wrote:

Another in the category of "man, that took me a while to figure out."
Here is the bug:

 https://lampsvn.epfl.ch/trac/scala/ticket/4279
 "Sliced view foreach is incredibly slow for indexed sequences because it defaults to TraversableViewLike"

So the question ended up being, why is a view created from an IndexedSeq using the foreach defined in TraversableViewLike$#Sliced, which ought to be waaaay back in the inheritance chain? The answer, in diff form, is:

-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {
-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {
-  trait Sliced extends Transformed[A] with super.Sliced
+  trait Sliced extends super.Sliced with Transformed[A]
-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {

Before reversing the order of the parents, view was 5000 to 150,000 times slower than calling slice directly.  (The iterator/view numbers are multiples of the base nanoseconds.)

Runner(1000000, 10) base: 48000.  Iterator: 0.7917.  View: 4994.4583.
Runner(10000000, 10) base: 46000.  Iterator: 0.8478.  View: 52212.3696.
Runner(1000000, 50) base: 88000.  Iterator: 1.6818.  View: 14692.2500.
Runner(10000000, 50) base: 80000.  Iterator: 1.7125.  View: 150877.0750.

Afterward it's the same, plus or minus.

Runner(1000000, 10) base: 55000.  Iterator: 0.7455.  View: 0.6364.
Runner(10000000, 10) base: 51000.  Iterator: 0.8039.  View: 0.6863.
Runner(1000000, 50) base: 94000.  Iterator: 1.5213.  View: 1.2128.
Runner(10000000, 50) base: 89000.  Iterator: 1.6067.  View: 1.1573.

The reason is that correct collections behavior depends on Iterable* overriding Traversable* so that foreach uses iterator.  But when the Sliced subtraits do it like

 trait Sliced extends Transformed[A] with super.Sliced

they manage to reverse the overrides: super.Sliced is last in the linearization and its foreach wins.

Since all the view traits inherit their parents in this order except those in the parallel collections, I think most everything involving views is actually using the implementations in Traversable rather than the implementations designed for what they're viewing over.

This might explain why views are vexingly slow.  Great catch.  I'm going to re-run my performance tests against this new change.
- Josh

On Wed, Mar 9, 2011 at 1:11 PM, Paul Phillips <paulp@improving.org> wrote:

Another in the category of "man, that took me a while to figure out."
Here is the bug:

 https://lampsvn.epfl.ch/trac/scala/ticket/4279
 "Sliced view foreach is incredibly slow for indexed sequences because it defaults to TraversableViewLike"

So the question ended up being, why is a view created from an IndexedSeq using the foreach defined in TraversableViewLike$#Sliced, which ought to be waaaay back in the inheritance chain? The answer, in diff form, is:

-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {
-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {
-  trait Sliced extends Transformed[A] with super.Sliced
+  trait Sliced extends super.Sliced with Transformed[A]
-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {

Before reversing the order of the parents, view was 5000 to 150,000 times slower than calling slice directly.  (The iterator/view numbers are multiples of the base nanoseconds.)

Runner(1000000, 10) base: 48000.  Iterator: 0.7917.  View: 4994.4583.
Runner(10000000, 10) base: 46000.  Iterator: 0.8478.  View: 52212.3696.
Runner(1000000, 50) base: 88000.  Iterator: 1.6818.  View: 14692.2500.
Runner(10000000, 50) base: 80000.  Iterator: 1.7125.  View: 150877.0750.

Afterward it's the same, plus or minus.

Runner(1000000, 10) base: 55000.  Iterator: 0.7455.  View: 0.6364.
Runner(10000000, 10) base: 51000.  Iterator: 0.8039.  View: 0.6863.
Runner(1000000, 50) base: 94000.  Iterator: 1.5213.  View: 1.2128.
Runner(10000000, 50) base: 89000.  Iterator: 1.6067.  View: 1.1573.

The reason is that correct collections behavior depends on Iterable* overriding Traversable* so that foreach uses iterator.  But when the Sliced subtraits do it like

 trait Sliced extends Transformed[A] with super.Sliced

they manage to reverse the overrides: super.Sliced is last in the linearization and its foreach wins.

Since all the view traits inherit their parents in this order except those in the parallel collections, I think most everything involving views is actually using the implementations in Traversable rather than the implementations designed for what they're viewing over.

On 3/9/11 7:27 PM, Josh Suereth wrote:
> This might explain why views are vexingly slow. Great catch. I'm going
> to re-run my performance tests against this new change.

Be aware there is an unrelated and large performance regression in slice
which I introduced yesterday or so which will make for useless
results. I'm fixing it all up now.

Is there a case for a compiler warning when linearization causes a concrete method to be inherited in reverse order compared to the ordering of the class/traits with each other? If I understood the issue....the warning would aid in identifying such an issue like this in the future.
Thanks,Jon

On Wed, Mar 9, 2011 at 1:11 PM, Paul Phillips <paulp@improving.org> wrote:

Another in the category of "man, that took me a while to figure out."
Here is the bug:

 https://lampsvn.epfl.ch/trac/scala/ticket/4279
 "Sliced view foreach is incredibly slow for indexed sequences because it defaults to TraversableViewLike"

So the question ended up being, why is a view created from an IndexedSeq using the foreach defined in TraversableViewLike$#Sliced, which ought to be waaaay back in the inheritance chain? The answer, in diff form, is:

-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {
-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {
-  trait Sliced extends Transformed[A] with super.Sliced
+  trait Sliced extends super.Sliced with Transformed[A]
-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {

Before reversing the order of the parents, view was 5000 to 150,000 times slower than calling slice directly.  (The iterator/view numbers are multiples of the base nanoseconds.)

Runner(1000000, 10) base: 48000.  Iterator: 0.7917.  View: 4994.4583.
Runner(10000000, 10) base: 46000.  Iterator: 0.8478.  View: 52212.3696.
Runner(1000000, 50) base: 88000.  Iterator: 1.6818.  View: 14692.2500.
Runner(10000000, 50) base: 80000.  Iterator: 1.7125.  View: 150877.0750.

Afterward it's the same, plus or minus.

Runner(1000000, 10) base: 55000.  Iterator: 0.7455.  View: 0.6364.
Runner(10000000, 10) base: 51000.  Iterator: 0.8039.  View: 0.6863.
Runner(1000000, 50) base: 94000.  Iterator: 1.5213.  View: 1.2128.
Runner(10000000, 50) base: 89000.  Iterator: 1.6067.  View: 1.1573.

The reason is that correct collections behavior depends on Iterable* overriding Traversable* so that foreach uses iterator.  But when the Sliced subtraits do it like

 trait Sliced extends Transformed[A] with super.Sliced

they manage to reverse the overrides: super.Sliced is last in the linearization and its foreach wins.

Since all the view traits inherit their parents in this order except those in the parallel collections, I think most everything involving views is actually using the implementations in Traversable rather than the implementations designed for what they're viewing over.

I've just checked the linearization order of ParIterableViewLike.Sliced,
unless I'm mistaken, it's:

L(ParIterViewLike.Sliced) = ParIterViewLike.Transformed, ParIterView,
ParIterViewLike, ParIter, ParIterableLike, ...

meaning implementations from ParIterableLike come first. The same should
then apply for

SeqViewLike.Sliced extends super.Sliced with Transformed[A]:

L(SeqViewLike.Sliced) = SeqViewLike.Transformed, SeqView, SeqViewLike,
Seq, SeqLike, IterableViewLike.Sliced...

meaning that the new inheritance should pick up the correct implementation.

The other way around:

SeqViewLike.Sliced extends Transformed[A] with super.Sliced

produces:

L = IterViewLike.Sliced, TraversableViewLike.Sliced, ...

taking the implementation from traversable like, if I got this right.

My head is spinning. You're right. Nice catch.

On 09/03/11 19:11, Paul Phillips wrote:
> Another in the category of "man, that took me a while to figure out."
> Here is the bug:
>
> https://lampsvn.epfl.ch/trac/scala/ticket/4279
> "Sliced view foreach is incredibly slow for indexed sequences
> because it defaults to TraversableViewLike"
>
> So the question ended up being, why is a view created from an
> IndexedSeq using the foreach defined in TraversableViewLike$#Sliced,
> which ought to be waaaay back in the inheritance chain? The answer, in
> diff form, is:
>
> - trait Sliced extends Transformed[A] with super.Sliced {
> + trait Sliced extends super.Sliced with Transformed[A] {
> - trait Sliced extends Transformed[A] with super.Sliced {
> + trait Sliced extends super.Sliced with Transformed[A] {
> - trait Sliced extends Transformed[A] with super.Sliced
> + trait Sliced extends super.Sliced with Transformed[A]
> - trait Sliced extends Transformed[A] with super.Sliced {
> + trait Sliced extends super.Sliced with Transformed[A] {
>
> Before reversing the order of the parents, view was 5000 to 150,000
> times slower than calling slice directly. (The iterator/view numbers
> are multiples of the base nanoseconds.)
>
> Runner(1000000, 10) base: 48000. Iterator: 0.7917. View: 4994.4583.
> Runner(10000000, 10) base: 46000. Iterator: 0.8478. View: 52212.3696.
> Runner(1000000, 50) base: 88000. Iterator: 1.6818. View: 14692.2500.
> Runner(10000000, 50) base: 80000. Iterator: 1.7125. View: 150877.0750.
>
> Afterward it's the same, plus or minus.
>
> Runner(1000000, 10) base: 55000. Iterator: 0.7455. View: 0.6364.
> Runner(10000000, 10) base: 51000. Iterator: 0.8039. View: 0.6863.
> Runner(1000000, 50) base: 94000. Iterator: 1.5213. View: 1.2128.
> Runner(10000000, 50) base: 89000. Iterator: 1.6067. View: 1.1573.
>
> The reason is that correct collections behavior depends on Iterable*
> overriding Traversable* so that foreach uses iterator. But when the
> Sliced subtraits do it like
>
> trait Sliced extends Transformed[A] with super.Sliced
>
> they manage to reverse the overrides: super.Sliced is last in the
> linearization and its foreach wins.
>
> Since all the view traits inherit their parents in this order except
> those in the parallel collections, I think most everything involving
> views is actually using the implementations in Traversable rather than
> the implementations designed for what they're viewing over.
> .
>

It would be hard to design such a compiler warning such that it didn't give a lot of useless information. A better idea would be to have some sort of style checker/bug finder tool that would heuristically search for a particular pattern.

Donna

On Mar 9, 2011, at 7:50 PM, Jon Steelman wrote:
> Is there a case for a compiler warning when linearization causes a concrete method to be inherited in reverse order compared to the ordering of the class/traits with each other? If I understood the issue....the warning would aid in identifying such an issue like this in the future.

There's a simple way to check linearization -- ScalaDoc does it for you. Just go the the class, find the method, and see what "definition classes" looks like.

On Wed, Mar 9, 2011 at 15:51, Aleksandar Prokopec <aleksandar.prokopec@epfl.ch> wrote:

I've just checked the linearization order of ParIterableViewLike.Sliced, unless I'm mistaken, it's:

L(ParIterViewLike.Sliced) = ParIterViewLike.Transformed, ParIterView, ParIterViewLike, ParIter, ParIterableLike, ...

meaning implementations from ParIterableLike come first. The same should then apply for

SeqViewLike.Sliced extends super.Sliced with Transformed[A]:

L(SeqViewLike.Sliced) = SeqViewLike.Transformed, SeqView, SeqViewLike, Seq, SeqLike, IterableViewLike.Sliced...

meaning that the new inheritance should pick up the correct implementation.

The other way around:

SeqViewLike.Sliced extends Transformed[A] with super.Sliced

produces:

L = IterViewLike.Sliced, TraversableViewLike.Sliced, ...

taking the implementation from traversable like, if I got this right.

My head is spinning. You're right. Nice catch.


On 09/03/11 19:11, Paul Phillips wrote:

Another in the category of "man, that took me a while to figure out."
Here is the bug:

 https://lampsvn.epfl.ch/trac/scala/ticket/4279
 "Sliced view foreach is incredibly slow for indexed sequences because it defaults to TraversableViewLike"

So the question ended up being, why is a view created from an IndexedSeq using the foreach defined in TraversableViewLike$#Sliced, which ought to be waaaay back in the inheritance chain? The answer, in diff form, is:

-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {
-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {
-  trait Sliced extends Transformed[A] with super.Sliced
+  trait Sliced extends super.Sliced with Transformed[A]
-  trait Sliced extends Transformed[A] with super.Sliced {
+  trait Sliced extends super.Sliced with Transformed[A] {

Before reversing the order of the parents, view was 5000 to 150,000 times slower than calling slice directly.  (The iterator/view numbers are multiples of the base nanoseconds.)

Runner(1000000, 10) base: 48000.  Iterator: 0.7917.  View: 4994.4583.
Runner(10000000, 10) base: 46000.  Iterator: 0.8478.  View: 52212.3696.
Runner(1000000, 50) base: 88000.  Iterator: 1.6818.  View: 14692.2500.
Runner(10000000, 50) base: 80000.  Iterator: 1.7125.  View: 150877.0750.

Afterward it's the same, plus or minus.

Runner(1000000, 10) base: 55000.  Iterator: 0.7455.  View: 0.6364.
Runner(10000000, 10) base: 51000.  Iterator: 0.8039.  View: 0.6863.
Runner(1000000, 50) base: 94000.  Iterator: 1.5213.  View: 1.2128.
Runner(10000000, 50) base: 89000.  Iterator: 1.6067.  View: 1.1573.

The reason is that correct collections behavior depends on Iterable* overriding Traversable* so that foreach uses iterator.  But when the Sliced subtraits do it like

 trait Sliced extends Transformed[A] with super.Sliced

they manage to reverse the overrides: super.Sliced is last in the linearization and its foreach wins.

Since all the view traits inherit their parents in this order except those in the parallel collections, I think most everything involving views is actually using the implementations in Traversable rather than the implementations designed for what they're viewing over.
.

--
Daniel C. Sobral

I travel to the future all the time.