The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

STM ?

Has anyone had experience of using a Software Transactional Memory implementation ? Preferably on .Net.

I'm thinking of using STM on a restricted quadtree, which as far as I can see is almost impossible to update concurrently with normal locks (unless I lock the whole tree..)

I've found the SXM library, NSTM and LibCTM. Also the Intel compiler, but that's not .NET :-(

Experiences - good, bad, problems etc would be most useful.

Thanks.
Count Almasy
Monday, September 08, 2008
 
 
I've been reading on STM, but have never used it in practice. Its an interesting approach, but not one I'd favor using. The only two languages that I know of with serious support is Haskell and Closure. (book: http://www.amazon.com/Transactional-Synthesis-Lectures-Computer-Architecture/dp/1598291246/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1220906152&sr=8-1)

I've never used a quadtree before, but looking at it I would imagine the locking is only needed on the parent node with expanding, adding, deleting children. My understanding of why trees are bad under locks is due to the popularity of types that must be rebalanced, like Red-Black trees, which usually requires locking the entire structure. Quadtrees don't seem to have that property, if I understand the wikipedia article correctly, so it may work fine.

I'd be curious to read a deeper explanation of quadtrees if you have any good references and to also learn why you're using them.
Benjamin Manes Send private email
Monday, September 08, 2008
 
 
I'm using a region quadtree as a spatial data structure to hold elevation data at variable resolution - the wikipedia  article gives a good intro. A complication is that I'm using a *restricted* quadtree, which means that the (spatial) neighbours of a node can only differ in level by 1. This makes it much easier to convert the elevation data into a triangle mesh.

It also means that any update to a node can affect its four neighbours. In the worst case the common 'ancestor' node may be the root node. I haven't been able to think of an efficient locking scheme that will guarantee that the tree will remain consistent for concurrent update and read traversals, hence the interest in transactions. Or, of course, efficient locking schemes.
Count Almasy
Monday, September 08, 2008
 
 
hmm, the more I read up on quadtrees the more I understand how difficult a lock-based algorithm would be to implement it. I can definately see why STM would make sense here. This is actually a great example, because most use cases I've seen (e.g. the Santa Claus problem) can be easily done using other idioms. This one, though, is quite tricky!

If I was faced with this I would first use a read-write lock to judge whether the performance was good enough. If its read-centric, then it should perform relatively well. I'd take a very pragmatic approach and use STM only when I have no other options.

I've discussed STM with former Sun engineers. From their perspective, the roll-back is very costly since it thrashes the CPU caches. Azul's Cliff Click has stated that it has unpredictable performance penalties. You may want to ask this question on the Haskell or Clojure forums, where STM has been used heavily.
Benjamin Manes Send private email
Tuesday, September 09, 2008
 
 
Benjamin,

Interesting, thanks. As far as I can tell from my Googling, work on 'mainstream' STM (i.e. C, C++, C#, java) seems to have stalled a year or two ago. I wonder if the performance penalties from rollback make it impractical in real applications ? It will be interesting to see if the Intel compiler makes it out of alpha.

I'll have a browse around Haskell and Clojure.
Count Almasy
Tuesday, September 09, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz