search

scala / bug

Scala 2 bug reports only. Please, no questions — proper bug reports only.
https://scala-lang.org
232 stars 21 forks source link

Now that immutable.Map keySet returns an immutable.Set in 2.9.0, there is no apparent way of accessing an effiicient Set-like view of the keys of an immutable Map #4616

Closed scabug closed 13 years ago

scabug commented 13 years ago

I have production code that looks like this

  aVeryBigCollection forall (e => aVeryBigImmutableMap.keySet(e.someProp))

This used to perform fine under 2.8.x because immutable.Map.keySet returned (correctly, in my opinion) a very cheap, set-like view of the keys of the immutable Map. It was an O(1) operation. Now it is an O(n) operation with no workaround to get back to O(1) (at least that I can find). I was also contend that the "principle of least surprise" is for keySet to return a view-like structure.

I suspect that this is a done deal and that there is no way of going back to the old behaviour, so I must request that there is a new method keysView or keySetView which provides the old functionality. In my experience keySet is almost always used in such a view-like manner

scabug commented 13 years ago

Imported From: https://issues.scala-lang.org/browse/SI-4616?orig=1 Reporter: @oxbowlakes See #4001

scabug commented 13 years ago

@ijuma said: I think we first need to understand the motivation for the change before considering a new method.

scabug commented 13 years ago

@dcsobral said: This was done at r23666, to fix #4001. Here's the log:

immutable.Map keySet returns immutable.Set.  Closes #4001, no review.

git-svn-id: http://lampsvn.epfl.ch/svn-repos/scala/scala/trunk@23666 5e8d7ff9-d8ef-0310-90f0-a4852d11357a

And that's that. Scala.collection.keySet returns a protected KeySet class that does the trick, while scala.collection.immutable.keySet creates a new collection.

Commit by extempore.

scabug commented 13 years ago

@SethTisue said: this code shows the performance regression:

val m = Iterator.from(1).map(x => x -> x).take(100000).toMap
Iterator.continually(m.keySet).drop(1000).next

in 2.8 it runs in a fraction of a second, in 2.9 it takes 57 seconds.

scabug commented 13 years ago

@ijuma said: It should be possible to use a view for this without changing the signature again unless I am missing something.

scabug commented 13 years ago

@paulp said: Fixed in r24992.