The ViewGroup.descendant function is very slow because it uses sequence.yield [316568512]

Fixed

Feature Request

Status Update

No update yet.

Description

ma...@gmail.com

created issue #1

Dec 16, 2023 12:25PM

Component used: androidx.core.view

I'm writing an article about different ways to optimize recursion. I found that the standard ViewGroup.descendant function is very, very slow. This is because it uses slow calls to yield, yieldAll. I think this function is used by so many developers and it's too bad that it works so slowly.

You can see this for yourself if you look at the measurement results

https://github.com/maxssoft/yield_recursion

Test results for find view in view hierarchy

main summary: depth of hierarchy = 1000 
Benchmark                             Mode  Cnt      Score   Error  Units
RecursionTest.treeIteratorBenchmark  thrpt        6982,174          ops/s
RecursionTest.yieldBenchmark         thrpt          61,194          ops/s

main summary: depth of hierarchy = 3000 
Benchmark                             Mode  Cnt      Score   Error  Units
RecursionTest.treeIteratorBenchmark  thrpt        3182,863          ops/s
RecursionTest.yieldBenchmark         thrpt           6,055          ops/s

main summary: depth of hierarchy = 5000 
Benchmark                             Mode  Cnt     Score   Error  Units
RecursionTest.treeIteratorBenchmark  thrpt       1310,270          ops/s
RecursionTest.yieldBenchmark         thrpt          1,826          ops/s

https://github.com/maxssoft/yield_recursion/blob/develop/benchmarks/src/main/java/com/maxssoft/test/RecursionTest.kt

Optimization

I want to propose a solution based on my lazy tree iterator that speeds up this function by hundreds and thousands of times. https://github.com/maxssoft/yield_recursion/blob/develop/benchmarks/src/main/java/com/maxssoft/func/TreeIterator.kt

Source code of the optimized function and TreeIterator

/**
 * Optimized descendants function based on lazy [TreeIterator]
 * This function works hundreds of times faster than the original function descendants
 */
public val ViewGroup.descendantsTree: Sequence<View>
    get() = TreeIterator(children.iterator()) { (it as? ViewGroup)?.children?.iterator() }.asSequence()

/**
 * Find views by hierarchy with predicate
 * Demonstrate using [TreeIterator] for optimize recursion
 */
fun ViewGroup.findViewTreeIterator(predicate: (View) -> Boolean): Sequence<View> {
    return sequenceOf(this)
        .plus(descendantsTree)
        .filter { predicate(it) }
}

/**
 * Lazy iterator for iterate by abstract hierarchy
 * @param rootIterator Iterator for root elements of hierarchy
 * @param getChildIterator function which get child iterator for current item
 * if current item has child return child iterator else return null
 *
 * Example of using for ViewGroup hierarchy
 * TreeIterator<View>(viewGroup.children.iterator) { (it as? ViewGroup)?.children?.iterator() }
 *
 * @author Max Sidorov on 15.12.2023
 */
class TreeIterator<T>(
    rootIterator: Iterator<T>,
    private val getChildIterator: ((T) -> Iterator<T>?)
) : Iterator<T> {
    private val stack = mutableListOf<Iterator<T>>()

    private var iterator: Iterator<T> = rootIterator

    override fun hasNext(): Boolean {
        return iterator.hasNext()
    }

    override fun next(): T {
        val item = iterator.next()
        prepareNextIterator(item)
        return item
    }

    /**
     * calculate next iterator for [item]
     * if current item has child then get child iterator and save current iterator to stack
     * else if current iterator hasn't more elements then restore parent iterator from stack
     */
    private fun prepareNextIterator(item: T) {
        val childIterator = getChildIterator(item)
        if (childIterator != null && childIterator.hasNext()) {
            stack.add(iterator)
            iterator = childIterator
        } else {
            while (!iterator.hasNext() && stack.isNotEmpty()) {
                iterator = stack.last()
                stack.removeLast()
            }
        }
    }
}

Comments

al...@google.com <al...@google.com> #2Dec 18, 2023 03:17PM

It's really odd that yield was used here in the first place. +cc adamp in case he can discern a reason.

I want to propose a solution based on my lazy tree iterator that speeds up this function by hundreds and thousands of times.

I can copy/paste that in, but if you want proper commit attribution you can use our GitHub or AOSP contribution workflows.

ma...@gmail.com <ma...@gmail.com> #3Dec 18, 2023 06:25PM

Oh yes, I'll try it. I didn't know that this was possible)

al...@google.com <al...@google.com> #4Dec 19, 2023 07:48PM

Reassigned to bu...@google.com.

Bugjuggler: wait 2 weeks

Putting this on ice until either (a) I get a notification from Gerrit / GitHub or (b) I get back from vacation. Please leave a comment if you have a commit up somewhere for review.

bu...@google.com <bu...@google.com> #5Dec 19, 2023 07:48PM

Accepted by bu...@google.com.

Hi. I've received your bug and will wait until 2024-01-02 14:48 -0500 EST and then assign the bug to alanv@google.com.

ma...@gmail.com <ma...@gmail.com> #6Dec 26, 2023 07:44AM

I tried to do this, but I lost my brain until I understood how it works. It is necessary to correct the instructions for contribution and add instruction importMaven.md about loading prebuilts dependencies. I spent the whole day trying to figure out how I can download these dependencies. I found it by searching the source code when I was looking for where prebuilts dependencies are declared.

I have configured the dependencies, but now I get an error when I try to run the command

cd Development/androidx/playground-projects/core-playground
./gradlew studio

I'm getting an error in LibraryVersionsService.kt

> Task :supportBuildSrc:private:compileKotlin
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:23:12 Unresolved reference: tomlj
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:24:12 Unresolved reference: tomlj
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:25:12 Unresolved reference: tomlj
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:36:33 Unresolved reference: TomlParseResult
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:36:52 Property delegate must have a 'getValue(LibraryVersionsService, KProperty<*>)' method. None of the following functions is suitable: 
public inline operator fun <T> Lazy<???>.getValue(thisRef: Any?, property: KProperty<*>): ??? defined in kotlin
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:37:22 Unresolved reference: Toml
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:41:51 Unresolved reference: it
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:41:69 Unresolved reference: it
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:48:40 Unresolved reference: TomlTable
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:54:50 Property delegate must have a 'getValue(LibraryVersionsService, KProperty<*>)' method. None of the following functions is suitable: 
public inline operator fun <T> Lazy<Map<String, Version>>.getValue(thisRef: Any?, property: KProperty<*>): Map<String, Version> defined in kotlin
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:56:43 Cannot infer a type for this parameter. Please specify it explicitly.
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:115:76 Property delegate must have a 'getValue(LibraryVersionsService, KProperty<*>)' method. None of the following functions is suitable: 
public inline operator fun <T> Lazy<List<LibraryGroupAssociation>>.getValue(thisRef: Any?, property: KProperty<*>): List<LibraryGroupAssociation> defined in kotlin
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:118:47 Unresolved reference: TomlTable
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:120:29 Overload resolution ambiguity: 
public fun File.startsWith(other: String): Boolean defined in kotlin.io
public fun CharSequence.startsWith(prefix: CharSequence, ignoreCase: Boolean = ...): Boolean defined in kotlin.text
public fun String.startsWith(prefix: String, ignoreCase: Boolean = ...): Boolean defined in kotlin.text
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:133:40 Cannot infer a type for this parameter. Please specify it explicitly.
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:140:24 Not enough information to infer type variable  for subcalls of if expression
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:150:75 Not enough information to infer type variable T
e: file:///Users/17543251/Development/androidx/buildSrc/private/src/main/kotlin/androidx/build/LibraryVersionsService.kt:151:21 Unresolved reference: it

> Task :supportBuildSrc:private:compileKotlin FAILED

FAILURE: Build failed with an exception.

I almost gave up, maybe it would be better if you made the corrections yourself.

Message last modified on Dec 26, 2023 07:47AM

bu...@google.com <bu...@google.com> Jan 2, 2024 07:55PM

Assigned to al...@google.com.

al...@google.com <al...@google.com> #7Jan 2, 2024 07:59PM

Yep, I can take care of it. I think I have "forge author" rights, so we can probably still get you on the commit as author.

al...@google.com <al...@google.com> #8Jan 3, 2024 08:53PM

Accepted by al...@google.com.

Up for review at https://android-review.googlesource.com/2896460.

je...@google.com <je...@google.com> #9Jan 4, 2024 09:51PM

Oh hey this seems super cool to me; thanks!

A potential clarification:

I think the slowness of the yieldAll() approach isn't necessarily that yieldAll() processes an individual element more slowly, but that the current approach using yieldAll() can pass an individual element through yieldAll() many times: once per level of the hierarchy.

Perhaps a clearer description would be something more like "ViewGroup.descendant is very, very slow because it constructs a new Sequence for each level of the hierarchy."

Thanks again!

ma...@gmail.com <ma...@gmail.com> #10Jan 8, 2024 10:03AM

I implemented DSF, BSF algorithms for treeIterator. I think this will be useful if you want to add this iterator to common functions. https://github.com/maxssoft/yield_recursion/blob/develop/benchmarks/src/main/java/com/maxssoft/func/TreeIterator.kt

ap...@google.com <ap...@google.com> #11Jan 12, 2024 12:07AM

Marked as fixed.

Project: platform/frameworks/support
Branch: androidx-main

commit 68930c1b6df3672e70be7394a1ce30e96ebd855d
Author: Max Sidorov <maxssoft@gmail.com>
Date: Wed Jan 03 15:20:41 2024

Improve efficiency of ViewGroup.descendants using lazy tree iterator

Includes some minor formatting and documentation changes from original
proposal in the linked issue, including replacing `.asSequence()` with
`Sequence { ... }` to obtain an unconstrained sequence.

Benchmarks from original author:

https://github.com/maxssoft/yield_recursion

Fixes: 316568512
Test: ViewGroupTest
Change-Id: I0a38193d207d1573eddc333fef11bb0ae0e56070

M core/core-ktx/src/main/java/androidx/core/view/ViewGroup.kt

https://android-review.googlesource.com/2896460

na...@google.com <na...@google.com> #12Jan 24, 2024 07:53PM

The following release(s) address this bug.It is possible this bug has only been partially addressed:

androidx.core:core-ktx:1.13.0-alpha04