This is the story of how I was no-hired by Microsoft; surprisingly, it is germane to our discussion of unusual list structures. Continue reading
Last time on FAIC I gave a standard implementation of a persistent immutable linked list, with cheap — O(1) —
IsEmpty operations, and expensive — O(n) —
Concatenate operations. In this episode we’re going to implement a Hughes list, which “flips” those costs:
IsEmpty become O(n),
Concatenate become O(1).
Push stays O(1) also. This data structure is useful for scenarios where we are accumulating a large list “from both ends” or out of smaller lists, and then want to read the whole thing out as a normal list once we’re done the accumulation.
As long-time readers of my blog know, I’m a big fan of functional persistent immutable list data structures. I recently learned about a somewhat bizarre but very practical implementation of such lists, and naturally I wanted to implement it myself to try it out. The list data structure I’m going to discuss today is called a “Hughes list”, after its creator John Muir Hughes. The Haskell implementation is called “DList”, which stands for “difference list”, and this data structure is also commonly used in Prolog and Scala.
We decided early in the Roslyn design process that the primary data structure that developers would use when analyzing code via Roslyn is the syntax tree. And thus one of the hardest parts of the early Roslyn design was figuring out how we were going to implement syntax tree nodes, and what information they would proffer up to the user. We would like to have a data structure that has the following characteristics:
- The form of a tree.
- Cheap access to parent nodes from child nodes.
- Possible to map from a node in the tree to a character offset in the text.
So what does the keyword “
volatile” mean, anyway? Misinformation abounds on this subject.
Last time we established that an “atomic” read or write of a variable means that in multithreaded scenarios, you never end up with “halfway mutated” values in the variable. The variable goes from unmutated to mutated directly, with no intervening state. I also talked a bit about how making fields of a struct
readonly has no effect on atomicity; when the struct is copied around, it may be copied around four bytes at a time regardless of whether its fields are marked as
readonly or not.
I get a fair number of questions about atomicity, volatility, thread safety, immutability and the like; the questions illustrate a lot of confusion on these topics. Let’s take a step back and examine each of these ideas to see what the differences are between them.
First off, what do we mean by “atomic”? From the Greek ἄτομος, meaning “not divisible into smaller parts”, an “atomic” operation is one which is always observed to be done or not done, but never halfway done. The C# specification clearly defines what operations are atomic in section 5.5. The atomic operations are: reads and writes of variables of any reference type, or, effectively, any built-in value type that takes up four bytes or less, like int, short and so on. Reads and writes of variables of value types that take more than four bytes, like double, long and decimal, are not guaranteed to be atomic by the C# language. (There is no guarantee that they are not atomic! They might in practice be atomic on some hardware. Or they might not.)
At long last, let’s get to that double-ended queue. Sorry for leaving you in suspense!Continue reading
Based on the comments, the implementation of a single-ended queue as two stacks was somewhat mind-blowing for a number of readers. People, you ain’t seen nothing yet.Continue reading
Good Monday morning all. I have received a lot of good comments on this series so far that I thought I would speak to a bit.Continue reading