Practical concurrent unrolled linked lists using lazy synchronization
| Autor: | Subbarayan Venkatesan, Neeraj Mittal, Kenneth Platz |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Theoretical computer science
Computer Networks and Communications Unrolled linked list Concurrent data structure Computer science 020206 networking & telecommunications 02 engineering and technology Linked list Data structure Theoretical Computer Science Artificial Intelligence Hardware and Architecture Synchronization (computer science) Node (computer science) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Software |
| Zdroj: | Journal of Parallel and Distributed Computing. 139:110-134 |
| ISSN: | 0743-7315 |
| DOI: | 10.1016/j.jpdc.2019.11.005 |
| Popis: | Linked lists and other list-based sets are some of the most ubiquitous data structures in computer science. They are useful in their own right and are frequently used as building blocks in other data structures. A linked list can be “unrolled” to combine multiple keys in each node; this improves storage density and overall performance. This organization also allows an operation to skip over nodes which cannot contain a key of interest. This work introduces a new high-performance concurrent unrolled linked list with a lazy synchronization strategy. Most write operations under this strategy can complete by locking a single node. Experiments show up to 300% improvement over other concurrent list-based sets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect