Search: id:"swepub:oai:DiVA.org:uu-351559" >
A contention adapti...
A contention adapting approach to concurrent ordered sets
-
- Sagonas, Konstantinos (author)
- Uppsala universitet,Datalogi,Natl Tech Univ Athens, Sch Elect & Comp Engn, Athens, Greece.
-
- Winblad, Kjell (author)
- Uppsala universitet,Datalogi
-
(creator_code:org_t)
- ACADEMIC PRESS INC ELSEVIER SCIENCE, 2018
- 2018
- English.
-
In: Journal of Parallel and Distributed Computing. - : ACADEMIC PRESS INC ELSEVIER SCIENCE. - 0743-7315 .- 1096-0848. ; 115, s. 1-19
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- With multicores being ubiquitous, concurrent data structures are increasingly important. This article proposes a novel approach to concurrent data structure design where the data structure dynamically adapts its synchronization granularity based on the detected contention and the amount of data that operations are accessing. This approach not only has the potential to reduce overheads associated with synchronization in uncontended scenarios, but can also be beneficial when the amount of data that operations are accessing atomically is unknown. Using this adaptive approach we create a contention adapting search tree (CA tree) that can be used to implement concurrent ordered sets and maps with support for range queries and bulk operations. We provide detailed proof sketches for the linearizability as well as deadlock and livelock freedom of CA tree operations. We experimentally compare CA trees to state-of-the-art concurrent data structures and show that CA trees beat the best of the data structures that we compare against by over 50% in scenarios that contain basic set operations and range queries, outperform them by more than 1200% in scenarios that also contain range updates, and offer performance and scalability that is better than many of them on workloads that only contain basic set operations.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Concurrent data structures
- Ordered sets
- Linearizability
- Range queries
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database