A couple of months ago I finished an article for PCPlus about algorithms for solving Rubik’s Cube. It’ll appear in issue 298 in September 2010.

As part of my research I came across this article and video on Wired about an iPhone app that helped you solve it and, more than that, solve it in a remarkably small number of moves (usually 20 or fewer) using Kociemba’s algorithm. The free app (called CubeCheater) was written by Eric Faller. Unfortunately it seems he didn’t request permission from Seven Towns (the current owners of the license to market Rubik’s Cube worldwide) and had to remove the app. (Aside: my editor at PCPlus, Alex Cox, obtained permission from them for me to write about Rubik’s Cube for the magazine before I ever put electronic pen to Microsoft Word paper.)

Bummer. I would have liked to try the app and written about it as well. But, no go, so I submitted the article and forgot about it.

Imagine my surprise when this weekend, I was perusing the App Store when I came across the official Rubik’s Cube iPhone app. Further imagine my surprise when I saw that said app had exactly the same solver function as CubeCheater. Not only that, but the same interface.

(Compare this to the interface shown in the video taken 18 months ago.) Interesting, no?

Anyway, I bought it ($4.99) to try it out. The only part of the app I was interested in was the Solver function where you input the state of a mixed-up cube and it solves it for you in as few moves as it can.

There is a cool feature where you input the faces using the camera rather than painting each cubelet with colors from the palette. You take a snapshot of the cube and the software works out the face’s grid and the colors in each cubelet.

For me and my particular cube this functionality is a complete and utter failure. The edge detection is pretty bad to begin with (hint: don’t try and fill the camera screen with the face like the image below, but make it occupy as much room as the image of the face above), but the color recognition just sucks. Here’s my white face (so called because it’s named after the center cubelet):

And here’s what the app thought it was:

There’s another problem which the app doesn’t address. For some unknown reason — perhaps because my cube is so old (I purchased it in 1979 before Ideal Toys got the original license to market the puzzle worldwide in 1980) — my cube center cubelets don’t follow the current standard positioning. I have red on the opposite side to white, not yellow. In fact, yellow and red are reversed on my cube, so, even if the camera input method worked, I’d have to fiddle with the colors anyway (wherever the app talks yellow, I have to think red, and vice versa).

OK, so given that for my physical cube I have to remember to switch yellow and red, does it work? Does it calculate a solution with a small number of moves? The answer is yes. It’s quite magical if you look at the cube after each move and see the colors slowly coming together.

I don’t particularly want to rate the app officially (after all, I haven’t tried the other parts of the app: solving a virtual cube on the screen with flicks of the finger, or the tutorial section), but I will admit to being very disappointed in the camera interface. Unlike this Sudoku Grab app, the AI in the Rubik’s Cube iPhone app is not that good at all.

Share it:                

Recently it seems that I’ve been banging my head against the ceiling of my 128GB drive in my laptop. My drive comes up red in Windows Explorer every now and then and red is the color that makes you panicky. And before you say, “128GB? How old is this laptop?” let me explain that it’s an SSD and that’s all I could afford at the time I upgraded the drive.

Newegg had a deal on this week with the Crucial ReadSSD 256GB — the price has since gone up again — so I pulled the trigger and bought one. Twice as much space should do me for a while. The Crucial is a nice bit of kit with some really rapid read/write timings and TRIM support in Windows 7. I think all new SSDs now support TRIM, but my current Super Talent MasterDrive SX didn’t (actually there’s now a firmware update you can apply — which wipes all data, note — which adds that support) and I’d have to say that I’ve noticed the drive seems a little sluggish with writes.

Since I decided to restore from Windows Home Server and ran into a few little gotchas as I did so, I thought I’d write it all down for next time or to help you out if you’re about to venture down the same path.

I made sure I made a final up-to-date backup onto my Windows Home Server (WHS), removed the old drive, and installed the new one.

To restore a drive’s contents from WHS, you use a special Restore CD. Boot up with that and follow the prompts, basically. Although your WHS hardware came with a Restore CD, Microsoft recommend that you download the latest ISO file from their site before doing the restore to make sure you have the best version that will work with the (probably frequently updated) WHS OS on your box. Fine, did that, burned the ISO, got a new bootable CD.

Since this was essentially the first time I was restoring a drive completely from WHS, I also found a site that went through the steps in nice gory detail (or at least seemed to).

I booted up into the Restore CD and followed the first few steps. Just like in my noob’s guide, the Restore CD didn’t recognize my network adapter and you absolutely must have that set up otherwise you won’t be able to connect to your WHS. I clicked on the “Where can I find drivers for my hardware?” link. The help came up and explained that every time you make a backup, WHS saves your drivers in a special folder on the server for just this eventuality. No problem, then. I followed the instructions and copied the drivers onto a USB drive. After plugging it into my laptop, I clicked on the Install Drivers... button and scanned for them. Success, it found the drivers and...

...They did didn’t show up in the Detect Hardware dialog. WTF?

I tried again: no show. I was a bit stumped, so looked at the USB drive, thinking that perhaps the drivers had to be in the root instead of in the weirdly named folders WHS had put them in. However, something in those weird names gave me pause: the letters “64”. Sure enough, they were 64-bit drivers since my laptop was running 64-bit Windows 7. Therein lies Gotcha no. 1: the OS booted up by the current Restore CD is a 32-bit OS. It can’t use those 64-bit drivers. There is no 64-Bit Restore CD at the time of writing, although I believe that the new version of WHS will include one.

So it seems I had to get the 32-bit drivers onto this USB drive. I visited the Dell site and downloaded the 32-bit drivers for the wireless adapter. Dell’s driver downloads work by unzipping a bunch of files into a folder and then running an install program. In essence I got the download to unzip the files onto the USB drive and then cancelled the installer. The drivers were unzipped into some sub-sub-folder.

Over to the laptop again: reboot and get it to find/install the drivers. Success: the wireless driver was found, so it was onto the next step: searching for my WHS over the network. It failed. I tried again and it failed. I tried entering the name of the server: it failed. Bummer.

OK, then. Back to Dell I went and downloaded the Ethernet 10/100 adapter drivers instead. Same rigmarole (unzip to USB, stop installer) and then reboot the Restore CD. It found the new drivers and this time found the server. I was in!

And then I suddenly realized why using the wireless drivers failed: it wasn’t the drivers, it was the fact that my wireless router is protected with a password. This is Gotcha no. 2: the Restore CD does not prompt you for the wireless router password. You either turn off security on your wireless router (and presumably it all works but your neighbors have a field day stomping over your Internet access) or you use a wired connection instead to do your restore. Another advantage to wired is that it’s a bit faster, so that’s what I continued with.

After that it was all a bit of a downer: I partitioned the SSD, formatted, and the restore is still going on.

Share it:                

In playing around with my blog’s new iPhone support I came across a doozy of a problem.

I display all of the code quoted in one of my blog posts in a special div that has the overflow style attribute set to auto. On desktop browsers, these divs are rendered in a block with horizontal and vertical scrollbars. If the lines are too wide for the width of the div they’re displayed in, the horizontal scrollbar is activated; similarly if there are too many lines to fit vertically (I set max-height to 400px currently), the vertical scroll bar is activated. Here’s an example of some code from a recent post, so you can see the effect I’m talking about:

  class SafeStackItem<T> {
    public T Value;
    public Int32 Next;
  }

  class SafeStack<T> where T : class {
    private Int32 head;
    private Int32 count;
    private SafeStackItem<T>[] array;

    public SafeStack(SafeStackItem<T>[] array, int pushFrom, int pushCount) {
      this.head = -1;
      this.array = array;

      count = pushCount;

      head = pushFrom;
      for (int i = 0; i < pushCount - 1; i++)
        array[i + pushFrom].Next = pushFrom + i + 1;
      array[pushFrom + pushCount - 1].Next = -1;
    }

    public Int32 Pop() {
      while (count > 1) {
        Int32 oldHead = head;
        Int32 oldHeadNext = Interlocked.Exchange(ref array[oldHead].Next, -1);

        if (oldHeadNext >= 0) {
          if (Interlocked.CompareExchange(ref head, oldHeadNext, oldHead) == oldHead) {
            Interlocked.Decrement(ref count);
            return oldHead;
          }
          else

            Interlocked.Exchange(ref array[oldHead].Next, oldHeadNext);
        }
      }

      return -1;
    }

    public void Push(Int32 index) {
      Int32 oldHead;
      do {
        oldHead = head;
        array[index].Next = oldHead;
      } while (oldHead != Interlocked.CompareExchange(ref head, index, oldHead));

      Interlocked.Increment(ref count);
    }
  }

However on the iPhone there are no scrollbars. How the heck are you supposed to scroll wide lines from left to right or many lines up or down?

It turns out that iPhone’s mobile Safari has a special trick up its sleeve: you use two fingers. Place two fingers in the block and move them simultaneously. You’ll find that you can scroll the text up/down, left/right. Try it and see using the above code block.

Share it:                

This blog uses GraffitiCMS as the blogging engine. This software has now been open-sourced by the original developers, Telligent, and is available on CodePlex. Although it’s pretty full-featured and does most of what I want and need from a blogging engine (and has lots of features I don’t use) there is no built-in support as yet for providing a special view for mobile devices.

Consequently, when you view the site on an iPhone, say (since this is what I use as a mobile phone), it displays the wide full look (currently 3 columns across) in a much shrunken form. Better would be to display the site in a single column and — even better — to not display the full text of the usual 10 articles shown on the front page. So, this week, after helping sort out some Medium Trust issues one of the patches had introduced (and that had left my site in a bit of a fragile state), I set out trying to find a way to create a special view of the site for the iPhone.

The first hint was a package called Graffiti Extras. It’s available on CodePlex at version 1.3, but hasn’t been updated for about 18 months. It contains a plug-in called Mobile Theme Selector. Put simply, this plug-in installs itself into GraffitCMS and, when a request is detected and the user agent string passed by the browser indicates a mobile device, the code switches the theme for the request. The theme switched to is one you write in the normal manner — views and CSS files — but that is optimized for a mobile device.

Sounds simple enough, and I set it up, but it didn’t work. I’d connect with my iPhone and still got the usual full view. Meh.

I looked at the code: in essence, in order to identify a mobile device, all that happens is that the user agent string is tested to contain “IEMobile” (presumably for Windows Mobile devices) or that the Browser object’s IsMobileDevice returns true. Well, I knew the first would fail, but the second?

  if ((HttpContext.Current.Request.UserAgent.IndexOf("IEMobile") > -1) ||
      (HttpContext.Current.Request.Browser.IsMobileDevice))
  {
    GraffitiContext.Current.Theme = MOBILETHEMENAME;
    ...
  }

Time to investigate IsMobileDevice; surely it should recognize the iPhone?

It turns out, apart from some default behavior, IsMobileDevice uses an external definitions file in order to decide whether the user agent string identifies a mobile device. And, lo, that definitions file is also on CodePlex (here).

Once you download it, you should extract the mobile.browser file and place it in the /App_Browsers/Devices folder of your web application (if the folder doesn’t exist yet, create it). Restart your application (in my case, that’s GraffitiCMS) and you should find that the iPhone is recognized as a mobile device.

Next time, I’ll talk about what needs to be done in order to display a page optimized for the iPhone.

Share it:                

Yesterday afternoon I finished my latest PCPlus article on generating all possible arithmetic expressions with four operators. The article explored several algorithms, such as evaluating all full binary trees with a certain number of internal nodes (mine was four), evaluating an expression tree, and the like, and for the sidebar I slipped in a quick bit about RPN (Reverse Polish Notation) and how succinct it is for describing arithmetic expressions (there’s no operator precedence or parentheses to worry about). Equally important is the absolute ease with which you can evaluate an RPN expression compared to an algebraic one (that is, an expression using the standard infix notation).

I sent it off but then started to think about how to convert an RPN expression (say, 1 2 3 4 5 + × - ÷) into its algebraic equivalent (1 ÷ (2 - 3 × (4 + 5)), or 0.04). The reason for doing this is to keep and use the speedy succinct RPN form internally, but to display any result in the normal format. There’s lots of information online about doing the reverse operation — that is, converting infix to postfix, for example Dijkstra’s Shunting-yard algorithm, which I first implemented at university using FORTRAN (shudder) — but virtually none about doing the opposite (and some of them I’ve seen even assume that the postfix expression has parentheses, for heaven’s sake).

So, as I said, I thought about it for a while and came up with this answer.

The easy algorithm is to read the RPN expression as if you were going to evaluate it but build up an algebraic expression instead.

Let’s show this with 2 3 + 4 ×. We read the 2 and push it onto the stack. We do the same with the 3. The next token is +, which we process by popping the right-hand operand (call this the rhs for right hand side), the left hand operand (lhs), forming an algebraic expression with parentheses: (2 + 3) and then pushing it onto the stack. Push the next token, the 4. The next token is ×. We pop the rhs (the 4), the lhs (the bracketed expression), form a new expression as before: ((2 + 3) × 4), and push it onto the stack. There’s no more RPN expression left, and so the answer is the final string on the stack. Not too bad, expect for the superfluous parentheses around the entire answer.

The problem with this simple algorithm is that it pays no attention to precedence and to avoid any problems with it surrounds each sub-expression with parentheses. For example, 2 3 × 4 + would be converted to ((2 × 3) + 4), instead of the more succinct, yet unambiguous 2 × 3 + 4.

So how can we improve on the situation? First of all we assign a precedence number to each of the four arithmetic operators: add and subtract get 1, and multiply and divide get 2. That way we can easily say that, for example, multiply is of greater precedence than addition (that is, given a choice between multiply and divide, we do the multiplication first).

We’re going to build up an expression tree from the RPN expression instead of a simple string as in the previous algorithm. We proceed as before but now the stack will store nodes of the expression tree.

Let’s show this with 2 3 + 4 × again. We read the 2, create a node to hold it, and push that node onto the stack. We do the same with the 3. The next token is +, which we process by popping the rhs, the lhs, and form a mini tree with a new root node to hold the +.

We push the root node, the operand node, onto the stack. We then read the 4, so create a node for it, and push that. The next token is ×. For this we pop the rhs, then the lhs, and form a new tree with the × operator as root:

This new root gets pushed onto the stack. As before, we’ve run out of RPN expression and so the answer is the top item on the stack. Of course, we’re not quite there yet: an expression tree is not an algebraic expression, but we’re close.

We now walk the tree using an inorder traversal, paying attention to precedence. In fact we use a rule that says if we go from an operator with a higher precedence to one with a lower precedence, we’ll output parentheses to surround the subexpression containing the lower precedence operator. If the precedence number is equal or lower, we don’t output any parentheses. Here’s the pseudo code:

string Visit(node, priorPrecedence) {
  if node is number 
    return number.ToString()
  result = Visit(left, node.precedence) +
           node.Operator +
           Visit(right, node.precedence)
  if node.precedence < priorPrecedence
    result = '(' + result + ')'
  return result
}

There are some assumptions here but they’re pretty obvious (for example, there’s some way to distinguish a number node from an operator node, operator nodes have left and right children, and so on).

So, a two-step process, but nothing too difficult once you’re used to the stack-based approach to evaluating an RPN expression. I quite like this idea of reconstructing an expression tree and then traversing it in a different order than before.

Share it:                

I’m in a show at the moment at the Fine Arts Center here in Colorado Springs (as it happens, tonight is opening night). We’re doing Crazy For You, a modern musical that marries up lots of great Gershwin tunes with a light 30s style plot. And tap dancing. Lots of tap dancing. Man, am I glad I’m not in those numbers: I get exhausted just watching.

Anyway, I play a British character (type-casting?) called Eugene Fodor who’s on a trip through the American West with his sister writing a guide book (no, nothing to do with the real Eugene Fodor or the Fodor’s guides, it’s just a joke). At a point in the second act I propose that the assembled company could learn a thing or two from Englishmen: to keep a stiff upper lip. And the company then slips into another wild tap number called Stiff Upper Lip, in which I’ll admit I do participate (probably muttering under my breath ‘step-ball-change’, ‘step-ball-change’). I am not, in any sense of the words, a gifted dancer.

Moving right along...

Last night I discovered that our set designer, Tom Hansen, is a cartoonist. As a present to each actor on preview night, he’d done a cartoon of them. Here’s mine, showing me giving my line with Tom’s recurring kid character listening in.

I’m so going to use that drawing of me. Maybe for the DevExpress newsletters?

Share it:                

It’s a little known fact that Roger Moore (he of the James Bond movies in the 70s and 80s and The Saint in the 60s) started out as a male model before he started to become more famous. As such, he was renowned for appearing in knitwear shots (to the extent of being known as ‘The Big Knit’) in the early 50s.

It just so happened that Mum had a Patons & Baldwins knitwear pattern booklet from that time amongst all her stuff and, lo and behold, there are some shots of Mr Moore in there. I snagged it from the house clearance people and brought it home for your delectation. Here’s the cover:

The booklet (number 698) is 12 pages long and cost sixpence (now 2½p). It was published by Patons and Baldwins Ltd, but unfortunately has no publish date.

He’s in the two pictures middle and bottom left on the cover. As you can see he’s modeling two patterns. The first is the Waistcoat for a Live Wire:

No, that’s not his iPhone he’s checking in the picture — bit early for one of those 55 years ago — but what it is I’m really not sure. Something electric, perhaps; hence the ‘Live Wire’ moniker. Actually the waistcoat doesn’t look too bad in this shot, methinks, though the cocky be-piped stance of the middle cover image is somewhat off-putting.

The second pattern he models is the Executive Type, a “pullover in three-ply”, which can be made either with long sleeves or sleeveless:

A serious executive look here with the secretary in the background, and on the cover a more go-getting attitude with phone in hand.

I must admit the pictures are a hoot. Very 50s.

Share it:                

The last couple of weeks has been spent sorting out stuff from my parents’ house. Some to be shipped here to the States, some that my sister was taking, some Victoriana (mostly furniture) to be auctioned off, and the rest to be disposed of. One of the things from my past that I found was my first 35mm SLR camera.

I bought it in 1979, my final year at University, because I wanted to learn about photography. Was I capable of training myself to take good photos? Did I have an ‘eye’? Would my photos be aweful or awful? The photos I took with this camera are on the slow boat to Colorado, so I’ll sort them out eventually and scan the best. I gave up the camera for a simpler Olympus point-and-shoot when I came to the States in 1993, a going away gift from my colleagues at Deutsche Bank.

The camera I’d bought was a pretty good inexpensive SLR: the Fujica ST605N. Completely manual, simple TTL metering (that worked surprisingly well), and the standard M42 mount (well standard at the time, anyway). It came with a Fujinon 55mm f/2.2 lens, but because of the universal mount it was easy to get other lenses. I eventually got three others (the first two of which I’ve now abandoned): a wide angle, a telephoto, and a Hoya 75-205mm f/4 zoom in 1985. I even went as far as getting some extension tubes to really play around with macro work.

However, because I used this when I was somewhat poor (students didn’t get a lot of money, and during my first few years of working I wasn’t earning that much and then got married), I was somewhat parsimonious when taking photos: the cost of processing was comparatively expensive. These days, I take photos with abandon on my DSLR, because they’re all essentially free. I can discard crappy ones without a thought. But with film I was under some self-imposed pressure to make each photo count.

Here’s a couple of examples I shot on a vacation with my then wife using Kodachrome slide film. We were holidaying in Normandy, so I’m guessing it would be around 1981, I suppose. (I scanned these examples with the film cassette of my Canon scanner at 1200dpi. No post-scan photo fixing.)

First is a boat in the harbor at Honfleur at low tide:

(Click to make larger.) Looking at this now, I just love the color and seeing the old French cars on the quayside...

Here’s another, perhaps not quite as successful. It’s of the central monument in the main German World War II cemetery in Normandy at La Cambe:

It seems this one was taken late in the afternoon. I find La Cambe difficult to photograph in dim or cloudy light: unlike the American cemetery at Colleville-sur-Mer, the gravestones are all dark, somewhat dismal stone. It definitely feels more melancholic than the grand American memorial, or even the simpler British one at Bayeux.

I feel like trying film again now that I’ve become a more confident photographer through using the Canon Digital Rebel XTi. So I’ll be buying some reels of film and seeing what happens next. The light meter still works after replacing the batteries, so there’s hope...

Share it:                

To say that the last three to four months have been grim is to understate it somewhat. On 13 December last year, in the middle of the night, Dad had a cardiac arrest and, being Dad, did nothing about it until the next morning when finally he was rushed to hospital. He died a week later of another heart attack, on 21 December.

Yesterday morning, Colorado time, I got a text from my sister saying Mum had been rushed to hospital with breathing problems that afternoon, UK time. Mum was looking for a warden-controlled flat near my sister’s and my sister was driving her over to view some. Apparently Mum had woken up feeling ‘sick’. After a couple of hours, they decided that Mum was feeling better and set off. They’d just joined the M6 when Mum complained of not being able to breathe. Nicola pulled into the next Motorway Services and phoned an ambulance. Mum was going white. Apparently, she stopped breathing altogether in the ambulance, only to restart again.

In the hospital, she was put in the Cardiac Care unit, since it was obvious she’d had a cardiac arrest at some point in time. Although, during that afternoon, she seemed to get better, by about midnight it was obvious that the medications weren’t working. Her kidneys had packed it in, she was still having difficulty breathing. She was taken off the meds and put on morphine to help with the breathing. Palliative care, in other words. She slept. On the occasions she woke, she didn’t seem to know where she was or what was happening or who anyone was, including Nicola. She’s fading.

Although she made it through the night and today (as I write this it’s 7pm in England), there is no hope. Nicola is by her bedside in the hospital simply waiting for her to die. I’m just waiting by my phone for the news. There’s no way for me to get there in time to say goodbye (the earliest I’d make it would be in about 24 hours’ time), not that she would recognize me anyway.

I thought I’d post a photo of them both on their wedding day in remembrance. It was a cold damp day at St Paul’s Church, Foleshill Road, Coventry, that Saturday, 5 November 1955. The church’s front door looks forbidding in this photo, but maybe it’s because it’s in black and white. Dad was 22, Mum had just turned 27. They are a handsome couple and Mum looks radiant.

I miss them both.

Share it:                

In the comments to my post on testing the lock-free stack, Dmitriy V'jukov wondered if my code could test a broken implementation of a stack built on a preallocated array. He provided a link to the code on a Russian forum (yes, I used Google Translate a lot). It seems it’s not his, but a friend’s or a colleague’s.

I downloaded it and cleaned it up a bit for here (the volatile keywords aren’t needed for example since there are memory fences all over the place, so that gets rid of the #pragmas, and I really wanted better names for the variables):

  class SafeStackItem<T> {
    public T Value;
    public Int32 Next;
  }

  class SafeStack<T> where T : class {
    private Int32 head;
    private Int32 count;
    private SafeStackItem<T>[] array;

    public SafeStack(SafeStackItem<T>[] array, int pushFrom, int pushCount) {
      this.head = -1;
      this.array = array;

      count = pushCount;

      head = pushFrom;
      for (int i = 0; i < pushCount - 1; i++)
        array[i + pushFrom].Next = pushFrom + i + 1;
      array[pushFrom + pushCount - 1].Next = -1;
    }

    public Int32 Pop() {
      while (count > 1) {
        Int32 oldHead = head;
        Int32 oldHeadNext = Interlocked.Exchange(ref array[oldHead].Next, -1);

        if (oldHeadNext >= 0) {
          if (Interlocked.CompareExchange(ref head, oldHeadNext, oldHead) == oldHead) {
            Interlocked.Decrement(ref count);
            return oldHead;
          }
          else
            Interlocked.Exchange(ref array[oldHead].Next, oldHeadNext);
        }
      }

      return -1;
    }

    public void Push(Int32 index) {
      Int32 oldHead;
      do {
        oldHead = head;
        array[index].Next = oldHead;
      } while (oldHead != Interlocked.CompareExchange(ref head, index, oldHead));

      Interlocked.Increment(ref count);
    }
  }

My first comments were essentially summed up by the word ‘horror’. The array is public, the indexes into the array are public (the push and pop operations work on array indexes, for heaven’s sake), and the elements are all public. I also pointed out that the stack was just completely broken: even in a single-threaded app you could never pop off the last item on the stack. He came back and asked whether I could find the bug in the algorithm. I replied with a negative, pointing out that

I'm not even sure how it's supposed to be used, so a test app would be more than welcome. In using a multithreaded stack, I'm more used to having 'producers' that push 'work' items on the stack, and 'consumers' that pop them off. Here I'm not even sure how a consumer would signal to a producer that it had completed the work on index N and hence that index can now be reused. Yuk, even writing that down gives me the shivers.

In translating and reading the thread on the Russian forum, I got the impression that he tested it with each thread popping off an item, “processing” it in some way, and then pushing it back. Why, I have absolutely no idea; I just think this stack is broken as a usable multi-threaded container for the reason given above, and that’s even before you get to the problem of it suffering from an ABA problem. (Or maybe you should have two such stacks, equal in size, pop off from one and push onto the other. Yuk.)

The ABA problem occurs because of the reuse of ‘nodes’ without making sure that all threads have relinquished control of a given node before reusing it. It’s a classic ABA scenario and after I’d thought about it for a little while, I played the game of “hunt the node reuse”. In the end, it wasn’t that hard to find.

Let us suppose that slow thread A ‘sees’ the stack 3 -> 4 -> 5 -> etc; that is, the head of the list is node 3. It calls Pop(). The first step is to read the head index into oldHead, setting it to 3. In between this step and the next, it falls asleep, and another thread, X, pops node 3. The oldHead node (that is, node 3) will have its Next index set to -1 by this pop operation.

Thread X then starts to push node 3 back onto the stack. However, it has some extraordinary difficulty because some rogue super-fast thread is pushing a bunch of nodes back onto the stack, bam, bam, bam. X tries, node 3’s Next gets set to 42, the current head, but the compare-exchange fails because the head has changed right under its nose. Damn. It tries again, node 3’s Next gets set to 43. No go, fails again. It tries again, setting node 3’s Next to 44 and finally succeeds.

The stack now should look like 3 -> 44 -> 43 -> 42 -> 4 -> 5 -> etc.

But in the middle of all that, thread A wakes up. It sees the momentary scenario of 3 -> 42 that is about to fail in the middle of thread X’s Push() loop. Its own exchange succeeds (the second step of its loop), and node 3 now points to -1 and oldHeadNext is 42. Thread A falls asleep again...

...and a little time passes. The stack now looks like this: 44 -> 43 -> 42 -> 4 -> etc. Thread X, in its attempt to push node 3 back onto the list has just set its Next pointer to point to 44, since that’s the current head of the stack (that -1 from the previous paragraph has long gone). It’s about to call the compare-exchange when...

...thread A awakes with a start. It fails its compare-exchange and so resets oldHead.Next to 42 (that is, node 3’s Next to 42) and goes round its loop again.

And thread X completes its compare-exchange successfully to push element 3 back onto the stack. Unfortunately, the stack now looks like this: 3 -> 42 -> 4  -> 5 -> etc, and elements 44 and 43 have been lost. ABA!

So, in summary, rule 1 of lock-free containers is “don’t reuse a node until every thread has relinquished that node’s reference”. With ‘my’ lock-free stack, the garbage collector enforces that rule in spades.

And before Dmitriy asks, this array-based stack is broken beyond repair. There is no fix. An array of nodes just implies “node reuse”.

Share it: