search

Kotlin / kotlinx.collections.immutable

Immutable persistent collections for Kotlin
Apache License 2.0
1.12k stars 56 forks source link

Consider `addAll` special cases #154

Open chuckjaz opened 8 months ago

chuckjaz commented 8 months ago

When a PersistentVector<T> is added to another PersistentVector<T> through addAll this can be optimized and, when the shift alligns, layers of the vector, as a whole, can be copied over instead of copying individual elements. Even if the shifts don't allgin, copyInto can be used instead of going through the addAll of the builder which can avoid several otherwise unncessary allocations and virtual dispatches.

A similar technique can be used for the TrieNode for the PersistentHashMap but the special cases end up not being nearly as rare as it will often be the case when whole TrieNodes can be copied from one PersistentHashMap to another.

develar commented 8 months ago

Yes, this is quite essential. For instance, the IJ Platform uses this for the implementation of extensions. A pattern like "get all extensions and merge with another one" is quite popular. If it will behave as described above, it will provide a good reason to prefer the kotlinx collections library over the Java immutables one.