IntMap / LongMap.tail very slow #13148
Description
IntMap / LongMap.tail is implemented as drop(1), which turns out to be very slow. Implementation using removed(head) is much faster.
Reproduction steps
Scala version: 3.7.4, 2.13.18
import scala.collection.immutable
import scala.util.Random
object Main {
def main(args: Array[String]): Unit = {
val items = List.tabulate(20_000)(_ => Random.nextInt() -> ())
val longMap = immutable.IntMap.from(items)
// warm-up
(0 until 1_000).foldLeft(longMap)((acc, _) => acc.tail)
(0 until 1_000).foldLeft(longMap)((acc, _) => acc.removed(acc.head._1))
{
val start = System.nanoTime()
(0 until 5_000).foldLeft(longMap)((acc, _) => acc.removed(acc.head._1))
val end = System.nanoTime()
println(s"acc.removed(head): ${(end - start) / 1e6} ms")
}
{
val start = System.nanoTime()
(0 until 5_000).foldLeft(longMap)((acc, _) => acc.tail)
val end = System.nanoTime()
println(s"acc.tail: ${(end - start) / 1e6} ms")
}
}
}Problem
Output of the program above is like:
acc.removed(head): 2.4249 ms
acc.tail: 4841.3555 ms
IntMap and LongMap do not override tail, they just inherit Iterable implementation which is implemented using drop(1). For large collections such implementation is several orders of magnitude slower, it seems to rebuild the whole collection.