Possible O(n^2) instead of O(n) cost ?

[Dennis4b]

Consider the following example:

def test() = {
    val itemCount = 1000
    val filterText = Var("")
    val items = Var( (0 until itemCount).map(idx => (idx, s"Item ${idx}")))
    val filteredItems = items.signal.combineWith(filterText.signal).map{
        case (its, "") => its
        case (its, x) => its.filter(_._2.contains(x)).toList
    }

    div(
        div(
            input(
                `type`("text"),
                value <-- filterText,
                onInput.mapToValue --> filterText
            )
        ),
        div(
            children <-- filteredItems.split(_._1)( (idx, initial, fstream) => {
                div(s"I am item: ${initial._2}")
            })
        )
    )
}                                                                                            

(As test input, just enter for example "2")

With itemCount = 1000, it takes well under a second to react
With itemCount = 2000, it takes several seconds to react
With itemCount = 3000, it takes until the browser warns about stopping the script because things are taking so long

I believe this should be linear degradation in n. Could there be a list lookup (instead of map lookup), or nested iteration, or similar, causing the execution time to explode as n grows?

(yes, while unusual, I have a component like this in production, currently with React where this works ok-ish, but creating the next version in Laminar and running into this problem)

Happy to test any suggestions!

[Dennis4b]

Something like this would do it:
if (!prevChildren.contains(nextChild)) {
in ChildrenInserter.

Will try some ideas.

[raquo]

Thanks for the report, I reproduced the slowness locally.

By my first measures, surprisingly, it does not seem that ChildrenInserter#updateChildren it the culprit, the worst offender seems to be elsewhere. Looking into it now.

[raquo]

Actually, turns out I got distracted by another, less important, perf issue, but yes, ChildrenInserter#updateChildren is indeed slow for me when following the steps you described. Looking for alternative approaches...

[raquo]

Ok, I've worked through a lot of performance bottlenecks for this issue and related issues in Laminar and Airstream, and I have a solution.

I was using js.Array's indexOf method (and contains which let's assume delegates to that) rather liberally on arrays that could potentially be very large when rendering long lists of children. However, this alone wasn't as bad of a decision as it may sound. JS Arrays do not provide O(1) search, but they are nevertheless highly optimized in the browsers. Also, several years ago JS array were actually faster than js.Set and js.Map when I faced similar perf issues in my unrelated JS work (not in Laminar), from todays benchmarks I have to assume that js.Set / js.Map performance has improved dramatically in the meantime.

I have now tentatively switched to using js.Map for prevChildren in updateChildren, that alone gave a nice boost.

I also noticed that the indexOf implementation in the js.Array Scala.js type does not call the native JS Array indexOf method, instead it calls a Scala method which in my testing is approx 10x slower. That performance issue was actually not always the case. So for now I switched the bottlenecked js.Array-s in Airstream to a custom copy of the js.Array interface which delegates the indexOf method to the native JS implementation.

Together these two measures have pretty much solved this performance issue. In Firefox and fastOptJS, time to render after entering "1" or "2" went down from 2-4 seconds to <50ms on my machine when rendering 2000 items. With 10000 items rendering the "1" filter takes ~850ms, with 20000 items it takes ~1500ms.

But even the new logic gets exponentially slower as you go higher, e.g. 50000 items takes ~20 seconds to filter. However, that is not due to indexOf or contains, those account only for maybe 6% of that time. It is due to the browser taking this long to remove the nodes from the document. I'm not sure what can be done here because I'm not sure what commands I should be issuing to the browser's DOM API to make this faster. I tried several tricks like setting display=none or setting empty innerHTML before deleting the node, but it appears that browser vendors are smarter than me and have already optimized all of these quirky methods by the same amount, I did not get faster results.

Speaking of removing nodes... I did all of these benchmarks above by putting your list in a div with maxHeight("300px"), overflow("auto"). That is the only "trick" I found to improve performance. Without constraining the view like this, the document itself grew to be many pages long, and I think repainting all that area took the browser way too long, especially when removing nodes for some reason. So, if you intend to render such huge lists, at a minimum I suggest you put them inside a scrollable div, rather than make the <body> itself scrollable. I'm not sure why exactly the browsers find this easier, to deal with, but it is what it is. At least that's an easy hack.

Aside from this trick, seems that we're just hitting the browser limitations when it comes to removeNode performance.

If you need to render 50000 elements, I suggest reading about what makes for more expensive repaint / reflow / etc. and how to work around that. OTOH I don't know much about that.

You can also virtualize your list view, only giving Laminar a subset of rows to render, and changing that smaller subset as the user scrolls, that's a pretty common strategy. Downside is that ctrl+f does not work in such UIs, but it looks like you're implementing your own Ctrl+F UI or something similar anyway.

I asked in scala.js discord what my performance expectations should be regarding js.Array, let's see what they say. It might not be fixable in js.Array because it's supposed to follow Scala == semantics, whereas the JS Array's native indexOf does not. If that's the case, I guess I'll need to publish a library of raw js.Array / js.Set / js.Map interfaces that simply call to native JS methods as-is, semantics be damned. I have a feeling such a library might exist already, but I couldn't find it.

I'll publish the code I have in a few days for you to check it out, it's a terrible (but working) mess right now.

[Dennis4b]

Thank you for such a quick and thorough reply.

Let me start with saying I don't want to quite show 50.000 items :-) It's more of a grid which fits a few hundred items on a screen, with outliers to a few thousand (some users prefer this). Sub 1-second for 10.000 visible items as you describe would be an excellent result!

I tried some solutions, basically indexing the prevChildren to avoid prevChildren.contains/indexOf, and creating a ref lookup map to eliminate the containsRef and prevChildFromRef loops.

This made things a lot better, after which the bottleneck became the maybeChildren List in the ParentNode which also uses indexOf when manipulating the children.

I didn't think of falling back to plain javascript arrays, makes sense that they are highly optimized, and is good for the output javascript code size (compared to dragging in more Scala collections).

One other thing might be though, that once you're at such large lists, trying to make small adjustments by reordering, inserting, and removing, that you might as well just recreate the whole thing and replace it in a single step (where applicable with regard to component state). In fact I tried this for my component and the only issue there is the ~1 second delay when going from showing 0 to showing 2000 items. I think your fixes will actually help this case too though.

Will continue my component knowing this will be worked around / fixed, thank you and if you need me to test anything please let me know.

[raquo]

Ha, we followed very similar trails diagnosing this, it seems :) It's rare that I get to use the profiler, it was nice to hunt this down.

FTR, with my changes, repainting / reflowing will be the only bottleneck, so I think small adjustments (adding / removing a small number of elements) will actually work much faster than big adjustments and full re-renders, since the slowdown seems to be proportional to the affected element count and the repaint area, more or less.

[raquo]

@Dennis4b Please check that Laminar 0.14.1 and Airstream 0.14.1 solve the issue for you (without creating other issues...). To keep it (kinda) binary compatible this release only has ~90% of the performance I mentioned, but it's still plenty fast. I'll add a few more optimizations to 0.15.0.

[raquo]

@Dennis4b FYI it appears that the split operator in 0.14.1 behaves slightly differently – the memoization key that you provide (e.g. _.id) is compared using JS semantics rather than Scala semantics. If your keys are primitives or strings, that's fine, but if they're objects, this will now use reference equality instead of == equality. That wasn't intended, I'll need to change that back in the next version. I don't think this has a significant effect on performance, it's just a matter of using JS map vs Scala mutable.Map

[raquo]

I'll keep this issue open for visibility until we settle this completely.

[Dennis4b]

Wow you're fast! Will be a great addition to Laminar.

Couple of thoughts:

In my particular use-case (live filtering), I found that the construction times of these particular items to be shown/hidden also plays a role (there's a lot of information crammed into a small item on a big dashboard).

For this use-case ended up hiding/showing the items via a hidden css class. This means thousands of items subscribed to a blacklist of hidden ids, and this actually works very well. I will compare this approach to the final performance release of Laminar as it would simplify my code a bit.

I will try to test it soon but I'm not using scalajs-dom 2.0 yet and on Laminar 0.13.1, so I might have some legacy JS stuff to adapt.

Finally, I can't really judge the impact of the split operator memoization key, but I typically have a Scala object as the id (sometimes composite key, like (UserID,ProjectID) where these themselves are case classes wrappers to provide a type-safe Int, i.e. against accidental swapping), here, but I would not want you to unpleasantly surprise other Laminar users with a change that might affect their projects. I am happy to wait a bit longer.

[raquo]

Welp, yes, then 0.14.1 won't work for you properly. I just published Airstream 0.14.2 which should solve the issue, try it out whenever you're ready. BTW ScalaJS DOM 2.0.0 is actually a very easy upgrade, unless you have other dependencies that require the old version.

[Dennis4b]

The ScalajS DOM 2.0.0 requires a new scalajs-react lib which also requires some modifications, but I think I have it mostly working again.

Using Laminar 0.14.1 with Airstream 0.14.2 the testcase from the original report now flies along with 5000 elements! So I would say your changes are a great success.

When comparing hiding items versus removing/adding items in my use-case, due to the cost of creating items the showing/hiding "feels" slightly faster during live text filtering.

Another function is changing the sort-order of the elements, which basically reorganizes all thousands of items inside the same container. I didn't test this beforehand to have a reference, but at the moment this code runs as fast as the React version it replaces, which when used with a key (similar to split) I would imagine to be highly optimized already.

All in all very happy!

[raquo]

Closing this since everything seems ok with 0.14.2