{"parents":["9f3c4da588b542af2e11ddec4a86ce6c2e65a3a0","59f72bd9916af0ff2c90bb6cadf69176d3ae5d5e"],"patch":"diff --git a\/docs\/_data\/nav_docs.yml b\/docs\/_data\/nav_docs.yml\nindex 2a121249bb..dd5d072dcd 100644\n--- a\/docs\/_data\/nav_docs.yml\n+++ b\/docs\/_data\/nav_docs.yml\n@@ -57,3 +57,5 @@\n title: DOM Differences\n - id: special-non-dom-attributes\n title: Special Non-DOM attributes\n+ - id: reconciliation\n+ title: Reconciliation\ndiff --git a\/docs\/docs\/ref-07-special-non-dom-attributes.md b\/docs\/docs\/ref-07-special-non-dom-attributes.md\nindex c174deb030..ae0b5e7c6a 100644\n--- a\/docs\/docs\/ref-07-special-non-dom-attributes.md\n+++ b\/docs\/docs\/ref-07-special-non-dom-attributes.md\n@@ -4,6 +4,7 @@ title: Special Non-DOM Attributes\n layout: docs\n permalink: special-non-dom-attributes.html\n prev: dom-differences.html\n+next: reconciliation.html\n ---\n \n Beside [DOM differences](\/react\/docs\/dom-differences.html), React offers some attributes that simply don't exist in DOM.\ndiff --git a\/docs\/docs\/ref-08-reconciliation.md b\/docs\/docs\/ref-08-reconciliation.md\nnew file mode 100644\nindex 0000000000..1b3fcab0f0\n--- \/dev\/null\n+++ b\/docs\/docs\/ref-08-reconciliation.md\n@@ -0,0 +1,133 @@\n+---\n+id: reconciliation\n+title: Reconciliation\n+layout: docs\n+permalink: reconciliation.html\n+prev: special-non-dom-attributes.html\n+---\n+\n+React key design decision is to make the API seem like it re-renders the whole app on every update. This makes writing applications a lot easier but is also an incredible challenge to make it tractable. This article explains how with powerful heuristics we managed to turn a O(n^{3<\/sup>) problem into a O(n) one.\n+\n+\n+## Motivation\n+\n+Generating the minimum number of operations to transform one tree into another is a complex and well-studied problem. The [state of the art algorithms](http:\/\/grfia.dlsi.ua.es\/ml\/algorithms\/references\/editsurvey_bille.pdf) have a complexity in the order of O(n^{3<\/sup>) where n is the number of nodes in the tree.\n+\n+This means that displaying 1000 nodes would require in the order of one billion comparisons. This is far too expensive for our use case. To put this number in perspective, CPUs nowadays execute roughly 3 billion instruction per second. So even with the most performant implementation, we wouldn't be able to compute that diff in less than a second.\n+\n+Since an optimal algorithm is not tractable, we implement a non-optimal O(n) algorithm using heuristics based on two assumptions:\n+\n+1. Two components of the same class will generate similar trees and two components of different classes will generate different trees.\n+2. It is possible to provide a unique key for elements that is stable across different renders.\n+\n+In practice, these assumptions are ridiculously fast for almost all practical use cases.\n+\n+\n+## Pair-wise diff\n+\n+In order to do a tree diff, we first need to be able to diff two nodes. There are three different cases being handled.\n+\n+\n+### Different Node Types\n+\n+If the node type is different, React is going to treat them as two different sub-trees, throw away the first one and build\/insert the second one. \n+\n+```xml\n+renderA: \n+renderB: \n+=> [removeNode ], [insertNode ]\n+```\n+\n+The same logic is used for custom components. If they are not of the same type, React is not going to even try at matching what they render. It is just going to remove the first one from the DOM and insert the second one.\n+\n+```xml\n+renderA: \n+renderB: \n+=> [removeNode ], [insertNode ]\n+```\n+\n+Having this high level knowledge is a very important aspect of why React diff algorithm is both fast and precise. It provides a good heuristic to quickly prune big parts of the tree and focus on parts likely to be similar.\n+\n+It is very unlikely that a `` element is going generate a DOM that is going to look like what a `` would generate. Instead of spending time trying to match those two structures, React just re-builds the tree from scratch.\n+\n+As a corollary, if there is a `` element at the same position in two consecutive renders, you would expect to see a very similar structure and it is worth exploring it.\n+\n+\n+### DOM Nodes\n+\n+When comparing two DOM nodes, we look at the attributes of both and can decide which of them changed in linear time.\n+\n+```xml\n+renderA: \n+renderB: \n+=> [replaceAttribute id \"after\"]\n+```\n+\n+Instead of treating style as an opaque string, a key-value object is used instead. This lets us update only the properties that changed.\n+\n+```xml\n+renderA: \n+renderB: \n+=> [removeStyle color], [addStyle font-weight 'bold']\n+```\n+\n+After the attributes have been updated, we recurse on all the children.\n+\n+\n+### Custom Components\n+\n+We decided that the two custom components are the same. Since components are stateful, we cannot just use the new component and call it a day. React takes all the attributes from the new component and call `component[Will\/Did]ReceiveProps()` on the previous one.\n+\n+The previous component is now operational. Its `render()` method is called and the diff algorithm restarts with the new result and the previous result.\n+\n+\n+## List-wise diff\n+\n+### Problematic Case\n+\n+In order to do children reconciliation, React adopts a very naive approach. It goes over the list of children both at the same time and whenever there's a difference generates a mutation.\n+\n+For example if you add an element at the end:\n+\n+```xml\n+renderA: first<\/span><\/div>\n+renderB: first<\/span>second<\/span><\/div>\n+=> [insertNode second<\/span>]\n+```\n+\n+Inserting an element at the beginning is problematic. React is going to see that both nodes are spans and therefore run into a mutation mode.\n+\n+```xml\n+renderA: first<\/span><\/div>\n+renderB: second<\/span>first<\/span><\/div>\n+=> [replaceAttribute textContent 'second'], [insertNode first<\/span>]\n+```\n+\n+There are many algorithms that attempt to find the minimum sets of operations to transform a list of elements. [Levenshtein distance](http:\/\/en.wikipedia.org\/wiki\/Levenshtein_distance) can find the minimum using single element insertion, deletion and substitution in O(n^{2<\/sup>). Even if we were to use Levenshtein, this doesn't find when a node has moved into another position and algorithms to do that have a much worst complexity.\n+\n+### Keys\n+\n+In order to solve this seemingly intractable issue, an optional attribute has been introduced. You can provide for each child a key that is going to be used to do the matching. If you specify a key, React is now able to find insertion, deletion, substitution and moves in O(n) using a hash table.\n+\n+\n+```xml\n+renderA: first<\/span><\/div>\n+renderB: second<\/span>first<\/span><\/div>\n+=> [insertNode second<\/span>]\n+```\n+\n+In practice, finding a key is not really hard. Most of the time, the element you are going to display already have a unique id. When it is not the case, you can hash some parts of the content to generate an id. Remember that the id only has to be unique among its sibling, not globally unique.\n+\n+\n+## Trade-offs\n+\n+It is important to remember that the reconciliation algorithm is an implementation detail. React could re-render the whole app on every action, the end-result would be the same. We are regularly refining the heuristics in order to make common use cases faster.\n+\n+In the current implementation, you can express the fact that a sub-tree has been moved between siblings, but you cannot tell that it has moved somewhere else. The algorithm will re-render that full sub-tree.\n+\n+Because we rely on two heuristics, if the assumptions behind them are not met, performance will suffer.\n+\n+1. The algorithm will not try to match sub-trees of different components classes. If you see yourself alternating between two components classes with very similar output, you may want to make it the same class. In practice, we haven't found this to be an issue.\n+\n+2. If you don't provide stable keys (by using Math.random() for example), all the sub-trees are going to be re-rendered every single time. By giving the users the choice to chose the key, they have the ability to shoot themselves in the foot.\n+\n","commit":{"authorEmail":"vjeuxx@gmail.com","authoredAt":"2013-12-22T11:36:26-08:00","subject":"Merge pull request #411 from vjeux\/diff_algorithm","authorName":"Christopher Chedeau","revision":"0bbf535b7b2bf2195195a125f6cb4526d0173435","shortRevision":"0bbf535b7b"},"files":[{"status":"M","path":"docs\/_data\/nav_docs.yml"},{"status":"M","path":"docs\/docs\/ref-07-special-non-dom-attributes.md"},{"status":"A","path":"docs\/docs\/ref-08-reconciliation.md"}],"body":"Document the Diff algorithm"}}}}

dillon1000/react

Files changed