Map#keySet is slow in 3.8.0-RC3

[Zschimmer]

Compiler version

3.8.0-RC3

Minimized code

object ScalaTest:

  private val n = 10_000

  def main(args: Array[String]): Unit =
    val map: Map[Int, Unit] = (1 to n).map(i => i -> ()).toMap

    // FAST
    meter(".toMap"):
      map.contains

    // SLOW
    val set = map.keySet
    meter(".toMap.keySet"):
      set.contains

  private def meter[A](prefix: String)(f: Int => Boolean): Unit =
    val t = System.nanoTime() / 1_000_000
    for i <- 1 to n do if !f(i) then throw new NoSuchElementException
    println(prefix + " " + (System.nanoTime() / 1_000_000 - t) + "ms")

Output

.toMap 3ms
.toMap.keySet 105ms

Expectation

Checking whether a Set derived via the Map#keySet operation contains a key should not be slower than checking whether a Map contains a key. But it's really slow.

Probably due list traversal since e55df11.

The example's execution time grows quadratically with n.

When compiled with Scalac 3.7.4, the example has same short execution times in both cases.

[He-Pin]

Great, Maybe change the code to toIndexedSeq

[som-snytt]

There is history about keys and keySet as to specification and implementation:

scala/bug#11727
scala/scala#10544

scala/bug#12991
scala/scala#10766 (not merged)

It says if you want a view, use scala.collection.View.fromIteratorProvider(m.keysIterator).

at https://www.scala-lang.org/files/archive/api/current/scala/collection/Map.html#keySet-0

Edit: it says that the expected behavior is not guaranteed. Does that mean the implementation is free to change? or only that different implementations may have differing characteristics?

Edit: keysIterator should be ordered.