7.1.2.3 Hashed Double-Ended Queue

One of the simplest and most effective ways to deterministically partition a data structure is to hash it. It is possible to trivially hash a double-ended queue by assigning each element a sequence number based on its position in the list, so that the first element left-enqueued into an empty queue is numbered zero and the first element right-enqueued into an empty queue is numbered one. A series of elements left-enqueued into an otherwise-idle queue would be assigned decreasing numbers (-1, -2, -3, ...), while a series of elements right-enqueued into an otherwise-idle queue would be assigned increasing numbers (2, 3, 4, ...). A key point is that it is not necessary to actually represent a given element's number, as this number will be implied by its position in the queue.

Figure: Hashed Double-Ended Queue
\resizebox{3in}{!}{\includegraphics{SMPdesign/lockdeqhash}}

Given this approach, we assign one lock to guard the left-hand index, one to guard the right-hand index, and one lock for each hash chain. Figure [*] shows the resulting data structure given four hash chains. Note that the lock domains do not overlap, and that deadlock is avoided by acquiring the index locks before the chain locks, and by never acquiring more than one lock of each type (index or chain) at a time.

Figure: Hashed Double-Ended Queue After Insertions
\resizebox{3in}{!}{\includegraphics{SMPdesign/lockdeqhash1R}}

Each hash chain is itself a double-ended queue, and in this example, each holds every fourth element. The uppermost portion of Figure [*] shows the state after a single element (``R1'') has been right-enqueued, with the right-hand index having been incremented to reference hash chain 2. The middle portion of this same figure shows the state after three more elements have been right-enqueued. As you can see, the indexes are back to their initial states, however, each hash chain is now non-empty. The lower portion of this figure shows the state after three additional elements have been left-enqueued and an additional element has been right-enqueued.

From the last state shown in Figure [*], a left-dequeue operation would return element ``L-2'' and left the left-hand index referencing hash chain 2, which would then contain only a single element (``R2''). In this state, a left-enqueue running concurrently with a right-enqueue would result in lock contention, but the probability of such contention can be arbitrarily reduced by using a larger hash table.

Figure: Hashed Double-Ended Queue With 12 Elements
\resizebox{1.5in}{!}{\includegraphics{SMPdesign/lockdeqhashlots}}

Figure [*] shows how 12 elements would be organized in a four-hash-bucket parallel double-ended queue. Each underlying single-lock double-ended queue holds a one-quarter slice of the full parallel double-ended queue.

Figure: Lock-Based Parallel Double-Ended Queue Data Structure
\begin{figure}{ \scriptsize
\begin{verbatim}1 struct pdeq {
2 spinlock_t llo...
...
5 int ridx;
6 struct deq bkt[DEQ_N_BKTS];
7 };\end{verbatim}
}\end{figure}

Figure [*] shows the corresponding C-language data structure, assuming an existing struct deq that provides a trivially locked double-ended-queue implementation. This data structure contains the left-hand lock on line 2, the left-hand index on line 3, the right-hand lock on line 4, the right-hand index on line 5, and, finally, the hashed array of simple lock-based double-ended queues on line 6. A high-performance implementation would of course use padding or special alignment directives to avoid false sharing.

Figure: Lock-Based Parallel Double-Ended Queue Implementation
\begin{figure}{ \scriptsize
\begin{verbatim}1 struct element *pdeq_dequeue_l(...
...eright(d->lidx);
48 spin_unlock(&d->rlock);
49 }\end{verbatim}
}\end{figure}

Figure [*] shows the implementation of the enqueue and dequeue functions.7.1Discussion will focus on the left-hand operations, as the right-hand operations are trivially derived from them.

Lines 1-13 show pdeq_dequeue_l(), which left-dequeues and returns an element if possible, returning NULL otherwise. Line 6 acquires the left-hand spinlock, and line 7 computes the index to be dequeued from. Line 8 dequeues the element, and, if line 9 finds the result to be non-NULL, line 10 records the new left-hand index. Either way, line 11 releases the lock, and, finally, line 12 returns the element if there was one, or NULL otherwise.

Lines 15-24 shows pdeq_enqueue_l(), which left-enqueues the specified element. Line 19 acquires the left-hand lock, and line 20 picks up the left-hand index. Line 21 left-enqueues the specified element onto the double-ended queue indexed by the left-hand index. Line 22 updates the left-hand index, and finally line 23 releases the lock.

As noted earlier, the right-hand operations are completely analogous to their left-handed counterparts.

Quick Quiz 7.4: Is the hashed double-ended queue a good solution? Why or why not? End Quick Quiz

Paul E. McKenney 2011-12-16