https://kotlinlang.org logo
#language-proposals
Title
# language-proposals
d

Derek Peirce

05/02/2020, 2:22 AM
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:
Copy code
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:
Copy code
val processedItemNames = items
        .asStream()
        .filter { it.isProcessed }
        .map { it.name }
        .toList()
into this:
Copy code
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.
d

Dico

05/03/2020, 9:55 AM
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.
d

Derek Peirce

05/04/2020, 1:00 AM
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.
I ran my performance tests again with your suggestions, and was very surprised:
Copy code
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.
d

Dico

05/04/2020, 5:53 PM
You determined there is a measurable performance difference, however that is not a performance issue. What is your use case for this?
Copy code
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
d

Derek Peirce

05/05/2020, 1:47 AM
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.
2 Views