Would you consider inplace collection operations?


#1

All Iterable.* extension methods, for example filter() and map(), create a new ArrayList and place the output there. This of course introduces the overhead of creating a new ArrayList every time I call one of those methods, which may get ugly when multiple methods are chained together.

I learned that there in fact is in-place filter operation - the MutableIterable.retainAll() and its counterpart MutableIterable.removeAll(), which is great. Unfortunately there is no mapInPlace().

In particular, mapInPlace could be implemented not on top of MutableIterable, but rather on top of ListIterator. While technically possible, it seems just weird having *inPlace() counterparts of all Iterable.* methods… So, perhaps would you consider implementing only a subset of those methods, like mapInPlace and perhaps a couple of others?

Many thanks, and I apologize if this question has been already answered elsewhere.


#2

Is it something like List.replaceAll from Java 8? We’re going to expose this method on MutableList in Kotlin 1.1, if you target java 8.


#3

If you have a big sequence of operations of operations and are concerned about this overhead, you might want to convert to a sequence and only convert back to a list at the end (if you actually need to do that). Sequence works on Iterables.


#4

@dalewking Thank you. Sequences definitely are a valid option. Yet, sequence methods effectively call anonymous class’s method for every sequence item, which I am worried that may introduce a measurable overhead, especially on Android phones. However, perhaps the JVM (or Dalvik) inlines those calls at runtime (or ART inlines them upon compilation), producing the desired output.

For example, let us discuss this code: persons.filter { it.age < 50 } .map { it.name }.joinToString(). I know that there is more effective version (persons.filter { it.age < 50 }.joinToString(transform -> { it.name })) but please bear with me :wink:

The code produced by the kotlin compiler is very efficient because of inlining, but still it creates two intermediate lists, which introduces certain overhead. When using sequences, the memory overhead is replaced by CPU overhead, by calling methods of anonymous classes. Yet, there is more effective (and more ugly) java code:

StringBuilder sb = new StringBuilder();
for (Person p: persons) {
  if (sb.length() != 0) sb.append(", ");
  if (p.age < 50) sb.append(p.name);
}

Is there some way in kotlin to somehow combine/chain the Iterable methods, so that the code produced looks like the code above? Or perhaps the overhead is insignificant and I am just asking stupid questions? :slight_smile:

@ilya.gorbunov thank you very much for your tips. From List.replaceAll I actually learned that my mapInPlace may have limited uses, as it may only be used for functions (T)->T. Basically, what I tried to ask is whether the overhead introduced by chaining of the Iterable methods is any significant, and if it is, is it possible to avoid the overhead.


#5

I don’t have much more to add, I was just making sure you knew that with sequences you avoid the overhead of creating the list at each step. That could be a huge win if you for example had a huge list that you did a map on then a filter that filtered that to only a few items. Depends on the problem whether that is the best choice.

I think the overhead of the anonymous class is a limitation of the JVM that could probably only be eliminated when the JVM gets value objects. Each method has to return something. That is either a primitive or an object.

The asynch stuff coming in 1.1 with the ability to do a yield may be an improvement on this as well.