Posts tagged with 'stack'


Making a stack persistent or immutable

A while ago I wrote a book on algorithms and data structures, in my case for Delphi. It’s still on sale , but regrettably somewhat out of date, given the changes to the language in the last 15 years (I’m thinking of the new support for generics in particular). While on my vacation over the last couple of weeks I started thinking about writing a new series of blog posts on data structures, and what easier than updating the book into a new generics-capable one? There was one drawback: I haven’t done...

READ MORE

Nasty ABA problem in array-based lock-free stack

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

READ MORE

Testing the lock-free stack

Recently a reader was having some issues with my lock-free queue implementation. In investigating the problem, I decided to throw out my previous “stack and queue” multithreaded test program as being way too hard to modify and started out afresh. In doing so, I also cleaned up the implementations of the lock-free stack and queue, making extensive use of CodeRush ’s code issues functionality. For details on the lock-free stack, read here . For details on the lock-free queue, see...

READ MORE

More on the lock-free stack/queue: memory fences

Last time I talked about the lock-free stack and queue , I was more concerned about proving that my code was free from the ABA problem than anything else. In making my argument I naturally glossed over such niceties as the .NET memory model and so assumed (pretty much) a sequential memory model, because, to be honest, that's how we think as programmers. Consider the following set of statements in C#: int foo; bool fooHasBeenSet = false ; // ... foo = 42 ; fooHasBeenSet = true ; Now, you and I...

READ MORE

Someone is wrong on the internet — the lock-free stack edition

Getting on for 4 years ago, I wrote a series of posts on lock-free containers in .NET, like the lock-free stack and the lock-free queue . They were fun to write, mainly because of the difficulty of the topic and trying to rationalize why early versions didn't work, and so on so forth. Along the way I learned about the .NET memory model, volatile , memory fences, and other arcana, but in the end I had something that worked and worked well. Over the years since then I've had many emails from...

READ MORE

PCPlus 262: Best Data Use

I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the back of every issue. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. After all, the PDFs do appear on each issue's DVD after a couple of months....

READ MORE