Regression: prepended SeqView should still be a SeqView

[Atry]

1 +: 2 +: Nil.view compiles in Scala 2.12:

Welcome to Scala 2.12.6 (GraalVM 1.0.0-rc2, Java 1.8.0_171).
Type in expressions for evaluation. Or try :help.

scala> 1 +: 2 +: Nil.view
res0: scala.collection.SeqView[Int,Seq[_]] = SeqViewAA(...)

but not in Scala 2.13.0-M5

Welcome to Scala 2.13.0-M5 (GraalVM 1.0.0-rc2, Java 1.8.0_171).
Type in expressions for evaluation. Or try :help.

scala> 1 +: 2 +: Nil.view
         ^
       error: value +: is not a member of scala.collection.View[Int]

[julienrf]

I think @joshlemer has a work in progress that fixes this issue.

[joshlemer]

This is not a problem if you don't use the symbolic operators:

val seqView: SeqView = Nil.prepended(2).prepended(1)

But that's pretty dissatisfying. Is it worth unmarking symbolic operators as final to satisfy this usecase?

[SethTisue]

(discussed just now at collections meeting)

Stefan (@szeiger) observes that Scala 3 might offer some better way forward for the symbolic aliases, but that doesn't help us now

we could remove final and document that custom collections may need to remember override both the alphabetic and symbolic methods together, in cases where when the return type need to be refined

but removing final could have a performance impact, we'd be relying on the JIT to inline the forwarder, the Scala optimizer wouldn't do it without final

sigh

[SethTisue]

would someone like to run some benchmarks and see if the feared performance impact for removing final materializes? if performance is okay, then I think removing final is a reasonable way forward here. making more work and more potential pitfalls for custom collections implementers isn't ideal, but it's a pretty small audience, and it's an audience we can reasonably expect to be cautious about consulting documentation

[szeiger]

If you disregard the anomaly for large ArraySeqs (where the overhead of the method call is very small compared to the actual work and the performance numbers may be unreliable) there is a noticeable performance loss from removing inline final from +::

Inline final:

[info] Benchmark                     (size)  Mode  Cnt       Score       Error  Units
[info] SeqBenchmark.prependArraySeq      10  avgt   40     505.493 ±     5.862  ns/op
[info] SeqBenchmark.prependArraySeq     100  avgt   40   13062.416 ±   699.455  ns/op
[info] SeqBenchmark.prependArraySeq    1000  avgt   40  801025.490 ± 30199.926  ns/op
[info] SeqBenchmark.prependList          10  avgt   40     252.836 ±     1.713  ns/op
[info] SeqBenchmark.prependList         100  avgt   40    2719.735 ±    32.294  ns/op
[info] SeqBenchmark.prependList        1000  avgt   40   32303.112 ±   192.225  ns/op

[info] Benchmark                     (size)  Mode  Cnt       Score      Error  Units
[info] SeqBenchmark.prependArraySeq      10  avgt   40     496.886 ±    1.908  ns/op
[info] SeqBenchmark.prependArraySeq     100  avgt   40   12148.133 ±   81.234  ns/op
[info] SeqBenchmark.prependArraySeq    1000  avgt   40  755006.901 ± 6375.030  ns/op
[info] SeqBenchmark.prependList          10  avgt   40     249.958 ±    2.707  ns/op
[info] SeqBenchmark.prependList         100  avgt   40    2702.718 ±   28.612  ns/op
[info] SeqBenchmark.prependList        1000  avgt   40   32306.697 ±  978.823  ns/op

Regular method:

[info] Benchmark                     (size)  Mode  Cnt       Score      Error  Units
[info] SeqBenchmark.prependArraySeq      10  avgt   40     524.053 ±    5.349  ns/op
[info] SeqBenchmark.prependArraySeq     100  avgt   40   12212.575 ±  108.514  ns/op
[info] SeqBenchmark.prependArraySeq    1000  avgt   40  737278.517 ± 7166.837  ns/op
[info] SeqBenchmark.prependList          10  avgt   40     273.329 ±    2.449  ns/op
[info] SeqBenchmark.prependList         100  avgt   40    2808.817 ±   23.935  ns/op
[info] SeqBenchmark.prependList        1000  avgt   40   32818.090 ±  337.912  ns/op

[info] Benchmark                     (size)  Mode  Cnt       Score       Error  Units
[info] SeqBenchmark.prependArraySeq      10  avgt   40     529.835 ±    22.790  ns/op
[info] SeqBenchmark.prependArraySeq     100  avgt   40   12208.452 ±    86.415  ns/op
[info] SeqBenchmark.prependArraySeq    1000  avgt   40  748563.870 ± 14073.256  ns/op
[info] SeqBenchmark.prependList          10  avgt   40     268.424 ±     2.288  ns/op
[info] SeqBenchmark.prependList         100  avgt   40    2861.313 ±    45.830  ns/op
[info] SeqBenchmark.prependList        1000  avgt   40   32544.994 ±   422.023  ns/op

[szeiger]

Better data from a longer run (Old is with inline final):

[info] Benchmark                        (size)  Mode  Cnt       Score      Error  Units
[info] SeqBenchmark.prependArraySeq          3  avgt  100     157.155 ±    0.920  ns/op
[info] SeqBenchmark.prependArraySeq         10  avgt  100     532.178 ±    2.452  ns/op
[info] SeqBenchmark.prependArraySeq        100  avgt  100   12343.959 ±   44.568  ns/op
[info] SeqBenchmark.prependArraySeq       1000  avgt  100  750047.437 ± 2862.378  ns/op
[info] SeqBenchmark.prependArraySeqOld       3  avgt  100     153.532 ±    0.815  ns/op
[info] SeqBenchmark.prependArraySeqOld      10  avgt  100     518.741 ±    2.674  ns/op
[info] SeqBenchmark.prependArraySeqOld     100  avgt  100   12177.336 ±   42.216  ns/op
[info] SeqBenchmark.prependArraySeqOld    1000  avgt  100  772667.758 ± 7919.274  ns/op
[info] SeqBenchmark.prependList              3  avgt  100      83.207 ±    0.464  ns/op
[info] SeqBenchmark.prependList             10  avgt  100     277.146 ±    1.612  ns/op
[info] SeqBenchmark.prependList            100  avgt  100    2916.867 ±   17.418  ns/op
[info] SeqBenchmark.prependList           1000  avgt  100   33572.016 ±  171.341  ns/op
[info] SeqBenchmark.prependListOld           3  avgt  100      81.405 ±    0.426  ns/op
[info] SeqBenchmark.prependListOld          10  avgt  100     259.476 ±    1.398  ns/op
[info] SeqBenchmark.prependListOld         100  avgt  100    2838.381 ±   13.273  ns/op
[info] SeqBenchmark.prependListOld        1000  avgt  100   32608.003 ±  187.292  ns/op

The performance penalty affects all uses of +: whereas the regression is limited to the rarely used SeqView, it leads to a compiler error (rather than different runtime behavior), and it is easily fixed by using prepended instead of +:, so I'm rescheduling this for 2.14 (I don't expect that we can fix it before 3.0 but there's no milestone for that yet).

[Dicee]

There are similar issues with other operations like flatMap, unless this is intended (see explanation). I haven't made a full list of it, but I'm sure it's not the only one.