Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

mutable.ListMap should preserve insertion order #9893

Closed
scabug opened this issue Aug 17, 2016 · 10 comments · Fixed by scala/scala#6700
Closed

mutable.ListMap should preserve insertion order #9893

scabug opened this issue Aug 17, 2016 · 10 comments · Fixed by scala/scala#6700

Comments

@scabug
Copy link

scabug commented Aug 17, 2016

Scala 2.9:

scala> val m = collection.mutable.ListMap[Int, Int]()
m: scala.collection.mutable.ListMap[Int,Int] = Map()

scala> m += 1 -> 1
res0: m.type = Map(1 -> 1)

scala> m += 2 -> 2
res1: m.type = Map(2 -> 2, 1 -> 1)

scala> m += 3 -> 3
res2: m.type = Map(3 -> 3, 2 -> 2, 1 -> 1)

scala> m += 4 -> 4
res3: m.type = Map(4 -> 4, 3 -> 3, 2 -> 2, 1 -> 1)

scala> m += 5 -> 5
res4: m.type = Map(5 -> 5, 4 -> 4, 3 -> 3, 2 -> 2, 1 -> 1)

scala> m -= 99
res5: m.type = Map(5 -> 5, 4 -> 4, 3 -> 3, 2 -> 2, 1 -> 1)

scala> m -= 3
res6: m.type = Map(5 -> 5, 4 -> 4, 2 -> 2, 1 -> 1)

but Scala 2.10.6 scrambles the order:

scala> val m = collection.mutable.ListMap[Int, Int]()
m: scala.collection.mutable.ListMap[Int,Int] = Map()

scala> m += 1 -> 1
res0: m.type = Map(1 -> 1)

scala> m += 2 -> 2
res1: m.type = Map(2 -> 2, 1 -> 1)

scala> m += 3 -> 3
res2: m.type = Map(3 -> 3, 1 -> 1, 2 -> 2)

scala> m += 4 -> 4
res3: m.type = Map(4 -> 4, 2 -> 2, 1 -> 1, 3 -> 3)

scala> m += 5 -> 5
res4: m.type = Map(5 -> 5, 3 -> 3, 1 -> 1, 2 -> 2, 4 -> 4)

scala> m -= 99
res5: m.type = Map(4 -> 4, 2 -> 2, 1 -> 1, 3 -> 3, 5 -> 5)

scala> m -= 3
res6: m.type = Map(1 -> 1, 2 -> 2, 4 -> 4, 5 -> 5)

The intent that either ListMap should preserve insertion order wasn't explicit in the doc until scala/scala#4788 and scala/scala#4994, and there's some confusion at http://stackoverflow.com/questions/7539924/why-do-mutable-and-immutable-listmaps-have-different-orders-in-scala and https://twitter.com/travisbrown/status/735201036873400321 about what the behavior should properly be.

But I think not preserving the order is just absurd. There's no downside to preserving. Also, note that http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#list_maps implies that the only reason to use a ListMap at all is if you care about the order.

@scabug
Copy link
Author

scabug commented Aug 17, 2016

Imported From: https://issues.scala-lang.org/browse/SI-9893?orig=1
Reporter: @SethTisue
Affected Versions: 2.10.6, 2.11.8

@scabug
Copy link
Author

scabug commented Aug 17, 2016

@SethTisue said:
There remains an issue of what order we want: are new items inserted at the back or the front?

mutable.ListMap is implemented as a very simple wrapper around scala.collection.immutable.List. As a natural consequence, new items are added to the front.

immutable.ListMap doesn't work that way — it's implemented on top of a private Node class. internally, it adds items on the front, but then it does def iterator = ... .toList.reverseIterator so the externally observable order is forwards. Note that this is expensive, as both toList and reverseIterator copy the whole collection.

@scabug
Copy link
Author

scabug commented Aug 17, 2016

@SethTisue said:
So, what is to be done? There are different possibilities, and there are different considerations depending on whether a fix is targeting 2.11.x, 2.12.x, or 2.13.x.

in ascending order of ambitiousness, possibilities include:

  • document the existing (gruesome) 2.10/2.11 behavior
  • restore the 2.9 behavior (both kinds of ListMap preserve order, but in opposite directions) and document that
  • choose a direction and make both kinds of ListMap preserve it, redoing the implementations if necessary

Note that wrapping immutable.List is a really terrible way to implement mutable.ListMap — tons of unnecessary copying.

@scabug
Copy link
Author

scabug commented Aug 17, 2016

@Ichoran said (edited on Aug 17, 2016 9:02:39 PM UTC):
ListMap and ListSet have basically zero reason to exist if they don't preserve insertion order. Except there isn't even a mutable.ListSet. I think this suggests that the mutable one should just be deprecated. If you reeeeeally need the functionality of traversal-in-order, there is LinearHashMap/Set, and if you reeeeeeally need speed you should implement your own anyway. In the meantime, before deprecation kicks in, insertion order is probably a good thing to preserve. I have no strong feeling about which order.

For immutable.ListSet/Map, I think either order is okay as long as it is incredibly clear what the expectation is, and it is followed for every operation. That is: head gives you the most recent item and iteration is always from recent to older; or head gives you the oldest item and iteration is always from recent to older. And this property should be maintained through map, flatMap, etc. (which will mean using builders to create the underlying links because otherwise the order will switch every time you map).

@scabug
Copy link
Author

scabug commented Oct 19, 2016

Dmytro Kondratiuk (dk14) said (edited on Oct 19, 2016 1:29:07 AM UTC):
I've noticed that LinkedHashMap works as expected, but it also (same as mutable.ListMap) seems to have 0 tests for ordering (https://github.com/scala/scala/blob/2.12.x/test/junit/scala/collection/mutable/LinkedHashMapTest.scala).

scala> val m = collection.mutable.LinkedHashMap[Int, Int]()
m: scala.collection.mutable.LinkedHashMap[Int,Int] = Map()

scala> m += 1 -> 1
res42: m.type = Map(1 -> 1)

scala> m += 2 -> 2
res43: m.type = Map(1 -> 1, 2 -> 2)

scala> m += 3 -> 3
res44: m.type = Map(1 -> 1, 2 -> 2, 3 -> 3)

scala> m += 4 -> 4
res45: m.type = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4)

scala> m += 5 -> 5
res46: m.type = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5)

scala> m -= 99
res47: m.type = Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5)

scala> m -= 3
res48: m.type = Map(1 -> 1, 2 -> 2, 4 -> 4, 5 -> 5)

@scabug
Copy link
Author

scabug commented Oct 19, 2016

@Ichoran said:
[~dk14] A PR to fix this deficiency in the tests is welcome!

@scabug
Copy link
Author

scabug commented Nov 12, 2016

@ruippeixotog said:
Just to add that I recently made some modifications to immutable.ListSet and immutable.ListMap in order to make them behave in a more consistent way. Initially I tried to to make the immutable.ListSet iterator provide the elements in reverse order for performance reasons, but I was forced to do the other way around as it seems the compiler depends on the current iteration order of ListSet for some things. That's the reason why toList.reverseIterator was kept there. The PR is scala/scala#5103.

@scabug
Copy link
Author

scabug commented Jan 14, 2017

Apoorv Agarwal (apoorv024) said:
https://issues.scala-lang.org/browse/SI-9893?focusedCommentId=75566&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-75566

I was thinking of adding test cases for ordering here. Are those tests still needed?

@lrytz
Copy link
Member

lrytz commented Apr 23, 2018

@julienrf @szeiger should we deprecate mutable.ListMap in 2.13? People should just use a var immutable.ListMap instead, the current implementation (besides being buggy) doesn't add any value.

@lrytz lrytz modified the milestones: 2.13.0-M4, 2.13.0-M5 Apr 23, 2018
@julienrf
Copy link

I’m happy to deprecate mutable.ListMap

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

6 participants