Insertion to a BindingSeq should not take O(log n) time

[Atry]

Current implementation use Vector, which consumes linear time when an element is inserted or removed in the middle of a BindingSeq.
While, finger tree could be O(1) or O(log n).

[deontologic]

Aren't Vectors effectively constant for inserts/deletion? Perhaps I don't understand your use case.

[Atry]

I meant Vector.patch method, which are called whenever a @BindingSeq changes

Binding.scala/Binding/src/main/scala/com/thoughtworks/binding/Binding.scala

Line 485 in 6ff5e1e

cache = cache.patch(event.from, mappedNewChildren, event.replaced)

Vector.patch is O(n) in current version (2.10.6 or 2.11.8) of Scala.

[deontologic]

Ah, I see.

I'd be careful using a finger tree, though. Despite having a great theoretical performance, actual implementations are pretty unsatisfactory (at least on the JVM). If you're considering using them over the default red-black trees, I'd recommend benchmarking.

I hope to read the source this weekend, so perhaps then I can be of more assistance

[Atry]

@kantianethics I agree. I changed the title of this issue in order to fit solutions other than finger tree.

[Atry]

I created an issue at https://issues.scala-lang.org/browse/SI-10001