1.The Transactional Memory / Garbage Collection Analogy
Dan Grossman
University of Washington
Microsoft Programming Languages TCN
September 14, 2010
2.Today
Short overview of my history and research agenda
The TM/GC Analogy: My perspective on
Why high-level languages benefit from transactions
What the key design dimensions are
How to think about the software-engineering benefits
Plenty of time for discussion
September 14, 2010
Dan Grossman: The TM/GC Analogy
2
3.September 14, 2010
Dan Grossman: The TM/GC Analogy
3
Biography / group names
Programming-languages academic researcher,1997-
PhD for Cyclone UW faculty, 2003-
Type system, compiler for memory-safe C dialect
30% 85% focus on multithreading, 2005-
Co-advising 3-4 students with computer architect Luis Ceze, 2007-
Two groups for “marketing purposes”
WASP, wasp.cs.washington.edu
SAMPA, sampa.cs.washington.edu
September-December 2010: Sabbatical visiting RiSE in MSR
4.Some things not in today’s talk
Work at lower levels of the system stack
Compiler/run-time for deterministic multithreading [ASPLOS10]
Lock prediction [HotPar10]
Other approaches to improve shared-memory concurrency
Code-centric partial specifications [OOPSLA10]
Better PL support for web-application extensibility (with MSR)
Aspects for JavaScript [OOSPLA10]
Progress-estimation for MapReduce ensembles [SIGMOD10]
Better type-checker error messages [PLDI07]
Older work on memory-safe C (2000-2005)
…
September 14, 2010
Dan Grossman: The TM/GC Analogy
4
5.TM at Univ. Washington
I come at transactions from the programming-languages side
Formal semantics, language design, and efficient implementation for atomic blocks
Software-development benefits
Interaction with other sophisticated features of modern PLs
[ICFP05][MSPC06][PLDI07][OOPSLA07][SCHEME07][POPL08][ICFP09]
September 14, 2010
Dan Grossman: The TM/GC Analogy
5
transfer(from,to,amt){
atomic {
deposit(to,amt);
withdraw(from,amt);
}
}
An easier-to-use and
harder-to-implement synchronization primitive
6.A key question
Why exactly are atomic blocks better than locks?
Good science/engineering demands an answer
Answers I wasn’t happy with:
“Just seems easier” [non-answer]
“More declarative” [means what?]
“Deadlock impossible” [only in unhelpful technical sense]
“Easier for idiom X” [not a general principle]
So came up with another answer I still deeply believe years later…
September 14, 2010
Dan Grossman: The TM/GC Analogy
6
7.The analogy
September 14, 2010
Dan Grossman: The TM/GC Analogy
7
“Transactional memory is to
shared-memory concurrency
as
garbage collection is to
memory management”
Understand TM and GC better by explaining remarkable similarities
Benefits, limitations, and implementations
A technical description / framework with explanatory power
Not a sales pitch
8.September 14, 2010
Dan Grossman: The TM/GC Analogy
8
Outline
Why an analogy helps
Brief separate overview of GC and TM
The core technical analogy (but read the essay)
And why concurrency is still harder
Provocative questions based on the analogy
9.September 14, 2010
Dan Grossman: The TM/GC Analogy
9
Two bags of concepts
reachability
dangling pointers
reference counting
space exhaustion
weak pointers
real-time guarantees
liveness analysis
conservative collection
finalization
GC
races
eager update
deadlock
obstruction-freedom
open nesting
false sharing
TM
memory conflicts
escape analysis
11.September 14, 2010
Dan Grossman: The TM/GC Analogy
11
Analogies help organize
reachability
dangling pointers
reference counting
space exhaustion
weak pointers
real-time guarantees
liveness analysis
conservative collection
finalization
GC
races
eager update
deadlock
obstruction-freedom
open nesting
false sharing
TM
memory conflicts
escape analysis
12.September 14, 2010
Dan Grossman: The TM/GC Analogy
12
Analogies help organize
reachability
dangling pointers
reference counting
space exhaustion
weak pointers
real-time guarantees
liveness analysis
conservative collection
finalization
GC
races
eager update
deadlock
obstruction-freedom
open nesting
false sharing
TM
memory conflicts
escape analysis
commit handlers
13.September 14, 2010
Dan Grossman: The TM/GC Analogy
13
So the goals are…
Leverage the design trade-offs of GC to guide TM
And vice-versa?
Identify open research
Motivate TM
TM improves concurrency as GC improves memory
GC is a huge help despite its imperfections
So TM is a huge help despite its imperfections
14.September 14, 2010
Dan Grossman: The TM/GC Analogy
14
Outline
“TM is to shared-memory concurrency as
GC is to memory management”
Why an analogy helps
Brief separate overview of GC and TM
The core technical analogy (but read the essay)
And why concurrency is still harder
Provocative questions based on the analogy
15.September 14, 2010
Dan Grossman: The TM/GC Analogy
15
Memory management
Allocate objects in the heap
Deallocate objects to reuse heap space
If too soon, dangling-pointer dereferences
If too late, poor performance / space exhaustion
16.September 14, 2010
Dan Grossman: The TM/GC Analogy
16
GC Basics
Automate deallocation via reachability approximation
Approximation can be terrible in theory
Reachability via tracing or reference-counting
Duals [Bacon et al OOPSLA04]
Lots of bit-level tricks for simple ideas
And high-level ideas like a nursery for new objects
roots
heap objects
17.September 14, 2010
Dan Grossman: The TM/GC Analogy
17
A few GC issues
Weak pointers
Let programmers overcome reachability approximation
Accurate vs. conservative
Conservative can be unusable (only) in theory
Real-time guarantees for responsiveness
18.September 14, 2010
Dan Grossman: The TM/GC Analogy
18
GC Bottom-line
Established technology with widely accepted benefits
Even though it can perform terribly in theory
Even though you cannot always ignore how GC works
(at a high-level)
Even though an active research area after 50 years
19.September 14, 2010
Dan Grossman: The TM/GC Analogy
19
Concurrency
Restrict attention to explicit threads communicating via
shared memory
Synchronization mechanisms coordinate access to shared memory
Bad synchronization can lead to races or a lack of parallelism (even deadlock)
20.September 14, 2010
Dan Grossman: The TM/GC Analogy
20
Atomic
An easier-to-use and harder-to-implement primitive
lock acquire/release
(behave as if)
no interleaved computation;
no unfair starvation
void deposit(int x){
synchronized(this){
int tmp = balance;
tmp += x;
balance = tmp;
}
}
void deposit(int x){
atomic{
int tmp = balance;
tmp += x;
balance = tmp;
}
}
21.September 14, 2010
Dan Grossman: The TM/GC Analogy
21
TM basics
atomic (or related constructs) implemented via transactional memory
Preserve parallelism as long as no memory conflicts
Can lead to unnecessary loss of parallelism
If conflict detected, abort and retry
Lots of complicated details
All updates must appear to happen at once
22.September 14, 2010
Dan Grossman: The TM/GC Analogy
22
A few TM issues
Open nesting:
atomic { … open { s; } … }
Granularity (potential false conflicts)
atomic{… x.f++; …} atomic{… x.g++; … }
Update-on-commit vs. update-in-place
Obstruction-freedom
…
23.September 14, 2010
Dan Grossman: The TM/GC Analogy
23
Advantages
So atomic “sure feels better than locks”
But the crisp reasons I’ve seen are all (great) examples
Personal favorite from Flanagan et al
Same issue as Java’s StringBuffer.append
(see essay for close 2nds)
29.September 14, 2010
Dan Grossman: The TM/GC Analogy
29
Code evolution
void deposit(…) { atomic { … }}
void withdraw(…) { atomic { … }}
int balance(…) { atomic { … }}
void transfer(Acct from, int amt) {
//race
if(from.balance()>=amt && amt < maxXfer) {
from.withdraw(amt);
this.deposit(amt);
}
}
30.September 14, 2010
Dan Grossman: The TM/GC Analogy
30
Code evolution
void deposit(…) { atomic { … }}
void withdraw(…) { atomic { … }}
int balance(…) { atomic { … }}
void transfer(Acct from, int amt) {
atomic {
//correct and parallelism-preserving!
if(from.balance()>=amt && amt < maxXfer){
from.withdraw(amt);
this.deposit(amt);
}
}
}
31.September 14, 2010
Dan Grossman: The TM/GC Analogy
31
But can we generalize
So TM sure looks appealing…
But what is the essence of the benefit?
You know my answer…
32.September 14, 2010
Dan Grossman: The TM/GC Analogy
32
Outline
“TM is to shared-memory concurrency as
GC is to memory management”
Why an analogy helps
Brief separate overview of GC and TM
The core technical analogy (but read the essay)
And why concurrency is still harder
Provocative questions based on the analogy
33.September 14, 2010
Dan Grossman: The TM/GC Analogy
33
The problem, part 1
Why memory management is hard:
Balance correctness (avoid dangling pointers)
And performance (no space waste or exhaustion)
Manual approaches require whole-program protocols
Example: Manual reference count for each object
Must avoid garbage cycles
race conditions
concurrent programming
loss of parallelism
deadlock
lock
lock acquisition
34.September 14, 2010
Dan Grossman: The TM/GC Analogy
34
The problem, part 2
Manual memory-management is non-modular:
Caller and callee must know what each other access or deallocate to ensure right memory is live
A small change can require wide-scale changes to code
Correctness requires knowing what data subsequent computation will access
synchronization
locks are held
release
concurrent
35.September 14, 2010
Dan Grossman: The TM/GC Analogy
35
The solution
Move whole-program protocol to language implementation
One-size-fits-most implemented by experts
Usually combination of compiler and run-time
GC system uses subtle invariants, e.g.:
Object header-word bits
No unknown mature pointers to nursery objects
In theory, object relocation can improve performance by increasing spatial locality
In practice, some performance loss worth convenience
thread-shared
thread-local
TM
optimistic concurrency
parallelism
36.September 14, 2010
Dan Grossman: The TM/GC Analogy
36
Two basic approaches
Tracing: assume all data is live, detect garbage later
Reference-counting: can detect garbage immediately
Often defer some counting to trade immediacy for performance (e.g., trace the stack)
update-on-commit
conflict-free
conflicts
update-in-place
conflicts
conflict-detection
optimistic reads
37.September 14, 2010
Dan Grossman: The TM/GC Analogy
37
So far…
38.September 14, 2010
Dan Grossman: The TM/GC Analogy
38
Incomplete solution
GC a bad idea when “reachable” is a bad approximation of “cannot-be-deallocated”
Weak pointers overcome this fundamental limitation
Best used by experts for well-recognized idioms (e.g., software caches)
In extreme, programmers can encode
manual memory management on top of GC
Destroys most of GC’s advantages…
39.September 14, 2010
Dan Grossman: The TM/GC Analogy
39
Circumventing GC
class Allocator {
private SomeObjectType[] buf = …;
private boolean[] avail = …;
Allocator() {
/* initialize arrays */
}
SomeObjectType malloc() {
/* find available index */
}
void free(SomeObjectType o) {
/* set corresponding index available */
}
}
40.September 14, 2010
Dan Grossman: The TM/GC Analogy
40
Incomplete solution
GC a bad idea when “reachable” is a bad approximation of “cannot-be-deallocated”
Weak pointers overcome this fundamental limitation
Best used by experts for well-recognized idioms (e.g., software caches)
In extreme, programmers can encode
manual memory management on top of GC
Destroys most of GC’s advantages…
TM
memory conflict
run-in-parallel
Open nested txns
unique id generation
locking
TM
TM
41.September 14, 2010
Dan Grossman: The TM/GC Analogy
41
Circumventing GC
class SpinLock {
private boolean b = false;
void acquire() {
while(true)
atomic {
if(b) continue;
b = true;
return;
}
}
void release() {
atomic { b = false; }
}
}
TM
42.September 14, 2010
Dan Grossman: The TM/GC Analogy
42
Programmer control
For performance and simplicity, GC treats entire objects as reachable, which can lead to more space
Space-conscious programmers can reorganize data accordingly
But with conservative collection, programmers cannot completely control what appears reachable
Arbitrarily bad in theory
(some) TM
accessed
less parallelism
Parallelism
coarser granularity (e.g., cache lines)
conflicting
43.September 14, 2010
Dan Grossman: The TM/GC Analogy
43
So far…
44.September 14, 2010
Dan Grossman: The TM/GC Analogy
44
More
I/O: output after input of pointers can cause incorrect behavior due to dangling pointers
Real-time guarantees doable but costly
Static analysis can avoid overhead
Example: liveness analysis for fewer root locations
Example: remove write-barriers on nursery data
Obstruction-freedom
thread-local
escape
potential conflicts
irreversible actions
in transactions
45.September 14, 2010
Dan Grossman: The TM/GC Analogy
45
One more
Finalization allows arbitrary code to run when an object successfully gets collected
But bizarre semantic rules result since a finalizer could cause the object to become reachable
A commit handler
transaction
commits
commit handler
transaction to have memory conflicts
46.September 14, 2010
Dan Grossman: The TM/GC Analogy
46
Too much coincidence!
47.September 14, 2010
Dan Grossman: The TM/GC Analogy
47
Outline
“TM is to shared-memory concurrency as
GC is to memory management”
Why an analogy helps
Brief separate overview of GC and TM
The core technical analogy (but read the essay)
And why concurrency is still harder
Provocative questions based on the analogy
48.September 14, 2010
Dan Grossman: The TM/GC Analogy
48
Concurrency is hard!
I never said the analogy means
TM concurrent programming is as easy as
GC sequential programming
By moving low-level protocols to the language run-time, TM lets programmers just declare where critical sections should be
But that is still very hard and – by definition – unnecessary in sequential programming
Huge step forward = panacea
/
49.September 14, 2010
Dan Grossman: The TM/GC Analogy
49
Stirring things up
I can defend the technical analogy on solid ground
Then push things (perhaps) too far …
Many used to think GC was too slow without hardware
Many used to think GC was “about to take over” (decades before it did)
Many used to think we needed a “back door” for when GC was too approximate
GC was invented in 1960 and went mainstream in the mid-1990s
50.September 14, 2010
Dan Grossman: The TM/GC Analogy
50
Next steps?
Push the analogy further or discredit it
Generational GC?
Contention management?
Inspire and guide new language design and implementation
Teach programming with TM as we teach programming with GC
First?
Understand that TM solves some problems for some multithreading patterns: It doesn’t have to be all things for all people
Find other useful analogies
51.Thank you
www.cs.washington.edu/homes/djg
Full essay in OOPSLA 2007
September 14, 2010
Dan Grossman: The TM/GC Analogy
51