Home

The Transactional Memory / Garbage Collection Analogy

Courtesy of my shiny new commute, I have been listing to various podcasts, including Software Engineering Radio. A while back, they had an interview with Dan Grossman on his OOPSLA 2007 paper, which I have not seen discussed here.

The Transactional Memory / Garbage Collection Analogy is an essay comparing transactional memory with garbage collection based on the analogy:

Transactional memory (TM) is to shared-memory concurrency
as
garbage collection (GC) is to memory management.

Grossman presents the analogy as a word-for-word transliteration of a discussion of each of the technologies. (Hence the "fun" category.)

(As an aside, Grossman does not address message-passing, but says, "Assuming that shared memory is one model we will continue to use for the foreseeable future, it is worth improving," which is probably a correct assumption.)

One point that he does make is that

[This essay] will lead us to the balanced and obvious-once-you-say-it conclusion that transactions make it easy to define critical sections (which is a huge help in writing and maintaining shared-memory programs) but provide no help in identifying where a critical section should begin or end (which remains an enormous challenge).

The one serious weakness of the analogy, to me, is that GC does not require (much) programmer input to work, while TM does.

Although some parts of the analogy are strained, there are some interesting correspondences.

By Tommy McGuire at 2008-09-17 15:37 | Fun | Implementation | Parallel/Distributed | other blogs | 15117 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

OT on the SE podcast

I'm surprised and pleased to say that podcast looks like it has some great episodes. I'll be downloading some f'sure.

By Noel at Wed, 2008-09-17 16:34 | login or register to post comments

TM vs GC

Interesting paper, although I don't find the analogy a particularly compelling one.

However, it did get me to wonder: doesn't TM make GC's evaluation of reachability virtually intractable? Unless it can somehow peek into the contents of each transaction's memory cache but that doesn't seem at all feasible for HTM. Obviously, I'm assuming at least a hybrid HW/SW TM solution, if not full hardware TM.

By Michael McCarty at Wed, 2008-09-17 16:54 | login or register to post comments

Programmer thought

but provide no help in identifying where a critical section should begin or end (which remains an enormous challenge).

The one serious weakness of the analogy, to me, is that GC does not require (much) programmer input to work, while TM does.

I can't exactly refute that statement, but it seems to me that by making the result of a TM commit go into the IO monad, Haskell's STM makes it awfully hard to do the wrong thing regarding the extent of critical sections.

By James Iry at Wed, 2008-09-17 17:58 | login or register to post comments

True, but...

Haskell's type system would help a lot (for some reason, I keep thinking of STM in terms of the Java implementations). But consider ye olde synchronized data structure race condition:

  1. Acquire a lock on a structure, make a query, and release the lock.
  2. Acquire the lock again and based on the results of the query, modify the structure.

That's just as easy to do with Haskell's STM.

By Tommy McGuire at Wed, 2008-09-17 19:11 | login or register to post comments

Actually a bit harder

That's just as easy to do with Haskell's STM.

Not without subverting the type system. The result of your example query transaction is "locked up" in the IO monad so to speak, and you can't pull a result out of the IO monad for use in another transaction*. In order to use a value from a query in an update both the query and the update must be part of the same transaction.

* Actually, transactions can share values using unsafePerformIO and friends so saying it can't be done in Haskell's type system should be qualified by what is meant by "in Haskell's type system." :-) That's why I said originally that Haskell's STM makes it hard to do the wrong thing - you have to be pretty deliberate about shooting yourself in the foot in this way.

By James Iry at Wed, 2008-09-17 20:11 | login or register to post comments

I'm not sure what you mean

This is valid according to Haskell's type system:

query = undefined :: STM Int
update = undefined :: Int -> STM ()
bad = atomically query >>= atomically . update

By Jake M at Wed, 2008-09-17 22:57 | login or register to post comments

You know,

One of the things I hate about Haskell is that the code is both shorter and simpler than the English description.

By Tommy McGuire at Wed, 2008-09-17 23:16 | login or register to post comments

Sigh

Sometimes it doesn't pay to get out of bed. You're right. I wasn't thinking clearly as I wrote that. So, for the record, it is easy to pass values from transaction to transaction possibly violating your consistency requirements. I'm going to go eat a little crow, transactionaly.

By James Iry at Wed, 2008-09-17 23:22 | login or register to post comments

Verifying Correct Usage of Atomic Blocks and Typestate

On the other hand, I just noticed Verifying Correct Usage of Atomic Blocks and Typestate in the OOPSLA 2008 program:

The atomic block, a synchronization primitive provided to programmers in transactional memory systems, has the potential to greatly ease the development of concurrent software. However, atomic blocks can still be used incorrectly, and race conditions can still occur at the level of application logic. In this paper, we present a intraprocedural static analysis, formalized as a type system and proven sound, that helps programmers use atomic blocks correctly. Using access permissions, which describe how objects are aliased and modified, our system statically prevents race conditions and enforces typestate properties in concurrent programs. We have implemented a prototype static analysis for the Java language based on our system and have used it to verify several realistic examples.

I haven't read it, but it sounds promising.

By Tommy McGuire at Thu, 2008-09-18 20:23 | login or register to post comments

Beautiful analogy

I think this is a beautiful analogy, which is why I have been saying it for years. In fact it's rather surprising to me that this correspondence isn't highlighted more often. I think it has something to do with the plethora of concurrency approaches vs. the relative paucity of memory management options.

As far as programmer input goes, the analogy works there too. With GC, programmers still need to manually identify where allocations need to happen; GC removes "only" the effort of managing deallocations, which in the worst case requires global program analysis. Likewise, with transactions, the programmer still needs to identify where atomic operations need to occur. Transactions remove "only" the global program analysis needed to identify how to code that atomicity.

Where atomicity is needed is not something that the compiler will ever be able to infer; it's part of the semantics of the program. Which, when you think about it, means that transactions are the simplest programmer interface to atomicity that can possibly exist; they require of the programmer only that he identify atomic operations, which he always has to do anyway.

By marshall at Wed, 2008-09-17 19:06 | login or register to post comments

A part!

[[GC removes "only" the effort of managing deallocations]]

Removes only a part of the effort of managing deallocation, if you're not careful it's much too easy to have a global map or a chain of objects referencing many obsolete objects which "leak" memory.

By renox at Fri, 2008-09-19 18:33 | login or register to post comments

More analogy...

Yes, the analogy is a bit strained at points, but it's quite interesting anyway. If we want to extend it a little, we can see that GC only went "mainstream" when a new language, designed from the start to use GC, was widely adopted (in this case, Java). If this is preserved under the mapping from GC to TM (is it an homomorphism?), it means TM will not become mainstream as adaptations to the current mainstream languages, but only when (and if) a language is designed with TM in mind, and this language is widely adopted. So Java + TM won't cut it.

By Andrei Formiga at Thu, 2008-09-18 00:20 | login or register to post comments

whence Haskell and Clojure?

Haskell with STM has been around a while already, but perhaps for various reasons the whole gestalt is too big a horse pill for e.g. Java coders to swallow.

Perhaps Clojure will be an easier sell.

By raould at Thu, 2008-09-18 01:08 | login or register to post comments

One difference between GC and arbitrary transactions...

...that may or may not be of import:

The liveness of objects are (assuming the absence of brain-dead finalizers and such) is a monotonic property. Once an object is garbage it stays garbage.

The state changes guarded by transactions are, in general, not monotonic.

By Scott Johnson at Thu, 2008-09-18 22:24 | login or register to post comments