Large Data Set Complexity

[ShawnCZek]

Hello @mikke89, 👋

Once again, thank you for your continuous work on the library. The upcoming 6.0 release looks promising, and I cannot wait for it!

Our TruckersMP team has been progressively working on the port from our previous GUI library to RmlUi. One of the current components in work is the player list, which can show up to 300 players, if not more. This is very important for community interaction or a case when players are misbehaving; you must be able to report such behavior. :)

Unfortunately, one of RmlUi's most significant downsides is performance. For our complex UI document, the context update can take up to 15 ms (for around 120 players) on a fairly powerful CPU, which is unacceptable; the player list will be updated often, as it must show the most recent information and new players. After modifying compilation settings and playing around with CSS (see below why), I can get down to around 5 ms, which is still a lot, as this does not include rendering. It would be great to get under 2 ms, in the best-case scenario, to get under 1 ms.

What is such a player list, anyway? For us, a real-time MMO modification for a truck simulation game, such a list is a mix of an end screen with a result and a scoreboard in a real-time FPS game. Basically, it must show all players in the area while accurately displaying the distance to the player, their latency, their tag, and their name. The user can sort this list or query only some players. When it comes to styling, the user can resize the window. The bottom controls, such as the query input, must always remain at the bottom of the window.

I created an isolated sample for this case to showcase, test, and profile the problem. This is stripped of any more advanced processing or complex styling: https://github.com/ShawnCZek/RmlUi/tree/sample_player_list

I enabled Tracy and Lua, used the Win32_VK backend, and modified the following variables:

Configuration	Value
RMLUI_CUSTOM_RTTI	✔
RMLUI_FONT_ENGINE	freetype
RMLUI_THIRDPARTY_CONTAINERS	❌

My PC configuration is the following:

The first thing you may notice is that the styling is off. I am attaching a comparison between RmlUi and Firefox. The styling is not 1:1 due to differences with browsers, but they should both show a similar result:

The input is overflowing, and the margin between the top text and the player list table is off. You can notice this even better when you try to resize the player list in RmlUi. Even more worrying, though, is that this table causes the layout to reformat four times!

Anyway, if we forget this issue, formatting the player list still takes 2.63 ms! In the provided sample, there are only 100 entries in a simple table, as opposed to how complex our solution will be (e.g., an addition of controls and images). One of the problems, I believe, is the high number of calls and nesting. Playing around with the compilation settings to enforce as much inlining as possible and enabling link-time optimization bring slight improvement. This does not fix the root problem, though.

Another area for improvement apparent from sampling is the number of allocations. This does not have to be clear when reading the code, but using strings and vectors with a dynamic allocator causes a sheer amount of allocations. Most of these allocations are very small, too. Using a page frame/buddy allocator would probably improve the performance. Or the burden can be redirected to the library user by providing an option to set a custom allocator.

The Rml::Element::Update() and Rml::Element::Render() methods are a massive issue for every frame. With many elements, which can be just a simple table, we pay a considerable cost for the OOP architecture. For elements with no animations, the update method does barely anything for 99+% of the time, apart from checking the change of internal states and calling a virtual method (another cost!). The same goes for Rml::Element::Render(), which, without a change to effects or transform, does a few virtual calls to the font engine (in the case of Rml::ElementText) and itself (OnRender()), apart from the apparent rendering.

Sure, profiling causes an overhead, which exaggerates all these issues. Nonetheless, some of this is a price we pay on every frame and a huge price for multiple (or) more complex documents, not just for this scenario.

---

After reading it all, I realized I diverged slightly from my original point. Nevertheless, to summarize this entire discussion post, there are three fundamental discoveries from this case/sample:

1. Flex is broken when trying to grow dynamically, leading to formatting the element multiple times.
2. When purely updating data, the layouting is very expensive for a game GUI library.
3. With more elements (or just a long table), every single frame gets very expensive, while, seemingly, this cost can be reduced.

---

I wonder what your recommendation is to work around these issues or if you plan to improve these aspects of the library.

[Paril]

I think we actually ran into point 1 accidentally when making a custom element that uses flex; we clear the children and added new ones each frame (which obviously was not great and we've since fixed), and it caused the UI to get progressively slower as time went on, which is strange since you'd expect it to be a consistent slowdown since we're always removing & adding the same number of elements. I hadn't had time to pull it out into a test project, though.

[ShawnCZek]

Did you manage to work around the problem with flexbox? Or do you just update elements less often?

[Paril]

We worked around it by not updating the UI, yeah. We keep the elements in place and only update the contents.

[mikke89]

Hey, I appreciate the thorough post! It's quite a bit to chew over, but it's always very interesting with real-world use cases.

For your first point, I would suggest that you make a separate issue for that. I will instead focus on the performance side here.

So to begin, I absolutely agree that performance is important. That is one of the first things I dived into after forking the library from libRocket. There was room there for orders-of-magnitude improvements, so at least I feel we are in a much more workable state. In any case, there is still a lot of room for improvements, there are many really dumb things we do.

So, then, let's get to your example. It's neat, and I definitely see the use for it, it's a great example where performance becomes critical. I might actually steal it for our benchmarks, if you don't mind. The library just isn't really optimized the same way like web browsers, with the possibility of huge pages. In game dev, and most applications, pages are usually relatively small, and the complexity isn't that high. Huge tables are one of those complicated things that are very tricky in the general case, but with some assumptions could in principle be made much faster (like fixed row heights).

In fact, there has been some discussion on large tables before, see this gitter link and nearby discussion. Here, I go through some of the aspects of possibly optimizing this. I think a lot of this still applies, so I'll quote it here:

Alright, let me give a brief overview here. So we have three important steps to consider in terms of culling (in this order) :

• Update. Updating properties of all elements to reflect and compute any new style.
• Layout. Sizing and partially positioning every element.
• Rendering.

Render culling is probably the most straightforward one since all the information is available at this step: render region (scissor), element properties, sizing, and position. I have actually already been tinkering with this, see here: mikke89/RmlUi@4eb9d2b

The update step is usually relatively fast, unless perhaps if you have a lot of new elements. At this stage we don't know which elements will be rendered or affect layout, aside from obvious things like the display property, so that limits most culling strategies. I have thought about culling update of elements beneath elements with display: none. It wouldn't help your case since they're all visible, but might help if there is e.g. a large document with many pages that are displayed one at a time. The downside is that querying information (properties) of any child of the invisible pages would return wrong results. Which is the primary reason I haven't proceeded with this yet, in addition to unknown consequences and just development priorities. I would be interested to hear what people think of this trade-off though.

Now layouting. I feel like this is the black sheep of the library, it is currently an all-or-nothing approach, and it is by far one of the slowest and most complicated things in the library, especially with a lot of elements. Whenever any property that could potentially change the layout is changed, then the whole thing must be redone. An obvious step is to try to isolate layout where it possible, and only dirty the closest isolated layout to avoid doing the whole document. Again, this wouldn't help your list though.

• We don't know the position of all elements, since the library has been designed so that position can change without affecting layout, in particular for scrolling. And of course due to transforms as you mention as well. Thus we can't know which parts of your list is visible during layouting and can't cull it at this stage.
• Even just to know how long that list is we have to format all 5000 of them. Even if they all have the same height we don't know that upfront.

There are some things we could possibly do. For example, if the list item has a fixed width and height, and hidden overflow, we don't actually need more information from it do the rest of the layout. At least I think so, CSS layout is complicated. But assume that we find the right conditions for that, then we could potentially defer inner formatting of the list items to the render step when we know it is visible (not culled by the above render step). It would still be O(n) and a lot of work, but potentially far less work.

But with that said, I believe putting 5000 items in a list is just bad user interface and unnecessary. No human can ever process that much or easily navigate that. You need some sort of hierarchical approach to make sense of that information, or a filter with a limited number of results. Let's not go out of our way to optimize for exotic use cases, there's a reason web browsers are bloated. Let me know what you think about the above suggestions though.

Just to be clear, I think your list with 300 players is fine. Maybe I would say today that it's okay with 5000 too as long as there are some great filtering abilities and such. But obviously, with that many rows, I also think it's reasonable to expect more from the user in terms of accommodating that, such as making some additional assumptions or specialized containers. Here, I am thinking of something like a "big table" layout mode, where we know most rows are out of view, and the user can for example tell exactly the height of each row up-front. That would be massively helpful to make something fast. Perhaps it might not be so hard to add to our existing table implementation? I think that's a more fruitful approach than the layout proposal I mention in the quote.

---

Even more worrying, though, is that this table causes the layout to reformat four times!

Right, there are some cases where we need to do layouting multiple times. Taking a closer look at the example, let me quickly go through what's going on here.

First of all, one culprit is the auto overflow. It's actually really bad when combined with a huge table, because with auto overflow, we always do layout without scrollbars first. Then, if we detect that scrollbars are necessary due to overflow, we have to start over again with the scrollbars present and the new layout width. Of course, this is another one of those "dumb" things, but is great for ensuring correctness. I have been thinking of some ways to possibly reduce this, by checking regularly for overflow, but it would have some overhead for cases where it doesn't apply. By replacing overflow: auto with overflow: scroll we get down from four to three format iterations (16ms to 12.3ms frame time).

The next ones are all about flex layout with content-based sizing. Flex layout is just not great for performance when used naively, and I would generally avoid it for large layout structures if you can. The issue is that a lot of the calculations requires the size of its contents to be known, as part of its algorithm. Of course, this is also one of its strengths, but should be used with care when performance is critical. In this case, it's all documented behavior, see the performance section in the flexbox documentation. The two points here directly relate to your observations. By updating the example with this advice, I get the following:

• Using flex: <number>: 2 iterations (10.5ms)
• Using width: 100%: 1 iteration (6.56ms)

We're down to 1 iteration where we want to be for such a large table, much better. It wouldn't surprise me if there are situations where we could skip some of these iterations automatically, or early out somehow, it hasn't really been looked at thoroughly.

With these optimizations, most of the layout time is spent actually doing layout of each individual table cell once (something like 2.8ms / 3ms). The context render update is in total 2 ms. If we could skip layout of all the ones we cannot see, and also skip the render update on all of them, then we might be left with only 20/100 (visible rows) parts of that, so 1ms. And that would be the same for any number of rows.

The element update step is currently 0.4ms and that would scale linearly with new elements. I see that for some reason, all the elements need to update their definitions, not exactly sure why this happens here, so perhaps something to look at. Otherwise, during the "no-op" frames the element updates are 0.1ms, not the most critical to optimize in my view.

These repeated layout iterations are quite "dumb" in many ways. But there are reasons for all of them being there, they are easy ways to ensure correctness. Working around them in general can be a great effort, but I'm sure there is a lot of potential here for better approaches. And probably some trivial cases where we can skip them, or at least some early outs. In particular, I'm not sure if the layout update due to the lack of width: 100% is really needed in this case.

I generally agree that memory allocation is one area where we are taking a pretty naive approach. From my measurements there is something like 15% CPU time being spent here during some intensive operations (off the top of my head). It's one thing to study more, I actually have some local branches working with reducing a lot of these allocations. However, what we're really looking for are those order-of-magnitude improvements, so it might not be the first place we should put in our efforts. By the way, using the built-in thirdparty containers has a pretty big impact here in my measurements, I would really encourage you to measure and consider those. And all our types are using aliases that you can override, so you can set a (global) custom allocator that way.

---

Some workarounds should be considered. One approach is to sidestep the library altogether, make your own element, and do all the layouting manually. You could still take advantage of our text layouting and such. Another approach is to only add the rows that are visible to the table. Above the visible rows, you could add a fake row which takes the height of all the omitted rows, and the same below. This way, the scroll height is correct. This would essentially be the same as some of the culling discussed earlier, just a bit more manual work. And you would automatically get the culling for all parts of the update and render steps.

So this post became longer than I expected. I'm not sure how useful it is really? While there are a lot of approaches we can continue on, the main thing is finding the time and effort to sit down and implement these things. Ideas are quite plentiful. But it's nice that you bring it to the forefront, I certainly think large tables in particular are valuable. A sample with one of the workarounds could be nice in the meantime. Also, I would encourage anyone to really take note when coming over performance notes in the documentation, there are always good reasons for writing them, perhaps they should be elaborated upon.

[mikke89]

Yeah, you should not manually add or remove elements in the context of data models, that is expressively not legal, especially in the context of data-for, as you will just be fighting with the data view.

I think I wasn't very clear above in my suggestions. Especially the suggestion "to only add the rows that are visible to the table". So, what I thought of here was to entirely skip adding the invisible entries into the data model itself. I.e. the "players" table would only contain the entries that are visible at any one time. Then you could react to scroll events and change the data accordingly. You would also need to add a top filler and bottom filler in this case, like in your fast table example.

This approach would make so many aspects easier from the library side: only the visible elements would even be added, so we get a lot things for free. In fact, each of the data views, the element update step, the layout step, the render step. Each of these will be bounded by the number of visible elements, without any modifications to the library. On the other hand, trying to do this automatically on the library side requires a lot of effort for each of these steps. I'm not saying we should never do parts of that on the library side, but it's hard to beat "not adding data" in any other way.

Thanks for actually implementing the "fast table", there are no substitutes for seeing these things in practice. I think it serves as a great example, and something that could work well many cases. Although as you allude to, I think it's a bit too specific to include directly in the library.

This did lead me to one idea that perhaps generalizes a bit more easily, if it works out in practice. So what if we made a smarter data-for? This data view controls the creation of the its child elements and subviews. So if we can avoid adding the non-visible children from the data view itself, then we effectively get everything for free, almost all the same things as if we omitted the entries in the data model altogether.

The advantage is that this wouldn't be tied to any particular structure, any layout mode would be supported: table, flex, or just block layout. Of course, we would need to make some assumptions, so that we know the overall layout structure before-hand. The same way we know the row heights in your fast table example. We could rely on the box height of a row. Though we might not always have clearly defined rows, so we could let the user override the height using e.g. a data expression.

And to extend a bit further on this idea. We might not always need an exact row height either. For example, say we have a huge chat log. Each entry varies in height. But we if we say that we have some typical mean height, then we could get an approximate scroll bar at least. It wouldn't be exact, but you should be able to navigate alright. You might need to either over-commit the number of visible elements, say with an assumption of a minimum row height. But at least it would be bounded.

overflow: scroll removes yet another iteration; we are down to 1 layouting operation only! However, the downside of this optimization is that the table permanently has a scrollbar. Not the most desirable solution, but let's use it with this sample.

Yeah, it's not something that that can be used in all cases. Of course, if we are already being quite invasive, you could also toggle it manually according to the current number of rows. Not a good general solution though. One thing we could do is to add the scrollbar-gutter property. This way you could reserve the area for the scollbar, without showing it when it is not needed. Is this something that could be used in your case? Otherwise, it's not easy to ensure correctness without doing layout twice.

[ShawnCZek]

I have first fixed adding/removing elements for the fast table element: ShawnCZek@784a830

I have also tried the approach you mentioned (with populating the data model only with visible entries). As you suggested, it was easier than the previous one and yielded much better performance. You can view it here: ShawnCZek@371e93a

In the end, I tried to implement it for our product. Except for a few anomalies, which would be more apparent with sampling, and the performance overhead caused by profiling, I believe we got under the target of 2 ms during a frame with an update. 🎉

I wonder if some of these findings are worth adding to the documentation or samples because RmlUi can quickly become a performance bottleneck just by making wrong assumptions or using incorrect tools.

---

About the smarter data-for: it is one of the things one would hope the library handles automatically, but I sadly cannot see how this can be applied with a correct layout output. For this specific use case, it is possible as the row height and column width are fixed. Unless the burden is moved onto the user by providing an estimated height (not the best DX) of each entry beforehand and unless tables are excluded. Without estimation, I do not think this can work great; for instance, our chat log entries' height varies greatly from one text line to multiple ones. The scrollbar would have been changing rapidly, especially if you decided to drag it.

The scrollbar-gutter property would work great, preventing the "jump" caused by displaying the scrollbar and avoiding displaying it at all times. I can create an issue for this, or feel free to do so with detailed specifications. :)

---

By the way, using the built-in thirdparty containers has a pretty big impact here in my measurements, I would really encourage you to measure and consider those.

I forgot to comment on this. This seems like a significant improvement, too. We avoided them in the past because we were afraid of ABI compatibility. But from what I can see, third-party containers are used only internally and are always included with the library, making me wonder why this is an option and not something being enforced. However, I do not think we will switch before the 6.0 release as any changes to third-party software and the build process might become risky.

[ShawnCZek]

By the way, I do not think creating an issue for the flexbox problem is necessary. It seems to be well-documented:

No automatic minimum-sizing of flex items. Generally, RmlUi does not have the ‘min-content’ size concept.

Source: https://mikke89.github.io/RmlUiDoc/pages/rcss/flexboxes.html#differences-from-css

This looks like something I missed; again, I am making (wrong) assumptions based on my experience with web browsers.

[mikke89]

First of all, that's very cool, great to hear you are now reaching your targets!

And I think having a page in the documentation dedicated to performance is a great idea, and even better when accompanied by a sample like the one you made. I'd be very interested in pursuing that, and we already have a very good foundation there, so thanks!

As for the data-for idea. It would be great if we could do this automatically, but I agree with you that it would be too difficult in the general case. And for most use cases and small amounts of data it wouldn't be needed anyway, and possibly just slow things down. So to implement this, I would make it a separate view dedicated to large data. That way we can make some additional assumption, as long as we communicate those clearly, and also expect the user to contribute some additional details when necessary. I think it's something to consider, I'll put it on my list of things to experiment with for now.

I wonder what could be a good name for it? data-bigfor, data-for-big, data-for-culled, data-for-sliced, data-for-fast, data-bigtable...

Glad to hear scrollbar-gutter might be of use to you. I will add it to my list, it shouldn't be too hard to implement I think, and we can just follow the CSS specs for it.

By the way, I do not think creating an issue for the flexbox problem is necessary. It seems to be well-documented:

No automatic minimum-sizing of flex items. Generally, RmlUi does not have the ‘min-content’ size concept.

I suspect that something else is going on here, as I don't really think min-content applies here. There should be room to use the max-content sizing, which we do support. I would need to actually look closer at what's going on to be convinced either way. An issue would be appreciated, even if it turns out to not be a supported case.

[ShawnCZek]

I believe the name of the data view heavily depends on the implementation, and I am curious to see how you will approach this. But in general, I would prefer a more "user-friendly" name than "culled". "sliced" could be misleading as it sounds like a range of a collection. What about a name indicating that the data view displays only viewable data? Something like data-for-viewable...?

It is not the most critical topic, anyway, considering the possible workarounds, but it will be a very welcome feature.

For the flexbox problem, I have created an issue: #658

[ShawnCZek]

While going through your first comment here and trying out the suggested optimizations, I noticed one pain point that I completely missed and is significantly related to this sample: updating elements with data from the model.

We are looking at 0.6 ms (using the same build configuration as in the initial post) for a data model update when dirtying the collection of players. Again, it looks like there are a lot of small allocations and deallocations, but I believe this is not as important to optimize here.

Right now, there is no way to dirty only one structure member in a collection, which would be very beneficial in cases like this. For instance, every 500 ms, one could only update the score (DirtyVariable("players.score")), and if a player's tag changes, we can only update the tags. Alternatively, RmlUi could offer to dirty only one entry (by index?) in a collection while keeping the other entries untouched. Because in a real-life scenario, the score will not change as often.

What do you think of this?

[mikke89]

Yeah, this has been on my todo-list for a while. But never really prioritized since it hasn't really showed up in any profiling I've seen until now ;) And also, I wasn't sure if the ideas I had would actually help, since there may be some overhead too.

I did implement a quick test of an approach taking an arbitrary data address, and the improvements look quite nice, from 0.60ms to 0.09ms for me when updating just a single cell (not counting layouting or anything else of course): 0b7e006 (edit, improved a bit here: 6144d10).

By the way, for each dirty data address, this has to iterate over all the possible data views and test the address against them. So it doesn't scale well if you have a lot of individual addresses. This makes me somewhat reluctant to add this, I'm not sure if there are better approaches.

But this takes an actual address though. Dirtying everything with a given struct member in a collection as you suggest sounds quite complicated, and very specific to this use case. Maybe you could play a bit with the implementation above?

[ShawnCZek]

I have tried playing around with the prototype you made, and from the user perspective, this is a perfect API. Not only could I update a specific address, but dirtying a variable like players[0] worked perfectly, too!

As you mentioned, this does not scale well. Instead of doing a lookup when dirtying a variable, I tried to build a map of expression addresses to data views. This obviously brought a considerable performance improvement, going from 0.09 ms to just 0.01 ms. Even doing something stupid like dirtying all player scores by looping through the entries took only 0.12 ms:

for (size_t i = 0; i < entries.size(); ++i)
	data_model.DirtyVariable(Rml::CreateString("players[%llu].score", i));

I wonder if we could do something like this instead. Adding and removing a data view would be costlier, and if we wanted to support updating one whole item in the collection, we would first have to map addresses of a lower depth to all data views, increasing memory usage. Alternatively, instead of mapping an entire address, we could build a recursive collection, such as:

players
  0
    name
    tag
    score
  1
    name
    tag
    score
  2
    ...

Lookup for a specific address should be pretty quick, and dirtying the top-level variable should not differ from now. Moreover, it would still be possible to dirty one entry in a collection (players[0]), or we could support dirtying just a specific property for all players (players.score, for instance).

Nevertheless, both these proposals are concrete in the use case, although they would be desirable for us. I would like to know what you think of this and whether there could be any performance hit for other (regular) use cases.

I committed the prototype of my version to my branch: ShawnCZek@128523c

[mikke89]

Yeah, I think we would need to store all the addresses in such a case, there are in some cases multiple ways to refer to the same element (e.g. spaces in [ n ]).

One aspect that could be a bit tricky here in general is the removal and addition of data views. I mean, the use case is really only for huge data tables to begin with. But in these cases, you also have a lot of data views and associated addresses, to add and remove, especially when changing the number of players. These would be successively slower. I'm just worried that we are replacing performance in one area with another. We could add more lookup tables and such to maybe speed it up. But now we are adding more memory and complexity. So I don't have a good vibe with this direction as of now. At least I want to see where we get with the other enhanced data-for idea, as that could make all of these optimizations moot.

I would also first try to see if there are ways to speed-up the update calls of the individual data views. I believe we do try to early out if the value hasn't actually changed. But maybe there are more things to do here, they haven't been optimized and benchmarked a whole lot. And that would be a performance win in all cases.

[ShawnCZek]

Instead of mapping complete addresses, my idea was to recursively map the data address entries and resolve them as such. Indexes could then be mapped to an array for a faster iteration. The structure could look like the following:

struct DataViewDatabase {
	UnorderedMap<String, DataViewDatabase> keys_map;
	Vector<DataViewDatabase> indexed_views;
	UnorderedMap<String, DataView*> name_view_map;
};

Take the names with a grain of salt; this all is just a quick idea. The structure would look like the following for this sample:

keys_map:
  - players:
    keys_map:
    indexed_views:
      - 0:
        keys_map:
        indexed_views:
        name_view_map:
          - name
          - tag
          - score
    name_view_map:

Of course, this would be memory-demanding. On the other hand, it would allow for dirtying an exact address or only a specific attribute of structures in a collection. Initialization of the "root variable" would take longer, but removal would be quicker, I believe. Although I admit this is a particular need, and after going through issues, it appears that nobody has ever needed it (except for us).

I do not think data-for can be optimized without the user specifying what has changed; the data view has to parse and look up the address (if no data expression is used), which will take some time, no matter what we try.

[mikke89]

There is one important consideration with the "big data-for" discussed in the other thread, that I want to emphasize. When this view skips adding a lot of non-visible elements, then most of the views will also not be added. Thus, the number of views will be dramatically reduced too, and bounded by the number of visible entries!

That is the main reason I think this optimized data structure is not really needed. Or at least we should wait until we have some experience with the big data-for first, before spending too much time on this. If you want, you could perhaps try this approach together with the manually "occluded" players table example, to get a sense of the potential savings.