Download

The Transactional Memory Garbage Collection Analogy

Upload
0
Embed
Share
Upload and view presentations on any device and embed the player to your website! --- > >
Upload PPT
Upload PPT

Download this Presentation

winnie

2021-9-26 published at Business&Finance category

Presentation Transcript

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
10.September 14, 2010 Dan Grossman: The TM/GC Analogy 10 Interbag connections 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)
24.September 14, 2010 Dan Grossman: The TM/GC Analogy 24 Code evolution void deposit(…) { synchronized(this) { … }} void withdraw(…) { synchronized(this) { … }} int balance(…) { synchronized(this) { … }}
25.September 14, 2010 Dan Grossman: The TM/GC Analogy 25 Code evolution void deposit(…) { synchronized(this) { … }} void withdraw(…) { synchronized(this) { … }} int balance(…) { synchronized(this) { … }} void transfer(Acct from, int amt) { if(from.balance()>=amt && amt < maxXfer) { from.withdraw(amt); this.deposit(amt); } }
26.September 14, 2010 Dan Grossman: The TM/GC Analogy 26 Code evolution void deposit(…) { synchronized(this) { … }} void withdraw(…) { synchronized(this) { … }} int balance(…) { synchronized(this) { … }} void transfer(Acct from, int amt) { synchronized(this) { //race if(from.balance()>=amt && amt < maxXfer) { from.withdraw(amt); this.deposit(amt); } } }
27.September 14, 2010 Dan Grossman: The TM/GC Analogy 27 Code evolution void deposit(…) { synchronized(this) { … }} void withdraw(…) { synchronized(this) { … }} int balance(…) { synchronized(this) { … }} void transfer(Acct from, int amt) { synchronized(this) { synchronized(from) { //deadlock (still) if(from.balance()>=amt && amt < maxXfer) { from.withdraw(amt); this.deposit(amt); } }} }
28.September 14, 2010 Dan Grossman: The TM/GC Analogy 28 Code evolution void deposit(…) { atomic { … }} void withdraw(…) { atomic { … }} int balance(…) { atomic { … }}
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

Latest Release