React's Diff Algorithm

http://calendar.perfplanet.com/2013/diff

by vjeux • 13 years ago

143 21 13 years ago

calendar.perfplanet.com

enginous• 13 years ago

I think the stuff React is doing is impressively simple and non-magical. Although I haven't used React yet, I wouldn't be surprised if these ideas make for code that's relatively easy to reuse and reason about.

The format of the post is also quite nice; a few short points with illustrations and a clear takeaway.

Touche2• 13 years ago

I use React and like it a lot. The biggest issue it has right now is there is no good way for a component on one branch of the tree to get information to a component in another branch. You have to talk to your parent components by having them attach a function as a property, and this simply doesn't scale to large or even medium sized applications.

peterhunt2• 13 years ago

This model usually works pretty well for smaller components (see http://facebook.github.io/react/blog/2013/11/05/thinking-in-...)

For larger ones, we provide lifecycle hooks so you can set up these subscriptions manually. In componentDidMount() and componentWillUnmount() you can subscribe/unsubscribe to some sort of messaging system, and when you receive the message call setState(). Usually you only need to do this in a few places and the regular React dataflow will carry you the rest of the way.

Does that make sense? We should probably write up this technique.

skybrian• 13 years ago

This isn't specific to React; in large GWT apps we use an event bus. Perhaps you could do the same thing?

Or, instead of an event-based approach, you could could pass in an object and use Object.observe() to observe state changes.

It looks like React just implements the view in MVC, so you still need a separate way to observe the model.

tomhallett• 13 years ago

I've been using React for a few months - it definitely does make for code which is easy to reuse and reason about.

The part of the architecture which has had the biggest impact on my code: the relationship between a component and it's subcomponents. A parent component can only pass "props" to it's subcomponents (ie it can't pass state, which is easily mutable). And a child component can only call a function on it's parent if that function is provided to it via props (ie a callback).

This design has forced me to reason about the interface between components (open/closed principle, law of demeter, etc) and has really improved my code.

Also, the team is very active/helpful in their irc room.

pornel• 13 years ago

React's rendering looks really awesome, but I'm missing the bit that binds application data to views.

e.g. in KnockoutJS I can just use observable arrays and properties and never have to call `setState()` on anything. What's the equivalent for React?

Touche2• 13 years ago

setState is equivalent to an observable. The only problem is that it's specific to the component you're working in, you have to get that information to others manually.

peterhunt2• 13 years ago

You can very easily do this by combining Object.observe() (or a polyfill) and calling forceUpdate().

However we've found that this sort of data binding is suboptimal since it encourages mutation which forces you out of some great perf optimizations (like the Om stuff, and Object.observe() has its own performance penalties). And thinking about your data flow a little more explicitly makes it easy to follow where updates are being triggered from (so a mutation in one part of your app doesn't accidentally trigger updates all over the place).

Most of the time doing this explicitly is a little more typing up front but is worth it for larger apps from a performance and maintenance perspective. If you start building with React you'll find that your data model flattens out as you go down the view hierarchy so this becomes less of an issue.

juliangamble• 13 years ago

You can read more about how React combined with immutable data structures provides great performance in this blog post by David Nolen http://swannodette.github.io/2013/12/17/the-future-of-javasc...

vjeux2• 13 years ago

If your model is managed by a lib that provides callbacks when a piece of your model is updated you can make a mixin like it has been done for Meteor and Backbone integrations:

https://github.com/benjamn/meteor-react#how-it-works http://eldar.djafarov.com/2013/11/reactjs-mixing-with-backbo...

schrijver4• 13 years ago

I wonder if React’s algorithm could be used to implement support for ‘operational transformations’ on DOM trees?

OT is the technique used for collaborative editing, etherpad-style. Current implementations don’t work with conventional DOM’s: Etherpad has its own model of plain text with an additional ’attribute pool’. Libraries like http://sharejs.org/ only know to deal with plain text and JSON.

I would love if I could implement a collaborative editor that hooks into an existing HTML element on the page, in the way contentEditable allows for in single-user apps.

cf https://github.com/share/ShareJS/issues/1

amix• 13 years ago

For OT to work you would need the ability to track all the changes and mirror them to the other users. React appears to have the ability to track changes, but I am unsure how easy it would be to mirror them over the network.

There's a great article here that describes how OT and other synchronization algorithms work (OT is event passing): https://neil.fraser.name/writing/sync/

vjeux2• 13 years ago

React internals support being used in a web worker. It should be easy to send it via XHR.

Now, synchronizing two clients is going to be more tricky. The diff algorithm works on the virtual DOM which is the result of an arbitrary javascript execution.

So while it's certainly possible to synchronize and merge the virtual DOM. You'll need to also feed this result back to the javascript program that generates this virtual DOM. The next time you call render, it should return the new merged virtual DOM.

This would be a pretty exciting thing to be able to do, i'd love to see a demo :)

moonboots• 13 years ago

Instead of performing OT at the DOM level, you could do it at the data/JSON level with ShareJS and continuously feed this JSON into React.

schrijver4• 13 years ago

If the underlying data is structured as plain-text or JSON, I think that’s the way to go. But I’m specifically thinking of collaborative rich text editing, in which case you’re probably using HTML both as the data format and the presentation/editing format.

dangoor2• 13 years ago

There's a diff match patch library in JavaScript that can be used for this. In fact, we did use it in Mozilla Bespin

https://code.google.com/p/google-diff-match-patch/

Diff match patch is not necessarily easier than OT.

schrijver4• 13 years ago

That’s for plain text no?

kenster07• 13 years ago

It would seem that browsers could implement the exact same algo using native code and achieve far better performance.

This raises the question: why aren't browsers already using this or something superior?

tel• 13 years ago

Probably a big difference in the API applied; the DOM model may be much more flexible than what React allows.

dangoor2• 13 years ago

I implemented something similar for Brackets so that it could do "live development" of HTML. In an editor, it's not uncommon to need to reparent a node, so our algorithm supports that.

I had a chance to speak with some of the React team at JSconf.eu and there are similarities in our approaches, but it turns out that what you're trying to ultimately do (an editor vs. an rendering application views) makes a big difference.

For those curious, here's the talk about what goes on in Brackets:

http://2013.jsconf.eu/speakers/peter-flynn-kevin-dangoor-omn...

React's Diff Algorithm

Related Stories