Imported From: https://issues.scala-lang.org/browse/SI-4026?orig=1
Reporter: Piotr Koaczkowski (pkolaczk)
See #5331

@axel22 said:
Hello, thanks for reporting this!

Have you tried this with the trunk, after a recent commit:

https://lampsvn.epfl.ch/trac/scala/ticket/3796#comment:22

@dcsobral said:
Replying to [comment:1 prokopec]:

Hello, thanks for reporting this!

Have you tried this with the trunk, after a recent commit:

https://lampsvn.epfl.ch/trac/scala/ticket/3796#comment:22

Actually, that was a different issue. The original RedBlack code, the one that went into 2.8.0 and 2.8.1, was broken. The temporary fix was O(n), but never got released (as far as I know -- unless it went into 2.8.1 after all).

The problem referred to is here (scala.collection.immutable.TreeMap):

    val ntree = tree.range(from,until)
    new TreeMap[A,B](ntree.count, ntree)

Specifically, that count on ntree. On the other hand, turning NonEmpty's count into a {{val}} sounds reasonable. It can always be counted in constant time, because it only needs to add the counts of its (at most) two subtrees. And if those subtree's count have already been computed... And, of course, since the collection is immutable, there's no need to recompute.

It would make the memory footprint of RedBlack heavier. And if we went this way, I'd be much in favor of putting in a depth val too -- I missed it on range, and it usually helps with red&black algorithms.

@axel22 said:
@dcsobral: I've mistaken it for this commit - https://lampsvn.epfl.ch/trac/scala/changeset/23202/scala/trunk/src/library/scala/collection/immutable/RedBlack.scala, which didn't go to 2.8.1. as far as I know.

But, as far as the memory footprint goes, currently NonEmpty has 5 fields - $$outer reference and 4 other references. If "Rule 1: every object is aligned to an 8 bytes granularity." in Sun's JVM and this post are to be trusted ("http://www.codeinstructions.com/2008/12/java-objects-memory-structure.html"), then 4 bytes are lost anyway.

I wouldn't say that would hurt the memory footprint considerably, since clients of red black trees are already aware of them. So, I'd vote for adding the count field.

@retronym said:
TreeMap was reimplemented for Scala 2.10, these methods are efficient now.

https://github.com/scala/scala/commits?author=erikrozendaal