is vector never bigger than a list, even for some very small sequence lengths? if for some lengths vector occupy more space than list, then there’s a risk that for some apps switching to vector will cause out-of-memory errors or heavy gc cpu usage.
I would suggest instead of deprecating Seq.apply, it take a contextual parameter which defaults to List. This way we would maintain backward compatiblity and if random access is needed, one can provide Vector contextual parameter, or even their custom data structure.
it could potentially look something like this:
trait DefaultSeqFactory:
def apply[A](elems: A*): Seq[A]
object DefaultSeqFactory:
given DefaultSeqFactory with
def apply[A](elems: A*): Seq[A] = List(elems*)
object Seq:
def apply[A](elems: A*)(using factory: DefaultSeqFactory): Seq[A] = factory(elems*)
But the tradeoff here would be increasing the complexity for Standard library.
This seems like a bad idea, there is already a way to be sure to get a Vector:
replacing Seq(...) with Vector(...)
The idea behind the current proposal is that when you don’t care about the performance characteristics, Vector is still a better default
1 Like
Hyrum’s Law states that with a sufficient number of users of an API, all observable behaviors of a system will be depended on by somebody, regardless of what the official contract promises. Given that, we have to assume that some projects out there rely on Seq.apply returning a List, whether we like it or not. This means that if we’re going to change the default, we should have some good reason for doing so, and thus far I haven’t seen anything compelling. At least for the Scala compiler itself, the performance difference is negligible according to the numbers presented by Haoyi, and I haven’t seen any evidence to suggest that the situation is any different for any other projects.
Really what it seems to come down to is this, and I’m quoting @SethTisue here:
my own take is that the proposed change isn’t targeting experienced Scala programmers writing performance-sensitive code. it’s targeting people who are new to the language and/or less sophisticated/expert about reasoning about performance, aiming to prevent them from falling into accidentally writing O(n^2) code
Whether this is sufficient justification is a judgement call, but for me personally, it doesn’t pass that bar. If somebody learning the language writes O(n^2) code, that’s probably not the end of the world. Beginners usually deal with small amounts of data, and when that changes, they’re going to have to learn about the performance characteristics of the different data structures anyway. Probably Vector would have been the right choice if Scala were a new language. But it’s not, and changing it now is just not worth the hassle IME.
8 Likes
At $WORK I am adopting Vector as the default collection instead of List because its performance is much better on large collections (hundreds of thousands), and similar or a little bit worse on small collections (usually 1 element). That small performance hit is still worth it, because the performance degradation on large collections dwarfs everything else.
Nevertheless, I would still like to be more confident when choosing Vector, that’s why I’m offering to review my proposal on optimizing Vectors in small-size cases. It’s not strictly better, there are still some tradeoffs. I also think it will potentially help improve compiler’s performance, but I have not benchmarked that yet.
3 Likes
The problem with such benchmarks is that they are way too isolated. What do I mean by that?
HotSpot JVM has the idea of profiling methods and classes, that includes analyzing how many different implementations appear in the runtime. If there is only 1, C2 assumes that the implementation can be inlined, when 2, still inlined but with the if-else. More? It’s megamorphism and JVM does not inline, uses pointer chasing etc. So multiple implementations in runtime in some place usually implies performance degradation.
If you benchmark focuses on just 1 branch - e.g. testing Vector for exactly 1 value, or exactly 2 values, etc - JVM in the benchmark detects 1 implementation of several possible (Vector1, Vector2, …) so you see the big boost… while the actual user using Vector that might be of size whatever will get megamorphism and a degradation in performance.
From what I remember Flavio Brasil pointed out that’s what 2.13 did - it made benchmarks for specific-size collections, assumed that it created a perf boost - by splitting single Vector into Vector1, Vector2, … and shipped a rewrite of a Vector type into several subtypes… that in practice degraded performance compared to 2.12. But benchmarks shows that everyone can pats themselves on the back for a great job.
I don’t mentioning it because I want to call anyone out, but to point out that benchmarking is hard. Unless some JVM expert (ideally several), reviewed them, there’s a change that the result are skewed. So showing +X perf improvement without someone deep diving in the context, analyzing JFR, looking how many of the observed the optimizations applied in the benchmark can actually be repeated in the average case in a real use cases, etc - it’s a vanity metric.
And that’s before anyone start looking for cases like:
Seq(a) ++ another match {
case a :: b :: tail =>
case a :: tail =>
case _ => ??? // lol, not happening since Seq is List
}
where some code relies on a reference implementation rather than official contracts (bad practice, but still a legal code that is being used and works - for now that is), where we would start thinking how this improvements can break the existing codebases after a “backward-compatible” version bump.
3 Likes
Would it be better to introduce another three-letter type (therefore also simple to type) that is also a good all rounder? (considering JIT for multi-size instances)
1 Like