Persistence, Facades and Roslyn's Red-Green Trees

Persistence, Facades and Roslyn's Red-Green Trees

Rate This
  • Comments 23


  • Immutable.
  • The form of a tree.
  • Cheap access to parent nodes from child nodes.
  • Persistent.










  • This post could have used some pictures of the whiteboard to illustrate the concepts presented.

  • I have been reading you blog for a number of years, and this might be my first comment, so I would first like to thank you.  I love the "esoteric" details that you go into and love the background and context that is gives to the language I have been spending a vast majority of my time developing in.

    Out of curiosity, as an implementation detail, what is the number of children per node that the team decided to use?  And could you talk about the reasoning for that decision as well?

    I ask because I have been learning Clojure, and have seen discussions on its persistent and immutable data structures where the decided that they are using 32 children per node, giving them a log32 n, instead of log2 n that is typically seen.

    It would be interesting to hear what informed your teams decisions, and then be able to compare and contrast them to Rich Hickey's decisions when developing Clojure, as developers of two different languages, both of which run on virtual machines, and where those underlying frameworks (CLI vs JVM) might have made a difference.



  • "We are at present doing experiments to see if we can reduce some of the costs without losing the benefits."

    Hmm, isn't a bit late in the project to do something like this? :)

    @Steven Proctor: The syntax tree nodes don't have a fixed number of children, after all they need to represent the syntax, a binary operator will probably have 3 children (left, op, right) and an "if" could have at least 4 (if, cond, then block, else block).

  • Re: Mike

    I think Roslyn is C# 5.0, and Visual Studio 2012 will only come out with C# 4.5, so without Roslyn

  • Given that the red tree is both immutable and created on-demand, then presumably if you ask for the same child node twice you'll get two different objects.  (Because otherwise you'd have to alter parent nodes to keep references to the freshly generated children.)  So the red tree is rebuilt and thrown away every time you traverse it, not just every time there's an edit.  Is that right?

  • @Andomar You're confusing different things. Visual Studio 2012 comes with C# 5.0 (biggest change: await) and .Net 4.5. The finished version of Roslyn is supposed to be released some time (probably quite a long time) after Visual Studio 2012.

    But since Roslyn doesn't change the C# language or the .Net framework in any way, it may be released without changing the version number of C# or .Net.

  • Thanks a lot for covering this, I have been wondering about this and exact three problems you listed! Your solution makes a lot of sense. I guess GC pressure must have been another important factor you considered in your design? How bad is discarding the red tree on every edit in that regard? How often is the full red tree needed?

    Other blog posts about the internals of Roslyn would be very welcome! In particular, design decisions regarding the handling of trivia and the bindings between the syntactic tree and semantic model would be great!

  • ... so the purple text is coming back /soon/, right? :)

    OT: this sounds like a really neat solution: simple (logically, at least!) and flexible - I'll probably end up stealing the idea at some point! I can potentially see a usability issue with people assuming identity holds across traversals, but even on that metric the tradeoff seems pretty clearly in favor of immutability. I'd love to know what sort of performance cost you're looking at though, compared to a mutable tree: are we talking 10%? 2x? 10x? Even then I'd probably pick the immutable implementation in many cases.

    (looks like it dropped my post again?)

  • Great information as usual. I am glad the markers were not Black and Blue, that would have given rise to some interesting speculation...

  • Hi Eric

    Would be that kind and response to my comment on SO?


  • I love this kind of fly-on-the-wall posts.

    @Mike: I hope it's never too late to revisit implementation details. Roslyn is a large project, but since it doesn't implement all of C# or VB, it couldn't even have come to the point where it passes all tests, leaving plenty of time for wringing out performance before it needs to settle. Maybe you're confusing it with the public APIs that they want to settle early on so that people can get comfortable with them and know that the ground's not going to be moving beneath them as they start to build on them.

    @carlos: He didn't say "always" created on demand. It would be trivial to keep returning the same red node if the green tree (or maybe even green node) hadn't changed.

  • I assumed part of the reason for making these nodes immutable was so they could be used from multiple threads without need for any locks (or even for lock-free techniques, for that matter). But if the red nodes are created on demand, I take it that must mean you *do* have some locking around that lazy-creation?

  • So what happens if I want to manipulate the tree, inserting a node, etc. Is it possible to reuse parts of the red tree? Or is the API read only in general? It seems to me that the separation green/red has some advantages and making this separation explicit in the API would be beneficial in many applications.

  • Sounds fairly close to zippers (

  • Regarding your comment on the migrated settings, I think it would only be fair that you should save your fellow developers some work and just officially change your name to Carl Nolan!

Page 1 of 2 (23 items) 12