I’ve been trying to build the ideas of literate programming into b8r (and its predecessor) for some time now. Of course, I haven’t actually read Knuth’s book or anything. I did play with Oberon for a couple of hours once, and I tried to use Light Table, and I have had people tell me what they think Knuth meant, but what I’ve tried to implement is the thing that goes off in my head in response to the term.
One of the things I’ve grown to hate is being forced to use a specific IDE. Rather than implement my own IDE (which would (a) be a lot of work and (b) at best produce Yet Another IDE people would hate being forced to use) I’ve tried to implement stuff that complements whatever editor, or whatever, you use.
Of course, I have implemented it for bindinator, and of course that’s pretty specific and idiosyncratic itself, but it’s a lot more real-world and less specific or idiosyncratic than — say — forcing folks to use a programming language no-one uses on an operating system no-one uses.
Anyway this weekend’s exploit consisted of writing tests for my debounce, throttle, and — new — throttleAndDebounce utility functions. The first two functions have been around for a long time and used extensively. I’m pretty sure they worked — but the problem is the failure modes of such functions are pretty subtle.
Since all that they really do is make sure that if you call some function a lot of times it will not get called ALL of those times, and — in the case of debounce — that the function will be called at least once after the last time you call it, I thought it would be nice to make sure that they actually worked exactly as expected.
Spoiler alert: the functions did work, but writing solid tests around them was surprisingly gnarly.
The reason I suddenly decided to do this was that I had been trying to optimize my data-table (which is now virtual), and also show off how awesome it is, by adding a benchmark for it to my performance tools. This is a small set of benchmarks I use to check for performance regressions. In a nutshell it compares b8r’s ability to handle largish tables with vanilla js (the latter also cheating, e.g. by knowing exactly which DOM element to manipulate), the goal being for b8r to come as close to matching vanilla js in performance as possible.
I should note that these timings include the time spent building the data source, which turns out to be a mistake for the larger row counts.
So, on my laptop:
- render table with 10k rows using vanilla js — ~900ms
- render table with 10k rows using b8r — ~1300ms
- render table with 10k rows using b8r’s data-table — ~40ms
Note: this is the latest code. On Friday it was a fair bit worse — maybe ~100ms.
Anyway, this is pretty damn cool. (What’s the magic? b8r is only rendering the visible rows of the table. It’s how Mac and iOS applications render tables. The lovely thing is that it “just works” — it even handles momentum scrolling — like iOS.)
Virtual javascript tables are nothing new. Indeed, I’ve had two implementations in b8r’s component examples for three years. But data-table is simple, powerful, and flexible in use.
So I added a 100k row button. Still pretty fast.
A little profiling revealed that it was wasting quite a bit of time on recomputing the slice and type-checking (yes, the b8r benchmarks include dynamically type-checking all of the rows in the table against a heterogeneous array type where the matching type is the second type checked). So, I optimized the list computations and had the dynamic type-checking only check a subsample of arrays > 110 rows.
- render table with 100k rows using b8r’s data-table — ~100ms
So I added a 1M row button. Not so fast. (Worse, scrolling was pretty bad.)
That was Thursday. And so in my spare time I’ve been hunting down the speed problems because (after all) displaying 40 rows of a 1M row table shouldn’t be that slow, should it?
Turns out that slicing a really big array can be a little slow (>1/60 of a second), and the scroll event that triggers it gets triggered every screen refresh. Ouchy. It seemed to me that throttling the array slices would solve this problem, but throttle was originally written to prevent a function from being called again within some interval of the last call starting (versus finishing). So I modified throttle to delay the next call based on when the function finishes executing.
Also, you don’t want to use throttle, because then the last call to the throttled function (the array slice) won’t be called) which could leave you with a missing array row on the screen. You also don’t want to use debounce because then then the list won’t update until it stops scrolling, which is worse. What you want is a function that is throttled AND debounced. (And composing the two does not work — either way you end up debounced.)
So I needed to write throttleAndDebounce and convince myself it worked. I also wanted to convince myself that the new subtly different throttle worked as expected. And since the former was going to be used in data-table, which I think is going to be a very important component, I really want it to be sure it’s solid.
- render table with 1M rows using b8r’s data-table — ~1100ms
Incidentally, ~600ms of that is rendering the list, the rest is just building the array.
At this point, scrolling is smooth but the row refreshes are not (i.e. the list scrolls nicely but the visible row rendering can fall behind, and live filtering the array is acceptably fast). Not shabby but perhaps meriting further work.
Profiling now shows the last remaining bottleneck I have any control over is buildIdPathValueMap — this itself is a function that optimizes id-path lookup deep in the bowels of b8r. (b8r implements the concept of a data-path which lets you uniquely identify any part of a javascript object much as you would in javascript, e.g. foo.bar.baz[17].lurman, except that inside of square brackets you can put an id-path such as app.messages[uuid=0c44293e-a768-4463-9218-15d486c46291].body and b8r will look up that exact element in the array for you.
The thing is, buildIdPathValueMap is itself an optimization specifically targeting big lists that was added when I first added the benchmark. b8r was choking on big lists and it was the id-path lookups that were the culprit. So, when you use an id-path on a list, b8r builds a hash based on the id-path once so you don’t need to scan the list each time. The first time the hash fails, it gets regenerated (for a big, static list the hash only needs to be generated once. For my 1M row array, building that hash is ~300ms. Thing is, it’s regenerating that hash.
So, eventually I discover a subtle flaw in biggrid (the thing that powers the virtual slicing of rows for data-table. b8r uses id-paths to optimize list-bindings so that when a specific item in an array changes, only the exact elements bound to values in that list item get updated. And, to save developers the trouble of creating unique list keys (something ReactJS developers will know something about) b8r allows you to use _auto_ as your id-path and guarantees it will efficiently generate unique keys for bound lists.
b8r generates _auto_ keys in bindList, but bindList only generates keys for the list it sees. biggrid slices the list, exposing only visible items, which means _auto_ is missing for hidden elements. When the user scrolls, new elements are exposed which b8r then detects and treats as evidence that the lookup hash for the id-path (_auto_) is invalid. A 300ms thunk later, we have a new hash.
So, the fix (which impacts all filtered lists where the _auto_ id-path is used and the list is not initially displayed without filtering, not just biggrid) is to force _auto_ keys to be generated for the entire list during the creation of the hash. As an added bonus, since this only applies to one specific property but a common case, in the common case we can avoid using getByPath to evaluate the value of each list item at the id-path and just write item._auto_ instead.
- render table with 1M rows using b8r’s data-table — ~800ms
And now scrolling does not trigger Chrome’s warning about scroll event handlers taking more than a few ms to complete. Scrolling is now wicked fast.