Add immutable map that maintains insertion order (VectorMap/SeqMap) #6854

mdedetrich · 2018-06-24T22:21:16Z

This PR adds an implementation of scala/collection-strawman#277. Currently there isn't any known immutable map which also maintains key insertion order while keeping effectively constant lookup time on key, so the only known implementations are done by combining a Vector with a HasMap (or in Scala's case HashMap/ChampHashMap)

Some other notes on the PR

We duplicate private val useBaseLine in a very stupid way, I can refactor this into a package private variable however I am under the impression this is some workaround which will get removed later
Benchmarks were done to try and make the overhead of VectorMap as low as possible (in terms of performance). More work can be done here, its just a time consuming process
Basic ordering tests were added to make sure the collection works correctly
In particular, improving performance often meant manually inlining code and reusing internal structures as efficiently as possible (i.e. we reuse a lazy iterator for the values method on a VectorMap)
Another new data structure, called a SeqMap was added. A SeqMap is a type that identifies whether or not a Map maintains key insertion order, the current ListMap extends SeqMap as well as the new VectorMap
Also adds a mutable.SeqMap however this just reuses current collections instead of introducing a new one (i.e. it uses mutable.LinkedHashMap)

mdedetrich · 2018-06-24T22:25:59Z

@julienrf Here is the PR for adding the new collection type. Also I have signed the CLA, but for some reason the check seems to be failing

mkeskells · 2018-06-25T07:18:09Z

src/library/scala/collection/immutable/VectorMap.scala

+  * @define coll immutable vector map
+  * @define Coll `immutable.VectorMap`
+  */
+final class VectorMap[K, +V] private[immutable] (


This is an Insertion Ordered [Vector] Map. It happens to be based on a Vector. I think that the naming should reflect the interface and contract, not the implementation detail

Can you come up with a better name?

@mkeskells The name of the trait (LinkedMap) is based on the contract, but this is a concrete implementation. It is quite common for implementations to be named based on their structure (see ArraySeq, ChampHash{Map,Set}, ArrayDeque, TrieMap, Tree{Map,Set}, and many more)

mkeskells · 2018-06-25T07:19:06Z

src/library/scala/collection/immutable/VectorMap.scala

+  */
+final class VectorMap[K, +V] private[immutable] (
+    val fields: Vector[K],
+    val underlying: Map[K, (Int, V)])


please make the fields private - they are not part of the public interface

Woops missed this, thanks for picking it up, will fix it tonight

julienrf

Thanks @mdedetrich! See my comments below.

julienrf · 2018-06-25T09:28:58Z

src/library/scala/collection/immutable/LinkedMap.scala

+  * functionality for the abstract methods in `LinkedMap`:
+  *
+  * @tparam A
+  * @tparam B


They are named K and V. Can you also add one line of doc for each?

julienrf · 2018-06-25T09:30:51Z

src/library/scala/collection/immutable/LinkedMap.scala

+  extends Map[K, V]
+    with Iterable[(K, V)]
+    with MapOps[K, V, LinkedMap, LinkedMap[K, V]]
+    with Equals


I think only the with MapOps[…] line is useful, all the other with … are already inherited.

Also note that LinkedMap inherit from Map equality, meaning that LinkedMap(1 -> "foo", 2 -> "bar") == LinkedMap(2 -> "bar", 1 -> "foo"). (This is also the case for s.c.m.LinkedHashMap)

We should probably document that clearly.

I asked @Ichoran and this is intentional. Apparently even if we do have LinkedMap's which maintain insertion order, we should not take this into account when checking for equality, i.e. order equality is not a property for any type that implements immutable.Map.

I will document this though

julienrf · 2018-06-25T09:32:08Z

src/library/scala/collection/immutable/LinkedMap.scala

+  */
+
+trait LinkedMap[K, +V]
+  extends Map[K, V]


extends AbstractMap[K, V] yields a smaller bytecode.

julienrf · 2018-06-25T09:40:20Z

src/library/scala/collection/immutable/LinkedMap.scala

+    override def foreach[U](f: ((K, V)) => U): Unit = {
+      f((key1, value1))
+    }
+  }


I don’t think we should have these optimizations yet.

Could you explain what you mean exactly? Are you talking about the specialization's specifically?

Yes, the small size specialized cases.

Can you explain why we shouldn't have these optimizations, even more so in the case of VectorMap the performance/memory usage are issues, and specialization helps in the most common cases (maps of sizes 1-4)

The only reason is to not bloat the scala-library jar. But ok this code is probably very small compared to size of the whole jar…

julienrf · 2018-06-25T09:49:04Z

src/library/scala/collection/immutable/VectorMap.scala

+
+  override def updated[V1 >: V](key: K, value: V1): VectorMap[K, V1] = {
+    if (underlying.get(key).isDefined) {
+      val oldKey = underlying(key)._1


The lookup in underlying is supposed to be fast but still, I guess it would be more efficient to store the result of underlying.get(key) instead of performing two lookups?

Also, can you rename oldKey to oldIndex (or just index)?

julienrf · 2018-06-25T10:00:28Z

src/library/scala/collection/immutable/VectorMap.scala

+  }
+
+  override def tail: VectorMap[K, V] = {
+    val tail = fields.last


tail is probably not a good name as it suggests a collection type. What do you think about lastKey?

julienrf · 2018-06-25T10:02:09Z

src/library/scala/collection/immutable/VectorMap.scala

+  override def tail: VectorMap[K, V] = {
+    val tail = fields.last
+
+    new VectorMap(fields.slice(1, fields.size), underlying.remove(tail))


fields.tail is probably both more readable and more efficient than using .slice.

julienrf · 2018-06-25T10:02:46Z

src/library/scala/collection/immutable/VectorMap.scala

+  override def init: VectorMap[K, V] = {
+    val head = fields.head
+
+    new VectorMap(fields.slice(1, fields.size - 0), underlying.remove(head))


What do you think of using fields.init here?

julienrf · 2018-06-25T10:05:03Z

src/library/scala/collection/immutable/VectorMap.scala

+  // Only care about content, not ordering for equality
+  override def equals(that: Any): Boolean =
+    that match {
+      case vmap: VectorMap[K, V] =>


Should be vmap: VectorMap[_, _] => to not have a warning.

julienrf · 2018-06-25T10:07:27Z

src/library/scala/collection/immutable/LinkedMap.scala

+  def newBuilder[K, V]: Builder[(K, V), LinkedMap[K, V]] =
+    new ImmutableBuilder[(K, V), LinkedMap[K, V]](empty) {
+      def addOne(elem: (K, V)): this.type = { elems = elems + elem; this }
+    }


I think we should extend MapFactory.Delegate[LinkedMap](VectorMap) instead of implementing empty, from and newBuilder.

mdedetrich · 2018-06-25T10:56:24Z

@julienrf Thanks for the comments, will address these tonight

sjrd · 2018-06-25T11:18:06Z

Is this really necessary? Looks like it could exist in a separate library without any downside.

mdedetrich · 2018-06-25T14:26:56Z

@sjrd If you read scala/collection-strawman#277, you can see the reasoning why its ideal to put this collection in the stdlib (the current Map is not deterministic in ordering, actually even worse, its deterministic up to 4 only as a side effect of specialization and then ordering is lost). Not having such a collection has also caused headaches/endless debates with scalajson because there is no immutable map type which maintains key insertion order plus has effectively constant lookup by key.

It was also discussed in various SLIP meetings with scala center that it makes sense to add this collection into Scala for 2.13 (i.e. when the collections are redesigned). Arguably the biggest advantage of this PR is more the LinkedMap trait than the actual VectorMap implementation, since we can actually specify as a constraint that we are working with Map's that maintain key insertion order.

Note that I am already providing this as a separate library for Scala 2.10 to 2.12 (see https://github.com/mdedetrich/linked-map), however we lose the benefit that the LinkedMap trait was meant to provide. i.e. ideally we wanted to have our JsonObject be defined as so

case class JObject(values: LinkedMap[String, JValue])

To ensure that key insertion ordering isn't lost, however this ship has already sailed (as discussed in the last SLIP meeting)

SethTisue · 2018-06-25T19:13:58Z

I think this is well worth having in the standard library. Whenever possible, we should supply at least one concrete collection in the matrix (mutable, immutable) x (set, map) x (Ordering-ordered, insertion-ordered, arbitrarily-but-efficiently-ordered).

Nondeterministic ordering can be a real nuisance for reproducibility, particularly in tests, but also in general application code.

sjrd · 2018-06-25T19:56:04Z

I just think there's been way too much of "let's add x to the collections library, because why not?" lately. It's especially infuriating to me because I firmly believe that "let's not add x to the std lib, because why?" is the better approach. All this stuff will need to be supported forever onwards!

mdedetrich · 2018-06-25T21:23:57Z

@julienrf I have either replied and/or applied your suggestions. Also let me know if you want me to squash my commits.

I just think there's been way too much of "let's add x to the collections library, because why not?" lately. It's especially infuriating to me because I firmly believe that "let's not add x to the std lib, because why?" is the better approach. All this stuff will need to be supported forever onwards!

What do you mean? Afaik no single new collection (apart from this one) has been added in 2.13, instead a lot has been redesigned (and I think some things may have actually been removed).

In any case, I agree with @SethTisue, a stdlib should have a general purpose collection that is "good" in all operations while maintaining insertion order, and we currently don't have that for Map

sjrd · 2018-06-25T21:28:04Z

A bunch of methods have been added. LazyList was added (and no, it does not fix Stream).

mdedetrich · 2018-06-25T21:33:22Z

A bunch of methods have been added

I think thats a world of difference compared to adding a new collection, they aren't really comparable.

LazyList was added (and no, it does not fix Stream).

Well yes, its designed to be a replaced for Stream since Stream is completely broken which is why Stream is deprecated (and likely to be removed in Scala 2.14), i.e.

@deprecated("Use LazyList (which has a lazy head and tail) instead of Stream (which has a lazy tail only)", "2.13.0")
sealed abstract class Stream[+A] extends AbstractSeq[A] with LinearSeq[A] with LazyListOps[A, Stream, Stream[A]]

You are right that LazyList still has issue, but LazyList is intended to replace a broken Stream, not to generally be an addition.

In any case, during the last SLIP meeting no one had any real objections to this. Not sure why its being brought up now.

sjrd · 2018-06-25T23:55:09Z

I think thats a world of difference compared to adding a new collection, they aren't really comparable.

So if I'm already tense about added methods, you can imagine how afraid I am about entire new collections.

Well yes, its designed to be a replaced for Stream since Stream is completely broken which is why Stream is deprecated (and likely to be removed in Scala 2.14), i.e.

LazyList is just as broken as Stream because of scala/collection-strawman#367

In any case, during the last SLIP meeting no one had any real objections to this. Not sure why its being brought up now.

Because I'm not a member of the SLIP committee, so I'm not attending those. I only monitor PRs. I'm just a regular chap raising my anxiousness about the future, as far as the library goes.

You're of course free to disregard my comments (you = yourself, the SLIP committee, and scala/scala maintainers).

mdedetrich · 2018-06-26T08:09:39Z

LazyList is just as broken as Stream because of scala/collection-strawman#367

Yes, which will hopefully be fixed

Because I'm not a member of the SLIP committee, so I'm not attending those. I only monitor PRs. I'm just a regular chap raising my anxiousness about the future, as far as the library goes.

You were there at the meeting and I don't remember anyone (including you) raising such concerns.

You're of course free to disregard my comments (you = yourself, the SLIP committee, and scala/scala maintainers).

I am just curious as to why this wasn't raised earlier.

mdedetrich · 2018-06-26T23:20:33Z

@julienrf I just added a test to verify that the withDefault/withDefaultValue property on LinkedMap works, is there anything else that is needed to get the PR merged?

julienrf · 2018-06-27T07:58:00Z

src/library/scala/collection/immutable/LinkedMap.scala

+    }
+
+  def newBuilder[K, V]: Builder[(K, V), LinkedMap[K, V]] =
+    new MapFactory.Delegate[LinkedMap](VectorMap).newBuilder


You can just call VectorMap.newBuilder.

Cool, will add this tonight

julienrf · 2018-06-27T07:59:34Z

@mdedetrich Thanks a lot for your work. That looks good to me. We need some time to decide whether we should include this new collection type in the standard library or not. We will come back to you soon.

julienrf · 2018-07-02T09:19:42Z

We have just had a discussion on Gitter with @mdedetrich: https://gitter.im/scala/collection-strawman?at=5b39e80af166440661120e50

We see several solutions:

Include VectorMap and LinkedMap in the standard library. An argument against this option is that we don’t need them. On the other hand, it’d be nice to have an efficient implementation of this missing collection type in the standard library.
Include only the LinkedMap type (and make ListMap extend it), and provide VectorMap as an external library. Pro: very small surface added to the standard library.
Don’t even include LinkedMap into the standard library. Pro: no impact at all on the standard library.

I’m in favor of solution 2. The impact on the standard library seems reasonable. What do other people think?

mdedetrich · 2018-07-02T09:36:26Z

@jvican I think you also had an opinion on this matter which came from the SLIP meeting (in context of ScalaJson where it was suggested to add such a collection to stdlib)

sjrd · 2018-07-02T09:36:44Z

Option 2 seems reasonable to me.

Side-track: can we find a better name for LinkedMap? That name suggests an implementation detail, not an abstract property. It would be weird if one implemented a hash-map that keeps insertion order, that would be called a linked map. Such structures are not unheard of; they are for example used to represent objects in various dynamically typed languages, such as JavaScript. I understand InsertionOrderMap is perhaps too long, but I'd like to find something along those lines. OrderedMap is misleading as it suggests the use of an Ordering, unfortunately.

mdedetrich · 2018-07-02T09:44:25Z

Side-track: can we find a better name for LinkedMap? That name suggests an implementation detail, not an abstract property. It would be weird if one implemented a hash-map that keeps insertion order, that would be called a linked map. Such structures are not unheard of; they are for example used to represent objects in various dynamically typed languages, such as JavaScript. I understand InsertionOrderMap is perhaps too long, but I'd like to find something along those lines. OrderedMap is misleading as it suggests the use of an Ordering, unfortunately.

I agree, this is the best name I could come up with that didn't conflict with what we already have (that also isn't too long). I came up with LinkedMap to imply the property that the keys in the Map are linked, and hence they maintain order (but I agree this isn't very formal reasoning). I also used LinkedMap because other people who have made the same collection came up with this name (for whatever reason).

I am open to better suggestions for name, does InsertionMap sound weird?

martijnhoekstra · 2018-07-02T10:01:58Z

InsertionMap definitely sounds weird, and doesn't to me imply that iterating over its elements iterates in insertion order (but rather that it has something to do with insertion sort or something). Is SequencedMap maybe any better?

lrytz · 2018-07-04T15:03:45Z

Ah, no, the scabot doesn't talk to travis.. I restarted the travis build. But in any case jenkins is what matters (for now), we're just testing travis.

mdedetrich · 2018-07-05T17:46:19Z

@julienrf I have added mutable.SeqMap and made LinkedHashMap extend it. Do you want me to add a factory method to mutable.SeqMap which constructs a LinkedHashMap?

julienrf · 2018-07-06T12:39:49Z

Do you want me to add a factory method to mutable.SeqMap which constructs a LinkedHashMap?

Why not. You can just use MapFactory.Delegate[SeqMap](LinkedHashMap).

SethTisue · 2018-08-07T02:35:50Z

@julienrf is this ready for merge, in your opinion? can this make M5?

SethTisue · 2018-08-07T03:25:22Z

tentatively marking as M5 blocker since if we're going to ship this, I think we want to get it out there for people to test

szeiger · 2018-08-07T11:08:40Z

@jvican Was this discussed at a SIP meeting?

I'm generally in favor of adding this and the implementation looks good after a cursory review. This type of collection comes up frequently in data formats such as JSON or XML but is sorely missing from many collection libraries. I would like to see this added to the standard library eventually but if it is deemed to big a change without a more formal process we can defer the decision until 2.14.

jvican · 2018-08-07T11:47:11Z

@szeiger We couldn't discuss it at a SIP meeting yet. I'm super happy that there are so many requests to the SIP Committee (we've never been so busy), so I've proposed to increase the frequency of our SIP meetings in the next three months after vacation to cope up with this demand.

However, it would make some sense to me to merge this in M5 and remove it in RC1 if the Committee finally votes against it (@adriaanm). We're already doing that for symbol literals, and we could use the experience our users gain from using it to nitpick on its current design in RC1 in case it stays.

mdedetrich · 2018-08-07T12:08:01Z

@jvican @szeiger @SethTisue Thanks for the update guys, on another note there hasn't been extensive micro bench marking on this collection because I noticed that @retronym was doing it on basic collections that we depend on, so I wanted to wait for this to get merged before attempting to do this, is this okay with you guys?

julienrf · 2018-08-07T13:23:32Z

I lean towards putting this in an external library, but in case you want to merge it in the standard library, then yes, this is good to merge!

mdedetrich · 2018-08-07T13:38:40Z

My opinion basically mirrors what is said quite eloquently here #6854 (comment). I agree with @jvican that merged for M5 and then removing it for RC1 if the SIP meeting decides to not want the collection sounds like a good idea.

adriaanm · 2018-08-07T13:48:06Z

Thanks, @mdedetrich! 🍰

mdedetrich · 2018-08-07T13:58:51Z

@adriaanm Should I delete the branch or do you want it as a reference?

adriaanm · 2018-08-08T11:58:10Z

Deleting is fine. We use the merge commits for reference.

sjrd · 2018-08-08T14:28:34Z

src/library/scala/collection/immutable/LinkedMap.scala

+  }
+
+  @SerialVersionUID(3L)
+  final class LinkedMap1[K, +V](key1: K, value1: V) extends LinkedMap[K,V] with Serializable {


This should have been private, along with all the other ...N's, IMO.

Ah this must have been overlooked, should I make a PR to fix this?

@mdedetrich That would be awesome!

mdedetrich · 2018-08-10T09:17:24Z

@sjrd @adriaanm PR to fix the specializations being non private is here #7038

xuwei-k · 2018-08-15T14:25:38Z

scala/bug#11080

He-Pin · 2018-11-22T22:23:00Z

@mdedetrich Is there any reason that there is no SeqSet out there?

mdedetrich · 2018-11-25T23:17:10Z

@hepin1989 Don't think so, anyone is free to contribute such a collection (although I suspect its like for Scala 2.13)

Add LinkedMap/VectorMap

9ae3932

scala-jenkins added this to the 2.13.0-M5 milestone Jun 24, 2018

mkeskells reviewed Jun 25, 2018

View reviewed changes

julienrf reviewed Jun 25, 2018

View reviewed changes

Apply additional changes

a53a8d8

mdedetrich force-pushed the addLinkedVectorMap branch from 790f618 to a53a8d8 Compare June 25, 2018 21:25

mdedetrich force-pushed the addLinkedVectorMap branch from 5312fda to e942959 Compare June 26, 2018 23:21

Add ordering on withDefault test

76b3be0

mdedetrich force-pushed the addLinkedVectorMap branch from e942959 to 76b3be0 Compare June 26, 2018 23:24

julienrf reviewed Jun 27, 2018

View reviewed changes

Simplify newBuilder

9ed2358

Rename LinkedMap to SeqMap

07b7358

mdedetrich force-pushed the addLinkedVectorMap branch from 66e768c to 07b7358 Compare July 4, 2018 15:06

Add mutable.SeqMap plus make LinkedHashMap extend it

debe9bb

Add delegate for mutable.SeqMap to LinkedHashMap

b1f8f7c

jackkoenig mentioned this pull request Jul 6, 2018

Make InstanceGraph have defined iteration order chipsalliance/firrtl#843

Merged

SethTisue assigned szeiger Aug 7, 2018

SethTisue added the prio:blocker release blocker (used only by core team, only near release time) label Aug 7, 2018

SethTisue added the release-notes worth highlighting in next release notes label Aug 7, 2018

adriaanm merged commit a6170bd into scala:2.13.x Aug 7, 2018

lrytz mentioned this pull request Aug 7, 2018

Work around a local type inference limitation (fixes the build) #7010

Merged

sjrd reviewed Aug 8, 2018

View reviewed changes

mdedetrich deleted the addLinkedVectorMap branch August 8, 2018 21:31

SethTisue changed the title ~~Add SeqMap/VectorMap~~ Add immutable map that maintains insertion order (VectorMap/SeqMap) Aug 22, 2018

Add immutable map that maintains insertion order (VectorMap/SeqMap) #6854

Add immutable map that maintains insertion order (VectorMap/SeqMap) #6854

Uh oh!

Conversation

mdedetrich commented Jun 24, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mdedetrich commented Jun 24, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

julienrf left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mdedetrich commented Jun 25, 2018

Uh oh!

sjrd commented Jun 25, 2018

Uh oh!

mdedetrich commented Jun 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

SethTisue commented Jun 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sjrd commented Jun 25, 2018

Uh oh!

mdedetrich commented Jun 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sjrd commented Jun 25, 2018

Uh oh!

mdedetrich commented Jun 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sjrd commented Jun 25, 2018

Uh oh!

mdedetrich commented Jun 26, 2018

Uh oh!

mdedetrich commented Jun 24, 2018 •

edited

Loading

mdedetrich commented Jun 25, 2018 •

edited

Loading

SethTisue commented Jun 25, 2018 •

edited

Loading

mdedetrich commented Jun 25, 2018 •

edited

Loading

mdedetrich commented Jun 25, 2018 •

edited

Loading

martijnhoekstra commented Jul 2, 2018 •

edited

Loading

mdedetrich commented Jul 5, 2018 •

edited

Loading