Beyond Virtual Lists: How to Render 100K Items with 100s of Updates/sec in React

Good morning, everyone. My name is Michel Westrater. I work at Facebook, I think, because it might have another name today. But it's good to be here, and it's very good to see all your faces without also seeing your bedroom and your laundry and your empty bowl of porridge. So thanks for having me. I'm working currently on a project called Flipper, which is an open source debugging platform which is used primarily by mobile developers. And I'm going to talk about how to optimize rendering of really big tables. And in this talk, I'll feature a little bit about Flipper, I'll find an actual useful application of Bitcoins, and I will show you an open source library. So first of all, there's a tool called ADB which is used for debugging mobile applications, and if you run, for example, ADB log, it just generates a lot of data. It can easily generate up to 100 lines per second or something. And so, we're working on Flipper, a tool that allows you to inspect layouts in a mobile device, see the network request of your react Native application, and so forth, and so on. However, we're going to focus in this talk on one specific feature, which is the logs. And the logs, they basically show the very same output as you just saw from ADB, except that we parsed it so they can sort and filter. Now, the original implementation we had isn't very fluent. Like it starts a bit, it doesn't really keep up, and especially if you apply some filters, it kind of slows down. And also, it doesn't properly wrap lines, which is really annoying if you use logs. So we figured that this is kind of too slow, and actually what we detected, even in production builds, if the filter is slightly complicated, and you have 100,000 log lines in there already, then a single render pass of our react component could easily eat up to 250 milliseconds, so you end up with four frames per second, which is really annoying. And so we figured we needed a better implementation, and we built one. And so this is the new version, which is much more smooth, but actually keeps up with the data that arrives over ADB, and even if you're filtering, it does barely affect performance. And we made the user interaction a lot better as well, so we have links that are highlighted, lines that wrap automatically if you resize the window, that kind of stuff. So we made the data a lot richer. We even added things like being able to sort on any column you want. And so how did this affect performance? It turns out the performance of the new implementation was ten times faster. And we saw that inside Facebook, we measure what the performance is, how many frames we drop, what CPU load is for our users, and we saw basically a ten times frame drop, and a much slower usage of CPU. And if you look at the profile in Chrome, we can actually explain that. And so the left two sections are basically the old situation where there's a lot of CPU going on, and most of it is yellow. And yellow means this is running javascript code, our code of Flipper. And in the new situation, there's still a lot of CPU usage, but it's spent differently. It's no longer spent on the yellow part, no longer on the scripting, no, it's doing a lot of layouting and styling, and it means that it's cranking out much more frames per second. So, in short, purple is good, yellow is bad. And so how did we do that? And to explain it a little bit, I'm going to show you a small demo application which streams a lot of Bitcoin transactions so that we at least put all those wasted CPU cycles to good use. And I'm not as gracious as Sarah, so I just pre-recorded it. Anyway, so let's start with the basis. What do we do? We set up a web socket connection to Coinbase, and we start listening for three different exchange rates, and for every new message we arrive, we collect callback. And the data basically looks a little bit like this. Just an exchange with a certain rate. And so what happens here is that we're not really rendering at all. Sorry, I'm messing this up. So what Sarah can do with live coding, I can do with a video. Isn't that amazing? And so the idea here is that we don't render anything yet, and if you start streaming, you will see that we basically are receiving 1,000 items per second. CPU isn't doing anything because we don't do anything with it. And this is our baseline. So conceptually, this is what is happening. So let's throw react into the mix. So we have our little base component, and we start to introduce some state in which we store all the rows that arrive. We also start with a base set of 10,000 rows to have something at least. And every time any row arrives, we update the state, allocate a new array, and put it in there. And then if there's a filter active, we apply that to the data set. And similarly, if the user wants to sort the sections by price, we apply a sorting function. So then we map over all the rows and render them out one by one. So if you run this, I think the presentation is broken. Moving it over to a laptop. Anyway, that's what happens if you change it at the last moment. So if you render this, it renders pretty okay as long as the data is static. But as soon as we start to filter, it really starts to slow down. We have now five frames per second, and CPU at the bottom is maxing out. And if we start to enable the stream, we actually are able to process like three new records per second, and that's because we're rendering all those 10,000 rows over and over again. This is really slow. Not a good idea. The obvious thing which we do in these kind of situations is apply virtualisation. At this point, there's usually some people who are like, why are you rendering 10,000 rows in the first place? That's not a good user experience. Why show so much data? And my experience, that's usually a kind of a lame excuse to avoid a hard problem, and it's very simple to prove. Take a terminal. A decade ago, it used to have like a fixed amount of scroll back lines, like maybe 1,000. And what every engineer out there does is like he puts it to unlimited, right? We want to have all those lines at our fingertips when we do an npm install. We want to scroll back very quickly, search filter, and I'm pretty sure that most engineers would quit their job if someone suggested that a terminal should be paginated. And the same holds for many dashboards that show a lot of commercial data, graphs, rows that updates with real-time stock information. Having thousands of data points with hundreds of updates per second isn't really that strange at all. So the typical thing to do at this point is to apply virtualisation. There's a bunch of good libraries out there for react, react Window, Virtuoso, but the best one I found is react Virtual by TennoLintze. And it's really good. Basically, the usage is pretty simple. It provides you a hook, but it also supports row wrapping. And the idea is that you call this use virtual hook, you give it the amount of data you want to render, and a container which is used for search calculations, and then it gives you back a bunch of items to map over, and for each of them, you apply some styling. It's a bunch of style, but it's really straightforward to build this. So let's put this one to the test. So again, on the static dataset, it scrolls very fluently. And the interesting thing is, like, once we start streaming in the data, we can now, instead of three, four items, we can render a... we can receive a couple of hundred items before we start to slow down. Now filtering is still expensive. Like once you apply the filtering and sorting, you see really the amount of the items you can process in the meantime drop down. And we're nicely maxing out the CPU as well. So react Virtual solves the problem for us if we have a static dataset and we need to be able to scroll really fast. That's the problem it solves. However, this doesn't solve our problem. Because that's not the only part that's expensive, rendering. It's also the data processing. If every time we receive a new item, we have to map over the whole dataset, filter it again, and if they're sorting active, also have to re-sort the dataset. That is actually where the performance goes down the drain. So the virtualization we already had in the very first example I showed. And yet we still had 250 milliseconds of per render, just because all the processing that goes on. And there's a few tricks that people commonly apply. Like we could memo the filtered rows. But that doesn't really help. It only helps if the filter changes now and then, but not if your rows are changing all the time. If you have dozens of updates you have to process, then your memo is never going to have a positive cache hit. And similarly, you can debounce, which makes sure that at least your application kind of stays usable, but it doesn't drop the performance of a single render, and it does allow you to go beyond those four frames per second in our use case. So what can we do smarter? One thing we can do smarter is not filtering the whole dataset we have. Actually we already know for every item whether it matches the filter criteria or not. We only need to filter the data that arrives, not the data we already have. So let's do that. So the first thing is that we're not going to sort the rows in state, which would cause a render every time we change it, but we sort in ref. And the state we're going to contain is just the visible rows. Now, if a new event arrives, we apply it to the base set, and then we also check if it matches the current filter. If it matches the current filter, then we also update the visible row set. And then there's one other thing to do, is that whenever the filter criterion itself changes, then we need to re-filter the whole set, but that's now the exceptional case. And so let's put this one to the test. So remember the important thing is that we only update the state if the item matches the filter. So in the base case, our performance is the same as in the previous example. However, if we start filtering, now the performance goes up in the sense of the amount of new items we can process, because now in two out of three of the transactions, we don't cause a render, so we leave much more CPU capacity available to process that incoming web socket. So that's a good improvement already. This moves our filtering cost from the order of n to a constant overhead. Can we do the same for sorting? And the answer is yes. We can also do the very same thing for sorting. How do we do that? The basic idea is that we leverage the fact that we know that whatever we're rendering is already sorted if it was sorted before. So whenever new data arrives, we don't need to re-sort the full set. Instead, we can use a small utility from Lodash and find, by using sorted last index by, the binary, the insertion index at which we have to insert our new row. And that is only a binary search instead of a full sort on the data. So that moves from basically n log n to log n. Again, the same thing applies for if the sorting itself changed, we have to do the full set, but again, this is the much less common case. So let's put this one to the test. And remember, the crucial thing here is that instead of sorting the full set, we do a binary search to find the insertion position. And so again, we process the data, we start tailing, we start filtering, and we have the nice performance, and now we enable sorting, so now all the data set is sorted, yet it doesn't really affect our performance anymore. Where normally sort is really expensive, now it's not impacting that much. So now we optimise filtering, we optimise sorting, can we do even better than this? And the answer is yes. We can also start to window the data we process. Now, it sounds a little bit controversial because we're already applying windowing, but we are only applying windowing to the render. But actually, if you think about it, we can apply the windowing earlier, at the moment we process the data. So when a new row is added, but it's effectively added outside the current view, we don't even need to trigger a rendering, even if it matches the filter and finds insertion index. If after that we find it's not within the viewport, there's actually no need to cause react to re-render and do those fertilisation computations. So let's apply that trick as well. So now we don't have any state anymore, and to capture what we're currently looking at, we introduce a window that just stores the visible set of rows, and we use a trick, force update, to force a render of react whenever we want, and if we don't want to render, react will never re-render. Now the next thing we do is after every render, we store what range we did render, that's the range we got back from react virtual, and then we check when we find the insertion index of a row, we check is it within the current window, then we trigger react to re-render, and otherwise not. Now there's one exception case, and that is once in the 100 rows, we're still going to trigger a render, and that is to make sure that our scroll bar keeps growing if more data arrives, even if all the data arrives outside of the current viewport. So let's test this one. So we start streaming, and you see that we process a lot of data, especially if we don't tail, because then all the appends happen outside the window. Every tail, we have still the same performance as before, but without tailing, almost everything is added outside the screen, so we barely use any CPU. And this is also the first time that the CPU actually drops below maximum usage. So now we have a longer pipeline, we filter, we store, we check if the update actually appears within the visible window, and only if that's all true, then we cause react to render. So we did now add a lot of logic, and it was just for appends. How do we deal with updates? How do we deal with inserts? How do we deal with removals? And the solution I've showed you so far, we've generalised in a packet, it's called flipper data source. It's maintained for now inside the flipper repository on GitHub, but you can use this packet right away. And the basic idea is that actually all the other operations basically follow the same pattern, and update or removal is not significantly different from an insert. And those four steps are basically a pipeline where we describe the initial operation, for example, pending an item, then we apply sorting, and we just transform the description of the operation, so an append operation becomes an insert at a different position with the very same item. And then we also have a reversal operation in case we reverse sorting, and then we decide whether this operation ends up in the window. So first we transform the operation without thinking actually about rendering at all. And the other operations are also really easy to express in these very same terms. They go just through the same pipeline. And so let's refactor our example to leverage the flipper data source package. So we remove all our custom logic, our effects, we still have the same view criteria, the user has still the same features, we're just going to wire it up differently. So we don't need react Virtual anymore, that's abstracted away. We remove all that rendering stuff, which is over here. There we go. And then we just import a few things from the packets. So we import the createDataSource, which creates a data source and we keep a reference to it. And the only thing we do when a new event arrives is we call append, and that stores the event in the data source. Then whenever the filter or sorting criteria is changed by the user, we just update the view configuration of the data source. That data source, we pass it to the data source renderer virtual, and with that we basically have the same thing as what we built so far in this entire demo. It's just now a few lines of code. So let's put this one to the test. Again, we start, we start tailing, make it hard, and we start filtering, and actually see that the performance is really good now. Even though this is only a debug build of react, it's easily keeping up CPU-wise. So this is slightly more efficiently implemented as what we did so far. But now our CPU is barely breaking a sweat, even though we're adding almost 1,000 records per second and we're sorting and filtering them. And to make it even harder, we can start off with a large dataset. So instead of a fan file of items, let's start with 100,000. Again we do the same thing. And what we will notice is that this makes it a little bit more expensive, so CPU usage is slightly higher, but still it's keeping up nicely. So we're not maxing out on CPU and JavaScripting, so that means that the rendering, the frame rate stays stable at 50 frames per second. So basically this is all that was left to make this demo performant. And that is what a Flipper data source package does. It's not perfect yet, but it works really well in those cases. We use it to power all our performance critical views in Flipper. You can just look at the source code. It's on our repository. And there are some future ideas, like the very same mechanism could be used, for example, to power charts. There's a small demo of it. But there's a lot of possibility, because like many visualizations, follow this filter sort and window principle. So give it a try. Let me know what you think. If you have any questions, feel free to ask. Thank you. That was an amazing talk. Thank you so much. Give it up for him again. All right. So we have some questions that came in during the talk. And I'll just ask you, and then what we'll do is at the end, you'll pick your favorite question and that person can get a T-shirt. So I'll just go in order of the way they've been upvoted so far. The first one is how does incremental sorting work with nonlinear data in terms of having to recompute the sorted data set and incoming unsorted set of dates, for example? So let me see if I understand the question correctly. So how the sorting works is that it's based off a comparison function where you can have a stable sorting output. For example, there can be a date indeed. And it's only compared relatively to other items. So the incoming data doesn't have to be sorted at all. You can sort on as many criteria as possible as long as you have a stable sorting function that works. Perfect. And another question is how does the virtual list handle dynamic row height? That's a really good question. I've read the source code of it a while. So what it does, it runs out the items, then measures them and caches the measurements and uses that to offset the next items. But because the height is memorized per row, at least as long as the width doesn't change, that works in practice really well. You have to give a heuristic function for a base height, but then that starts adjusting. And funny enough, that's not really noticeable. Awesome. And another one. Thanks for the great talk. Does the Flippert data source already have an api for virtualization in two dimensions, for example, for grids? No. It's currently only does one dimensional virtualization. And also, which is I think really interesting to add in the future, is adding downsampling into the abstraction. So that would make it really useful to plot charts if we could dynamically downsample the events that come in. And have you tried optimizing auto zebra rendering? So for example, dark and light rows one after the other? No, I didn't give that a try. But that should not... So what you get back from use virtual is just an array with items. So you can use the array item index for zebraing instead of associating it with the data. That should work fine. Unless if you really care about that the specific row is always gray and another one is always white. But I don't think that's usually the case. Nice. Now, there's so many questions, we won't be able to get to them all. So I'm just gonna do this last one to wrap us up. Because this is one of my favorites. How many sleepless nights were there getting to the end of getting to this end solution? Actually, not that many. The reason is, I wanted to build this years ago, but I never had a solid excuse until I started working on Flipper. And so Flipper, to answer your question, yes, we use it in real life in Flipper. So you can just download Flipper and give it a try. So it didn't give that much sleepless nights. Cool. Thank you so much. Now, I know there were more questions. So you can hang out in the in-person speaker discussion room, which will be around the corner just outside the door. And if you're in the remote audience, you can go to the spatial react advance, that's bit.ly forward slash spatial react advance to join the conversation. But you've got a big decision to make. What was your favorite question out of all of the ones that you saw? That would be the one about sleepless nights. Sleepless nights. So Dave... It's so nice with care. That's such a good question, right? So Dave or DJ Amy, you're going to have a t-shirt. If you're here in person, just come over to the front. If you're online, we will contact you. Come on, give it up for him. And definitely check out his talks.