Riot: 8-10x slower than React at 10k item list reversal

[brianmfranklin]

I was very interested in seeing how fast Riot was compared to React based on the intro docs.

So I put together these simple demos to help me learn and compare.

10k item list with reverse button. After you click the button, you'll see the time it took to reverse and finish rendering. (Actually, in a separate issue, I don't understand why you have to click the button twice on the Riot version before the timing text appears.)

React: http://jsfiddle.net/brianmfranklin/w674Lv7p/
Riot2: http://jsfiddle.net/brianmfranklin/j05ukz2r/

On my MacBook Pro, I consistently get about 2500 ms for Riot, and only 250-350ms for React.

I thought maybe this was a quirk of how I was having to measure the timing. But it DOES seem to actually take longer to do the re-render.

Is this expected? Or are there more optimizations to do?

[GianlucaGuarini]

@brianmfranklin Thanks for your issue! Now we have a new test that will be used to check the speed of the riot rendering engine. We'll work on this

[rsbondi]

I get about 450 for react on my machine and about 1600 for riot. A little less dramatic. If I cut it down 5000 items it is about 450 for riot. This seems acceptable but performance enhancements are always nice..

[GianlucaGuarini]

I think we can still optimize a lot the riot rendering speed and fix the memory leak re-introduced with the new releases https://github.com/muut/riotjs/issues/480

[brianmfranklin]

I agree that losing the DOM element references is less than ideal. I am glad to have contributed in some way to any improvements that come of it.

I am not sure if 10k is a realistic real world case, at least not commonly, however I think it is reasonable to think someone might have a grid view with some x thousands of rows that get re-sorted when a heading is clicked. Somewhere there is a balance between the speed of the computer and the browser, the size of the list, and Riot's optimizations.

For anyone who is wondering, I realized why the timing text didn't get updated until after the second button click. It's because the automatic update() that gets invoked after the clicked() handler happens before the setTimeout() sets the timeTaken property. So you are actually seeing the timeTaken on the PREVIOUS reversal, not the one that just happened. Here is an adjusted version:
http://jsfiddle.net/brianmfranklin/j05ukz2r/10/

[pakastin]

Here's native test:
http://jsfiddle.net/xue5b5eg/2

appendChild method is a lot faster than insertBefore (at least in Chrome) and a bit surprise is that documentFragment method is not faster but slower.

I will work these results out to Riot.

[GianlucaGuarini]

@pakastin Awesome test, I think a combination of RAF + documentFragment would be awesome

[pakastin]

Here's requestAnimationFrame + documentFragment:
http://jsfiddle.net/xue5b5eg/3/

appendChild seems to be the fastest (Mac Chrome 41).

Edit: Actually in Safari requestAnimationFrame + documentFragment is the fastest and in Firefox all of them are almost equally slow.. And after some cycles Chrome slows down appendChild also. requestAnimationFrame + documentFragment seems to maintain performance better.

[pakastin]

I think we have to use documentFragment anyway, because there can be elements after iterated nodes (appendChild is out of question):

<p each="{items}">{item.title}</p>
<p>Element after iterated nodes..</p>

[GianlucaGuarini]

I think so too

[pakastin]

Here's a Riot-test with documentFragment updates:
http://jsfiddle.net/j05ukz2r/11/

There's something else wrong, because I still get delays over one second (compared to 30 ms on my native version). It's a bit faster than insertBefore though..

Here's what I did:
https://github.com/pakastin/riotjs/blob/dev/lib/tag/each.js

[pakastin]

documentFragment + requestAnimationFrame is not any faster:
http://jsfiddle.net/j05ukz2r/12/

[GianlucaGuarini]

Hmm.. it seems the problem is somewhere else..

[cognitom]

I think another possible bottleneck is Array.prototype.indexOf. Actually it takes more than 500ms just for this call in my setup. for loop would be 5 times faster.
http://jsperf.com/js-for-loop-vs-array-indexof/8

[cognitom]

Oh, really? Hmm...

[paldepind]

It looks like the algorithm inside _each is O(n^2). No amount of replacing x with y based on micro benchmarks is going to fix that.

Maybe supplying unique keys could be optional? Then a more efficient algorithm is possible.

[brianmfranklin]

I don’t know the internals of Riot at this point, but if appendChild is faster, then would it be possible to basically clear out the parent’s children, then rebuild the parent element out of 3 segments of children:

1. children before the iterated nodes
2. the reordered iterated nodes
3. children after the iterated nodes

Or would this cause other problems, e.g. with event handlers firing on these temporary node removals?

On Mar 9, 2015, at 1:36 AM, Juha Lindstedt <[email protected] [e-mail]> wrote:

I think we have to use documentFragment anyway, because there can be elements after iterated nodes (appendChild is out of question):

{item.title}

Element after iterated nodes..

—
Reply to this email directly or view it on GitHub https://github.com/muut/riotjs/issues/484#issuecomment-77816411.

[paldepind]

Ok. One of the reasons the React example is fast is because it doesn't preserve the elements between renders. We can tell React to reuse elements. This makes it about twice as slow in my tests. See for yourself: http://jsfiddle.net/paldepind/w674Lv7p/4/

[brianmfranklin]

A 2x difference from the normal React behavior (resulting in 1 sec to reverse) would still be quite an improvement and probably quite acceptable.

Notably, that 1 sec becomes around 4 seconds when doubling the list size to 20k with the keyed React demo. So there's certainly some dropoff point on the list size/performance curve, even with React.

[GianlucaGuarini]

I will be back on this as soon as other important bugs will be fixed #480 #475

[tipiirai]

Definitely need to address this one. My guess is that this is caused by cascading updates, since every time a parent is updated all the children are updated as well. I'm sure this can be fixed.

[pakastin]

Here is quite fast way to reorder:
http://jsfiddle.net/rju8rzmn/1/

1) request animation frame for all the following:
2) detach container from parent (add placeholder to keep place)
3) create documentFragment
4) move items to documentFragment
5) add documentFragment to container
6) attach container to parent (replace placeholder)

That all should happen during one event loop to prevent flashing to white.

[brianmfranklin]

Wow. That’s quite an improvement. And only takes 33% the time that the keyed React demo does with a 20k list.

Well done.

On Mar 10, 2015, at 3:56 AM, Juha Lindstedt <[email protected] [e-mail]> wrote:

Here is quite fast way to reorder:
http://jsfiddle.net/rju8rzmn/1/ http://jsfiddle.net/rju8rzmn/1/
1) request animation frame for all the following:
2) detach container from parent (add placeholder to keep place)
3) create documentFragment
4) move items to documentFragment
5) add documentFragment to container
6) attach container to parent (replace placeholder)

That all should happen during one event loop to prevent flashing to white.

—
Reply to this email directly or view it on GitHub https://github.com/muut/riotjs/issues/484#issuecomment-78032245.

[paldepind]

@pakastin, You're not only timing the actual reordering but also the idle time between the frames? I get a more accurate smaller timing by not doing that: http://jsfiddle.net/paldepind/rju8rzmn/4/

The performance is very impressive. For me it's quite a bit faster in Firefox though.

[GianlucaGuarini]

Tnx guys!! Would you like to make a pull request? I am really excited about the results in riot

[pakastin]

@paldepind, requestAnimationFrame triggers _before_ next DOM reflow. You have to wait for the next reflow to get correct results. Idle time between reflows is normally around 1/60th second, so it doesn't add that much extra time.

[paldepind]

I don't think this can be pulled. The problem is that @pakastin program rebuilts the entire list. This is faster in the current case when the entire list of elements is to be reversed. But, if only one item was moved, the current Riot implementation would only move one element but this code would still rebuilt the entire list.

@pakastin, The update happens inside updateElements(). You need to track the time spent inside that function to get accurate results. You're _also_ tracking the time the browser waits until the next frame. That is not relevant with regards to the speed of the DOM manipulations. For me in FF there is a quite significant difference between the two results.

[pakastin]

I created a test project for DOM updates and it happened to become a new framework called frzr!

It's heavily inspired by Riot.js 2.0, but doesn't have all the features like templating/binding/routing:
http://pakastin.github.io/frzr
http://github.com/pakastin/frzr

Be free to copy the ideas from frzr. I'm really busy right now with my own client projects, so I don't have that much time to contribute to Riot.js. If you have any questions, I'm happy to answer – there's not that much comments yet.

[GianlucaGuarini]

Thanks @pakastin we will update riot using also your contribute

[pakastin]

:thumbsup:

[brianmfranklin]

Is there any concern for a regression of performance during small reordering changes based on Simon’s comment?

On Mar 10, 2015, at 11:41 AM, Gianluca Guarini [email protected] wrote:

Thanks @pakastin https://github.com/pakastin we will update riot using also your contribute

—
Reply to this email directly or view it on GitHub https://github.com/muut/riotjs/issues/484#issuecomment-78119538.

[paldepind]

The current algorithm does something similar to an insertion sort (and a reversed list is the absolute word case for insertion sort btw). This will result in a single DOM node move if only a single element in the source list has changed position.

The code in @pakastin hardcodes a reverse operation and reinserts every child in the list. I don't think its suitable as a general purpose difference function for Riot.

[paldepind]

Here is a demo that shows how fast moving elements is with React: http://jsfiddle.net/paldepind/w674Lv7p/7/

It's not particularly snappy but it's significantly faster than the reverse operation.

[pakastin]

frzr actually appends only items next to each other in fragments, and in place - so it's also fast to move only few elements:
https://github.com/pakastin/frzr/blob/master/lib/mountAll.js

Detaching container doesn't matter (just speeds things up) if you make all the updates during the same cycle.

Logic here is similar to what I did to Riot. Only thing is that mounting gets done elsewhere so I couldn't implement it straight to Riot. But if someone knows mounting logic better in Riot, it shouldn't be that hard to do in Riot also.

[paldepind]

@pakastin, the algorithm you're using here looks like it's O(n^2). Could you show an example similar to the above demonstrating the speed of reversing a list and of moving a single element?

like I've said many times; you can't compare React because it replaces items' contents - and loses references in the operation.

That is not true. React preserves elements and their content. They do require users to supply keys, but it's a small price to pay for performance (and btw, Angular and virtual-dom takes advantage of unique keys as well).

[tipiirai]

@pakastin @paldepind Guys – would love to merge your expertise to Riot! I've had thoughts about using requestAnimationFrame but looks like you guys have some additional knowledge regarding to React and templating performance in general.

I'll also have a deeper look into this over the next days.

Great job.

[pakastin]

I'll check out unique key possibility and how it would change the rendering logic. I think it would require at least immutable array changing. Let's see how much faster it would be. I haven't thought about indexOf being slow, but I understand why it could be. I also haven't understood why Facebook created Immutable.js since now, but indexOf must be the reason why.

[tipiirai]

Do we need to make updates in batch with requestAnimationFrame?

[paldepind]

Hi again

I've created a very fast algorithm for updating/reordering children (I'm working on my own view library, hence my interest in this). Check out the demo here. It's identical to the last React demo I posted (the one that doesn't destroy elements, not the original).

Remarks:

• My demo reverses the list 5 times as fast as the React demo.
• In Chrome I get even better performance than the hand coded demos (which I is quite odd). In Firefox the hand coded demo is faster.
• Moving elements around is _instant_, no noticeable lag at all. The React demo has a very noticeable delay when moving elements.
• The algorithm is general – it can handle all types of reordering
• To achieve its performance it uses a JS object as a hash table. Thus it requires that all list elements have a unique key
• A each/map loop cannot appear in the same parent along with other elements. In Riot terms it means that this is supported:

<ul>
  <li each={ item, i in items }>{ item }</li>
</ul>

but this is not:

<ul>
  <li>I am and element with the same parent as the `each`
  <li each={ item, i in items }>{ item }</li>
</ul>

The last restriction could be fixed, but I'm not convinced of the utility. For now I've decided that this is a restriction in my view library to keep it simple an performant.

The source code is here. It's heavily commented. I'm sharing this here because I hope some of this could be useful to you guys.

[brianmfranklin]

In case it helps, that demo link comes up blank in Safari 8.0.3 (latest) on OSX Yosemite. Works in Chrome on OSX, though. Gives me around 100ms, although the rendering/repaint looks like it takes maybe half a second after that.

Here’s the Safari error:

[Error] TypeError: undefined is not an object (evaluating 'frag.children.length')
update (flyview.js, line 78)
(anonymous function) ([native code], line 0)
(anonymous function) (flyd.js, line 55)
updateStream (flyd.js, line 97)
updateStream ([native code], line 0)
stream (flyd.js, line 161)
map (flyd.js, line 55)
map ([native code], line 0)
attach (flyview.js, line 39)
handleContent (flyview.js, line 213)
v (flyview.js, line 245)
createMainView (script.js, line 42)
(anonymous function) (script.js, line 55)

As far as the scenario you describe about a static

with iterated

, I think a possible real world example would be a select/option list where’d you have something like:

Select a Color

and didn’t want to have to clone model.colors (and possibly then keep in sync), and insert an element at [0] for “Select a Color”.

If you do decide to keep it the way you’ve got it, then it might be good to at least mention that situation and how’d you recommend solving it.

On Mar 15, 2015, at 8:39 AM, Simon Friis Vindum <[email protected] [e-mail]> wrote:

Hi again

I've created a very fast algorithm for updating/reordering children (I'm working on my own view library, hence my interest in this). Check out the demo here http://paldepind.github.io/flyview/examples/reverse-list. It's identical to the last React demo I posted http://jsfiddle.net/paldepind/w674Lv7p/7/ (the one that doesn't destroy elements, not the original).

Remarks:

My demo reverses the list 5 times as fast as the React demo.
In Chrome I get even better performance than the hand coded demos (which I is quite odd). In Firefox the hand coded demo is faster.
Moving elements around is instant, no noticeable lag at all. The React demo has a very noticeable delay when moving elements.
The algorithm is general – it can handle all types of reordering
To achieve its performance it uses a JS object as a hash table. Thus it requires that all list elements have a unique key
A each/map loop cannot appear in the same parent along with other elements. In Riot terms it means that this is supported:

• { item }

but this is not:

• I am and element with the same parent as the `each`
• { item }

The last restriction could be fixed, but I'm not convinced of the utility. For now I've decided that this is a restriction in my view library to keep it simple an performant.

The source code is here https://github.com/paldepind/flyview/blob/gh-pages/flyview.js#L87-L142. It's heavily commented. I'm sharing this here because I hope some of this could be useful to you guys.

—
Reply to this email directly or view it on GitHub https://github.com/muut/riotjs/issues/484#issuecomment-81105903.

[brianmfranklin]

Also, thank you for creating this and sharing. I think that with the continued exploration of how to solve this problem — this among them — we really are going to end up with the best strategy or blend of strategies for quickly rendering, manipulating, and re-rendering complex views.

On Mar 15, 2015, at 8:39 AM, Simon Friis Vindum [email protected] wrote:

Hi again

I've created a very fast algorithm for updating/reordering children (I'm working on my own view library, hence my interest in this). Check out the demo here http://paldepind.github.io/flyview/examples/reverse-list. It's identical to the last React demo I posted http://jsfiddle.net/paldepind/w674Lv7p/7/ (the one that doesn't destroy elements, not the original).

Remarks:

My demo reverses the list 5 times as fast as the React demo.
In Chrome I get even better performance than the hand coded demos (which I is quite odd). In Firefox the hand coded demo is faster.
Moving elements around is instant, no noticeable lag at all. The React demo has a very noticeable delay when moving elements.
The algorithm is general – it can handle all types of reordering
To achieve its performance it uses a JS object as a hash table. Thus it requires that all list elements have a unique key
A each/map loop cannot appear in the same parent along with other elements. In Riot terms it means that this is supported:

• { item }

but this is not:

• I am and element with the same parent as the `each`
• { item }

The last restriction could be fixed, but I'm not convinced of the utility. For now I've decided that this is a restriction in my view library to keep it simple an performant.

The source code is here https://github.com/paldepind/flyview/blob/gh-pages/flyview.js#L87-L142. It's heavily commented. I'm sharing this here because I hope some of this could be useful to you guys.

—
Reply to this email directly or view it on GitHub https://github.com/muut/riotjs/issues/484#issuecomment-81105903.

[paldepind]

That error is odd. frag is the document fragment and it should surely have children with a length. I'll see if I can find a way to debug with Safari. Thanks for letting me know about this.

Your point about wanting a default select item is a good one. Another use case could be rendering some static data in a list followed by some dynamic data. Having to merge them together into one cumbersome I agree. I'll think about it and see if I can find a neat way to have the each/map coexist with other children.

I suggest Riot could do something like this. Keep using the O(n^2) algorithm if users do not want to supply unique keys and switch to a faster algorithm if they do. Furthermore I think the DOM manipulations done by the current algorithm can be speed up by using documentFragment and by detaching the element operated on from the document if a lot of reordering is going on.

[paldepind]

If you do decide to keep it the way you’ve got it, then it might be good to at least mention that situation and how’d you recommend solving it.

I've updated the algorithm to handle this case as well. A map/each can now exist in the same element as other children without any problems. It could be handled simpler than I expected – so that is good.

[krisselden]

The DOM is a tree with link-list structure for children, treating childNodes like it is an array and constantly using indexOf on it is no good (it is a view of this linked list that behaves like an array, last I checked only length was cached in webkit, but even if the array was cached if you are mutating it the cache wouldn't buy you much). I said as much here https://github.com/krisselden/simple-dom/issues/4#issuecomment-77890017

[tipiirai]

@paldepind thanks a million for sharing! Really valuable stuff. I hope I can get some time for this shortly.

[pakastin]

I also updated frzr to even more performant:
http://pakastin.github.io/frzr/

[paldepind]

I also updated frzr to even more performant:
http://pakastin.github.io/frzr/

Nice :)

I've tested in both Firefox and Chrome though, and for reversing yours is several times slower than the demo I linked above. I took a brief look at your code, and it looks like you're not taking the parent offline?

[pakastin]

I wanted a one good all-around method and decided to leave that out, because I think that's fast enough without. And it's hard to know when it's faster to take offline and when to keep on dom. Could add that back later if necessary.

One thing I noticed is that unshifting / removing can also be quite slow if not done properly (might trigger lots of reorderings). That's the main issue I worked on. Reversing is still just an extreme edge case.

[pakastin]

Another thing to notice is that frzr works in Safari as well. Even in iPhone 6 I get under 300ms reversing which I think is quite good. Flyview throws errors in Safari..

[GianlucaGuarini]

I will try to get a better rock solid unit test on the riot each rendering and as soon as this will be completed we could work also on this in order to avoid to break the existing features

[pakastin]

@paldepind Somehow I'm getting worse results dropping parent offline. I think results depend also on which DOM elements used. I'm using <p> because <li> is, for whatever reason, slower in Safari. Also I have event listeners bound in every item – maybe should propagate events. Let's see.

[pakastin]

Heureka! Here's some more things to notice:
https://gamealchemist.wordpress.com/2013/05/01/lets-get-those-javascript-arrays-to-work-fast/

..there's A LOT of interesting optimizations. Doesn't matter that much when dealing with small arrays, but boy they add up when you have 10 000 items.

An example:
http://jsperf.com/push-allocated-vs-dynamic

Really interesting stuff. Thanks @paldepind for bringing array optimizations up in the first place, I love you man! :D sorry I didn't listen you at start.. I didn't know about indexOf being so slow, not to mention these new stuff.

https://korynunn.wordpress.com/2013/03/19/the-dom-isnt-slow-you-are/
;)

[paldepind]

@pakastin, I see no reason why my library shouldn't work in Safari. I'll see what my options are with regards to debugging in Safari on Linux.

I find it odd that you're getting worse results when taking the parent offline. I consistently got better performance with that approach. Which makes sense to me.

The indexOf does a linear search so its performance grows proportional to the length of the array you searching in. Riot does that inside a loop over the list. That leaves you with a O(n^2) algorithm which will end up in horrible performance on large data sets.

A few questions about your algorithm

• You're using a unique ID just like me right? But frzr generates that ID automatically is that right? If that's true, then that could be a great approach for Riot.
• Do you handle additional elements in the same parent along with the looped elements? I can't see any code handling that.

[pakastin]

@paldepind My first quess was right: it depends on the wanted DOM structure – check out:
http://pakastin.github.io/frzr/test3.html – with <li>
http://pakastin.github.io/frzr/test2.html – with <li> and <a>Remove</a>
http://pakastin.github.io/frzr/test.html – with <p> and <a>Remove</a>

Small changes in HTML but a huge difference in DOM rendering speed..

[paldepind]

@pakastin Interesting. I'll have to take a closer look at that. What is your current conclusion. Is taking the parent offline generally worth it? To me it still seems to bring significant performance improvements, at least in some cases.

[pakastin]

It does seem to improve performance when reordering/removing high number of items - I'm not that sure about adding, if made with documentFragment.

[pakastin]

@tipiirai Would it be possible to attach tag to the DOM inside each.js and not inside tag.js?

Because effective adding would require documentFragment and that's not possible if tag.js adds to the DOM, and not each.js.

Should we create a dedicated branch for this new rendering logic and work together? I don't want to break anything I don't know for sure.

[tipiirai]

I think that's possible. Cannot figure out any reasons why not so feel free to fool around on a different branch. I'm happy to merge all kinds of performance improvements as long as the tests pass.

[rstuven]

Regarding performance in general, I found this comparison where Riot happens to be the slowest one :(
http://jsperf.com/angular-vs-knockout-vs-ember/585

[pakastin]

That's just a stupid test – you should always add elements in bunch, not one by one.

It should be:

for (var i = 0, len = 100; i < len; i++) {
  riotapp.data.push('ritem')
  // no update here!
}
riotapp.update() // ..but here

Edit: actually there is an updated version, which gives better results:
http://jsperf.com/angular-vs-knockout-vs-ember/590

It's not THAT bad. But we will make Riot even faster, that's for sure. Just have to decide some big changes first..

[GianlucaGuarini]

@pakastin Wow riot seems to be one of the fastest :laughing:

[rstuven]

@pakastin Of course. Updating in batches (as in the updated test, that uses a throttling of 16 ms ,~60 fps) is better for sure. I haven't examined how the other frameworks implement the update, but maybe the stupid test is just reflecting the fact that Riot does not have the throttling built-in and others have.

[pakastin]

Angular also have forced update, which was not in use in the old revision of the test. So it's not fair to compare without pushing updates in other frameworks as well.

Throttling is something many frameworks lack, but you can't always blame framework when user does basic things wrong. Sometimes it's harder to work with asynchronous framework, because then you lose the control and things become unpredictable.

And however you design the framework, someone will use it wrong anyway.

[pakastin]

I remember having implement throttling in at least Knockout, Angular and Ractive.js. It's just that some frameworks have automatic updating and some don't. I prefer having control.

Having said that, if you update by user action, you will have auto update in Riot as well. Then it uses throttling in sense that everything goes like it should be! So case closed :)

I will try to merge frzr's good parts to Riot as well. One thing I have to think about is how to deal with arrays containing other than objects. One option would be to have id's in tags, but let's see.

[GianlucaGuarini]

I will try to merge frzr's good parts to Riot as well. One thing I have to think about is how to deal with arrays containing other than objects. One option would be to have id's in tags, but let's see.

@pakastin take your time and go for it! Looking forward to seeing your work on riot

[tipiirai]

Can you just use a DOM property, such as my_dom_elem.riot_id = 'abc' so the property will not shown as an attribute? I'm not a fan of those react-id attributes.

[pakastin]

Me neither.. There is an id in tag already (someone added it there), but I think there should be one hidden in original array as well - otherwise have to keep on using indexOf. I used non-enumerable value in frzr, I think that would be ok in Riot as well? It works IE9 and up..

[pakastin]

@paldepind Have you thought about both of the following cases
(I'm not sure if your library already does this):

CASE 1:
  [1,2,3,4,5] -> [5,1,2,3,4]

  add first:
    [1,2,3,4,5] -> [5,1,2,3,4]
    (one move)

  remove first:
    [1,2,3,4,5] -> [2,3,4,5] -> [3,4,5,1,2] -> [4,5,1,2,3] -> [5,1,2,3,4]
    (four moves)

CASE 2:
  [1,2,3,4,5] -> [2,3,4,5,1]

  add first:
    [1,2,3,4,5] -> [2,1,3,4,5] -> [2,3,1,4,5] -> [2,3,4,1,5] -> [2,3,4,5,1]
    (four moves)

  remove first:
    [1,2,3,4,5] -> [2,3,4,5,1]
    (one move)

My suggestion is following:

CASE 1:
  [1,2,3,4,5] -> [5,1,2,3,4]
  [1,2,3,4,5] -> [[1,2,3,4], [5]] -> add first -> [[5], [1,2,3,4]]

CASE 2:
  [1,2,3,4,5] -> [2,3,4,5,1]
  [1,2,3,4,5] -> [[1], [2,3,4,5]] -> remove first -> [[2,3,4,5], [1]]

..so:

1) first group items which are next to each other in both cases (start, end)
2) then:

• if current group has more items than next group, add first
• if current group has less items than next group, remove first

New method might be slower in JavaScript (because of the grouping part first), but it should be way faster in DOM, because you always have smallest possible amount of DOM elements moving!

[tipiirai]

@pakastin: I'm curious – what are your plans around loops and riot?

[pakastin]

You are free to copy the ideas from frzr and from this conversation. I'm really busy at the moment and I have to try this new better grouped reordering idea with my own library first, since it's easier not to break anything there. There's also many edge cases in Riot which will have to think about (arrays of numbers or objects not having id's etc..). Also there are couple of reasons why I can't use Riot in my current client projects at the moment and I have my priorities finishing client work first asap..

[tipiirai]

Cool. Thank you for the update.

[paldepind]

@pakastin

Sorry, about the late reply.

Have you thought about both of the following cases

Yes, I have thought about those cases. And you're right that my library does not generate an optimal amount of moves in those cases. It will however group all of the moves together in a fragment so that the active DOM is still touched _only once_. Look at this example of yours:

add first:
    [1,2,3,4,5] -> [2,1,3,4,5] -> [2,3,1,4,5] -> [2,3,4,1,5] -> [2,3,4,5,1]
    (four moves)

Notice that all of the moved elements are moved to right before 1. So thanks to the lines I linked to above my library will add all the moved elements into the same fragment and only in the end insert that fragment before 1. This ensures pretty that performance is still quite good.

Your idea is interesting. But how would you do the grouping in JavaScript?

Btw, if you're curious you should also take a look at this method of doing children reconciliation
. It is from one of the very fastest virtual DOM libraries. I'm currently working on my own minimalistic virtual DOM which will hopefully be even faster ;)

[GianlucaGuarini]

It would be great if you guys @pakastin & @paldepind could join your skills and help us enhancing this riot feature honestly I don't know whether I will have soon time for this improvement. Let us know if you'd be interested

[pakastin]

@paldepind I also group all the moves together with documentFragment – the point was to only move the SMALLEST groups in the DOM and keep larger groups in place..

I will write an example....

[pakastin]

Here's grouping: http://jsfiddle.net/f07pLuL7/1/ ;)
Logic is similar to grouping with documentFragments.
Case 3 is random (hit refresh and see different results).

You can decide whether to add first or remove first by checking if current group is larger or smaller than the following one..

You don't really need even that much iterations:
http://jsfiddle.net/f07pLuL7/

..still just to prove a point, so not that optimized :)

[GianlucaGuarini]

@tipiirai @pakastin @brianmfranklin @paldepind
I am working on riot updating the each loops rendering and that's my first result:
http://jsfiddle.net/gianlucaguarini/cbjuek58/

the first rendering is a bit slow but if you try to update the DOM now it seems to be superfast (even faster than react)

[pakastin]

If you're working with Chrome, try with < li > -tags.. They seem to perform better and you can compare speed with @paldepind's flyview -demo ;)

Remember that the speed depends on HTML structure, so if you compare to anything, first check out you have identical HTML structure. Comparing to react you get a little help without those data-reactid's which slows react down a bit ;) And Safari is for some reason slow with < li >

Is there source somewhere for me to look at? I can give you tips on performance.. This is something I've studied a lot lately.

[GianlucaGuarini]

@pakastin I am working on the https://github.com/muut/riotjs/tree/feature/faster-loops branch it's not yet completed but I had to clean up almost the whole _each.js

[tipiirai]

@GianlucaGuarini I cannot help but admire how you lead this project.

[pakastin]

:+1:

[GianlucaGuarini]

@tipiirai no prob I would not do it if it wasn't enough fun :)

[GianlucaGuarini]

I think we could close this issue, with the new each.js riot gets much faster than react, check yourself http://jsfiddle.net/gianlucaguarini/cbjuek58/
If you want to test it you can pull the dev branch

[pakastin]

I think so too, great work! In many cases keeping it simple means faster results. Only with complex reordering situations you might get speed benefits, if grouping and moving smallest groups etc. I am using similar reordering right now with frzr as well and it seems to work really well also.

And in real life you won't be reordering 10 000 items.

Case closed! ;)

[cognitom]

Great!!
4 times faster than the first react example in my environment.

[tipiirai]

About 5 times faster on my laptop. So glad!

I need to write about this somewhere.

[pakastin]

React is actually even slower than Angular:
http://blog.500tech.com/is-reactjs-fast/
(notice: if Angular is used correctly with ngRepeat + "track by")

I don't understand where this "React is superfast" argument comes from. It is not that fast really. Facebook just (falsely) claim it is.

[paldepind]

@pakastin React is far from fast. It is one of the slowest virtual DOM libraries. Check out the VDOM benchmark. It is really easy to create a virtual DOM library that is faster than React. My virtual DOM library Snabbdom for instance is significantly faster and among the fastest in the VDOM benchmarks.

[geordee]

Not everyone is attracted by performance of VDOM alone. That would be just one small part of an app. Today in my mobile app, I am more bothered about repaints and reflows.

[simonvizzini]

Hey guys, I'm currently researching all the different UI frameworks out there and am specifically looking for something insanely fast that can handle a high amount of UI updates. I quickly came across the dbmonster demos, and since I couldn't find one for RiotJS I simply forked the ractive.js dbmonster demo and replaced it with riot.js. Swapping them was pretty straightforward, since this a rather simple demo, but I think it's a somewhat reasonable benchmark to get a visual impression of a frameworks performance (although I think it's far from a perfect benchmark for this kind of scenario).
Alright so I think I made it myself too easy, because my riot.js version doesn't perform that well, so I found the discussion here very interesting with regards to array performance, and I have yet to try out the dev version including the latest optimizations. Anyway, here is my 2.1.0 based demo: http://simonvizzini.github.io/riotjs-dbmonster

I have done a lot of research myself in the past month regarding array manipulation speed in JS, as well as efficient DOM rendering, and one main keypoint to fluent DOM rendering is the requestAnimationFrame loop. I see that the rAF has been mentioned in this issue here too, and from that I assume an rAF loop is not implemented yet in riot.js. For example the popular Velocity.js animation library is insanely good at minimizing layout trashing and DOM manipulations. It uses an rAF loop among other smart things to figure out the least amount of DOM manipulations required to display the next frame. I guess this is also something an UI framework could definitively use, but admittedly, velocity.js has the advantage that all updates follow some kind of mathematical formula, which makes things easier, while UI frameworks have to deal with "random" data updates, with possibly complex structures, like deeply nested data, with also possibly complex relationships.

Anyway, diffing is not a simple task, especially arrays with randomly complex objects are difficult as well as DOM diffing. But for now I I'll try the latest riot.js dev version and see how it performs on the dbmonster benchmark. I'll keep you updated.

edit: always screwing up markdown links

[tipiirai]

Please just update your benchmark to use the dev- version. You can copy/paste it from this jsfiddle. It uses batching and documentFragment. No reason to analyse the performance of the current version since the logic will change soon.

[simonvizzini]

I adapted the benchmark before I discovered this issue, so of course I will
try again with the dev version, I just got caught up in other things but I
will do it this evening and post back.

On Thu, Jun 4, 2015 at 12:45 PM, Tero Piirainen [email protected]
wrote:

Please just update your benchmark to use the dev- version. You can
copy/paste it from this jsfiddle
http://jsfiddle.net/gianlucaguarini/cbjuek58/. It uses batching and
documentFragment. No reason to analyse the performance of the current
version since the logic will change soon.

—
Reply to this email directly or view it on GitHub
https://github.com/muut/riotjs/issues/484#issuecomment-108836613.

[tipiirai]

Awesome. Looking forward to your findings.

[GianlucaGuarini]

@tipiirai @simonvizzini the newest riot with my patch runs at speed of light http://gianlucaguarini.github.io/riotjs-dbmonster/
@simonvizzini thanks for your test

[pakastin]

Btw. this fix doesn't seem to reorder DOM elements anymore, am I right?
That's a breaking change and might cause problems for some. At least for me reordering is a required feature.

I understand it is hard to implement, because you can't define an id-key for loop at the moment – maybe that's something needs to be added.

Maybe like this (Angular.js uses track -parameter):

<div each={item, i in items track '_id'}></div>

What do you think?

[GianlucaGuarini]

@pakastin could you define a use case? Maybe you can open a new issue

[pakastin]

Here's an example:
http://jsfiddle.net/chhn3Lkd/

With your patch:
http://jsfiddle.net/chhn3Lkd/1/

See the difference..?

My version is actually not perfect either – seems to fail when rotating from last to first (maybe index 0 return false or something..).

I'd rather not open a new issue, since it's not an issue yet..

[GianlucaGuarini]

what's the difference sorry? In the first you move DOM nodes, in the second you update DOM properties

[pakastin]

Yes that is the difference. Code is the same. How would you move the nodes in your version (second link)? That is the issue..

[GianlucaGuarini]

It depends what's a loop for you, for me a loop is data driven, this means that the javascript items change their position and not the DOM nodes that get refreshed with new data. This makes the DOM updates super fast without weird nodes reordering. The current code is also more readable, smaller and more efficient, I don't see any problem right now with that. @tipiirai what do you think?

[tipiirai]

Developer should only worry about the JavaScript items and let the DOM take care of itself without troubling how Riot does it. If the JavaScript items are reordered the DOM nodes should reorder accordingly.

[pakastin]

Think that you have a tree structure, where you render every depth concurrently. If you move a node having a deep structure, then it's easier to render only the DOM reordering, and not removing components in all depths and recreating them in the new place.. (If replacing branch doesn't have equal deep structure). There are lots of other use cases where reordering is needed.

Remember that the loops in Riot are not only data loops, but also there could be components involved.

[GianlucaGuarini]

The current riot in dev branch does not reorder the DOM nodes, it just updates their properties, and this makes the updates really fast. @tipiirai please let me know if this is an issue because I must rewrite the _each.js again otherwise

[simonvizzini]

@GianlucaGuarini dbmonster with the latest dev version indeed looks much, much better! :) I had a long weekend and no access to a computer at all, so thanks a lot for updating the demo! Performance now looks really promising, great work guys and keep it going!

[pakastin]

We can change the default for now, but we should get "track key" (or similar) parameter soon to fix that..

I can develop the reordering part, but I don't know how to add a new parameter to tag syntax (regexps are not my cup of tea).

[pakastin]

Reordering is not that much slower, the only issue was using indexOf to track moving items, but "track by" parameter would change that.

Your way is a good default and we can go with that for now, but we need reordering as well.

[tipiirai]

@pakastin: using DOM reordering or redrawing all components are both implementation details and we should use whatever works best on a particular situation. Totally makes sense that DOM reordering is fastest with complex structures.

@GianlucaGuarini I think we want that the DOM nodes are also reordered. Really hope this doesn't turn into a massive project with a lot of extra code on the each.js. Perhaps evaluate that first? Maybe sorting could be a plugin? I rarely (or never) need sorting myself.

[tipiirai]

Agree with @pakastin, that we can release this version without reordering. This way we can also see how much it is actually needed.

[GianlucaGuarini]

I agree, we need to add this to the release-notes .. and let's see how many complain about that

[tipiirai]

Yup.

btw: just noticed that I _didn't_ actually agree with @pakastin :) Just this part:

Your way is a good default and we can go with that for now

[GianlucaGuarini]

@tipiirai I thought about it and I decided I could start working in a new branch on the DOM reordering and see how further I could go with it. In the meantime you can still work on the opened bugs https://github.com/riot/riot/issues/773.
What we need to consider is that we have no pressure for a new release soon, so let's wait and see what I could achieve, in the meantime I will reopen this bug

[pakastin]

I can write the DOM reordering (I have it ready actually), but I'd need the "track" property to be added to tag parsing, i.e. like this:

<div each={item, i in items track '_id'}></div>

That's the only way to effectively do the reordering (without indexOf)..

[pakastin]

Of course the need of reordering depends on the situation – I have even some use cases where it is the only way. I agree sometimes it is not needed. That's why the optional "track" property would be perfect.

Angular, React, Ractive, etc all have that also.

[tipiirai]

Glad to see you working on this @pakastin.

Instead of an extra track, can't you always use hidden DOM property on loops?

[pakastin]

Tracking DOM elements won't help anything. The thing is to be able to reference old and new array items with a key which could be used in lookup table. That's pretty much the only efficient way to reorder elements.

@paldepind said it also:

Maybe supplying unique keys could be optional? Then a more efficient algorithm is possible.

[paldepind]

Tracking DOM elements won't help anything. The thing is to be able to reference old and new array items with a key which could be used in lookup table. That's pretty much the only efficient way to reorder elements.

I agree. I don't know of a single children reconciliation algorithm that doesn't support optional keys when preserving elements is important.

[pakastin]

@paldepind 's snabbdom has a great example where reordering is helpful:
http://paldepind.github.io/snabbdom/examples/reorder-animation/

Works (almost) like this:
• Check position before removing from DOM
• Animate to new position when added back to DOM

Here's how it's really done.
Would be pretty hard to implement without reordering.
Although this example would also require Riot to have proper mount / unmount events..

[pakastin]

Another good example would be having a social media feed, where you'd want to add new items to the top. Without reordering all the items would have to re-render, which is not that efficient. There are a lot of use cases if you think about it.

[tipiirai]

Gotcha. Looks like you guys know a think or two about sorting DOM elements. Glad to have you onboard :)

[GianlucaGuarini]

@pakastin are you working on this? I would like to avoid to work in two on the same thing. Will you have time soon for a pull request?

[pakastin]

I would, but I really need to have a tracked key first. Who's done templates' parsing? One should add "track" -parameter there, like I exampled a bit up from here.. I really suck with regexps, so I think it's better to be done by someone else.

[tipiirai]

If possible I actually prefer not to introduce a new attribute for sorting. track is just extra burden for the user. It's implementation details and does not directly benefit the user. Would be best if Riot could do the tracking behind the scenes. I guess we can tolerate an extra DOM attribute if that is required.

[GianlucaGuarini]

Ok I will see if I could use the tags._id properties to reorder the DOM nodes as well, it shouldn't be too complicated, I will work on it asap

[pakastin]

I can't understand what will you compare that tags._id to, since it's a random number?

Trust us (me and @paldepind) when we say specifying a key is the only way (besides indexOf, which is unoptimal). We both have done a huge amount of work lately finding the most optimal iterations/reorderings.

Track key parameter would be an optional one to the advanced users (like it is in almost every other frameworks as well). Most of the people won't need that ever and would be just fine with Gianluca's simple version, which will also be the fastest way in most of the cases.

It would be a win-win for everyone, right?

[GianlucaGuarini]

@pakastin you are right make a pull request proposing your solution and let's see how fast is the rendering and how much more code is needed. Once we will have and alternative we could decide whether keeping just the DOM updates or using the nodes sorting solution. Let me know if you are gonna do that before I'll waste my next weekend working on it :smile:

[tipiirai]

@pakastin any way to solve this without introducing the new track- syntax?

[GianlucaGuarini]

After many tests I have decided to keep the current riot each method ( without DOM reordering ).
The fastest libraries here are the ones updating the templates not the children ( without any DOM reordering ) ( see vuejs, react, and backbone).
I think the next riot release will use the current each method (the one in the dev branch) that is small, fast and clear.
Anyway I will keep this issue open for a while.
@tipiirai I hope you could agree on this with me

[tipiirai]

Totally fine with that. No reason to block the development because of the lack of reordering.

btw: last time I checked the child elements lacked the parent reference on dev- branch.

[GianlucaGuarini]

@tipiirai could you check please the dev branch? Let me know if you still have the problem

[pakastin]

I'd argue the reasons for slowdowns are somewhere else. Here's 10 000 items reordering:
http://jsfiddle.net/ohaf2jxn/

Here's documentFragment -version, again 10 000 items reordering:
http://jsfiddle.net/ohaf2jxn/1/

I'm getting ~30-40 ms rendering time (Chrome/Safari) – I don't think that's slow..

[GianlucaGuarini]

Thanks for your input @pakastin but I think in this post we have a bit lost the point.
Here some thoughts about the topic:

1. in your demos you just reorder a list without any data lookup, and even in that case the rendering is slower than the current riot in the dev branch
2. I have tested several solutions and you are right, the rendering it's not slow but the items position lookup by using indexOf or even track slows down the loops
3. Other libraries such as vuejs, backbone, rivetsjs, react, do not really reorder the DOM nodes but they simply update them using a template engine (sometimes just strings) making the whole rendering fast ( try for example the iframe example also with other libraries and you will see what I mean)
4. The old riot each is x3 bigger, slower and more complicated to mantain (~110 lines vs 40 ) than the current version I consider this a win not a con
5. If anyone is able to bring back the DOM reordering in riot without bloating the source code and with the same performances of the current version I will be more than happy merging it

Right now I consider this topic closed and I am moving forward improving other riot features. Discussing about this without any new pull request is pointless to me
Thanks anyway for your help without you guys the riot loops probably wouldn't run at speed of light

peace :v:

[tipiirai]

~110 lines vs 40

That is just fantastic job @GianlucaGuarini !

[gut4]

Just a question. I need to make drag-n-drop sortable list. Is it possible with new version of each.js without dom reordering?

[GianlucaGuarini]

@gut4 of course it will.. It all depends from your code base. You should always keep your html list in sync with your javascript data collection.

[GianlucaGuarini]

Riot 2.2.0 is finally out! I will close this issue hoping our users will not complain the old each method :smile:

[geekingreen]

Awesome!

[MauriSalazar]

great!

[diegochavez]

I just got mesmerized with all the hard work, this is great!. I learn a lot of stuff!

[brauliobo]

there is clealy a regression in 2.3.x (tried 2.3.15), it requires more than 10s for the same jsfiddle. In best cases it takes 2s. Riot 2.4.0 is taking 1,5s here. Riot 2.2.4 takes less than 300ms.

that is probably related to the huge slowdown I'm having to render a big list (more than 40s to render)

I'll probably revert the app back to riot 2.2.0 if there is no easy fix for this?

[brauliobo]

@GianlucaGuarini the version you posted at http://jsfiddle.net/gianlucaguarini/cbjuek58/ still take less than 100ms, is it possible to use that same code in new riot versions?

[GianlucaGuarini]

Just use the no-reorder option an you should be fine

[brauliobo]

With no-reorder the rendering took +500ms on riot 2.3.15 and +1000ms on riot 2.4.0. Still not satisfatory IMHO. Shouldn't the most performant version be the default?

PS: Edited the original fiddle at http://jsfiddle.net/brianmfranklin/j05ukz2r/

[brauliobo]

Also it is important to note that the slowdown also applies to the initial rendering, which makes a really bad user experience in the page load.

[GianlucaGuarini]

@brauliobo it's already on our todo list https://github.com/riot/riot/issues/1694 . This does not mean that rendering huge lists on the clientside with any framework is not insane IMHO

[brauliobo]

nice @GianlucaGuarini. one thing to note is that the improvement proposed at http://jsfiddle.net/paldepind/rju8rzmn/4/ is taking +400ms to render, so still http://jsfiddle.net/gianlucaguarini/cbjuek58/ is much better (and also riot 2.2)

[brauliobo]

btw, in my usecase the list has almost 6k items, the each loop is using virtual and has 5 elements inside, and that is taking almost 60s for riot.mount to finish

[brauliobo]

sorry for buzz here, the issue I have is actually another problem, reported at #1819