Name
Abstract | ||
|---|---|---|
Concurrent collection classes are widely used in multi-threaded programming, but they provide atomicity only for a fixed set of operations. Software transactional memory (STM) provides a convenient and powerful programming model for composing atomic operations, but concurrent collection algorithms that allow their operations to be composed using STM are significantly slower than their non-composable alternatives. We introduce transactional predication, a method for building transactional maps and sets on top of an underlying non-composable concurrent map. We factor the work of most collection operations into two parts: a portion that does not need atomicity or isolation, and a single transactional memory access. The result approximates semantic conflict detection using the STM's structural conflict detection mechanism. The separation also allows extra optimizations when the collection is used outside a transaction. We perform an experimental evaluation that shows that predication has better performance than existing transactional collection algorithms across a range of workloads. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1835698.1835703 | PODC |
Keywords | Field | DocType |
transactional predication,single transactional memory access,high-performance concurrent set,software transactional memory,collection operation,transactional collection algorithm,concurrent collection class,underlying non-composable concurrent map,concurrent collection algorithm,multi-threaded programming,transactional map,transactional memory,programming model | Atomicity,Commitment ordering,Software transactional memory,Programming paradigm,Computer science,Parallel computing,Double compare-and-swap,Transactional memory,Database transaction,Transactional leadership,Distributed computing | Conference |
Citations | PageRank | References |
24 | 0.90 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nathan G. Bronson | 1 | 24 | 0.90 |
| Jared Casper | 2 | 824 | 34.12 |
| Hassan Chafi | 3 | 1118 | 61.11 |
| Kunle Olukotun | 4 | 4532 | 373.50 |