Currently, if one wants to perform a `filter` foll...

# language-proposals

[Derek Peirce]

Currently, if one wants to perform a filter followed by a map on a list, they have two FP-style options that both have drawbacks:
items.filter { ... }.map { ... } requires two separate loops and creates an intermediate list after the filter step.
items.asSequence().filter { ... }.map { ... } creates two Sequence objects and cannot inline its lambdas.
Both of these fall well short of the optimal mutableListOf<T>().apply { items.forEach { item -> if (...) add(...) } } performance-wise, but that code is also not nearly as easy to write, read, or debug.
One of the goals of a language should be to minimize scenarios where programmers must choose between the code that is most efficient and the code that looks the best. To that end, I propose that we create an inlinable version of Sequence, or modify the existing class, which will require the ability to create an inline class that contain multiple properties, including lambdas that can then be inlined. For example:

inline interface Stream<T> { // inline here means that all implementations must be inline, and it should be possible to determine the implementation of any given Stream at compile-time
    fun forEach(operation: (T) -> Unit)
}

inline class IterableStream<T>(private val iterable: Iterable<T>): Stream<T> {
    override fun forEach(operation: (T) -> Boolean) {
        iterable.forEach { if (!operation(it)) return }
    }

}

inline class FilteringStream<T>(private val sourceStream: Stream<T>, private inline val predicate: (T) -> Boolean): Stream<T> {
    override fun forEach(operation: (T) -> Boolean) {
        sourceStream.forEach { item: T ->
            if (predicate(item)) {
                operation(item)
            } else {
                true
            }
        }
    }
}

inline class TransformingStream<T, R>(private val sourceStream: Stream<T>, private inline val transformer: (T) -> R): Stream<R> {
    override fun forEach(operation: (R) -> Boolean) {
        sourceStream.forEach { item: T ->
            operation(transformer(item))
        }
    }
}

inline fun <T> Iterable<T>.asStream() = IterableStream(this)
inline fun <T> Stream<T>.filter(predicate: (T) -> Boolean) = FilteringStream(this, predicate)
inline fun <T, R> Stream<T>.map(transformer: (T) -> R) = TransformingStream(this, transformer)
inline fun <T> Stream<T>.toList() {
    val list = ArrayList<T>()
    forEach { item -> list.add(item) }
}

After everything is inlined, it would turn this:

val processedItemNames = items
        .asStream()
        .filter { it.isProcessed }
        .map { it.name }
        .toList()

into this:

val processedItemNames = ArrayList<String>()
items.forEach { item -> if (item.isProcessed) processedItemNames.add(item.name) }

This would come with the limitation that you can't pass Stream as arguments to a function or return them from a function, unless those functions are inlined, but I don't think that would pose much of a limitation on their use in practice. Some operators like zip on two `Stream`s would also be tricky, though zipping a Stream with an Iterable or Sequence would be very doable.

When I brought this up on the discussion board, the primary concern was that it's not enough of a performance issue, so I ran some benchmarks. Not only is the optimal code significantly faster than the other two options, using sequences in my example code was actually significantly slower than using lists!
https://discuss.kotlinlang.org/t/sequences-and-inlined-lambdas/17228/11

There's also the issue of lambdas creating more bytecode, especially on Java 7, which is problematic for Android, a large motivation of this proposal is to eliminate that bytecode by making these lambdas able to be inlined.

[Dico]

You mentioned a problem with filter->map operation: non-optimal performance.

You suggested an interesting inline interface feature, where use of the interface must always be inlined.
Effectively having to inline large call graphs leads to huge (exponential) binary code size increase in practice. Therefore I think your proposal needs some more thought.

If you want to make a high performance version of filter->`map`, I suggest you think about flatMap. It can do the same things (and more), and it has the added benefit that you never have to repeat logic shared between the filter and map operation.

I suggest starting with stdlib flatMap. If you observe an actual performance issue with it (which I doubt you will), you can consider making your own version of it, with some inline class trickery wrapping a field of type Any?, where one specific reference indicates no value. Basically a zero overhead version of Optional<T>. If your mapped type is non-nullable, you can also just use mapNotNull out of the box.

[Derek Peirce]

A few things:
• I challenge the suggestion that this would lead to an exponential increase in bytecode size where used. As long as each Stream is written reasonably, this should incur less bytecode cost than using the corresponding List operations (and perhaps also less than the corresponding Sequence operations, because it doesn't have to create lambdas objects at runtime). This is the same consideration that already needs to be made for inline methods in general. You can see in my example that fully inlined call chain appears roughly the same size as it did pre-inlining, though I don't have exact bytecode calculations.
• flatMap and mapNotNull would be useful in this specific case, but what if I threw in a distinct or a take between the two steps, or wanted to apply more steps after, before returning to a List, or even just wanted to use forEach in the end, in which case every List call creates an unnecessary structure? And if nullable values are involved so that I must use flatMap, then the resulting code looks very messy, and creates many unnecessary List objects: list.flatMap { listOfNotNull(it.takeIf { it.condition }?.value) } I covered this in my original discussion post (though I incorrectly labeled it as filterNotNull ), but forgot to mention it again here.

[Derek Peirce]

I ran my performance tests again with your suggestions, and was very surprised:

Benchmark                                   (N)  Mode  Cnt  Score   Error  Units
FilterMapLoopHelper.loopFlatMapOnce      100000  avgt   10  8.329 ± 0.132  ms/op
FilterMapLoopHelper.loopFlatMapTwice     100000  avgt   10  7.414 ± 0.079  ms/op
FilterMapLoopHelper.loopMapNotNullOnce   100000  avgt   10  1.140 ± 0.030  ms/op
FilterMapLoopHelper.loopMapNotNullTwice  100000  avgt   10  1.204 ± 0.067  ms/op
FilterMapLoopHelper.loopOptimalOnce      100000  avgt   10  1.087 ± 0.060  ms/op
FilterMapLoopHelper.loopOptimalTwice     100000  avgt   10  1.073 ± 0.017  ms/op

First, flatMap is absolutely a no-go. I knew that creating a new List and Iterator object for each item would be detrimental, but it absolutely wrecked performance by up to 8x.
Second, I knew mapNotNull would ultimately be worse than the optimal case, but I didn't expect the difference to be so measurable with ten iterations.

[Dico]

You determined there is a measurable performance difference, however that is not a performance issue. What is your use case for this?

[Dico]

inline class Optional<T> 
internal constructor(private val inner: Any?) {
    fun isPresent() = inner !== Empty
    fun value() = inner as T
}

private val Empty = Symbol("empty")

fun empty() = Optional(Empty)
fun <T> some(value: T) = Optional(value)

You might be able to make a high performance sort of flat map like this

[Derek Peirce]

My use case is a codebase that has tens of thousands of list or sequence operations (the most common of which is filter followed by map, but there may also be steps between them) that each introduce suboptimal performance, unnecessary and costly lambdas, or both. I don't quite understand what your custom flatMap intends to do. If it's effectively flatMapOptional, then it still suffers from creating a new Optional object for every object that passes the filter, which is what doomed the original flatMap . Even if the Optional is fully inlined to avoid this, the call will still have to look something like .flatMapOptional { if (it.predicate) Optional(it.mappedValue) else empty() } which doesn't read nearly as well as filter { it.predicate }.map { it.value }, won't allow you to perform a step like take or distinct between filter and map, and is going to match mapNotNull in performance at best.