Currently, the `count(predicate)` extension method...

# stdlib

[Derek Peirce]

Currently, the count(predicate) extension method is written for each type as:

public inline fun ByteArray.count(predicate: (Byte) -> Boolean): Int {
    var count = 0
    for (element in this) if (predicate(element)) ++count
    return count
}

However, this could be improved by instead writing it as:

public inline fun ByteArray.count(predicate: (Byte) -> Boolean): Int {
    var count = 0
    for (element in this) count += if (predicate(element)) 1 else 0
    return count
}

This is because the compiler can easily convert the ternary 1/0 as a boolean-to-int cast, and avoid using branches altogether, paying no penalty for missed predictions.
I ran a benchmark comparing the two implementation on a random 100,000 bytes (using Java Microbenchmark Harness), counting either 0s or even numbers, and got these results:

Benchmark                         Mode  Cnt   Score   Error  Units
CountBenchmark.countEvensAsInt    avgt   20  44.290 ± 0.879  us/op
CountBenchmark.countEvensBuiltin  avgt   20  53.830 ± 0.974  us/op
CountBenchmark.countZerosAsInt    avgt   20  28.937 ± 0.811  us/op
CountBenchmark.countZerosBuiltin  avgt   20  17.543 ± 0.136  us/op

That's a fairly significant reduction in count overhead.

[CLOVIS]

Shouldn't this be a thread in #C7L3JB43G to improve the compiler's matching? I'm pretty sure these two lines are semantically equivalent on the Kotlin language side, so the compiler should be able to optimize them both identically.

[Derek Peirce]

Improving the compiler would be ideal, identifying the specific case of if (boolValue) ++variable and turning into variable += if (boolValue) 1 else 0 when variable is guaranteed to be quickly accessible and not an object field or array value, but I expect improving the count method, at least at first, would be faster.

[CLOVIS]

Sure, it's faster, but one of the main design precepts of Kotlin is that the most obvious code should be the best one

[Derek Peirce]

I strongly agree (I made a post here before about how the most obvious code for chained sequence operations is often considerably less efficient than hand-written iteration, which is very unfortunate), I'll post this in #C7L3JB43G as well.

[CLOVIS]

I'm interested if you could update the benchmarks you published in the thread now that K2 is out. Maybe the situation has improved.

[CLOVIS]

But yeah what you're proposing is essentially how Rust does iterators, but Rust and Kotlin are quite different

[Derek Peirce]

Using Kotlin 2.1, and Kotlin compiler 2.2.21, and updating the code a bit to account for some deprecated methods, I got this result:

Benchmark                                   Mode  Cnt    Score    Error  Units
ScrabbleBenchmark.kotlinScrabbleFunctional  avgt   20  368.605 ± 14.725  ms/op
ScrabbleBenchmark.kotlinScrabbleImperative  avgt   20  263.723 ± 12.468  ms/op

When I ran this about six years ago on a different machine, imperative was a 13% time reduction. Here, it's a 29% time reduction.

[CLOVIS]

You should share those results in the forum thread, that may help revive it

[CLOVIS]

Lots of stuff has changed since then, and extended value class are currently in discussion, this may be a relevant point to those

[Derek Peirce]

Will do!