ArrayDeque introduced in Scala 2.13 is basically a superset of Buffer’s functionality, and there is no reason that anyone should use Buffer anymore. ArrayDeque supports all the same APIs efficiently, and more due to allowing efficient operations on the other side.
It should be straightforward to implement all the mutable.Buffer operations using ArrayDeque, and add in the other ArrayDeque operations as well. Since the name mutable.Buffer is the “default” mutable buffer semantically, we should make it do what most people would want, rather than forcing them to reach for the more verbose ArrayDeque sometimes but not other times.
This would streamline usage of mutable.Buffer/mutable.ArrayDeque, and remove a stumbling block of having to choose which one to use when there really is one right answer and the obvious answer is wrong
Every capability you add to the Buffer contract removes implementation freedom. This probably has some performance cost that would be nice to have quantified in the proposal. The problem is that even if it can be measured to be small with current hardware it probably hard it possible that might grow on future hardware.
A design concern: these new methods on Buffer , should they also be available on all mutable collections? (And are we sure that they aren’t there already?)
On the PR, Haoyi responded:
I want these added to buffer because it is in many ways the “default” mutable sequence constructor.
But that doesn’t really resolve my concern. Buffer and mutable.Seq both exist, and they’re both part of the overall design picture here:
Welcome to Scala 3.8.4
scala> collection.mutable.Seq(1, 2, 3)
val res1: collection.mutable.Seq[Int] = ArrayBuffer(1, 2, 3)
Given that mutable.Seq exists, why does Buffer also exist? If I understand correctly, it’s because Buffer is specifically intended for use for temporary collections, where you intend to convert the result to something else when you’re done. So you typically uses ListBuffer because you intend to ask for List at the end and you want that to be efficient, or you use ArrayBuffer because you want an Array at the end and you want that to be efficient.
Why would one ever use the generic Buffer at all, then? Personally, I wouldn’t, but I’m not sure about others. The Scaladoc on Buffer is no help here, sadly.
Also, I’m wondering why this proposal doesn’t also change the default implementation of Buffer (and perhaps of mutable.Seq as well) to be ArrayDeque?
I thought the names are pretty straightforward and look just like any other Scala collection APIs
I agree they look plausible. But we’re looking for a higher level of certainty than that, higher than mere plausibility. We want to be sure these additions are not merely plausible, but are actually right. That certainty has to come from somewhere for the additions to be mergeable; somebody has to do the design work.
For example, you’re proposing adding removeHeadWhile here; how is that different from dropWhileInPlace?
My point here is not only that to raise that specific objection, to met with a specific response. My point is that the fact that I suspect that until I did it just now, nobody even went looking for dropWhileInPlace. How much other such design work remains undone here…?
Where does this come from? I’ve seen Buffer be used anytime someone wants a mutable sequence and I’ve never once in my life seen someone use a mutable.Seq. If someone wants a builder that’s what .newBuilder is for!
I’m not sure if I’m missing something, but this proposal does change the default implementation of Buffer to ArrayDeque???
I didn’t touch mutable.Seq because I’ve never seen anyone use it
I’m generally not a fan of creating collections through abstract collection types, like Seq(..). I think it’s better to pick a concrete collection, so it’s visible in code what performance / memory characteristics come with it (List / Vector / IArray. ArrayBuffer / ListBuffer / Queue).
The methods in this PR only show up in ArrayDeque, so I’m not sure we should pull them further up. There was a design principle to keep mutating operations only in concrete collection types, see collection-strawman#473.
ArrayDeque was an external contribution, so the contributor might not have been up to date with all the (unwritten / unchecked) design principles.
I’m not sure if I’m missing something, but this proposal does change the default implementation of Buffer to ArrayDeque ???
Apologies, I’m the one that missed something. Not sure how I missed that even when I was specifically looking for it…!
About Buffer vs mutable.Seq, perhaps you’re right and the latter is relatively little used? I’m not sure. But it’s not a reason to leave it out of the design thinking; it’s a supertype of Buffer.
Over the years I’ve come to at least somewhat agree, and it raises an interesting question: is this a straight anti-pattern? More importantly, does the stdlib make it too easy to fall into this anti-pattern?
I think of it as a mistake that Scala newbies make a lot (I certainly did), and I kind of wonder if we should more actively discourage it. Maybe we should at least say in the documentation that it’s usually better to choose your collection explicitly, rather than use the default constructor for the trait?
I’m by no means certain – I vaguely feel like using the default constructor for Seq tends to be a bad idea (because the performance characteristics can vary a lot), but the default for Map is usually what you want except for special cases, so it’s unclear whether there’s a principled argument here. But I vaguely feel like we’re leaving a trap for new folks.
This is true in specific domains, but is not broadly generalizable. There is a lot of code where performance/memory characteristics are of secondary importance, e.g.
”business logic”, and people can pick specific data structures for the parts which are known hot or turn up in their profiles. If you’re saying that we shouldn’t improve Buffer(...) because having Seq(...)was a mistake, I think that ship sailed decades ago
It sounds like there are some concrete ideas, perhaps you guys could list out your suggestions in a bit more detail? The goal here is for us to try and come up with the best solution together, and since you guys don’t have the same blind spots as me your concrete suggestions would be very valuable
One big difference between the remove and dropInPlace methods is that the remove APIs return the thing that is removed, while the dropInPlace methods return this.
That makes the dropInPlace not a replacement for the remove methods that this proposal adds. Returning the thing being removed is incredibly useful. The dropInPlace methods all return this for consistency with the other *InPlace methods, but as a result they simply cannot satisfy the common use case of “take a few things out from the collection’s head/tail and return them”
Presumably that was the reason why the remove APIs were added separately in the first place, and is one of the reasons mutable.Queue and mutable.Stack have their own dequeueWhile/popWhile APIs rather than relying purely on the equivalent dropInPlace methods
It was first proposed by Pathrikit, but was thoroughly reviewed and discussed by JulienRF, Rex Kerr, and Stefan Zeiger, so I feel like we should have a bit more faith in the quality of the API. “They probably just didn’t think of dropInPlace operations” seems a bit silly to me, I doubt such a group review and discussion would make such trivial mistakes in the design and implementation of a Scala collection!
I think it’s OK to have Seq() as a constructor – it basically means “I don’t care about the performance characteristics of this.”
What’s usually more important is using particular kinds of sequence types in arguments – the performance characteristics are much more important when you’re consuming the value than when you’re creating it (particularly with a constructor, which means there won’t be a particularly large sequence).
It’s also a good idea to try and use more specific return types when you can… e.g. if you return a List, don’t use Seq in the type signature. I guess you could mean “the performance characteristics of the returned value shouldn’t matter”, but that’s really the caller’s… call.
So, if parameter types are more specific, and return types are more specific, that will lead to a lot of more specific constructors. Still, Seq is a useful way of saying “I don’t consider maximal performance to be important here”.
I’ve known people to advocate for always using the concrete type and constructor – e.g. Vector instead of Seq. Maybe I find that particularly inconvenient because there are a half dozen other types called Vector that I often need to deal with, and it’s annoying to disambiguate.