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 https://github.com/ThoughtWorksInc/Binding.scala/blob/6ff5e1e8d79d44916c2e79b5642f1296ed2856f4/Binding/src/main/scala/com/thoughtworks/binding/Binding.scala#L485

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