Support optimized list rendering

[jtdaugherty]

Right now, the List rendering process utilizes the viewport feature to simplify scrolling state tracking. While that means the list supports variable-height list items, it means we pay a (possibly big) penalty since we render all list items regardless of visibility and then crop to show the ones in view. This works fine for small lists, but the delay in rendering becomes noticeable even for realistically sized lists (thousands of elements).

This clearly isn't great.

I initially thought supporting variable-height list items as well as uniform-height items would be a slam-dunk but I'm now thinking that an optimized list is really needed in the (common) case where you know that the heights of all of your list items will be the same number of rows. The only way we can know which subset of list elements to bother rendering is by knowing how high they will be in advance, a luxury we don't have if we assume the item heights can't be precomputed. But if we restrict ourselves to the assumption that the list items all have the same known height, we can use the scrolling state and viewport size to select only the items worth rendering.

I think this is feasible, but it might increase the burden on the user slightly and might have some trade-offs that need consideration. This ticket is a reminder for me to implement this and to jot down notes about what I have in mind.

(CC @simonmichael)

[jtdaugherty]

While thinking about this I went ahead and made a small improvement to the list API in d7bf9e1 which moved the list element drawing function from being in the list state itself to being a parameter to renderList, thus further separating the presentation and state concerns.

[jtdaugherty]

I also changed lists to use Vector e instead of [e] in 14d2147 since many vector operations are O(1) while their list counterparts are O(n).

[jtdaugherty]

I've pushed a commit (693abbb) to address this. The only user-facing change is that renderList now takes an item height (in rows) and all item widgets returned by the item drawing function must match that height (or else). It's in the feature/long-lists branch. Give that a try.

[jtdaugherty]

FYI: I tested this solution with lists of 100,000 elements and saw no discernible performance difference between those and lists with ten elements. The reason is because the vector slice operation that obtains the sub-list is O(1).

[simonmichael]

Thank you! Sounds great. (Of course, my items are variable height; this will be strong incentive to change that).

[jtdaugherty]

Is that something your application needs? There might be other strategies, since you could always implement a custom widget and sidestep the List entirely. It would just be more work. :) But knowing that your elements all have the same height might have other benefits; I don't know.

[simonmichael]

Currently when Ledger (and hledger's) register report contains multi-currency balances, each currency is shown on its own line.

In hledger's multicolumn balance reports, because this disrupted the tabular layout I changed this to show such balances on one line, comma separated. I plan do the same thing here.

[simonmichael]

I confirm your latest List renders without the slowdown here too.

However I think str is no longer right-padding to the full terminal width. Eg with a box enclosing the list, each | of the box's right border is rendered immediately following the list element instead of at the terminal edge.

[jtdaugherty]

If you can reproduce using a minimal demo program and file an issue, I would be happy to take a look!

[jtdaugherty]

I'm going to mull over the change for this ticket and decide wether to merge to master; I need to decide whether giving up mixed-height list items is problematic.