performance and ideas

[ghost]

Hi. During the last month I studied your work, and adopted the concept of Javascript. I'm used to another language. So I deep dive into this to try to catch up with your brain. After all you become my inspiration.

Here is what I discovered so far. Prototype you are using are given a lot of overhead. In fact 35% slower then object iteration. Specially use of the new keyword.

However. What is bad are your IE performance. You should create the node, insert to DOM and then do a render. I figured it out from here: https://github.com/localvoid/vdom-benchmark/issues/15#issuecomment-71689398

Further is your patching. It is not optimal at all, but as you are writing it's the best so far... But you are not handling keyed nodes effecient enough. You are using O(n3). In fact this means that displaying 1000 nodes would require in the order of one billion comparisons. CPU expensive.

I solved it in my test project when I wrote my own patching. I give you something to study here

// all happen in a single while loop...

// 
if (childBKey != null) {  // build keys for this part

} else if (childAKey != null) { // build keys for this part too

I will not go in dept on this because you are probably not so interested, but my buildKeys() would then become

 var res = {},
        i = 0,
        len = children.length,
        child;

    while (i < len) {
        child = children[i];
        if ( child._key != null) { (res[child._key] = i); }
        ++i;
    }

    return res;

I only pass in either old or new children here, and later on I do a comparison like this

 childrenAKeys = childrenAKeys || buildKeys(childrenA);
if (childBKey in childrenAKeys) {

} else {  
childrenBKeys = childrenBKeys || buildKeys(childrenB);
}

If no keyed nodes, as will become a last check of the if else , I do it simple

function(childA, childB, idx, childrenPatch) {
    var childPatch = [];
    patch(childA, childB, childPatch);
    if (childPatch.length) {

        childrenPatch.push({
            idx: idx,
            patch: childPatch
        });

    }

[ghost]

If I directly compare my test project with domLayer in a benchmark, I will say domLayer are around 170+ in average when it comes to patching. My test are around 40+.

Huge difference I found here:

[5,100] ["insertLast(1)","skip"] render() 119 552

Where domLayer are on the right side.

and also this one

[50,10] ["removeLast(1)","skip"] render() 123 580

And you are using prototype solution, and so do I. Still if we look at SnabbDom where you got your ideas from I got this result here:

[5,100] ["reverse","skip"] render() 236 511

Where snabbDom are on the right side.

And we also need to compare it with citoJS who are actually very very fast, and I come up with this:

[50,10] ["insertFirst(1)","skip"] render() 122 380

CitoJS are on the right side.

This happen because of the way I handle the keyed nodes, and also because I'm now using a non-optimal O(n) algorithm .

[ghost]

Ah I forgot to mention that I also have option to set a unique key - key node - on the text itself for faster comparison.

[jails]

I'm not sure to get what you mean by "Prototype you are using are given a lot of overhead. In fact 35% slower then object iteration". Would be easier to understand with some piece of code illustrating the Prototype vs Object iteration you are talking about.

Performance is only one point to consider. For example the following code:

ref = create(vnode); // creates root level node
parent.appendChild(ref);
render(vnode); // renders subtree

requires to know where it's going to be inserted. In a object oriented approach, the separation of concern is imo the main point to consider.

So imo a virtual dom element need to work in insulation:

var button = new Tag("button");
var buttonFragment = button.render();
var buttonHtml = button.toHtml();
etc.

If you need for some optimization concerns introducing a additionnal requirement like a reference to an existing parentNode which has anything to do with your architecture logic, imo you are wrong. I want to be able to create dom fragments without have them inserted in the dom for example.

Optimizating shouldn't be done to the detriment of your architecture choices otherwise it's an anti-pattern imo.

So if it's slow on IE, it's a shame but I prefer to keep my code clean. Anyhow this behavior might be change on Edge. It's something on which I've no control so...

I think you missunderstood the algorithm, it's not O(n3), it's in 2O(n) in the worst case. At each iteration, one child is sorted out.

Anyhow if you acheived better performances feel free to open a PR, I'm really interested on how you where able to gain some CPU cycles.

[ghost]

Have a look at this jsperf: http://jsperf.com/object-notation-vs-constructor/31 This for prototype vs objects etc.

[ghost]

I think nothing changed on Edge. I will say yours are in overallTime around 500 000 comparing to citoJS around 27 000. And REACT around 248 000. Your render are alone 28 424 most of the time.

Problem is that I have no qlue how to integrate my patching solution as a PR because totally different approaches. It would need a re-write of some sort, and you are the only one who know this code 100%

[jails]

Oh indeed but all these syntaxes has different meanings. When you want a clean Object Oriented architecture the Prototype layer is not an option.

That's a shame for IE. If I find an alternative which allow better performances without breaking the architecture I will fix it for sure. Hopefully the render part is not the most important one.

[ghost]

I can show you the patch algorithm I'm using, and it will probably not break your architecture if you modify it, and it will be faster. In fact it's build after the same pattern, with optimizations on key nodes.

The main differences are simply things like:

patch.push(new removeChild(childA, iB));

and

patch.push(new appendChild(childB));

Btw. How it goes with your component?

[jails]

I've a workable draft but I'll need to clean it up a bit since it still a bit messy

[ghost]

Seems like we are in the same boat. I also made component thing, but still messy. And I'm cleaning up the patch algorithm now so at least you see how I do things. I will post soon. There are some sub-functions as well, but need your point of view first on the main code.

[jails]

Well it still a bit messy because I didn't had the chance to work on it a lot, I'm needed to finish an ORM in PHP first and it took longer than I expected.

[ghost]

Ok. Have a look at this draft:

function(node, childrenA, childrenB, patch) {

        var hasChildrenA = false,
            hasChildrenB = false,
            iB,
            iA;

        if (childrenA && childrenA.length) {
            hasChildrenA = true;
        }

        if (childrenB && childrenB.length) {
            hasChildrenB = true;
        }

        if (!hasChildrenB) {
            if (hasChildrenA) {
               // Remove all nodes from childrenA
            }
            return;
        }

        if (!hasChildrenA) {
            iB = 0;
            while (iB < childrenB.length) {
               // Append all nodes from childrenB
            }
            return;
        }

        var childrenALen = childrenA.length,
            childrenBLen = childrenB.length,
            childrenPatch = [];

        if (childrenALen === 1 && childrenBLen === 1) {
             patchChildWithChild(childrenA[0], childrenB[0], 0, childrenPatch);
        } else {

            iA = 0;

            var childA, childB,
                childAKey, childBKey,
                childrenAKeys, childrenBKeys,
                skippedAIndices = {},
                minMovedAIdx = childrenALen,
                foundAIdx, foundIdx, foundChildA, skippedCnt;

            iB = 0;
            while (iB < childrenBLen) {
                childB = childrenB[iB];

                while (skippedAIndices[iA]) {
                    ++iA;
                }

                if (iA >= childrenALen) {
                    // Append all children from 'childB'
                    ++iB;
                } else {
                    childA = childrenA[iA];
                    childAKey = childA._key;
                    childBKey = childB._key;
                    if (childBKey != null) {
                        if (childAKey === childBKey) {
                            patchChildWithChild(childA, childB, iB, childrenPatch);
                            ++iA;
                            ++iB;
                        } else {

                            childrenAKeys = childrenAKeys || buildKeys(childrenA);

                            if (childBKey in childrenAKeys) {
                                childrenBKeys = childrenBKeys || buildKeys(childrenB);
                                if (childAKey == null || !(childAKey in childrenBKeys)) {
                                    // remove the children here
                                    ++iA;
                                } else {
                                    foundAIdx = childrenAKeys[childBKey];
                                    skippedCnt = 0;
                                    if (foundAIdx < minMovedAIdx) {
                                        minMovedAIdx = foundAIdx;
                                    } else {
                                        for (var j = iA + 1; j < foundAIdx; j++) {
                                            if (skippedAIndices[j]) {
                                                ++skippedCnt;
                                            }
                                        }
                                    }

                                    foundIdx = foundAIdx - skippedCnt + iB - iA;
                                    foundChildA = childrenA[foundAIdx];
                                    skippedAIndices[foundAIdx] = true;

                                    if (foundIdx !== iB) {
                                        // move children here based on the 'foundIdx'
                                    }
                                    patchChildWithChild(foundChildA, childB, iB, childrenPatch);
                                    ++iB;
                                }
                            } else {

                                childrenBKeys = childrenBKeys || buildKeys(childrenB);

                                if (childAKey != null && !(childAKey in childrenBKeys)) {
                                    patchChildWithChild(childA, childB, iB, childrenPatch);
                                    ++iA;
                                } else {
                                    // insert children here (childB, iB);
                                }

                                ++iB;
                            }
                        }
                    } else if (childAKey != null) {
                        childrenBKeys = childrenBKeys || buildKeys(childrenB);
                        if (childAKey in childrenBKeys) {
                            // insert children (childB, iB);
                            ++iB;
                        } else {
                            // remove all children (childA, iB);
                            ++iA;
                        }
                    } else {
                        patchChildWithChild(childA, childB, iB, childrenPatch);
                        ++iA;
                        ++iB;
                    }
                }
            }

            while (iA < childrenALen) {

                if (skippedAIndices[iA] === true) {
                    skippedAIndices[iA];
                } else {
                    // Remove children (childrenA[iA], iB));
                }

                ++iA;
            }
        }

        if (childrenPatch.length) {
            // Update children (childrenPatch));
        }
    };

[jails]

Seems interesting but I don't think I will be able to get all the nuances. But if it passes all the specs and it's faster you did a good job ;-)

[ghost]

The code are running just fine and smooth on my computer, and tests are good. So are the performance. One thing thought, is that you could - as I did in the background - add a unique key on the child nodes as well, and for faster look-up and comparison. So my virtual text is like this:

    this._text = "";
    this._key = null;

The key is just the same as the parent, so I know what set it belong to.

[jails]

So maybe you should be able to apply this coding pattern on it http://debuggable.com/posts/programming-psychology-return-home-early:4811de9f-ae28-49c2-a7dc-2f154834cda3 ;-)

I didn't added key for text because I envisioned to build virtual doms from a template language like JSX or in HTML. And with a template language you can't have more than one text node inside a tag.

<div>one text node only here</div>

But if you have some different usage in mind, why not.

[dfilatov]

@marcorra Why do you copy/paste code from my project (https://github.com/dfilatov/vidom/blob/master/lib/nodes/TagNode.js#L144) without any references and says that it's your test project?

[jails]

Haha, thanks for the head up @dfilatov ;-) Btw how did you stumble on this issue ?

[dfilatov]

@jails just by chance