Sunday, March 25, 2012

Lock-free Queue (Single Producer Single Consumer)

I was searching for an efficient thread-safe queue implementation last week for my project at work, and I came up with the term "Lock-free Queue". It seems to be already a widely studied topic (Google suggested me a few papers) but I think they are too difficult to understand. After that I found this page which introduced and explained the author's lock-free queue implementation. Although it has certain limitations (only one producer and one consumer are allowed), its implementation is very simple and I think the author's explanation is simple and clear. What's more, it fits my case (even with those limitations).

For my own reference, I put part of my code (a little bit modified from what's described by the author) below. With CUSTOM_QUEUE_NODE_REUSE flag, the enqueue function will not do the lazy removal as the author suggested. Instead it directly reuses nodes which were previously dequeued. The drawback of this modification is the actual memory usage of the queue will always be the same as when it reached its longest queue size.

Update: Since C++ increment and decrement operations are not atomic and it causes bug in the code below, I removed the related code. If one needs to deal with queue size, he has to find atomic functions for increment and decrement.

Tuesday, March 6, 2012

Working with JSON using C# (.NET 3.5 or above)

Using .NET framework 3.5 or above, one can manipulate JSON object using a JavaScriptSerializer. To do so:
  1. Adding .NET reference System.Web.Extensions
  2. Use namespace System.Web.Script.Serialization
  3. Create appropriate classes to describe the target JSON structure
The following example demonstrates how to read from and write to a JSON object.

Note: The JSON string used below is adopted from web.

P.S. In C#, two double quotes are used to describe one double quote in a multi-line literal (string), all escape characters (e.g. \") does not work in this case