Here are the articles I've written regarding .NET development.
Something that occurred to me after I'd posted part 5 in my red-black tree series is that I was relying on you, the reader, visualizing the rotations and recolorings in my insertion example. I should have shown each intermediate step for each insertion, rather than just the end result. Doing so would have helped you picture the changes that are happening during this process. Read more..
In our previous installment, we'd introduced the principles behind red-black trees as well as an appreciation of why they would produce more balanced binary search trees than pure randomness by using a process called a rotation. Then we got stuck when actually inserting a node. Obviously this is one algorithm we are going to have to crack in order to be able to build a red-black tree that we can search. Read more...
Last time in this series on red-black trees, we convinced ourselves that leaving the balance of binary search trees to chance was pretty good but not completely optimal. Even if we could guarantee that we added items in a completely random order to our trees (and, to be honest, that's an unrealistic expectation), we would still only get average search times of 1.39 * log2(n), instead of the theoretic log2(n). So we shall have to exploit an "active" balancing algorithm, and the best one we know of is the red-black tree. Read more...
A couple of evenings ago, my wife was reading an article about a federal prosecutor, when she suddenly exclaimed "How many digits of π (pi) do you know? Because this lawyer knows 500 digits." I had to admit that I'd only memorized π to eight decimal places, 3.14159265, but I immediately jumped in with "I know how to write a program that can print out thousands of digits of π." So she threw down the gauntlet. Read more...
Dustin Campbell manages to display source code in his blog posts with the Visual Studio syntax highlighting. So, go on, how do you do it, I asked. Simple, as any fule kno, he said. When you copy source code with Visual Studio, it creates a data block in rich text format (RTF). Take that clipboard data, parse it, and output HTML. I could see that he felt I wasn't up to writing an RTF parser. Hah! Moi? Read more...
In this continuing series on red-black trees, we've now seen how to insert into a normal binary search tree. In fact the implementation and code were so simple, it's hard to even recognize that anyone would want to do anything else. Why invent more complicated binary trees, when the binary search tree seems to do so well? Read more...
Now that I have the technology available to draw trees quickly and accurately (and you have seen the algorithm and its implementation at first hand), it's time to go back to the main subject: red-black trees. Except that I have some more foundation to lay first. So in this episode we'll look at binary search trees, and how to insert new nodes into them. After all, visually, a red-block tree is a binary search tree with colorful nodes. Read more...
After my few recent rants, I need to cleanse myself with some hardcore algorithms and data structures. That's what you're here for, right? Read more..
Man, that was fun. A friend IMed me recently with a problem. It seems that he has some data from a legacy system (I know, yuk, and I can see you wiping your hands on your shirt from here), that was a floating point value in single precision MBF (Microsoft Binary Format). In case you didn't know — I didn't — this is the format used by CVS and MKS$ in Microsoft QuickBASIC and GW-BASIC, those fabby-dabby BASIC interpreters from MS-DOS days. Hey, I wrote my first BASIC program with GW-BASIC; no sniggering at the back. Yes, Virginia, we are talking l-e-g-a-c-y. Read more...
In the last installment, I'd got to the point where I could write code in C# to enumerate all the tracks in the iTunes library. I now need to do a little more work in order to select various tracks for inclusion in my random playlist. Read more...
Enough of all this angst, let's get down to some programming and algorithms. Read more...
Last time in this series on hazard pointers I looked at how the concept could help provide a node reuse manager for a lock-free stack using C#, admittedly without fleshing out the details of how hazard pointers would work under the hood. This time I just want to look at the lock-free queue in the same way, to see how hazard pointers would help provide lock-free memory management. Next time, we'll delve into the C# code for the hazard pointers themselves. Read more...
Back in September, I discovered a subtle bug in my node reuse code for my lock-free data structures. The bug has a name, the ABA problem, and I kind of promised to come back and solve it at some point. Well, it's a New Year, that was then and this is now, so let's go ahead and solve the problem. It helps that my January 2006 article for The Delphi Magazine solves the ABA problem for Delphi, and that implementation was the hardest, at least in theory. Anyway, unlike my thinking at the time, we're going to use hazard pointers to implement a lock free node reuse algorithm in C#. Pointers? C#? A contradiction, or just nasty unsafe code? Read more...
Every time I have to do this, I forget and have to look it up again. The last time, I thought I'd remembered how to do it and then wasted the next 10 minutes because I'd actually remembered it the wrong way round (well, I was tired, and an article had to be finished). The "this" I'm talking about? Implementing triangular matrices. Read more...
Let's have a little bit of fun today and talk about a minor yet elegant algorithmic change to a singly-linked list to make it a teensy bit more functional, and in doing so talk a bit about generics. This is certainly not earth-shattering stuff, but merely an enjoyable diversion from the horrors of your daily development. I'll be using C# 2.0 to implement this algorithmic amuse-bouche, so fire up your Visual Studios. Read more...
Um, I have an apology to make. There is a very subtle bug in my C# implementations of the various lock-free data structures. Sigh. And by subtle I mean very subtle, like the difference in taste between Vittel and Evian. Read more...
Last time I was visiting Microsoft, the organizers for the event I was attending had provided a trip to the company store, together with a voucher allowing us to spend up to $120 on software and hardware. Before you start thinking that's way too little to buy anything of import, realize that the Microsoft Company Store has deep discounts. Amongst other things, I picked up a copy of Encarta Premium 2007 for $20. I like Encarta (I'd bought my previous version of it at the company store too), but this time, it came with a little frisson. If you like algorithms (duh, that's why you're here) and you program in Visual Studio 2005 and .NET 2.0 and want a little fun, read on. Read more...
So last time, just like a cheesy Saturday morning movie serial, I left you hanging, wondering how I was going to solve the insoluble in C#. The insoluble issue in this case is the fact that we have two items of information that will vary independently of each other in different threads, but that we need to see as a unit when we write new values of them using CAS. And, of course, the size of both items is more than the size we can CAS. Read more...
Last time in this series of articles on lock-free linked lists we pointed out some of the issues we needed to solve in order to have any chance of implementing such a data structure. These were to do with deleting nodes from the list: the first being that deleted nodes could not be disposed or reused since other threads may still be using them, and the other was the problem of inserting a node after a node that was just about to be deleted. I ended with the subtle hint that we would have to add some extra fields to our node class. Read more...
Every now and then I just need to do some programming. Not only that, but something I haven't done before, preferably translating some weird code from something like an academic paper or from a book by Knuth into C#. So something algorithmic or data structure-y: I want to continue learning and being stretched. Read more...
Back in November 2005, I wrote a series of articles on writing lock-free data structures in C# and illustrated the concepts with a lock-free stack, queue, limited-priority queue, and a free list. All seemed well, except several people have commented that I never uploaded the source code and please could they have it? Why didn't I acquiesce? Read more...
I happened to be browsing through the Microsoft Research site last night, when I came across a project that I'd read about some months back, filed it as "interesting, must come back and read some more", but filed it in short term memory instead of in OneNote, and promptly forgot about it. (Updated: Wed 12-Apr-2006) Read more...
There's a coding anti-pattern in C# that's very prevalent but inefficient. I'm going to guess its popularity is due to the fact that most C# developers have come to C# from a non-managed code language, such as C++ or Delphi. I'm referring to the double-casting anti-pattern. Read more...
I had occasion over last weekend to do some research for an article on
the .NET memory model. Since the article was for Delphi readers (that
is, those using some version of Delphi for .NET) I needed to
illustrate my point using Delphi code, and in particular the
equivalent to the C# volatile keyword. There isn't one.
(Updated: 7-Feb-2006) Read more...
Time to start on this little project of mine to design and write a thread pool class. No sooner than I decide this course of action, though, that first, work and my personal life explode (sigh), and that second, Maxx, a fellow architect here shows me Joe Duffy's post on why you shouldn't write a thread pool, or, rather to be fair, why many people's reasons for doing so are not valid. Hah! I shall forge on since Joe's argument is mostly about performance. Nevertheless, I shall bear his posts on multithreading in mind as I TDD myself to a solution. Read more...
So a reader commented about my WaitableThread class. "Couldn’t you use a custom thread pool for this?" and encouraged me to take a look at a "smart" thread pool on Code Project. As it happened, the one he was recommending was one I'd taken a look at previously. Yes, you see the developer who wanted to launch lots of threads (see my previous post) had discovered this implementation and was all for using it. I took a look at it and decided that I could see enough problems on a cursory examination that I didn't want to use it for real code. Hence, the effort to write a WaitableThread class. Read more...
Continuing my occasional series on multithreading in C# and .NET
("continuing" in the obsessive sense of this just becoming a blog about
multithreading ), here's a quick implementation of a special kind
of thread, one that can be waited on. Hang on, I hear you say, that's
what Thread.Join() is for isn't it?
Read more...
Over the course of my work over the past month or so, I've been very involved in multithreading and concurrency, especially with regard to C# and .NET. As a first approximation (!) to my involvement, witness my recent articles on lock-free data structures in C# 2.0 (here'sthe final one; it has links to the others), but here's another item in the same general area that you may also find interesting and useful. Read more...
Last time in this series on building lock-free data structures in C# 2.0 we designed and implemented a lock-free queue, a FIFO structure that doesn't use locking to ensure correct thread safety. In doing so we also built a lock-free free list to ensure that we wouldn't block on the memory manager when allocating nodes. This time we'll tie it all up by creating a lock-free priority queue, one for a limited number of priority values, based on the code I wrote earlier. Read more...
In my previous article in this series on lock-free data structures, I'd implemented a lock-free queue. In doing so, I showed that despite the simplicity of the underlying data structure, making it perform in a lock-free manner in a multithreaded application was no mean feat.
In my closing remarks though, having breezily talked through the design and the implementation of the non-blocking queue, I briefly noted that there was a problem with the dequeuing operation (and indeed there was the same problem with the popping operation in the stack): there was no guarantee that a node had been finished with once the underlying linked list had been updated. Read more...
Last time we looked at implementing a lock-free stack, a stack that can be used in multithreaded applications but that doesn't need locks (such as mutexes) in order to provide thread-safe operation. This gave us an appreciation for one of the basics of lock-free programming: the Compare-And-Swap (CAS) function. This time we'll look at how to implement a queue, another very basic data structure, but this time things start getting difficult. Read more...
It's a fact that lock-based concurrency doesn't scale: only one thread at a time can execute the thread-safe code that's being protected by a lock or a mutex. The more threads there are accessing the lock, the more will be just sitting there waiting. Read more...
Recently, my brother-in-law, who programs in VB.NET, needed a priority queue that also had some behaviors of a normal queue: dequeue should remove the highest priority item as usual, but if there were two or more objects with the same priority, they should be removed in arrival order (also known as FIFO or first-in-first-out order). The normal heap implementation of a priority queue could not do that since it takes no account of arrival order; the only ordering is by priority and if there were several items with the same priority, they'd be returned in some non-deterministic order. Read more...
The solution to this problem has just wasted the last 2 hours of my life, so I thought I'd post it here for everyone else and for future reference. If you are developing as LUA (a least privilege user) then you'll find that you can't sign assemblies. Read more...
There seems to be a common pattern in some of the stuff I've been reviewing recently at work. In essence, there are several classes that implement some behavior such that an instance of one of the classes can be "opened" and then "closed" after use, after which it is no longer used. Also each class encapsulates a non-memory resource and hence needs a finalizer. A prime example of the resources being protected in this manner is a file, but others include sockets and the like. Read more...
Yesterday we were debugging a Windows service written in .NET. The issue being debugged was that sometimes (it seemed to happen mostly on Windows 2000 Server, but not every time) the service would hang during stopping. After some work we found the bug and also found how to abort a service start-up request in .NET. Read more...
This is one of the errors that FxCop spits out and it gets depressing, it happens so often. "Depressing, why?" I hear you ask. Mainly because I've never taken the time to understand what it's on about. Well, tonight I had time to work it out, not that it took a lot of working out. Just one of those things that if you took the time to understand it, it would hold no horrors. (Updated: 15-Mar-2003) Read more...
I've been code reviewing a part of Enterprise Configuration Manager (ECM) over the past week or so, mainly in an effort to help polish the code and also to identify possible problems before they surface and bite our collective butt. The part I've been involved with is the largest part that is implemented in C# and the .NET Framework. Read more...
How many .NET applications do you run on average? Do you remember the first time you had to install the .NET Framework? If you're a developer, it probably was for Visual Studio for .NET. How about for the average Joe? Read more...
If you're using delegates or events in a multithreaded application, be aware of a small subtlety when you invoke a delegate and when you remove a method from a delegate or event. Read more...