Skip to main content
Sign In |
  Help (new window)

Blog

Go Search
Home
  

Categories
Work
Personal
Other
Other Blogs
Staging Blog
Links
Photos
Archive
Archive (Calendar)
Blog of me, Chris Idzerda, containing my thoughts, comments, and questions.

6/11/2008

C++ Library v. .NET Framework

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
at front at back in the middle
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/A1
map O(log N) Dictionary
multimap O(log N) N/A1

1 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 efficiency1 and aliasing2 here, but for readability, I side with C#.

1 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.
2 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.

Project Properties - Debug
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/16/2008

ION TTUSB

About a year ago I received an ION TTUSB. It's a turntable that accepts 33's and 45's and has a USB output. I finally got around to using it last month to create some CDs for my mom from some old albums she has. My experience was good but the main problem I had along the way to a completely working system was configuring the audio properties on my computer. Initially, I was getting only mono recording. Here are the steps I took to get stereo.

First follow the directions to set up the turntable. This is mostly about attaching the belt and balancing the counterweight.

After plugging in the USB cable, you will see some notification bubbles about installing the hardware. When it is complete, you might need to change some of the audio properties. In the control panel, open "Sounds and Audio Devices". Click the "Audio" tab and inspect the "Default device" in the "Sound playback" section. If it says "USB Audio CODEC", change it to whatever other device you have that supports audio output.

Select an output-capable device for sound play-back.

If you have a microphone, click the "Voice" tab and inspect the "Default device" in the "Voice recording" section. Again, if it says "USB Audio CODEC", change it to whatever other device you have that supports your microphone.

If you're using Audacity, select "Preferences…" from the "Edit" menu. Inspect the devices and change the number of channels to 2 (Stereo). You might want to check the "Software Playthrough" check box so you can hear the music as it is recorded.

Select 2 channels for recording.

Something else I did since I have a small system drive and a large data drive is change the temporary directory to my data drive. I clicked the "Choose…" button and selected my "E:\tmp" directory. It automatically appended "audacity_temp".

Select a temporary file location on a large drive.

Doing so will require restarting Audacity.

On ION's TTUSB page, you can download Audacity, the LAME MP3 encoder it requires if you want to create MP3 files, as well as the software and user guides.

One problem I experience is the occasional dropping of the input signal. If it gets too low, Audacity stops recording. I didn't see anything about it on the ION USB Turntables forum, but I think it's an Audacity bug. I looked at Windows Task Manager and I noticed multiple instances of Audacity running. My work-around for this problem is to stop all such instances using the "End Process" button in Windows Task Manager.

A problem some people listed on the forum was with clipping. There's a gain control on the bottom next to the cables. Turn it down to fix the problem.

Another problem was an entire lack of input. Downloading an audio driver fixed the problem for some.

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

1/7/2008

Approximating a Sine Wave with a Cubic Bézier Curve

The standard cubic Bézier curve is given by

P(t) = (1–t)3P0 + 3(1–t)2tP1 + 3(1–t)t2P2 + t3P3

To find an approximation of the sine curve given by y = sin(πx/2) over the interval [0, 1], set P0 to (0, 0) and P3 to (1, 1). Here are a few methods that give P1 and P2.

Linear Interpolation

In the interval from P0 to P3, choose two equally spaced points, Q1 = P(1/3) and Q2 = P(2/3). Expanding P(t) for Q1 and Q2 gives

Q1 = 8/27P0 + 4/9P1 + 2/9P2 + 1/27P3
Q2 = 1/27P0 + 2/9P1 + 4/9P2 + 8/27P3

Since P0 and P3 are known, this gives a linear system of two equations with two unknowns. Solving for P1 and P2 gives

P1 = –5/6P0 + 3Q1 – 3/2Q2 + 1/3P3
P2 = 1/3P0 – 3/2Q1 + 3Q2 – 5/6P3

Choosing Q1 = (1/3, 1/2) and Q2 = (2/3, √3/2) gives

P1 = (1/3, 11/6 – 3√3/4)
P2 = (2/3, 3√3/2 – 19/12)

However, this doesn't have the correct slopes at the end points. This means joining the various reflections of the curve to produce a complete sine wave will give sharp corners. This happened because of the assumption t = Px(t) at t = 1/3 and t = 2/3. In fact, t is rarely equal to Px(t), such as at the end points in this case and in the trivial unity linear case. It's possible to choose different points for Q1 and Q2 or different values for t1 and t2, but applying the correct constraints to do so for interpolation to yield the correct slopes is unwieldy.

Curve Derivative

To overcome the slope problem, ensure the slopes of the vectors at the end points of the derivative of P(t) match the values of the derivative of the sine curve.

P′(t) = –3(1–t)2P0 + (3–9t)(1–t)P1 + 3t(2–3t)P2 + 3t2P3
y′ = π/2cos(πx/2)

Setting x = 0 gives y′ = π/2 and setting x = 1 gives y′ = 0. Determining appropriate values for P′(t), which gives vectors, requires more than knowing slopes, which are scalars. Fortunately, P′(t) also describes the arc velocity, dS/dt. Assuming dx = dt, dx/dt = 1 and dy/dt = y′. Since dS/dt = (dx/dt, dy/dt), P′(0) = (1, π/2) and P′(1) = (1, 0). Finally, since P′(0) = –3P0 + 3P1 and P′(1) = –3P2 + 3P3, this gives

P1 = (1/3, π/6)
P2 = (2/3, 1)

Simple Cubic

Another solution is to use a simple cubic, f(x) = ax3 + bx2 + cx + d, and choose its coefficients such that it meets our criteria. Starting with P0 = (0, 0) and P3 = (1, 1) gives d = 0 and a + b + c = 1. So the slopes will provide for a smooth piece-wise sine wave, choose appropriate values for its derivative

f′(x) = 3ax2 + 2bx + c

Choosing f′(0) = π/2 and f′(1) = 0 gives c = π/2 and 3a + 2b = –π/2. Combining these with a + b + c = 1 gives

a = π/2 – 2
b = 3 – π
c = π/2
d = 0

The next step is to convert the simple cubic equation into the Bézier equation. Let t = x and use a linear transform, given by the following matrix, to convert from the simple cubic basis, (t3, t2, t, 1), to the cubic Bézier basis, (–t3+3t2–3t+1, 3t3–6t2+3t, –3t3+3t2, t3).

  0 0 0 1  
  0 0 1/3 1  
  0 1/3 2/3 1  
  1 1 1 1  

Applying the above matrix to the above coefficients gives (0, π/6, 1, 1) for the y components of P(t), Py(t). Applying it to (0, 0, 1, 0) gives (0, 1/3, 2/3, 1) for the x components of P(t), Px(t). Extracting the second and third elements of these results for the control points gives

P1 = (1/3, π/6)
P2 = (2/3, 1)

This is the same result derived in the previous section. This is not surprising since the constraints are the same.

Links

Wikipedia – Bézier Curve
Drawing Arbitary Curves From Points – derivation of linear interpolation
NYU course – Introduction to splines – introduces the Bézier matrix
Wikipedia – Invertible matrix

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

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

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

Get

  1. Read the item from the read buffer.
  2. 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.

  1. Read the value of x.
  2. Increment it.
  3. 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)
1 - 10 Next

 ‭(Hidden)‬ Admin Links