GCList: Garbage Collection in Concurrent Sets

MARBANIANG, Jonathan and Peri, Sathya (2018) GCList: Garbage Collection in Concurrent Sets. Masters thesis, Indian Institute of Technology Hyderabad.

Thesis_Mtech_CS_4146.pdf - Submitted Version

Download (2MB) | Preview


Garbage Collection in concurrent data structures, especially lock-free ones, pose multiple design and consistency challenges. In this instance, we consider the case of concurrent sets. A set is a collection of elements, where the elements are ordered and distinct. These two invariants are always maintained at every point in time. Sets are usually represented as a linked list of nodes, with each node denoting an element in the Set. Operations on the set include adding elements to the set, removing elements from it and searching for elements in it. Currently, multiple implementations of concurrent sets already exist. LazyList[1], Hand-over-hand List[2] and Harris’ List[3] are some of the well-known implementations. However none of these implementations employ, or are concerned with garbage collection of deleted nodes. Instead each implementation ignores deleted nodes or depends on the language’s garbage collector to handle them. Additionally, Garbage collection in concurrent lists, that use optimistic traversals or that are lock-free, is not trivial. For example, in Lazy List and Harris’ List, they allow a thread to traverse a node or a sequence of nodes after these nodes have already been removed from the list, and hence possibly deleted. If deleted nodes are to be reused, this will potentially lead to the ABA problem.[4] Moreover, some languages like C++ do not have an in-built garbage collector. Some constructs like Shared Pointers[5] provide a limited garbage collection facility, but it degrades performance by a large scale. Integrating Shared Pointers into a concurrent code is also not a trivial task. In this thesis, we propose a new representation of a concurrent set, GCList, which employs in-built garbage collection. We propose a novel garbage collection scheme that implements in-built memory reclamation whereby it reuses deleted nodes from the list. We propose both lock-based and lock-free implementations of GCList. The garbage collection scheme works in parallel with the Set operations. In our experiments with varying workloads and randomised Set operations, GCList shows comparable performance to LazyList[1] & Harris’ List[3] while outperforming Shared Pointers[5], Hazard Pointers[6] and Hand-over-hand List[2]. GCList also consumed 3-4 times less memory as compared to LazyList[1] and Harris’ List[3] and is comparable to Shared Pointers[5] and Hazard Pointers[6].

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Thesis (Masters)
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 03 Jul 2018 10:35
Last Modified: 31 Jul 2019 09:35
URI: http://raiith.iith.ac.in/id/eprint/4146
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4146 Statistics for this ePrint Item