Performance issue in widget.List

[LaGregance]

Checklist

• I have searched the issue tracker for open issues that relate to the same problem, before opening a new one.
• This issue only relates to a single bug. I will open new issues for any other problems.

Describe the bug

Working with a really simple program using huge widget.List, I can see that there is two problems.

At the top of the list everything is working well, but as we go closer to the bottom two leaks appears:

1. It's start to be more and more slow (lag)
2. An offset appear when we select an item, that make the list goes up with no reason (the closer to the end, the bigger the offset is)

Video to see the problem: https://www.loom.com/share/0c2d5393fad9451cad7e8b0bb5d26676

How to reproduce

We just have to create a huge widget.List (actually I did it with 300000 items).

You can use this repo to reproduce (I added a TextField when you can put a number to directly go to the specified line).
https://github.com/LaGregance/fyne-listview-issue
Then just run go run .

Screenshots

Video: https://www.loom.com/share/0c2d5393fad9451cad7e8b0bb5d26676

Example code

package main

import (
	"fyne.io/fyne/v2"
	"fyne.io/fyne/v2/app"
	"fyne.io/fyne/v2/container"
	"fyne.io/fyne/v2/widget"
	"strconv"
)

func main() {
	a := app.New()
	win := a.NewWindow("Fyne ListView Issue")
	win.SetMaster()
	win.Resize(fyne.NewSize(1024, 700))

	listSize := 300000
	listWidget := widget.NewList(
		func() int {
			return listSize
		},
		func() fyne.CanvasObject {
			return widget.NewLabel("Template Object")
		},
		func(id widget.ListItemID, item fyne.CanvasObject) {
			item.(*widget.Label).SetText(strconv.Itoa(id) + " - aaaaaaa")
		},
	)

        // For convenience only, field to go to a specified line
	gotoField := widget.NewEntry()
	gotoField.OnSubmitted = func(idStr string) {
		id, err := strconv.Atoi(idStr)
		if id > 0 && err == nil {
			listWidget.Select(id)
		}
		gotoField.SetText("")
	}
        // ---------------------------------------------------

	win.SetContent(container.NewBorder(gotoField, nil, nil, nil, listWidget))
	win.ShowAndRun()
}

Fyne version

2.3.3

Go compiler version

1.20.1

Operating system and version

MacOS Ventura 13.2.1 (M1)

Additional Information

No response

[Bluebugs]

Just run a quick pprof as I had a hunch where this problem is coming from. On a 30s tests scrolling around, 24s is spend in list.visibleItemHeights which is a O(n) complexity and so show problem as the number of item increase. 13s could be shaved by caching the value of theme.Padding() at the top of the function.

Potentially a better fix, iterate on the the list itemHeights map instead so that n for the common case stays 0. List that use custom height could benefit from having some caching as iterating is definitively not a good approach as the number of item increase.

[LaGregance]

Interesting things.

Indeed I also think iterating isn't a good solution. Considering a list with a fixed itemHeight, a simple equation can solve this problem.

To manage list with custom heights, in SetItemHeight we may save another variable like itemIdsWithCustomSize []ListItemID which is the array of item ids that have a custom height (ideally should be keep sorted).
With that in visibleItemHeights we can calculate the rowOffset like that:

rowOffset := float32(0)
lengthWithoutCustomSize := length
for _, id := range l.itemIdsWithCustomSize {
    rowOffset += l.itemHeights[id] + theme.Padding()
    lengthWithoutCustomSize--
}
rowOffset += lengthWithoutCustomSize*(itemHeight + theme.Padding())

[Bluebugs]

That would still be quite linear complexity. If we continue to expect custom height to be an exception, we can just iterate over the map and discard position that are not inside the range of the current item position we are calculating. At the end of the loop, we can just calculate the space left as you did above. This is an O(n) complexity where n is the number of item with custom height.

I think the code can be reorganized to some extend so that instead of calling this O(n) complex algorithm for each visible item, it is called only once per scrolling event. Basically you calculate the top visible item and then you just iterate down from there. Maybe updating an array of position at once.

Additionally caching the value of theme.Padding() during the computation of that array would clearly improve performance too. Taking lock are really costly and should be avoided during hot path.

If we want to handle large amount of custom item height, I think the way forward for faster handling of custom size would be by caching. If we want to handle 300000 of them (currently your tests is not custom height, not sure it is needed). Most likely a tree of cache would be necessary, something where you have a first level of array that cache position every 1000 items, then another one that cache every 10000 and so on. When you are looking for the offset positioning, you pick the highest number the closer to your target. Then you go one step down and again select the closest offset (adding or subtracting it) walking a binary tree search basically. Once you are in between two first level entry (with each 1000 entries) you iterate going up or down. So instead of using a map, it would be logical to store the custom height in a sorted on position array per 1000 entries.

With this the worst case scenario for list below a million entry, would be one lookup in the 100000
cache level, followed by one in the 10000, followed by one in the 1000 level. There it would iterate on up to 500 entry to calculate the offset. This would speed up jumping to a position or fast scrolling. It might be necessary to use a sparse array for this and that would likely impact the complexity of the walk in the cache, but would save memory.

I think I am going to go ahead and implement the first three improvement and we can see later if anyone is heavily using custom item size to the point it needs to be really fast.

[LaGregance]

Wow, really impressive reasoning. Thank you for taking care of this issue.
Considering your solution, I'm not sure to understand the purpose of having 2 level of caching, one per 1000 & one per 10000, because if you only have the caching per 1000 entries you got in fine the cache per 10000 entries.

[Bluebugs]

It might be ok to skip the 10000 cache level, some benchmark will be useful at that point. It will be a trade-off between the use of a sparse array, the minimal target devices we want to support and with how much data we want to be able to push on this devices.

[Bluebugs]

As this issue was not including any custom item height case, I think that PR #3822 should address the problem at hand. If someone has a performance issue when using item height, we can come back to it and improve things again.

[LaGregance]

So fast ! Thank you

[Bluebugs]

And PR landed in develop, this should be good for now.