Clarification about variable height list items and efficiency?

[thomasjm]

I've been trying to use the List widget to make an application with mostly uniform-height list items, but an occasional list item that is larger. The idea is that if you hit enter on the selected list item, it "expands" to become larger and show more information. While researching this I've noticed the following:

1. There is nothing in the Brick.Widgets.List haddocks telling me not to do this :)
2. It seems to work fine. Even when I scroll up and down in the presence of expanded list items, it behaves well. I suspect this is because the underlying viewport code does the right thing to put the whole expanded list item in view.
3. However, looking at the list code itself, I see that it makes assumptions that there is a single listItemHeight and that it makes calculations on this basis. Also, looking through historical issues like Size of widget in viewport #169, Question: scrolling view #97, inconsistent scroll position after listMoveTo #11, Support optimized list rendering #7, vBox unusably slow if you give it hundreds of items #264, and Question: Variable Height List Widget #226, it seems this library has evolved in the direction of forbidding (discouraging?) variable height list items for reasons including ease of calculation and performance. So I'm wondering if I'm looking for trouble by doing this.
4. At the same time, the performance optimization this should give doesn't seem to be working, because when I run my application on slightly larger lists (100s to 1000s of items) it becomes extremely slow. When I profiled I confirmed that most of the time was being spent in list rendering code. (I am using the Vector container.)

Any clarity you could add about when/how/whether to use variable sized items would be greatly appreciated.

(Also, the side question that originally sent me down this rabbit hole: is it possible to somehow get the offset from the top of the list to a given item, in the presence of variable sized items? What I'd really like to do is add a command that "recenters" a list in the way the Emacs recenter-top-bottom command does -- with the ability to move the selected list item either to the center of the scrolled region, to the top, or to the bottom.)

[jtdaugherty]

There is nothing in the Brick.Widgets.List haddocks telling me not to do this

Yes, it is perhaps not shouted loudly enough from the rooftop. 😊 From the list constructor documentation:

The list item height in rows (all list item widgets must be this high).

It seems to work fine. Even when I scroll up and down in the presence of expanded list items, it behaves well.

Yes, it will appear to work fine; the trouble is that your scrolling will be broken under some conditions when the calculations about the item heights become wrong. The viewport logic does indeed make your selected item visible, but the logic that the List uses to fake that scrolling viewport does really depend on item height calculations. You'll probably see issues in scrolling behavior when you reach the top or bottom of a list, or when paging up and down.

it seems this library has evolved in the direction of forbidding (discouraging?) variable height list items for reasons including ease of calculation and performance.

That's right. In the early days, lists rendered every item and then just cropped the result. That led to O(n) rendering for lists, regardless of the number of visible entries in the viewport. The trade-off I made to deal with that was:

• Require an item height, H.
• Determine the render-time viewport height, V.
• Determine the number of items needed to fill the viewport, C = V/H.
• Render 2C items, and then translate the result so that it is offset by the topmost item in the sequence. This means that if you have a list of 1-row-high items and have item 100 selected, and if the viewport is 10 rows high, then 20 are rendered and a vertical translation of 90 is added. This makes the list work with viewport, which expects its child to be rendered fully. This makes the rendered items appear where they ought to in a larger viewport, without actually incurring the cost of rendering those other (90, here) items.

So this is all done in service of not rendering items you absolutely can't see. You mentioned that the optimization seemingly isn't working for you, but even with the optimization you may still need to consider the cost of rendering your items and add render caching, for example.

[jtdaugherty]

To follow up a bit more, though: if you really need the functionality you're going for, you may just need to implement your own mechanism for it rather than using List. Otherwise you might end up fighting List to get it to do what you need. Due to the trade-off I made for List, I want to acknowledge that it is not intended to work in all use cases. If that trade-off is unacceptable (e.g. if you need variable-heigh items) then something else will be called for.

[thomasjm]

From the list constructor documentation:

Ah sorry, I missed that.

Got it, the trade-off makes sense.

I've thought about this problem a bit in the setting of virtual DOM rendering in a browser, and I wonder what you think of the following idea to generalize List to work with variable-height (but known at render time) items:

Given a list of items of length N, compute an integral image of the item heights. (I.e. a list of length N where index N equals the sum of all heights from 0 to N inclusive.) The integral image can be computed in O(N). Once you have it, you can determine in constant time the height offset of any given item, the same way you do today. You can also determine the number of items needed to fill the viewport in constant time by walking up/down the list.

The user of this list would need to provide a callback or something when gives the height of an individual item, but other than that it seems like the nice interface of Brick.Widgets.List would not have to change. (It would also satisfy my desire to add easy list recentering, and perhaps a scrollbar.)

even with the optimization you may still need to consider the cost of rendering your items and add render caching

Hmm, this still doesn't make sense because there's a distinct performance difference between a small number of items (enough to fill the viewport) and 100s/1000s. I'll have to look into it further though.

[jtdaugherty]

Given a list of items of length N, compute an integral image of the item heights. (I.e. a list of length N where index N equals the sum of all heights from 0 to N inclusive.)
...
The user of this list would need to provide a callback or something when gives the height of an individual item

That could work so long as the item renderings themselves actually obeyed the heights that are given. That makes for a brittle interface since the invariant is very easy to violate; getting this right would be the application author's responsibility, since it would entail ensuring that the item rendering behavior is deterministic enough. I'm also concerned that this is a rabbit hole; someone has to specify heights, and then they're going to want to get access to rendering information to figure out what the heights should be (e.g. if the list viewport width necessitates a change in item height). That could create a data dependency that is impossible to resolve, since that information isn't available until after rendering has occurred in most cases.

But you're right that the current interface could hide that detail for users who don't want to mess with it (and just default the height of all elements to the constant item height that is already required).

[jtdaugherty]

Hmm, this still doesn't make sense because there's a distinct performance difference between a small number of items (enough to fill the viewport) and 100s/1000s. I'll have to look into it further though.

If it would be possible for me to see your source, I'd be happy to take a look.

[thomasjm]

That could create a data dependency that is impossible to resolve, since that information isn't available until after rendering has occurred in most cases.

That's true, even in my own case it would be kind of a drag to write that callback since I want the contents of my expanded list items to be able to wrap with strWrap.

As an alternative (I'm sure you've thought about this a lot, but hopefully you'll humor me here) -- what about rendering every list item once and then caching their heights in a hash table? For most re-renders I would expect the list elements to be highly cacheable. This would make it possible to generate the integral image efficiently on rerender and would be ideal from a user point of view because it would "just work" without requiring height specification.

If it would be possible for me to see your source, I'd be happy to take a look.

That would be fine, it's a soon to be released open source project. Let me just make sure I'm not crazy/come up with a good demonstration and I'll post a separate issue.

[jtdaugherty]

That's true, even in my own case it would be kind of a drag to write that callback since I want the contents of my expanded list items to be able to wrap with strWrap.

Yeah, this is exactly the kind of situation I was referring to.

what about rendering every list item once and then caching their heights in a hash table? For most re-renders I would expect the list elements to be highly cacheable.

This could work but it does raise some other issues. Rendering all items can be prohibitively expensive (think thousands of items) so this will introduce a noticeable stutter in responsiveness whenever the whole list of items needs to be re-rendered. Also, doing this requires the user to take on the responsibility of cache invalidation. It's hard to know when to invalidate the cache; invalidating at the right time requires that the application developer be aware of how a terminal resize or application state change affects the behavior of all of the combinators affecting the list dimensions. The cache also needs to be invalidated when the list contents change, but that's easier to get right.

I think you're right that in practice list items are highly cacheable, though. That's why I recommended considering caching above, but I think doing it in the general case -- especially with minimal user involvement -- is likely to be very hard to get right. I appreciate you trying to think of ways to tackle this, and I'm happy to keep bouncing around ideas!

That would be fine, it's a soon to be released open source project. Let me just make sure I'm not crazy/come up with a good demonstration and I'll post a separate issue.

Okay, great!

[thomasjm]

this will introduce a noticeable stutter in responsiveness whenever the whole list of items needs to be re-rendered

That's a price I would be happy to pay if everything else worked as expected and it only happened in predictable situations like a terminal resize. I suspect the other people who have asked about variable size items in the past would be too. But if this kind of stutter is unavoidable then maybe it's worth creating a separate module Brick.Widgets.VariableHeightList so people can pick their poison?

It's hard to know when to invalidate the cache

Hmm, my thought was that the Widget n type could be Ord so that it could be cached directly. That way we can just cache whatever the user returns from their rendering callback, and this will automatically respect application state changes and stuff. But looking at the type and how it contains a RenderM action, it seems like an Ord instance might be hard to come by?

That could work so long as the item renderings themselves actually obeyed the heights that are given. That makes for a brittle interface since the invariant is very easy to violate; getting this right would be the application author's responsibility

I was thinking about what you said earlier about this. If this would be considered a brittle interface, then isn't the current interface in which the user specifies a single height for all rows equally brittle? On reflection, it seems like it's not really valid to use strWrap at all in the present version, because with a sufficiently narrow terminal you could always get different amounts of wrapping, right?

Thanks for being so responsive on issues btw!

[jtdaugherty]

Hmm, my thought was that the Widget n type could be Ord so that it could be cached directly. That way we can just cache whatever the user returns from their rendering callback, and this will automatically respect application state changes and stuff. But looking at the type and how it contains a RenderM action, it seems like an Ord instance might be hard to come by?

Yes, it would be impossible to provide an Ord instance. A Widget is really a state monad computation in terms of a rendering context, which has information such as dimensions (initially the terminal size) and the current attribute to draw with, among other things. It's an example of a design where the interface is pure/declarative (functions like vBox or txt) but builds up terms that are impurely evaluated.

I was thinking about what you said earlier about this. If this would be considered a brittle interface, then isn't the current interface in which the user specifies a single height for all rows equally brittle? On reflection, it seems like it's not really valid to use strWrap at all in the present version, because with a sufficiently narrow terminal you could always get different amounts of wrapping, right?

You're right that the current interface is also brittle, in that you can fail to honor your item height pledge, and if you do, scrolling computations will be wrong and lead to occasional strangeness. The case where your items are too high is easy to rectify by (me) adding a vLimit n and a padBottom Max to the list rendering code to ensure that the resulting item is exactly of the promised height, but that also introduces an extra cost that may not be worth paying, so I pass that responsibility on to the user. The short answer about this issue is that list users are responsible for adding a vLimit or similar, as needed, to ensure that their item heights are correct. However, I would argue that this is less brittle than what we've been discussing above because I think that the amount of work to get item heights right is trivial compared to the amount of work required to carefully manage the cache state to get the list to render correctly and efficiently.

[jtdaugherty]

I do want to follow up on one thing, though: I definitely think it would be awesome to have a list that supported variable item heights. I think it might be good to start from scratch on making it rather than trying to massage the current List into shape because a very different approach might be needed. I also think it's possible that the Brick rendering algorithm, cache management, and/or viewport functionality might need to be augmented or changed in some way to support this, so I don't have the expectation that the current library core is adequate for dealing with this. To me, an ideal outcome would be one where there are minimal changes to the core (especially breaking changes), as well as a new list implementation that subsumes the current one.

If you do end up messing around with a patch to support this, I'd be happy to collaborate on it.

[jtdaugherty]

@thomasjm it looks like there isn't more we can do on this ticket right now, so I'm inclined to close it. Let me know if there's more we should discuss.

[thomasjm]

Sounds good -- I'd still like to try coming up with a solution to this, but the issue doesn't need to stay open in the meantime.

[jtdaugherty]

Okay, thanks!