Work - Blog

6/11/2008

I am still a die-hard C++ programmer. I don't call myself an expert (journeyman, perhaps); it's a huge and complex language. Put another way, it gives you enough rope to shoot yourself in the foot. Nowadays, I program primarily in C#. For the longest time, I still did significant recreational programming in C++ because I liked the power of the language and the C++ standard library, most notably the STL, which the .NET framework had not yet matched.

With .NET 2.0 and 3.x, that's changed. While I'm sure there are tasks more well suited for C and C++ (e.g. operating systems), I find myself doing much less of my recreational programming in C++. What really did it for me was the introduction of generics, introduced in .NET 2.0. Not so much that generic programming became possible, but rather the implementations of many of the same concepts found in the STL: containers, iterators, algorithms, and functors.

Iterators and functors previously existed in .NET in the forms of IEnumerable and delegates, respectively. They're more powerful now with IEnumerable<T> and anonymous methods. Those are interesting but the most interesting to me are the containers. Here is a list of the STL containers and the .NET equivalents. I also listed the STL insert complexity.

Type	STL	Insert complexity			.NET
Type	STL	at front	at back	in the middle	.NET
sequence containers	vector	O(N)	O(1)	O(N)	List
	deque	O(1)	O(1)	O(N)	Queue
	list	O(1)	O(1)	O(1)	LinkedList
associative containers	set	O(log N)			HashSet
	multiset	O(log N)			N/A¹
	map	O(log N)			Dictionary
	multimap	O(log N)			N/A¹

¹ These are more difficult to construct since they allow duplicate keys. Perhaps use a Dictionary of Lists.

There are other containers but they're either more for special purposes (e.g. bitset and valarray) or not yet part of the standard (e.g. hash_set and unordered_map).

.NET 3.x, with LINQ and extension methods, gives us not only many of the functors but also something even more valuable: expressiveness and elegance. For instance, which is more readable? (These are adapted from Scott Meyers' Effective STL, Item 47.)

C++

vector<int> v;

// ... other statements here

// remove elements < 100 except those preceding the last element >= 2500
v.erase(
remove_if(find_if(v.rbegin(), v.rend(),
bind2nd(greater_equal<int>(), 2500)).base(),
v.end(),
bind2nd(less<int>(), 100)),
v.end());

C#

List<int> v= new List<int>();

// ... other statements here

// remove elements < 100 except those preceding the last element >= 2500
v = v.SkipWhile((i, n) => n < 100 && i >= v.Last(m => m >= 2500)).ToList();

I still like C++ and I understand the above statement and have written many like it (although I wasn't sure how to indent it since I prefer to break it up as he suggests in his book). I'm ignoring efficiency¹ and aliasing² here, but for readability, I side with C#.

¹ The C++ code is likely to be more efficient, at least for primitive types such as int used here. For more complex classes with expensive copy constructors, the C# code is perhaps better since it deals with references, not values. C++ can certainly handle references (as pointers) but, in an unmanaged world, one must then contend with memory management.
² The C++ code modifies the vector while the C# example creates a new list. That matters if other code has a reference to the original list. It's possible to construct a more complex C# expression or set of C# statements involving RemoveAll or RemoveRange.

Posted at 10:31 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (0)

6/4/2008

Detect Visual Studio Debugging

If you have code that you want to run only while debugging in Visual Studio, you can detect it if you are running in its hosting process, which is enabled by default.

#if DEBUG
if(AppDomain.CurrentDomain.FriendlyName.EndsWith("vshost.exe"))
{
// Perform whatever tasks depend on running inside the Visual
// Studio debugger.
}
#endif

While it does provide several features not otherwise available, you might have a reason to disable it (such as a corrupted vshost.exe file). To do so, uncheck the last box (shown checked here) on the Debug tab in the Project Properties window.

Posted at 8:29 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (3)

5/28/2008

The nil attribute in XML-serialized nullable values

If in a class you have a value type property that is optional, it's common to specify it as nullable. However, if you serialize a nullable value type property to XML, you'll get something like this if it's null.

<Value xsi:nil="true" />

Or, if you turned off declaration of the XML schema instance namespace, it will be even more verbose.

<Value p2:nil="true" xmlns:p2="http://www.w3.org/2001/XMLSchema-instance" />

This might look strange but it will properly deserialize. Nonetheless, you might have a reason to have a nullable value type property serialize the way a class property does, which is to not appear in the XML output at all if it's null. Setting the IsNullable property of the XmlElement attribute for such a property will have no effect. (Well, setting it to false will result in a run-time error.)

The XmlElementAttribute.IsNullable Property page at MSDN has this to say.

You cannot apply the IsNullable property to a member typed as a value type because a value type cannot contain null. Additionally, you cannot set this property to false for nullable value types. When such types are null, they will be serialized by setting xsi:nil to true.

One work-around is to declare another property that is a class type, such as string, and parse it in the nullable value property.

[XmlElement("Value")]
public string ValueString { get; set; }

[XmlIgnore]
public int? Value
{
get { return int.Parse(ValueString); }
set { ValueString= value.ToString(); }
}

Of course, you can go in the opposite direction as well.

[XmlElement("Value")]
public string ValueString
{
get { return Value.HasValue ? Value.Value.ToString() : null; }
set
{
if(value != null)
Value= int.Parse(value);
else
Value= null;
}
}

[XmlIgnore]
public int? Value { get; set; }

Posted at 7:57 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (2)

5/21/2008

Removing the XML schema and instance namespace declarations

To remove the declarations of the XML schema (xsd) and schema instance (xsi) namespaces from the output file of XML-serialized objects, create an XmlSerializerNamespaces object and add an empty namespace to it.

XmlSerializerNamespaces ns = new XmlSerializerNamespaces();
ns.Add("", ""); // Remove the unnecessary xmlns:xsi and xmlns:xsd namespaces.

Use it in the XmlSerializer.Serialize method invocation.

s.Serialize(writer, o, ns);

Interestingly, the XmlSerializerNamespaces Class page at MSDN has a note about this:

The creation of an empty namespace and prefix pair is not supported. That is, you cannot create a pair using the following code:

It refers to the Add invocation above.

Posted at 7:20 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (0)

5/14/2008

XML-serializing a derived collection

A class derived from a collection class will XML-serialize only the collection, not any additional properties in your derived class.

public class NamedNodeList : List<Node>
{
public string Name { get; set; } // ignored during XML serialization
}

The work-around is to use containment instead of derivation.

public class NamedNodeList
{
public string Name { get; set; }
public List<Node> Nodes { get; set; }
}

This works except you will get an additional wrapping element around the collection. To get rid of this wrapper, use the XmlElement attribute on the collection property.

[XmlElement]
public List<Node> Nodes { get; set; }

In fact, applying the XmlElement attribute to any collection member in any context (not just the derivation context here) will give you a collection not surrounded by a containing element.

Posted at 5:27 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (1)

1/4/2008

Spin Buffers for Message Passing

There is a post on Dr. Dobb's about a message passing mechanism called Spin Buffers. The author of the article starts with a discussion of the canonical message passing producer-consumer problem and how the message buffer requires synchronization to prevent race conditions. He then says spin buffers don't need synchronization or low-level atomic operations.

Before presenting spin buffers, he discusses a common solution to the producer-consumer problem, ring buffers. His implementation includes a buffer size to resolve the ambiguity of the read and write pointers referencing the same location. Of course, access to multiple variables by multiple threads requires synchronization. This can cause contention and blocking between threads, reducing performance.

Finally, he discusses his implementation of spin buffers, describing them as "three internal ordered buffers" referenced by two pointers, one for the reader and one for the writer.

I think the 0, 1, 2 labels are backwards.

He then describes the put and get methods.

Put

Put the item into the write buffer.
If the next buffer is free, make the free buffer become the write buffer, and the current write buffer becomes free.

Get

Read the item from the read buffer.
If the current read buffer is empty and the next buffer is free, make the next buffer the read buffer, and the current read buffer becomes free.

He also discusses some of the caveats to using spin buffers as well as a performance comparison of ring buffers, a concurrent linked queue, and his spin buffers. The results he presents show spin buffers have a significant margin.

While his algorithm is perhaps correct in certain cases, there are cases where it definitely is not. For instance, if the compiler optimizer decides to reorder the code, it will fail. Even if the compiler doesn't, the processor might, especially on newer processors that use release consistency (e.g. Itanium). (See my previous post on consistency models.)

Also, the ring buffer implementation he chose isn't very good for multi-threading. A better variant is to not use a buffer size and instead assume equal pointers means the buffer is empty. Such an implementation can be lock-free (but not synchronization-free), although it does mean leaving one entry in the buffer unused. This isn't a problem unless you're in an extremely tight memory environment (e.g. Sinclair ZX81).

The article refers to a paper about concurrent queue algorithms (abstract, paper, pseudo-code) which are the basis for Java's ConcurrentLinkedQueue class. There is source code, but it's in uncommented C and MIPS assembly. Nonetheless, the paper has a thorough discussion of the testing environment and methodology. In comparison, the spin buffer article author's tests are overly simplistic, largely invalidating his results.

You can download the source code for the issue, but the enclosed Zip file which contains the test code for this article, spin.zip, appears to be corrupt or at least incomplete. It doesn't really matter since the author's own implementation of spin buffers is incorrect. I verified this by trying to perform my own tests. It fails in exactly the way revealed here where there is additional discussion about better solutions, ring buffers among them.

Posted at 1:11 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (0)

1/3/2008

Consistency Models

While working on my subsequent post about message passing, I realized I was creating a great deal of background information. So, rather than having that post be about two subjects, I decided to split it and discuss here the background information, consistency models.

I will discuss only two of them here, sequential consistency, adhered to by all older processor architectures, and release consistency, adhered to by some newer processor architectures (e.g. Itanium), because these two appear in most discussions. (I wasn't able to find a definitive list of which architectures supported which consistency models.) You can read about all of them in more depth here.

Consistency isn't so much a processor concept as a distributed system (or, more specifically, distributed shared memory) concept. Nonetheless, it is the processors and the bus architectures in which they appear that constitute the hardware implementation of the nodes in a distributed system. A processor that supports such relaxed consistency models makes it easier to design architectures and write software to take advantage of them.

Sequential consistency is the "common sense" consistency. That is, if one thread of execution writes to location X and then location Y, all observers of those locations will see such changes to those locations in the same order. It certainly suits programmers (i.e., humans) to view the machine's behavior in this way. It seems downright strange to expect it to happen any other way.

However, it's not very efficient from the machine's point of view. For instance, it's likely to be more efficient for a processor to flush its cache in order of increasing address to take advantage of the burst modes of modern memory. In this case, if location X appears "higher" in memory than location Y, observers of these locations can easily see them in the "wrong" order. Such behaviors that arise due to the hardware designer's desire to improve performance are why there are different consistency models.

Although release consistency allows such out-of-order behavior, it does have rules that bound this behavior so programmers can understand what is happening and write programs that are correct without sacrificing too much performance. While there are places you can read about release consistency (such as here), there aren't that many places that boil it down to simple rules a programmer can follow to know when to worry about it. I prefer Scott Meyer's take on it (emphasis mine).

When you want to read the value of a variable giving you permission to access shared state, label the read as an acquire.
When you are done accessing shared state, label the write of the permission variable as a release.

(An "acquire" is the complementary operation of a "release", from which this consistency model gets its name. See the second paragraph of the introduction of the aforementioned paper.) These are the very situations in which you actually care about the order of access: shared state used by multiple threads of execution. When one thread is modifying shared state, you want to know no other thread is modifying the same state until the first one is done. For instance, if two threads attempt to increment a variable at the same time, one of the increments is lost.

Consider the simple C# statement ++x. It certainly looks atomic; it's only three characters! However, at the machine code level, it becomes essentially three statements.

Read the value of x.
Increment it.
Write the value of x.

Even if there's a single machine instruction to increment a memory location, the bus sees two actions, one to read a value from an address (the value of x before the processor increments it) and another to write a value to that address (the value of x after the processor increments it). It's entirely possible for another thread on another processor to pre-empt the first one's bus accesses between the read and the write and perform the same read and write. And, if the increment is not a single machine instruction, it can be another thread on a uniprocessor machine. This is why one must acquire a lock before modifying x.

However, locks in high-level languages are a kernel-level concept, which means they're implemented in as system library calls, while acquire and release are machine-level concepts, which means they're often implemented as special versions of the processor's load and store operations.

While the increment example requires a lock, there are several other important problems whose solutions don't. One such problem is the producer-consumer problem, in which one thread "produces" items of work while another "consumes" them. A common solution to this problem is the ring buffer. Depending on the implementation, this solution requires no locks or special instructions so long as the compiler optimizer doesn't reorder the code, there is only one producer and one consumer, and the machine on which it runs uses sequential consistency.

On a machine that uses release consistency, it's possible for the consumer to read invalid data from the buffer even with the other two aforementioned restrictions. This can happen because the processor flushed its cache containing the producer's writes in the "wrong" order, allowing the consumer to read an updated "ready" flag before reading updated buffer data. This is a situation in which one must be aware of "acquire-release" semantics.

The .NET framework provides Thread class methods that express such semantics. These methods have been available since version 1.1.

Thread.VolatileRead says it "obtains the very latest value written to a memory location by any processor." While that's true, there's more to it than that. It ensures the current thread does not read writes to any locations performed by other threads after this location.

Thread.VolatileWrite says it "ensures that a value written to a memory location is immediately visible to all processors." Again, there's more to it than that. It ensures the current thread's writes to any locations occur before this one.

Thread.MemoryBarrier does it both ways: "The processor executing the current thread cannot reorder instructions in such a way that memory accesses prior to the call to MemoryBarrier execute after memory accesses that follow the call to MemoryBarrier."

C# has the volatile keyword that ensures all reads of variables with which it appears are volatile reads and all writes to such variables are volatile writes. There is an excellent discussion of exactly these issues in the Dr. Dobb's article on memory consistency and .NET.

Posted at 6:04 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (0)

11/9/2007

Restarting a Sound in Silverlight 1.0

More than one person has experienced this problem and asked me about it. My solution is simple.

function restartSound(mediaElement)
{
mediaElement.source= mediaElement.source;
mediaElement.autoPlay= true;
}

Posted at 4:28 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (0)

7/24/2007

Using RAISERROR in a TRY-CATCH block

As Adrian pointed out in his recent post, it is not a straightforward task to get all of the error information back to the middle tier from a stored procedure using RAISERROR. The RAISERROR statement provides three user-settable parameters: message, severity, and state. Since SQL Server associates particular semantics with the severity, use one or both of the other two to provide the middle tier with specific information. Here are a couple of possibilities.

Provide a custom message by constructing an easily parsed string in the stored procedure.

    SET @ErrorMessage = ERROR_MESSAGE()
        + N':' + CAST(ERROR_NUMBER() AS nvarchar)
        + N',' + CAST(ERROR_LINE() AS nvarchar)
        + N',' + ERROR_PROCEDURE()

Parse it in the middle tier.

    catch(SqlException sqlex)
    {
        string message= sqlex.Message;
        message= message.Substring(message.LastIndexOf(':') + 1);
        string[] parts= message.Split(',');
        switch(int.Parse(parts[0]))
        {
        case 544: // Cannot insert explicit value for identity column....
          break;
        case 8134: // Divide by zero error encountered.
          break;
        case 1105: // Could not allocate space....
            switch(sqlex.State)
            {
            case 2: // data segment full
              break;
            case 3: // log segment full
              break;
            default:
              break;
            }
            break;
        default:
          break;
        }
    }
Provide a custom state by using a CASE expression in the stored procedure.

SET @ErrorState = CASE ERROR_NUMBER() WHEN 544 THEN 1 WHEN 8134 THEN 2 ELSE 99 END

If you need to differentiate states for a single error (as option #1 does), add that to the CASE expression.

    SET @ErrorState = CASE ERROR_NUMBER()
        WHEN 544 THEN 1 -- Cannot insert explicit value for identity column....
        WHEN 8134 THEN 2 -- Divide by zero error encountered.
        WHEN 1105 THEN CASE ERROR_STATE() -- Could not allocate space....
            WHEN 2 THEN 3 -- data segment full
            WHEN 3 THEN 4 -- log segment full
            ELSE 5 END
        ELSE 99 END

The middle tier can use the state value to decide what to do.

    catch(SqlException sqlex)
    {
        switch(sqlex.State)
        {
        case 1: // Cannot insert explicit value for identity column....
          break;
        case 2: // Divide by zero error encountered.
          break;
        case 3: // Could not allocate space (data segment full)....
          break;
        case 4: // Could not allocate space (log segment full)....
          break;
        default:
          break;
        }
    }

There are several good guidelines and suggestions about using the TRY-CATCH construct in SQL Server in Books Online.

Posted at 3:24 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (0)

6/19/2007

Animating a GridLength

WPF provides several classes for animating many different types (e.g. ColorAnimation and Rotation3DAnimation) but none for animating a GridLength structure. I wanted such a class recently to create an animated navigation panel. There are a few MSDN forum posts asking for much the same functionality and providing some solutions, much like what I present here. Mine differs in that I followed the recommended approach to creating such a class by spreading its functionality across two classes, GridLengthAnimationBase and GridLengthAnimation, the latter inheriting the former. This split facilitates creating additional derivations, such as GridLengthAnimationUsingKeyFrames.

    public abstract class GridLengthAnimationBase : AnimationTimeline
    {
        public override sealed object GetCurrentValue(object defaultOriginValue, object defaultDestinationValue, AnimationClock animationClock)
        {
            if(!(defaultOriginValue is GridLength))
                throw new ArgumentException("Parameter must be a GridLength.", "defaultOriginValue");
            if(!(defaultDestinationValue is GridLength))
                throw new ArgumentException("Parameter must be a GridLength.", "defaultDestinationValue");
            return GetCurrentValueCore((GridLength)defaultOriginValue, (GridLength)defaultDestinationValue, animationClock);
        }

        protected abstract GridLength GetCurrentValueCore(GridLength defaultOriginValue, GridLength defaultDestinationValue, AnimationClock animationClock);

        public override sealed Type TargetPropertyType
        {
            get { return typeof(GridLength); }
        }
    }

    public class GridLengthAnimation : GridLengthAnimationBase
    {
        public static readonly DependencyProperty ByProperty= DependencyProperty.Register("By",
            typeof(double?), typeof(GridLengthAnimation));
        public static readonly DependencyProperty FromProperty= DependencyProperty.Register("From",
            typeof(double?), typeof(GridLengthAnimation));
        public static readonly DependencyProperty ToProperty= DependencyProperty.Register("To",
            typeof(double?), typeof(GridLengthAnimation));

        protected override Freezable CreateInstanceCore()
        {
            return new GridLengthAnimation();
        }

        protected override GridLength GetCurrentValueCore(GridLength defaultOriginValue, GridLength defaultDestinationValue, AnimationClock animationClock)
        {
            double fromValue= From.HasValue ? From.Value : defaultOriginValue.Value, toValue;
            if(To.HasValue)
                toValue= To.Value;
            else if(By.HasValue)
                toValue= fromValue + By.Value;
            else
                throw new ApplicationException("Specify either To or By in a GridLengthAnimation.");
            return new GridLength(fromValue + animationClock.CurrentProgress.Value * (toValue - fromValue), GridUnitType.Star);
        }

        public double? By
        {
            get { return (double?)this.GetValue(ByProperty); }
            set { this.SetValue(ByProperty, value); }
        }

        public double? From
        {
            get { return (double?)this.GetValue(FromProperty); }
            set { this.SetValue(FromProperty, value); }
        }

        public double? To
        {
            get { return (double?)this.GetValue(ToProperty); }
            set { this.SetValue(ToProperty, value); }
        }
    }

Note that my implementation assumes "Star" sizing (highlighted above) which is why the dependency properties are of type Nullable<double> instead of type GridLength. It is possible to modify it to support Pixel sizing as well but such an implementation must guard against animating between incompatible GridLength instances, such as from a Pixel-sized GridLength to a Star-sized GridLength. Besides, I didn't need any more than this for my animated navigation panel user control, shown here.

    <Grid x:Name="LayoutRoot">
        <Grid.RowDefinitions>
            <RowDefinition Height="21.96" />
            <RowDefinition Height="0*" />
            <RowDefinition Height="21.96" />
            <RowDefinition Height="*" />
            <RowDefinition Height="21.96" />
            <RowDefinition Height="0*" />
        </Grid.RowDefinitions>
        <Button Content="Button 1" x:Name="button1" Click="button_Click"/>
        <Grid Grid.Row="1">
            <TextBlock Text="Content 1"/>
        </Grid>
        <Button Content="Button 2" Grid.Row="2" x:Name="button2" Click="button_Click"/>
        <Grid Grid.Row="3">
            <TextBlock Text="Content 2"/>
        </Grid>
        <Button Content="Button 3" Grid.Row="4" x:Name="button3" Click="button_Click"/>
        <Grid Grid.Row="5">
            <TextBlock Text="Content 3"/>
        </Grid>
    </Grid>

    public partial class NavigationPanel
    {
        public NavigationPanel()
        {
            this.InitializeComponent();
        }

        private void ExpandRow(int rowIndex)
        {
            RowDefinitionCollection rowDefs= LayoutRoot.RowDefinitions;
            for(int i= 1; i < rowDefs.Count; i += 2)
            {
                if((rowDefs[i].Height.Value == 0) == (i == rowIndex))
                {
                    GridLengthAnimation gla= new GridLengthAnimation();
                    gla.To= i == rowIndex ? 1 : 0;
                    gla.Duration= new Duration(TimeSpan.FromSeconds(.125));
                    rowDefs[i].BeginAnimation(RowDefinition.HeightProperty, gla);
                }
            }
        }

        private void button_Click(object sender, RoutedEventArgs e)
        {
            DependencyObject dob= (DependencyObject)sender;
            int rowIndex= (int)dob.GetValue(Grid.RowProperty);
            this.ExpandRow(rowIndex + 1);
        }
    }

It turns out I never needed this code but I provide it now for your edification.

Posted at 5:15 PM by Chris Idzerda | Category: Work | Permalink | Email this Post | Comments (0)

1 - 10