7

In a post called What is this thing you call "thread safe"?, Eric Lippert says:

Thread safety of immutable data structures is all about ensuring that use of the data across all operations is logically consistent, at the expense of the fact that you're looking at an immutable snapshot that might be out-of-date.

I thought the whole point of immutable data structures is that they do not change and therefore cannot be out of date, and that therefore they are intrinsically thread-safe

What does Lippert mean here?

8
  • 7
    A print newspaper is immutable. Can a print newspaper be out of date? Dec 7, 2020 at 16:17
  • Fair point, but in the article, Lippert is talking about thread-safety specifically. He might have said "Immutable data structures are immutable therefore they are thread-safe", but instead he said that whole thing about " ensuring that use of the data across all operations is logically consistent", which sounds like there's something more to be careful about that simple immutability. Dec 7, 2020 at 16:22
  • 2
    Eric L. didn't just say "immutable," he said "immutable snapshot." That implies that there is some data structure that could change at any time, and that the immutable "snapshot" is a frozen copy of the state of that data structure, as it was at some instant in the recent past. While one thread looks at the "snapshot," and makes decisions based on its content, some other thread could be updating the "live" copy. Dec 7, 2020 at 16:25
  • 2
    If the original data structure were immutable, then there would be no need for a "snapshot." The article that you cited, clearly says, "snapshot." Dec 7, 2020 at 16:38
  • 1
    @NathanHughes: Thanks for sharing that; I had not seen it before. Pure functions on immutable data structures which are embedded in a world that is constantly changing through time is exactly the situation an IDE is in, and we considered many of the ideas presented in that document when designing asynchronous workflows. But there is still a lot to do to make them more usable. Dec 9, 2020 at 1:47

2 Answers 2

18

What does Lippert mean here?

I agree that the way I wrote that particular bit was not as clear as it could be.

Back in 2009 we were designing the data structures for Roslyn -- the "C# and VB compiler as a service" -- and therefore were considering how to do analysis in the IDE, a world where the code is almost never correct -- if the code were correct, why are you editing it? -- and where it can be changing several times a second as you type.

I thought the whole point of immutable data structures is that they do not change and therefore cannot be out of date, and that therefore they are intrinsically thread-safe.

It is the fact that they do not change that makes them possibly out of date. Consider a common scenario in the IDE:

using System;
class P
{
  static void Main()
  {
    Console.E
  }
}

We have immutable data structures which represent the world at the moment before you typed "E", and we have an immutable data structure which represents the edit you've just made -- striking the letter E -- and now a whole bunch of stuff happens.

The lexer, knowing that the previous lex state is immutable and matches the world before the "E" re-lexes the world just around the E, rather than re-lexing the entire token stream. Similarly, the parser works out what the new (ill-formed!) parse tree is for this edit. That creates a new immutable parse tree that is an edit of the old immutable parse tree, and then the real fun starts. The semantic analyzer tries to figure out what Console means and then what you could possibly mean by E so that it can do an IntelliSense dropdown centered on members of System.Console that begin with E, if there are any. (And we're also starting an error-reporting workflow since there are now many semantic and syntactic errors in the program.)

Now what happens if while we are working all that out on a background thread, you hit "backspace" and then "W"?

All that analysis, which is still in flight will be correct, but it will be correct for Console.E and not Console.W. The analysis is out-of-date. It belongs to a world that is no longer relevant, and we have to start over again with analyzing the backspace and the W.

In short, it is perfectly safe to do analysis of immutable data structures on another thread, but stuff perhaps continues to happen on the UI thread that invalidates that work; this is one of the prices you pay for farming work on immutable data out to worker threads.

Remember, these invalidations can happen extremely quickly; we budgeted 30ms for a re-lex, re-parse and IntelliSense update because a fast typist can get in well over ten keystrokes per second; having an lexer and parser that re-used the immutable state of past lexes and parses was a key part of this strategy, but you then have to plan for an invalidation that throws away your current analysis to happen just as quickly.

Incidentally, the mechanisms we needed to invent to efficiently track those invalidations were themselves quite interesting, and led to some insights into cancellation-based workflows -- but that's a subject for another day.

1
  • 3
    Wow. You were clearly dealing with a much nastier problem than I am. I'm just trying to deal with a very rare bug where one thread modifies a list that's in the middle of being enumerated in another thread. It's rare only because the time window when it can happen is very small, but it does cause considerable damage. The fix is just to make a ConcurrentList<T>, which uses locking internally, and when you call GetEnumerator, it clones the list and returns the enumerator for the copy, thus an "immutable snapshot". Your article really helped me understand how to think about the whole situation. Dec 10, 2020 at 19:14
2

He means that you might be looking at a different snapshot than someone else. Consider how cons lists work: after adding another element to the head of a list, there are effectively two lists (snapshots). Both of them are immutable but not the same.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.