Does the SIP committee have to obey its own precedent ?
Especially across features and time
6% on such a test with such high variability depending on the project and usage is a measurement error.
6% on unsigned Integers which are trivial to benchmark with low variance is significant.
It is not the same.
1 Like
Probably not. I am unaware of any guidelines in that direction. But it would make decisions more credible i guess.
True, they are not. An other difference is that you can choose if you want to take the performance hit by using unsigned integers or not. With the proposed transformation you are just hit by it if you code is already using default Seq.
Hi everybody! I wanted to report a negative result here, because I found the result fascinating.
As some of you may have seen, a week or two ago I published an experimental collections library, farray â an immutable, Array-backed sequence with O(1) structural ops (via lazy nodes over flat leaves), no boxing of primitives, name-based ::/+: extractors, and a fusion macro. I chose its main properties in part because I was convinced theyâd be an ideal fit for the Scala 3 compiler: covariance (FArray[+A], like List), dedicated special-casing for length 0 and 1 (a shared empty singleton and a one-field leaf), unboxed flat storage, and O(1) ++/+:/take/drop. Given everything I thought I knew about JVM performance, I was fully convinced that replacing List with FArray throughout the compiler would be a large, obvious win.
It wasnât.
The whole experiment was driven by Claude Fable, so it only made sense that Claude would summarize it as well. I know i had a lot of fun experimenting with this, and i think the conclusion is fairly strong (and surprising to me!)
Experiment summary gist
10 Likes
Reaching out to others yourself is never a waste of time !
I skimmed through it and it seems interesting
Thanks for trying this out!
Weâve discussed this during the core meeting and we are considering switching the default Seq implementation to Vector, which is a much more versatile collection. This is a separate decision than what should be used in the compiler (which will most likely not change).
If you see any issues with that change let us know. Currently the only issues we are worried is when someone relied on Seq being a List underneath, but that was never guaranteed. So any type casts or pattern matches that relied on this might fail.
Before the change is made we will check out the full open community build to make sure there is not significant impact on existing open source projects.
3 Likes
Iâve done a lot of work in migrating real world code bases across collections changes, so this is a bit triggering!
I found a regular occurence of fragile code that works âby accidentâ matching incoming Seq-s as case head :: tail. This likely flows from some of the education material about Scala pattern matching that uses linked lists as canonical examples.
I saw this issue already as part of the Scala 2.13 collections upgrade, which in some cases resulted in different concrete Seq subclasses collections for results of certain collections operations.
This risk can be mitigated with a linting rule that detects the pattern matches using the :: case class pattern for scrutinee types wider than List. But this needs to be run and remedied in your libraries as well as your application to have a high level of comfort.
For sure I would recommend analysing public corpus of source code for this pattern to inform the change. Could it be produced directly from Tasty?
The hard part about this sort of change is that the resulting error can be some distance from the failed pattern match.
EDIT: hereâs a rough version of the lint for the Scala2 compiler: SeqMatchLintPlugin.scala ¡ GitHub
5 Likes
Can we assume that for anyone bitten by this in production, that Vector#tail would show up prominently in profiling results?
Perhaps we could provide a (prominently release-noted) -W option that would warn on the case h :: t pattern when the scrutineeâs static type is Seq. Such an option could be backported to 3.9, too, so people could get their code 3.10-ready ahead of time.
Note that my original result is not fully positive! I was expecting âVector is about as fast as a drop in replacementâ and got âVector is about as fast if polished up and used idiomatically, otherwise thereâs a minor performance hitâ.
So not quite as positive as I was hoping for, but also not quite as negative as I feared. Truly one of the experimental results of all time.
2 Likes
Any idea of how switching the default Seq implementation from List to Vector would affect its performance in Scala.js? Since itâs a different runtime than the JVM.
6 Likes
I think the Seq constructor instantiated Vector in an older versions of Scala (< v2.13 IIRC).
Thereâs a lot of agreement in favour of this change, however I tend to discourage the use of the Seq constructor and only use Seq as the top type for sequential data structures.
My reasoning is that one should care about and be aware of the underlying data structure, (as all of us here know) different data structures exhibit vastly different performance characteristics.
In practice Iâve found that linear access of sequential data structures is a significantly more common pattern in FP than random access by index. For that case linked-list (List) is ideal.
Vectors suit a middle ground between arrays and linked-list, where the structure needs to support random access and shrink/grow efficiently. Iâve found that to be a rare case.
Where one would need the features of a vector, a hash map would often be a better choice for more accurate modelling of the given domain with descriptive keys, rather than.
historical digression:
I think the
Seqconstructor instantiatedVectorin an older versions of Scala (< v2.13 IIRC).
Itâs been List since Scala 2.8 in 2010.
In Scala 2.7, it was something called ArrayBufferRO which I assume is akin to todayâs immutable.ArraySeq.
Vector didnât become a suitable candidate for this purpose until Scala 2.13.2 (2020), when (Rewrite Vector (now "radix-balanced finger tree vectors"), for performance by szeiger ¡ Pull Request #8534 ¡ scala/scala ¡ GitHub) landed necessary improvements such as representing small sequences compactly.
In this discussion, I think we can assume it is known and agreed upon that production code written by professional engineers shouldnât use Seq.apply in contexts where exact performance characteristics might matter.
However, much Scala code doesnât meet that description. In a great deal of Scala code, I think itâs fine and normal to use Seq.apply. I use it myself often. Writing Seq communicates to the reader that âthe exact sequence type doesnât matter hereâ. And a lot of the time it simply doesnât matter:
- When still learning the language
- In tests
- In one-off scripts, prototypes, experiments, and other such casual coding
- In build definitions
- Even in production code for sequences that are known not to be performance-critical and/or where the sequence size is known to be short
To pick just one example from the above list, in build.sbt files we all write:
libraryDependencies ++= Seq(...)
I hope nobody would insist that itâs better to write List or Vector here instead of Seq.
3 Likes
Iâll argue that position.
The intention described for Seq.apply is that it is only for the cases where performance doesnât matter, but that is not something Seq.apply clearly advertises, and consequently itâs not something most users of Seq.apply are going to know about.
For code where performance doesnât matter, it is no harder to write libraryDependencies ++= Vector(...) than it is to write libraryDependencies ++= Seq(...). Such code will not benefit much from changing the underlying implementation, so the argument in favor of changing the implementation for this case is weak.
Meanwhile, I think existing projects would appreciate not having the implementation changed out from under them, unless it is a clear win in all cases. Code that is sensitive to performance should not be using Seq.apply at all, but there is such code out there, and changing the implementation creates a compatibility risk for upgrades.
I think the project should consider leaving the current implementation alone. You might consider deprecating Seq.apply instead.
Having Seq.apply exist with the implicit understanding that it should only be used when performance characteristics donât matter, not properly advertising that fact, and changing its underlying implementation to another collection type is a bad combination.
It marginally increases convenience for people who donât care which collection they get, at the cost of needing to teach people not to use Seq.apply when performance matters, and since not everyone will learn that bit of tribal knowledge, it creates an unnecessary migration risk for projects when upgrading Scala.
For the cases where the exact collection doesnât matter, documentation could guide people toward Vector instead, as the best current allrounder. If that recommendation changes in the future, it can easily be updated again, without introducing a risk of performance regressions for existing code.
2 Likes
there is also a compiler miniphase micro-optimisation that replaces Seq.apply with ::, so that needs to be considered (it casts to Seq so no types change from the outside)
1 Like
Then, itâs the whole type Seq that needs to be deprecated, not just Seq.apply. Seq(x,y,z) is too short to be dangerous; itâs longer sequences built from it (and thus of type Seq) that will have an impact. Or are we worried about code of the form: Seq(largeCol*)? That must be rareâŚ
My students get burned all the time with arguments of type Seq by using indexing (oops, it was a list) or head/tail recursion (oops, it was an array). But itâs their fault. They also get burned in Java by assuming a List is an ArrayList. They need to learn not to make assumptions.
I use Seq (and Seq.apply) quite a bit because when I donât care, I donât care. I donât want to spend time deciding between List and Vector and, a year later, spend time again wondering why I used List here and Vector there. Seq is a convenient way of saying: donât make assumptions on the underlying implementation.
2 Likes
Thatâs a completely fair stance, but by that logic, the argument for switching to another implementation is weak.
If performance doesnât matter, then performance doesnât matter, and switching to another implementation type is not worth the headache.
People accidentally depend on implementation details all the time, and itâs easy to say âIt was their own fault, I wouldnât write code like thatâ, but that doesnât change that this is a thing that happens in the wild. If Scala is going to cause users migration pain, it should be for a good reason, and I donât think improving the performance of code where performance doesnât matter is a very good one.
3 Likes
Fair enough. I was just reacting to the claim that nobody should write Seq(...). Iâll let others decide whether there is more code in the wild that benefits from Seq=List or from Seq=Vector. It wonât impact me[1].
famous last words⌠âŠď¸
Ideal solution is to just remove/deprecate Seq.apply. Second best is making it default to IArray / ArraySeq. Third best is making it default to Vector.
No. Even for sequential iteration List is terrible. Not to mention the space overhead of storing all the object headers of list nodes.
Again. The only operation where List beats Vector is prepend and tail.
1 Like