DOC PREVIEW
UCF COT 4810 - Split-Ordered Lists

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Split-Ordered Lists: Lock-Free Extensible Hash TablesORI SHALEVTel-Aviv University, Tel-Aviv, IsraelANDNIR SHAVITTel-Aviv University and Sun Microsystems Laboratories, Tel-Aviv, IsraelAbstract. We present the first lock-free implementation of an extensible hash table running on currentarchitectures. Our algorithm provides concurrent insert, delete, and find operations with an expectedO(1) cost. It consists of very simple code, easily implementable using only load, store, and compare-and-swap operations. The new mathematical structure at the core of our algorithm is recursive split-ordering, a way of ordering elements in a linked list so that they can be repeatedly “split” using asingle compare-and-swap operation. Metaphorically speaking, our algorithm differs from prior knownalgorithms in that extensibility is derived by “moving the buckets among the items” rather than “theitems among the buckets.” Though lock-free algorithms are expected to work best in multiprogrammedenvironments, empirical tests we conducted on a large shared memory multiprocessor show that eveninnon-multiprogrammed environments, the new algorithm performs as well as the most efficient knownlock-based resizable hash-table algorithm, and in high load cases it significantly outperforms it.Categories and Subject Descriptors: D.1.3 [Programming Techniques]: Concurrent Programming—Parallel programming; D.4.1 [Operating Systems]: Process Management—Synchronization; con-currency; multiprocessing/multiprogramming/multitasking; E.2 [Data Storage Representation]—Hash-table representationsGeneral Terms: Algorithms, Theory, Performance, ExperimentationAdditional Key Words and Phrases: Concurrent data structures, hash table, non-blocking synchro-nization, compare-and-swapThis work was performed while N. Shavit was at Tel-Aviv University, supported by a CollaborativeResearch Grant from Sun Microsystems.A preliminary version of this article appeared in Proceedings of the 22nd Annual ACM Symposiumon Principles of Distributed Computing (Boston, MA), ACM, New York, 2003, pp. 102–111.Copyright is held by Sun Microsystems, Inc.Authors’ address: School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel 69978, e-mail:[email protected]; [email protected] to make digital or hard copies of part or all of this work for personal or classroom use isgranted without fee provided that copies are not made or distributed for profit or direct commercialadvantage and that copies show this notice on the first page or initial screen of a display along with thefull citation. Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistributeto lists, or to use any component of this work in other works requires prior specific permission and/ora fee. Permissions may be requested from Publications Dept., ACM, Inc., 1515 Broadway, New York,NY 10036 USA, fax: +1 (212) 869-0481, or [email protected]2006 ACM 0004-5411/06/0500-0379 $5.00Journal of the ACM, Vol. 53, No. 3, May 2006, pp. 379–405.380 O. SHALEV AND N. SHAVIT1. IntroductionHash tables, and specifically extensible hash tables, serve as a key building block ofmany high performance systems. A typical extensible hash table is a continuouslyresized array of buckets, each holding an expected constant number of elements,and thus requiring an expected constant time for insert, delete and find operations[Cormen et al. 2001]. The cost of resizing, the redistribution of items between oldand new buckets, is amortized over all table operations, thus keeping the averagecomplexity of any one operation constant. As this is an extensible hash table,“resizing” means extending the table. It is interesting to note, as argued elsewhere[Hsu and Yang 1986; Lea (e-mail communication 2005)], that many of the standardconcurrent applications using hash tables require tables to only increase in size.”We are concerned in implementing the hash table data structure on multiprocessormachines, where efficient synchronization of concurrent access to data structuresis essential. Lock-free algorithms have been proposed in the past as an appeal-ing alternative to lock-based schemes, as they utilize strong primitives such asCAS (compare-and-swap) to achieve fine grained synchronization. However, lock-free algorithms typically require greater design efforts, being conceptually morecomplex.This article presents the first lock-free extensible hash table that works on currentarchitectures, that is, uses only loads, stores and CAS (or LL/SC [Moir 1997])operations. In a manner similar to sequential linear hashing [Litwin 1980] and fittingreal-time1applications, resizing costs are split incrementally to achieve expectedO(1) operations per insert, delete and find. The proposed algorithm is simple toimplement, leading us to hope it will be of interest to practitioners as well asresearchers. As we explain shortly, it is based on a novel recursively split-orderedlist structure. Our empirical testing shows that in a concurrent environment, evenwithout multiprogramming, our lock-free algorithm performs as well as the mostefficient known lock-based extensible hash-table algorithm due to Lea [2003], andin high-load cases, it significantly outperforms it.1.1. BACKGROUND. There are several lock-based concurrent hash table imple-mentations in the literature. In the early eighties, Ellis [1983, 1987] proposed anextensible concurrent hash table for distributed data based on a two level lockingscheme, first locking a table directory and then the individual buckets. Michael[2002a] has recently shown that on shared memory multiprocessors, simple algo-rithms using a reader-writer lock [Mellor-Crummey and Scott 1991] per buckethave reasonable performance for non-extensible tables. However, to resize onewould have to hold the locks on all buckets simultaneously, leading to significantoverheads. A recent algorithm by Lea [2003], proposed for java.util.concurrent,the JavaTMConcurrency Package, is probably the most efficient known concurrentextensible hash algorithm. It is based on a more sophisticated locking scheme thatinvolves a small number of high level locks rather than a lock per bucket, andallows concurrent searches while resizing the table, but not concurrent inserts ordeletes. In general, lock-based hash-table algorithms are expected to suffer fromthe typical drawbacks of


View Full Document

UCF COT 4810 - Split-Ordered Lists

Documents in this Course
Spoofing

Spoofing

25 pages

CAPTCHA

CAPTCHA

18 pages

Load more
Download Split-Ordered Lists
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Split-Ordered Lists and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Split-Ordered Lists 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?