Stu Smith: Making It Up As I Go Along

Eliminate Those Loops! - or - 'foreach' Considered Harmful

Wed, 28 May 2008 16:12:56 +0100

Lee and I are working on a project at the moment, and we got into a mini-argument about how best to write a tiny piece of code. Essentially, we're working with a thrid-party API that returns some data as key/value pairs in a hastable: the keys are always strings, but the values can be either strings, or further hashtables. (So essentially we have a tree structure). For the purposes of this discussion, we need to render that tree as XML.

Here's the "traditional" method of accomplishing this:

public static XDocument ConvertDictionaryToXml( IDictionary dictionary )
{
 XElement root = new XElement( "root" );

 ConvertDictionaryToXml( root, dictionary );

 return new XDocument( root );
}

public static void ConvertDictionaryToXml( XElement parent, IDictionary dictionary )
{
 foreach( DictionaryEntry kv in dictionary )
 {
  XElement newElement = new XElement( kv.Key.ToString() );

  if( kv.Value is IDictionary )
  {
   ConvertDictionaryToXml( newElement, (IDictionary)kv.Value );
  }
  else
  {
   newElement.Value = kv.Value.ToString();
  }
  parent.Add( newElement );
 }
}

Now I disagree with this - it's my belief that loops should go the way of the "goto" statement and be consigned to history. Here's my version:

public static XDocument ConvertDictionaryToXml( IDictionary dictionary )
{
 var root = new XElement( "root", DictionaryToXElement( dictionary ) );

 return new XDocument( root );
}

private static XElement[] DictionaryToXElement( IDictionary sourceDictionary )
{
 var xelements = from DictionaryEntry p in sourceDictionary
   let dp = p.Value as IDictionary
   select (dp == null)
    ? new XElement( p.Key.ToString(), p.Value.ToString() )
    : new XElement( p.Key.ToString(), DictionaryToXElement( dp ) );

 return xelements.ToArray();
}

Short and sweet. No (visible) changing state to understand, just a recursive sequence transform. I see parallels here in the new WPF model of animation: in the older WinForms, to animate something, you'd set up a timer and repeatedly change it. In the newer WPF, you simply set up the intent of the animation, and the system handles the messy updating stuff.

I see it as a natural progression in the power of languages:

C# 1.0 - zero-dimensional. Language support limited to operations on single data items.
C# 3.0 - one-dimensionalLanguage supports operations on sequences of data items.
C# N.0 - two-dimensional. Language supports operations on trees/graphs of data items.

(Incidentally, I'm well aware of the similarities to languages like LISP or Haskell - and if you think LISP is old-fashioned, you should probably have a read of Structure and Interpretation of Computer Programs).

If you're worried about performance, well, I guess there could be a hit with my version, you'd have to profile it, but on the other hand the LINQ version would parallelize nicely using PLINQ, something that can't be said for arbitrary for-loops. (Of course, if we were worried about performance, we wouldn't be using XML).

Microsoft Word Mail-Merge: Grrr

Tue, 15 Apr 2008 11:58:36 +0100

I'm sorry, I have to rant today. It's been building up inside me for a while, and now I can't contain it. Here's my tale of woe.

We're looking to expand the contracting side of the business at the moment, and one of the things I'm doing is sending small (50-100 recipient) mailshots out about once a month to potential customers or other companies we can work with. (Aside: fifty quid spent on stamps, envelopes, and printed flyers has a much, much greater return than the equivalent amount spent on Google ads).

So I have my list of addresses in an Excel spreadsheet, I have my labels ready, my printer is on, and I'm full of coffee. It should be a ten-minute job but it seems that the mail-merge feature in Word is a second-class citizen, and doesn't have that level of polish that the rest of the application does.

(And I really like the rest of the application - Microsoft have done great things with the latest version; they've taken a much-need risk with the new UI, have come up with a great new alternative to a complex menu system, and have really brought things up-to-date with the new style set and charting system).

Just through trying to print labels, I've found the following bugs. Not show-stoppers, obviously, but annoying as hell. I'll categorize them by operation.

Mailings -> Start Mail Merge -> Labels...

Defaults to manual tray. Every time. Even though that's the worst option on my printer. And if I forget to choose Tray 1, I get to the end of the mail-merge, won't be able to print, and will have to start all over again.

Select Recipients -> Use Existing List...

File browser always resets to "All Data Sources". My spreadsheet isn't there, so I always have to browse for it.
"First row of data contains column headers". You better hope your spreadsheet fits this pattern, because if it doesn't, even if you uncheck this option, you won't be able to print the first address.
By default, Excel creates three sheets. I would guess that 99% of spreadsheets only use the first one. Surely Word could filter out the empty sheets in the list?

Update Labels

OK, I'm not a mail-merge wizz, so maybe there's some special case I'm not aware of here. But basically, any time you make a change, you have to click "Update Labels". Couldn't this be automatic? Or perhaps, a checkbox for automatic/manual?
Line spacing. The labels default to paragraph-spacing between each address line, which means that the address won't fit on the labels. The solution is to highlight the address block, go to the home tab, then select "No Spacing", go back to the Mailings tab, and click "Update Labels". Would "no spacing" from the get-go be a better default? I think so.

Back to Excel

So I'm trying to figure stuff out. I want to open the source spreadsheet to compare. Excel tells me that the file format or file extension is not valid. So (a) it gives me an incorrect error message (actually the file is in use), and (b) Word surely doesn't need to keep the file open?

Preview Results

When previewing results, the back/forward buttons move in steps of one record. So to preview the next page, I have to know my 14-times table. Perhaps we could also have page back/page next buttons?

So What's the Solution?

Start testing the mail-merge feature. Not from specs, but from a task-based standpoint: actually buy some labels, use a cheap laser or inkjet printer, and see how long it takes.
Fix up the immediate problems. Have Word remember certain critical settings (such as data source locations and default printer trays). Fix Excel's confusing error messages.
Separate out orthogonal concepts. For example, the choice of tray to use in the printer could logically be modified in complete isolation to every other aspect of the mail-merge process. Unfortunately, with the current design, if you need to change it, you have to start the entire process from scratch.
Identify key tasks the user performs, and build the user interface around that. For example: you can choose the basic layout of the labels by manufacturer, but I often find that I've got my margins slightly wrong. Instead of having to go back to the beginning to reset the label layout, why not have a "nudge" feature to allow slight adjustments to the margins? If I realise I've picked the wrong source spreadsheet, let me just change that: I don't want to to have to re-format all my address lines first. (This "task-based" approach has worked very nicely with new features such as style-sets, and cover pages).

My Other Blog

Fri, 28 Mar 2008 16:16:32 +0000

I've been a bit slack with my blog posts lately - or rather, they've mostly been about things other than FeedGhost, so they've gone on my other blog.

If you didn't know about my other blog, it's called Just Effort (tagline: design skills are something you learn, not something you’re born with). It's all about graphic design, but from my perspective, i.e. that of a programmer. It's my belief that the stereotype of "programmer art" is down to lack of effort and practice, not some lack of innate skill.

So what might you find there? Here's a few past articles:

Getting Past Blank-Canvas-Block

How to get past the blank canvas and actually produce something.

Vista-Style Transparency

Using Photoshop to produce a frosted glass effect.

Designing and Printing Business Stationery

Ideas and how-to guides for producing promotional business materials.

3-D Reflective Screenshots

Making attractive reflective screenshots to show off your software.

You can find the blog here:

http://www.justeffort.com/

I've Got the 64-bit Blues

Wed, 20 Feb 2008 16:32:19 +0000

Pretty much all my development work at BinaryComponents has been done on a nice little Dell that we bought about 18 months ago, originally supplied with XP Pro. Unfortunately, in common with most desktop machines, it's been getting slower and slower as the cruft accumulated. Finally it all got too much for me, and I decided to wipe the whole lot and install Vista instead - and since I can see 2Gb RAM isn't going to be enough for much longer, I decided to go for a 64-bit version.

As you can see, it's all installed nicely, with service pack 1 on too, and in general it's a pleasure to use. There is one exception unfortunately... as some of our users have pointed out on the forums, FeedGhost has a few issues when running on 64-bit Vista. This week, I've been tracking them down. Here's one of them:

Yuck. It's not even as if FeedGhost is coded in some legacy language; it's a pretty standard .NET / Windows Forms application really.

A couple of days' hair-tearing, debugging, tracing, and stepping through the framework source code led me to this in Control.SetBoundsCore (Microsoft code, Microsoft comments):

SafeNativeMethods.SetWindowPos(new HandleRef(window, Handle), NativeMethods.NullHandleRef, x, y, width, height, flags);

// NOTE: SetWindowPos causes a WM_WINDOWPOSCHANGED which is processed

// synchonously so we effectively end up in UpdateBounds immediately following

// SetWindowPos.

//

//UpdateBounds(x, y, width, height);

I now had enough information to cross-reference with an MSDN forum post:

"A little investigation showed that Windows stops sending WM_SIZE when it reaches some certain nesting level. In other words, it won't send WM_SIZE to your child windows if you try to resize them when you process WM_SIZE in the parent ones. Depending on the USER stuff/updates/serivice packs the maximum nesting level at which it stops propagating WM_SIZE may vary from 15 to 31 and even much higher (effectively unreachable) under latest XP 32bit/sp2.

But it still too little under XP x64 and still some similar ugly things happen to other messages under some builds of Vista.

So it is certainly a Windows bug."

Don't you just love it? I know there have to be nesting limits, but 15? Way too low. (And besides, Windows Forms shouldn't expose that nastiness - the code in SetBoundsCore could have checked that the message was relayed, and if not, updated the bounds 'manually').

[ As Joel calls it, this is a good example of a "Leaky Abstraction" - that article by the way is well worth reading, if you haven't already. ]

If you happen to experience this problem, you have two choices: either reduce the depth of your control hierarchy (the more ideal solution), or else derive "fixed" controls from each of the system ones that you use, as follows:

public class FixedPanel : Panel

{

protected override void SetBoundsCore( int x, int y, int width, int height, BoundsSpecified specified )

{

    base.SetBoundsCore( x, y, width, height, specified );

    if( specified != BoundsSpecified.None )

    {

      if( ( specified & BoundsSpecified.X ) == BoundsSpecified.None )

      {

        x = Left;

      }

      if( ( specified & BoundsSpecified.Y ) == BoundsSpecified.None )

      {

        y = Top;

      }

      if( ( specified & BoundsSpecified.Width ) == BoundsSpecified.None )

      {

        width = Width;

      }

      if( ( specified & BoundsSpecified.Height ) == BoundsSpecified.None )

      {

        height = Height;

      }

    }

    if( x != Left || y != Top || width != Width || height != Height )

    {

      UpdateBounds( x, y, width, height );

    }

}

}

Ugly, but it (mostly) works.

I've managed to trim a few unneeded panels out of the deeper hierarchies in FeedGhost, and assuming testing goes OK, this issue will be fixed in the next release of FeedGhost.

Generating Shiny 3-D Images For Websites

Wed, 13 Feb 2008 18:03:54 +0000

We're currently in the process of re-launching our company website: here's one theme we came up with...

www.binarycomponents.com

...and we wanted to bring it a little bit more up-to-date with an eye-catching spread of a part of our portfolio.

I've used the 3-D screenshot effect before, notably on the FeedGhost website, and although one image is simple enough in Photoshop, I've never been able to get it looking quite right with more than one.

Today however I decided to bite the bullet and get it sorted properly. To that end, I wrote a little WPF-3D application that lets you import images, move and rotate them, and view them from various angles, and finally render them with a shiny reflection. Here's a few examples:

Once I've tidied this application up a little I'll put it on our labs page for download.

Some WPF Work

Tue, 29 Jan 2008 13:57:40 +0000

I've been doing quite a bit of WPF (Windows Presentation Foundation) experimenting recently, on a project that will hopefully turn into another commercial product for BinaryComponents.

It's in very early stages as yet, which is why I'm showing tiny screenshots instead of full-size ones. (You can't see so many rough edges that way). All of the XAML, both content and style, is hand-coded by the way - learning Expression Blend is a job for the future. Data access is using LINQ, of course.

I think I'm finally getting the hang of the WPF "way" - it's taking me a while to untrain myself from the WinForms modes of thought. If anyone's starting a new desktop application and can't decide whether to learn WPF or stick with WinForms - my advice is definitely to go for WPF - once it clicks, you won't want to go back. (Of course, whether you want to develop desktop applications is another question entirely).

Naming Confusions in WPF

Thu, 29 Nov 2007 15:06:00 +0000

WPF provides a wide range of container controls that lay out their children in various ways (Grid, StackPanel, DockPanel, etc), but occasionally you need something slightly out-of-the-ordinary, and in those cases you have to write your own layout logic. For not-very-interesting reasons, I needed a container that would layout all its children on top of each other, using the full size of the parent container.

The usual method of achieving this is derive from the abstract class Panel, and implement your own MeasureOverride and ArrangeOverride methods. There's plenty of examples out there, but in most cases they assume that the layout is going to be at least partly dependent on the sizes of the child elements. Mine of course, isn't, so I wrote the following:

protected override Size MeasureOverride( Size availableSize )
{
    // Error is here (missing code).

    return availableSize;
} 
protected override Size ArrangeOverride( Size finalSize )
{
    var rect = new Rect( finalSize ); 
    foreach( UIElement child in InternalChildren )
    {
        child.Arrange( rect );
    } 
    return finalSize;
}

...and it sort of worked, but only when expanding the control, not when shrinking. After half an hour of tearing my hair out, I finally found the answer in MSDN. (On a side note, it's a poor state of affairs when the official documentation is so bad that it's the last resort).

"UIElement.Measure()... Updates the DesiredSize of a UIElement."

Ah-ha! I should have measured my children! In my mind, while I can guess that arrange will change something, I just assumed that measure was free of side-effects, and so could be skipped. It's not, and I think that's slightly misleading naming. (Unless perhaps WPF elements are quantum...) The solution of course was to iterate the children in MeasureOverride, and measure each one, throwing away the results.

Deleting Rows in LINQ-to-SQL

Tue, 06 Nov 2007 16:14:55 +0000

I spent a while this morning trying to figure out a rather strange error message while trying to delete data using LINQ, so I thought I'd pass on the answer.

Let's suppose we have two tables, Parent and Child, linked by a one-to-many foreign key relationship:

Parent - PK ParentId

Child - PK ChildId, FK OwnerParentId referenced Parent.ParentId

Now let's suppose you want to delete a child row from the parent:

parent.Children.Remove( child );

The error you get, assuming your foreign key column is non-nullable, is:

An attempt was made to remove a relationship between a Parent and a Child. However, one of the relationship's foreign keys (Child.OwnerParentId) cannot be set to null.

After a fair amount of searching, I've found this is because LINQ's default behaviour is simply to try to unlink the relationship by setting Child.OwnerParentId to null.

If you actually want to delete the child row instead, you'll need to amend your DBML file to specify a different DeleteOnNull rule. Right-click it and choose "Open with..." then "XML Editor". Find the appropriate association (and note each one appears twice, once for each direction - you need to edit the one in the child table) and set DeleteOnNull:

<Association Name="Parent_Child" Member="Parent" AccessModifier="Internal" ThisKey="OwnerParentId" Type="Parent" IsForeignKey="true" DeleteOnNull="true" />

Sorted!

Why Is That Internal?

Mon, 05 Nov 2007 10:54:05 +0000

I'm a big fan of the .NET framework, so much so that for the past five years I haven't wanted to code in any other environment. Even so, sometimes I find myself getting frustrated with it - most recently when I was trying to get ASP.NET user controls (.ascx files) working from a different assembly (I mean come on - that's fairly basic - why won't ASP.NET let me do that?)

Since it's not a supported scenario, to get it to work I had to patch into the resource loading system, then fix up any field references and post-back events. Thanks to reflection I got it working in the end, but it's just so frustrating to be able to see the function I want to hook into in the call-stack or using Reflector, but not be able to because that function has internal accessibility.

I was pretty grumpy by then, so I decided to look into something that's been bothering me for a while now: why, whenever you want to do something slightly out-of-the-ordinary, do you find yourself blocked by the framework and its private, internal, non-virtual design?

I decided to focus on the 'internal' problem and knocked up a little application that scans the public types in an assembly, and counts the number of public, internal, and private, fields and methods. (I'm lumping public and protected in the same count since they're both part of the public contract of a class, and I'm only considering exported types since there can be good reasons to have internal classes with internal methods. For non-.NET coders, internal types are public to types in the same assembly, and private outside, a cousin to 'friend' in C++). Here's what we get for a selection of framework assemblies:

Yikes! Some of those assemblies are comprised 15% - 20% of internal methods. How come the System-Drawing team managed a design with just 1% internal, but the System-Xml-Linq team felt they needed nearly 20%?

'Internal' breaks a class's modularity and encapsulation. If you feel another class ought to be able to access a method, use public. If not, that's private. If you're using internal, you're too lazy to create a decent design.

When you have a lot of internal methods, you cease to have an assembly containing independent classes. You instead have a single, monolithic, assembly-sized class. You can't change anything without affecting every other class in your assembly.

I'm not saying that you have to get to 0% internal methods, just that that accessibility should be reserved for unusual cases. Some framework teams seem able to manage it. We've managed it, albeit in a much smaller project - see the screenshot below. Why can't the other framework teams?

Estimating Piracy Rates - IE7 Released Without WGA Checks

Sun, 07 Oct 2007 12:24:59 +0100

I noticed a few days back that Microsoft have announced that IE7 is to be released to everyone - without the usual WGA checks. Here's something they could do with the data they collect: estimate piracy rates.

A. Microsoft know how many people legally own Windows.
B. Microsoft know how many people upgraded to IE7 under the WGA checks.

=> Roughly, the proportion of people who want to or can upgrade is B/A.

C. Microsoft know how many EXTRA people upgraded after the WGA check was removed (they may have to wait a few months to make this more accurate).

=> There are roughly C * A/B pirated copies of Windows.

Easier Threading: Software Transactional Memory: Part 4

Fri, 07 Sep 2007 17:30:56 +0100

Last article I covered my implementation of software transactional memory in C#. If you haven't read those articles yet, in brief, it's a technique where we can write efficient, thread-safe client code without using having to think about locks or events - all isolation, atomicity and signaling is handled by a small set of common routines.

I've presented this technique, and the code, as the realization of an idea that could be taken further - I'm pretty sure it's not ready for production code yet. In this final article, I'll give a link to the source, and cover some pros and cons of this technique.

The articles and source will be kept up-to-date on:

http://www.binarycomponents.com/Labs

But for convenience, here's links to everything so far:

Part 1: The Problems with Locking

Part 2: Atomicity and Isolation: That Reminds Me Of A Database

Part 3: Implementation

Source: TransactionalMemory.zip

Pros

Safety: Transactional values must be accessed inside a transaction. This is enforced by a runtime check.
No deadlocks: All locks are taken by the implementation, not the client code. Locks are taken in a strict order.
No explicit communication: Communication is handled by the implementation; the client only needs to rollback and wake-ups are handled automatically and efficiently.
Fine-grained locking: Only those locks which need to be taken are taken, and for as short a time as possible.

Cons

Copy overhead: When values are first accessed, or a transaction committed, values are copied. This would be unacceptable for large data-structures.
Re-execute overhead: Code blocks that rollback must be re-run. If the block performs significant processing, this would waste CPU time.
No side-effect checking: Code blocks should be free of side-effects, but this cannot be enforced in C#.

Feedback

If you have any comments on this technique, please let me know. I'd be particularly interested if anyone uses it in "real" code, as opposed to my simple examples. Additionally, if you're able to overcome any of the "cons" listed, I'd like to know that too.

If you find any bugs, please do let me know, and I'll update the source. (Any bugs in the implementation will of course go to show how bug-prone normal locking techniques are).

Easier Threading: Software Transactional Memory: Part 3

Thu, 06 Sep 2007 12:11:30 +0100

Previously I presented transactions as an alternative conceptual scheme to locking. In this article I'm going to examine an efficient implementation of software transactional memory.

Preamble

Before I begin, I want to re-iterate that these ideas, and in particular the basics of the implementation, are drawn from the chapter "Beautiful Concurrency" by Simon Peyton Jones from this book. He described the Haskell version of software transactional memory; what I'm going to describe is my rendition of that into C#.

Source

The complete source code, plus a few simple test applications, can be found at:

http://www.binarycomponents.com/Resources/Source/TransactionalMemory.zip

You'll need Visual Studio 2008 Beta 2 if you want to compile this project.

Overview

This implementation draws on the usual implementation of database transactions. When a transaction is begun, a "log" is created that will store the state related to the transaction. This state may be read, written, or discarded, without affecting the committed, valid memory. The transaction logs, together with the locks, events, and most of the logic is held in a manager class.

All transactional data is held in classes derived from TransactionalValue. The derived classes proxy all requests through the manager, so that any necessary checks can be made (for example, to check that they aren't accessed outside of a transaction), and so that the log can be read or written appropriately.

Code that acts on transactional values is represented by Actions. To save the hassle of creating a derived class for each block of transactional code, a DelegateAction is provided so that code may be written inline. The code in an action should be side-effect free since it may be executed more than once. The action returns success or failure depending on whether the block should be committed or rolled back. (Of course, just because the block wishes to be committed doesn't mean it will be).

Locking

Each transactional value is associated with one of a number of lock objects, and one of a number of events. Locks and events are allocated in turn as each transactional value is created. The lock is used whenever the real, committed value needs to be read or written. (This will occur on the first read or write of the value in a transaction, or when a transaction log is being verified and committed). The events are simple "wake ups" used to retry transactional code blocks after a rollback. All locking and wake-up logic is contained within the manager. When locks need to be taken, they are taken in strict order, so deadlocking is avoided.

The Log

The first time a particular transactional value is accessed within a transaction (either read or write), it is "promoted" to the log. In the log is stored the working value, together with the value that was initially read. Subsequent reads or writes to that value act on the working value in the log. The log is stored per-thread.

When the log is ready to be committed, it must first be verified for consistency. Failing verification results in a rollback and retry. Before verification (and possible commit), all locks associated with values in the log are locked. A log is verified if all of the stored original values are the same as the current master values. If verified, the master values can safely be overwritten by the log values.

Rollbacks

If a transaction needs to be rolled back (either because the code block requested it, or because the log verification failed), the log is discarded, and the code block is scheduled for re-execution. Because the code is assumed to be free of side-effects, the only time the block could possibly succeed (having just failed) is when one of the values it has read during execution changes. To efficiently perform this wait, the manager waits on the events associated with the values in the log. These events are signaled when a log commits.

Explicitly requesting a rollback is a great way for threads to communicate. For example, in the "Dining Philosophers" sample, a rollback is requested if either fork is in use - the thread will be woken when one of the neighbours puts the fork down - and in the "Producer/Consumer" sample, a rollback is requested by the consumer if the buffer is empty - the thread will be woken when the producer adds a value. Note that none of this communication is explicitly stated in the client code - it just magically works.

In the next and final article, I'll look at some pros and cons of this technique.

Easier Threading: Software Transactional Memory: Part 2

Wed, 05 Sep 2007 14:18:38 +0100

Last article I talked about the use of locks to solve threading issues, and how they problematic they are: necessary, but very low level. In this article, I'm going to imagine a different world...

Let's imagine that we can open a transaction, just as we might when using SQL, but for ordinary variables. Transactions have two important properties:

Atomicity: Others can see the state before the transaction, the state after the transaction, but never the state part-way through. A transaction is all-or-nothing.
Isolation: Conversely, if you're working within a transaction, you can't see other's changes. You see a (consistent) snapshot of the state of system at the time of the start of the transaction.

And afterall, that consistency is what we're trying to achieve with locking. If we can get transactions working, we should be able to use them instead of locks.

So let's imagine that this exists for memory, not just SQL databases. Our bank account problem from the previous article suddenly becomes very easy to solve:

class BankAccount
{
  public void Deposit( long change )
  {
    BEGIN TRANSACTION
    _amount += change;
    COMMIT TRANSACTION
  }

  private t_long _amount;
}

public static void Transfer( BankAccount a, BankAccount b, long amount )
{
  BEGIN TRANSACTION
  a.Deposit( -amount );
  b.Deposit( amount );
  COMMIT TRANSACTION
}

Easy. Of course, we could never have that actual syntax in C#, but that's conceptually what we want to achieve.

Of course, one correct (but really bad) way of implementing this would be to have a single, global, lock, and to lock and unlock that as we enter and exit transactions. If we also checked that we were in a transaction before accessing a variable (and that's why I've changed the type to be "t_long" to imply that), then we have solved all three problems mentioned previously. Of course, that method doesn't scale very well: any contention on the lock, even if it was on different values, would block all other threads. It does at least demonstrate that the concept is good.

So next article I'm going to describe a better way of implementing memory-transactions using optimistic locking. I'll also look into the transaction command I've not mentioned so far, ROLLBACK, and discover it's really useful. I have an actual working implementation of all this in C#, so at the end of these articles, I'll make the source available.

Easier Threading: Software Transactional Memory: Part 1

Tue, 04 Sep 2007 16:27:20 +0100

As I mentioned in a previous post, I've been reading through "Beautiful Code: Leading Programmers Explain How They Think", and one chapter that really caught my attention was about Software Transactional Memory. What I'm about to present in this mini-series therefore is merely my take on an idea that greater minds than mine have come up with.

The Problems with Locking

I'm a C# / .NET programmer, and the staple multi-threaded construct is the lock block (which is basically a monitor or mutex):

lock( _lockObject )
{
  SharedResource.Foo(); // Access a shared resource.
}

All fine and good, and you certainly can't do without them, but there's a bunch of problems with them:

1. Locks Aren't Enforced

Since there's no necessary connection between the lock and the resource, it's possible to forget to lock:

Thread_1
{
  lock( _lock )
  {
    SharedResource.Foo(); // Access a shared resource.
  }
}
 
Thread_2
{
  SharedResource.Foo(); // Access a shared resource.
  // Oops!
}

There's not even a runtime error here. That program is wrong, silently wrong, and difficult to debug.

2. Locks Don't Combine

Let's say we have a bank account class:

class BankAccount
{
  public void Deposit( long change )
  {
    lock( _lock )
    {
      _amount += change;
    }
  }

  private long _amount;
  private object _lock = new object();
}

Then how do we write a thread-safe transfer method?

public static void Transfer( BankAccount a, BankAccount b, long amount )
{
  // This is incorrect:
  a.Deposit( -amount );
  b.Deposit( amount );
}

What can I lock on to make this function correct?

3. Locks Can Deadlock

If you're using more than one lock, you'd better get them in the right order, otherwise you're jammed. Getting into deadlock is easy; getting out is near-impossible.

The Cliff-Hanger

So locks are evil then. A necessary evil, but evil nonetheless. But we can hide them away...

As a parting teaser before the following parts, here's my implementation of the Dining Philosophers problem, written without any (obvious) locks:

using System;

using System.Threading;

namespace ConsoleTests

{

public static class DiningPhilosophers

{

public static void Run()

{

//

// Create fork values.

for( var i = 0; i < _numPhilosophers; ++i )

{

_forks[i] = new BinaryComponents.TransactionalMemory.Values.Boolean( false );

}

//

// Create a thread for each philosopher.

for( var i = 0; i < _numPhilosophers; ++i )

{

var pts = new ParameterizedThreadStart( RunPhilosopher );

var thread = new Thread( pts );

thread.Start( i );

}

}

private static void RunPhilosopher( object data )

{

var n = (int) data;

var rnd = new Random();

var leftFork = _forks[n];

var rightFork = _forks[( n + 1 ) % _numPhilosophers];

while( true )

{

Console.WriteLine( string.Format( "Philosopher {0} is hungry...", n ) );

//

// Try to grab the forks.

BinaryComponents.TransactionalMemory.Manager.Execute( delegate

{

//

// If either fork we want is in use, then retry.

if( leftFork.Value || rightFork.Value )

{

return false;

}

//

// Otherwise, grab them.

leftFork.Value = true;

rightFork.Value = true;

return true;

} );

//

// Eat for a while.

Console.WriteLine( string.Format( "Philosopher {0} is eating.", n ) );

Thread.Sleep( rnd.Next( 5000 ) );

Console.WriteLine( string.Format( "Philosopher {0} puts down the forks and starts thinking.", n ) );

//

// Drop the forks.

BinaryComponents.TransactionalMemory.Manager.Execute( delegate

{

leftFork.Value = false;

rightFork.Value = false;

return true;

} );

//

// Think for a while.

Thread.Sleep( rnd.Next( 5000 ) );

}

}

private const int _numPhilosophers = 5;

private static BinaryComponents.TransactionalMemory.Values.Boolean[] _forks = new BinaryComponents.TransactionalMemory.Values.Boolean[_numPhilosophers];

}

}

Silverlight Image Mashup Problems (And Solutions)

Tue, 21 Aug 2007 15:57:02 +0100

(Actually, most of the solutions presented here apply to all kinds of mashups in Silverlight, not just images).

Background

We've officially started work on the online/web version of FeedGhost, and given that our expertise in mainly in .NET, we've decided to make it a Silverlight application. I've started work on the component that will take the messy HTML found in feeds and display it using Silverlight's subset of WPF. The process will be something like:

Convert the HTML to XHTML (or at least, XML - we won't be validating anything at this stage).
Convert the XHTML to an intermediate format. This format will be simple and well-defined. CSS Styles will be expanded here.
Render the intermediate format to WPF elements. This stage may be repeated if further layouts are required.

Stage 1 has already been coded - you can read about its use in FeedGhost for Windows here. Stage 3 involves the most unknowns for me, so I'm working on that right now.

One of the features I'm going to have implement is displaying images: an author can include an image (or rather, a link to an image) in his/her blog, and FeedGhost Online should be able to display it. Let's take the obstacles one by one...

Cross-Site Scripting (XSS) Protection

Silverlight protects against cross-site scripting (XSS) attacks. I won't go into this in detail, but suffice to say, if your Silverlight application is hosted on foo.com (for example), it can happily download resources that are also hosted on foo.com, but it won't be able to download resources from bar.com. This immediately presents us with a problem, since FeedGhost Online will be hosted on feedghost.com, but the images will be coming from, well, anywhere.

Hopefully at some point Microsoft will allow developers to explicitly turn off aspects of XSS protection, but until that day, we need a work-around. There's various ways of achieving this, but I've chosen to use a proxy. Example: let's say my Silverlight application wants to download:

http://www.example.com/image.jpg

It can't, so instead I code up a proxy and have the application ask for this instead:

http://www.feedghost.com/imageproxy.ashx?uri=http://www.example.com/image.jpg

So long as my proxy delivers an image too, my Silverlight application will be able to download it.

(Don't bother trying either of those web addresses by the way, neither of them exist. Also, the parameter supplied should be encoded, but I haven't done that in this example for clarity).

The downside of this particular workaround is bandwidth - each image request is routed through your server, and you pay for each request twice: download and upload.

I'll show sample code for a proxy at the end of this article, but before then, we have more problems in the way.

Downloader Bugs

Silverlight comes with a really helpful class, Downloader, that really simplifies downloading resources asynchronously, but without any kind of threading hassles. Unfortunately, in the latest Alpha Refresh release of Silverlight, a nasty bug crept in.

The bug manifests itself under the debugger, and prevents the Silverlight application from accessing resources that under normal hosting circumstances, it would be able to access. In other words, if I run my Silverlight application under the debugger thus:

file:///C:/...somewhere.../Application.html

and it tries to access a resource:

file:///C:/...somewhere.../Resources/Blah

it (incorrectly) fails.

The moral of this story is that if you can't get your Downloader to work correctly, try hosting your application under IIS and running it from localhost.

I've logged this particular bug with Microsoft:

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=293772

Unsupported Image Formats

Having worked almost exclusively with the .NET Framework for the past few years, I've become accustomed to it being able to handle any standard file I throw at it - any format, any encoding. Silverlight however runs on a cut-down version of the framework, and many features are missing. One of these missing features is support for the GIF file format. Since blog authors can choose to use any image format for their images, we need to solve this.

Luckily, the solution to this dovetails nicely with the XSS/proxy solution - when proxying images, simply convert GIFs to another file format.

Note

Eventually, as well as using them in our online reader, we're planning to make the Silverlight flow-layout and HTML render components available for sale (together with the Silverlight river-view, tree, and list components that we'll need), but in the meantime, if you think you might be interested, please contact me.

Proxy Source Code

Hopefully the following source code is enough to get you started with cross-site mashups. It's very simple; a production version would probably implement some kind of caching, and better error handling.

ImageProxy.ashx

<%@ WebHandler Language="C#" CodeBehind="ImageProxy.ashx.cs" Class="Website.Content.Utility.ImageProxy" %>

ImageProxy.ashx.cs

using System; using System.Data; using System.Web; using System.Collections; using System.Web.Services; using System.Web.Services.Protocols; using System.Net; using System.IO; using System.Drawing; using System.Drawing.Imaging; namespace Website.Content.Utility { [WebService( Namespace = "http://tempuri.org/" )] [WebServiceBinding( ConformsTo = WsiProfiles.BasicProfile1_1 )] public class ImageProxy : IHttpHandler { public void ProcessRequest( HttpContext context ) { string uriText = context.Request["uri"]; Uri uri; if( !Uri.TryCreate( uriText, UriKind.Absolute, out uri ) ) { throw new HttpException( 404, "Bad URL parameter." ); } try { WebRequest request = WebRequest.Create( uri ); WebResponse response = request.GetResponse(); context.Response.ContentType = response.ContentType; Stream stream = response.GetResponseStream(); Image image = Image.FromStream( stream ); ImageFormat format = image.RawFormat; if( object.Equals( image.RawFormat, ImageFormat.Gif ) ) { format = ImageFormat.Png; context.Response.ContentType = "image/png"; } MemoryStream ms = new MemoryStream(); image.Save( ms, format ); ms.WriteTo( context.Response.OutputStream ); response.Close(); } catch { throw new HttpException( 404, "Failed to process image." ); } } public bool IsReusable { get { return true; } } } }

Book Recommendation: Beautiful Code: Leading Programmers Explain How They Think

Mon, 13 Aug 2007 19:16:34 +0100

I bought this book on a whim, and now, even though I'm only halfway through, I can thoroughly recommend it to any programmer.

Beautiful Code: Leading Programmers Explain How They Think

It's not a book of facts or techniques, rather it's thirty-odd "presentations" by different authors about the code they think is most beautiful. If you're anything like me you're not going to agree with 100% of these, and in fact I thought one chapter involving FORTRAN was horrific ugly code, but it will definitely get you thinking.

Why you might want this book:

If you've been working exclusively in one technology for a while (.NET, in my case), this book presents languages and environments of all kinds. Getting stuck in a rut is all too easy.
If you think you've got nothing left to learn, well, you really need this book.
If you've resigned yourself to the idea that certain aspects of programming are just facts of life, this book is full of radical new ways of thinking.

And if you're still not convinced, all author royalties from this book will be donated to Amnesty International.

Breaking Changes in Orcas

Wed, 01 Aug 2007 15:02:54 +0100

Having been using Visual Studio 2008 "Codename Orcas" Beta 1 (breathe) for a while now, I was excited to see that Beta 2 is now available. These betas are stable, have some great new features, and are available as Virtual PC images (if like me you can't risk breaking a work machine), so there's really no excuse not to give it a try.

Unfortunately, I've hit two big breaking changes upgrading from Beta 1 to Beta 2, which is surprising given Microsoft's usual commitment to backwards-compatibility; hopefully this won't be the shape of things to come.

Firstly, double-clicking any solution (.SLN) files created in Beta 1 doesn't do anything. The trick is to load it up into Notepad and change the line:

Microsoft Visual Studio Solution File, Format Version 10.00 # Visual Studio Codename Orcas

to:

Microsoft Visual Studio Solution File, Format Version 10.00 # Visual Studio 2008

I can't see any reason why the old format couldn't have been detected or upgraded in this situation.

Secondly, and far more seriously, if you've previously created any LINQ-to-SQL schema files (.DBML), well, they're just junk now. The file format has changed and I can't see any way of upgrading from the old to the new. I'm glad Microsoft aren't sticking with sub-optimal designs just for backwards-compatibility, but if they want us to really get stuck into the betas, especially in key new feature areas, then upgrade paths are a must.

An Interesting Find: ProductWiki

Wed, 25 Jul 2007 18:42:09 +0100

Now this isn't a new website by any means (although it is new to me), but it tweaked my interest. ProductWiki

http://www.productwiki.com/

aims to be "the most comprehensive product information resource supported by a passionate community", and it's a really nice idea: a review site in the form of a wiki. It does look like a fair few of the products are just the manufacturer's blurb with no actual independent review, HOWEVER if that bothers you, since it's a wiki you can go and add your voice.

(And yes, I have added FeedGhost to the list. Feel free to go and be as critical as you like).

Another nice aspect of this site is that it seems to be under active moderation - there's nothing so depressing as visiting a "community content" site only to discover it's nothing more than a billboard for spammers. Not long after I posted my entry, I received a couple of questions from one of the founders of the site, so it looks like someone "official" is keeping an eye on things).

One little feature they might consider adding is "reviews needed": let's say I search for a particular product, and it isn't in their database, perhaps they could tally those and present the most searched for as "needing reviews". They do say there's a hundred times as many content-consumers as content-producers, and that could be a nice way of leading people into creating reviews.

I'm Moving

Thu, 12 Jul 2007 14:07:35 +0100

Emma and I are moving house tomorrow (finally), so I'll be out of contact for a while. Hopefully the internets should be re-connected on Tuesday, but it could be as long as two weeks.

In the meantime, if you need to contact me, please email Lee instead and he'll pass on any messages.

Why Are Entity-Relationship Diagrams So Unintuitive?

Sat, 07 Jul 2007 20:15:01 +0100

I have a real problem with entity-relationship diagrams. I can never remember which way around is which.

Quick, answer me this: which side in the following is the parent ('one'), and which is the child ('many')?

What is the arrow pointing to? What does the diamond mean? There's no mnemonic that I can find there.

(If you can't remember the answer, and I don't blame you if that's the case, the 'parent' is on the left, and the arrow points to the 'child' on the right).

Just to make absolutely sure I can't remember, whoever standardized these diagrams choose to have arrows pointing 'downwards' on E-R diagrams, but 'upwards' on class-hierarchy diagrams.

It's not even as if my inability to remember is from lack of experience; the last commercial system I worked on had perhaps 200 tables, and I had a (minor) hand in the coding of the actual custom object-relational system itself.

I propose the following: drop those dumb diamonds that don't mean anything, and standardize on crow's feet diagrams:

One... to many. It speaks for itself. I'll even let you add bars and zeros to clarify the exact constraints if you feel you have to. Who's with me?