Abstract | ||
---|---|---|
Purely functional data structures stored inside a mutable variable provide an excellent concurrent data structure—obviously correct, cheap to create, and supporting snapshots. They are not, however, scalable. We provide a way to retain the benefits of these pure-in-a-box data structures while dynamically converting to a more scalable lock-free data structure under contention. Our solution scales to any pair of pure and lock-free container types with key/value set semantics, while retaining lock-freedom. We demonstrate the principle in action on two very different platforms: first in the Glasgow Haskell Compiler and second in Java. To this end we extend GHC to support lock-free data structures and introduce a new approach for safe CAS in a lazy language. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1145/2784731.2784734 | International Conf on Function Programming |
Keywords | Field | DocType |
Concurrent data structures,Lock-free algorithms | Data structure,Programming language,Non-blocking algorithm,Computer science,Compiler,Haskell,Concurrent data structure,Java,Semantics,Scalability | Conference |
Volume | Issue | ISSN |
50 | 9 | 0362-1340 |
Citations | PageRank | References |
4 | 0.43 | 12 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ryan Newton | 1 | 802 | 70.80 |
Peter P. Fogg | 2 | 4 | 0.43 |
Ali Varamesh | 3 | 4 | 0.43 |