Coder Social home page Coder Social logo

Comments (13)

Dennis4b avatar Dennis4b commented on June 18, 2024

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

Will try some ideas.

from laminar.

raquo avatar raquo commented on June 18, 2024

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.

from laminar.

raquo avatar raquo commented on June 18, 2024

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...

from laminar.

raquo avatar raquo commented on June 18, 2024

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.

from laminar.

Dennis4b avatar Dennis4b commented on June 18, 2024

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.

from laminar.

raquo avatar raquo commented on June 18, 2024

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.

from laminar.

raquo avatar raquo commented on June 18, 2024

@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.

from laminar.

raquo avatar raquo commented on June 18, 2024

@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

from laminar.

raquo avatar raquo commented on June 18, 2024

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

from laminar.

Dennis4b avatar Dennis4b commented on June 18, 2024

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.

from laminar.

raquo avatar raquo commented on June 18, 2024

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.

from laminar.

Dennis4b avatar Dennis4b commented on June 18, 2024

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!

from laminar.

raquo avatar raquo commented on June 18, 2024

Closing this since everything seems ok with 0.14.2

from laminar.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.