Joel Gibson

Vincent Gramoli
email: vincent.gramoli@sydney.edu.au

Why Non-Blocking Operations Should Be Selfish

Keywords: Helping, lock-freedom, wait-freedom, point contention, process contention, interval contention, overlapping-interval contention

Non-blocking data structures are often analysed by giving an upper amortised running time bound in terms of the size of the data structure and a measure of contention. The two most commonly used measures are the point contention cP , the maximum number of processes active at any one time during an operation, and the interval contention cI , the number of operations overlapping with a given operation. In this paper, we show that when summed across every operation in an execution, the interval contention cI is within a factor of 2 of the point contention cP . Our proof relies on properties of interval graphs where at least one simplicial vertex exists, and uses it to construct a lower bound on the overall point contention. We show that this bound is tight. This result contradicts the folklore belief that point contention leads to a tighter bound on complexity in an amortised context, and provides some theoretical grounds for recent observations that using less helping in nonblocking data structures can lead to better performance. We also propose a linked list algorithm based on Fomitchev and Ruppert's algorithm but with selfish operations: read-only operations that do not help others but rather execute wait-free. The higher performance of our approach compared to the original list confirms that reducing helping can increase performance, with the same asymptotic amortised complexity.

Introduction

Non-blocking algorithms guarantee that some process completes an operation in every sufficiently long execution 3 . They are appealing because they (i) do not suffer from the preemption imposed by the scheduler, and (ii) do not require the high cost of helping needed by common wait-free algorithms to make all operations complete in a finite number of steps [START_REF] Censor-Hillel | Help! In: PODC[END_REF]. As an example, existing non-blocking data structures that make use exclusively of compare-and-swaps (CASes) for synchronisation have recently been shown to outperform other stateof-the-art data structures [START_REF] Gramoli | More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms[END_REF]. A non-blocking update typically reads a memory location, then takes steps before executing a CAS that compares the previously seen value to the current value. A difference in these values indicates an inconsistency due to a concurrent modification: the CAS fails and the steps are typically re-executed. In a lock-free algorithm the step complexity (i.e., the worst-case number of steps taken in an execution) of a single operation cannot be bounded because it can fail and retry arbitrarily many times. Instead we consider the step complexity across every operation in the execution, usually stated as the amortised cost of an operation in terms of the size of the data structure and some contention parameter c.

Two notions of contention have attracted lots of interest in the recent years [START_REF] Attiya | Algorithms adapting to point contention[END_REF][START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF][START_REF] Oshman | The SkipTrie: low-depth concurrent search without rebalancing[END_REF][START_REF] Chatterjee | Efficient lock-free binary search trees[END_REF][START_REF] Ellen | The amortized complexity of nonblocking binary search trees[END_REF]. First, the interval contention c I is the number of operations overlapping with a given operation. An amortised bound on the step complexity in terms of the interval contention is relatively easy to obtain by making operations charge each other for steps that would usually be unnecessary in a sequential execution. Provided an operation charges any other overlapping operation a constant amount and at most a constant number of times, this leads naturally to an amortised additive O(c I ) term. Unfortunately, the interval contention of an operation can be arbitrarily large in a system involving as few as two processes. Second, the point contention c P is the maximum number of processes active at any time during the operation [START_REF] Attiya | Algorithms adapting to point contention[END_REF]. An amortised bound on the step complexity in terms of point contention is usually harder to achieve, for example the proofs in [START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF][START_REF] Ellen | The amortized complexity of nonblocking binary search trees[END_REF] rely on reasoning about the relative ordering of individual CAS steps inside operations. Some authors [START_REF] Oshman | The SkipTrie: low-depth concurrent search without rebalancing[END_REF][START_REF] Chatterjee | Efficient lock-free binary search trees[END_REF] have provided modifications of their algorithms which perform extra helping so that they can tighten what would otherwise be a bound in terms of the interval contention to a bound in terms of the point contention. Since the point contention is bounded above by the maximum number of concurrent processes, it appears to be a tighter and more realistic bound than the interval contention.

In this paper, we show that when summed across every operation in an execution, c I is within a factor of 2 of c P . Our proof relies on properties of interval graphs where the point (resp. interval) contention of an operation op is the size of one of the largest cliques containing op (resp. op's degree + 1). The presence of at least one special vertex called simplicial, in any interval graph, allows us then to construct a lower bound on the overall point contention. In other words, we show that point contention and interval contention are interchangeable additive factors of the amortised complexity of concurrent algorithms. We show that this bound is tight, in the sense that given any 0 < < 1/2, there are executions in which the ratio of the overall interval contention to the overall point contention is arbitrarily close to 2 -. Finally, we also compare these contention definitions to two other definitions, the original interval contention definition [START_REF] Afek | Long lived adaptive splitter and applications[END_REF] that we call process contention, and the overlapping-interval contention [START_REF] Oshman | The SkipTrie: low-depth concurrent search without rebalancing[END_REF]. We believe our result to be important as it shows that point contention does not give a tighter amortised complexity bound than interval contention.

Our result challenges a popular belief that increasing the amount of helping done by operations can reduce the asymptotic step complexity of data structures.

For example, in [START_REF] Oshman | The SkipTrie: low-depth concurrent search without rebalancing[END_REF], the amortised complexity of a skip list operation is given as O(c I ), as an inconsistency caused by an update may be encountered by every traversal concurrent with that update, and so the update may be charged O(c I ) times. The authors argue that by making the traversals perform extra helping so as to resolve this inconsistency, the update will be charged at most O(c P ) times. So it seems that by introducing more helping into the algorithm, an additive term of O(c I ) can be reduced to O(c P ). The authors of [START_REF] Chatterjee | Efficient lock-free binary search trees[END_REF] argue similarly for their lock-free binary search tree. To illustrate how helping seemingly reduces the cost due to contention, consider the execution of an algorithm depicted in Figure 1 representing the intervals of seven operations, A, B, C, D, E, F , G, where time increases from left to right. Operation A updates shared data, as indicated by the vertical bar. Before operation A completes, other operations observe a transient inconsistent state produced by A that incurs a cost. We say that operations, whose interval overlaps A's interval, charge A for the cost of observing this inconsistency. Since the inconsistency was introduced by A, and must be resolved for A to finish, at most c I operations can charge A for this. If, however, the first operation that observes this inconsistency, namely B, helps the update by resolving it, then subsequent operations E, F , G will no longer observe this inconsistency. As long as every operation eagerly attempts to remove this inconsistency, at most c P operations can charge A for observing the inconsistency. Since c P ≤ c I for each operation, up until now it was believed to lead to a tighter bound on complexity, even in an amortised context.

By contrast, extra helping could intuitively lower the performance of a data structure, especially by forcing an operation, which would otherwise be read-only, to write. Such a behaviour was recently observed on the Harris' list-based set [START_REF] David | Asynchronized concurrency: The secret to scaling concurrent search data structures[END_REF] and led researchers to prevent read-only operations from writing: they implemented what they called an "optimised" variant of Harris' with a contains operation that traverses logically deleted nodes without physically unlinking them. The authors compared these two implementations on up to 40 hardware threads and observed that their optimised version increases performance. Former implementation variants of Harris' algorithm also suggested the appeal of a waitfree contains [START_REF] Heller | A lazy concurrent list-based set algorithm[END_REF][START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF].

In the light of our result, we designed a new non-blocking list-based set algorithm based on Fomitchev and Ruppert's [START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF], but with a wait-free contains operation which performs no writes. Their original list has amortised complexity O(n + c P ) per operation, whereas the modification is easily seen as O(n + c I ), which our result tells us is equivalent. We implemented Fomitchev and Ruppert's linked list in C. We compared the performance of our linked list against the performance of Fomitchev and Ruppert's linked list on a 64-core machine with various sizes and update ratios. The results show that our linked list is more efficient in all tested settings than Fomitchev and Ruppert's. While we do not claim that helping is always detrimental to the performance, these results confirm empirically that limiting helping can lead to better performance, at no increase of the amortised cost of an operation.

To conclude, we believe our result is not only insightful for theoreticians but also for practitioners. First, an amoritised complexity with an additive O(c I ) term is equivalent to having an O(c P ) term instead, without the burden of modifying the algorithm or complicating the analysis required to measure the point contention. Second, as modern chip multiprocessors offer more and more cores, it is likely that enough processes (or threads) accessing a concurrent data structures can proceed without being preempted by the operating system. In this case, it seems that an implementation with selfish operations, which are wait-free read-only operations that do not help other operations, could lead to higher performance, simply because (i) read-only operations would avoid writing, hence limiting cache invalidations and (ii) update operations would fix any inconsistency they introduce without being arbitrarily delayed via preemption. Our result gives theoretical grounds to support favouring selfish operations over helpful operations when all that distinguishes them is an additive O(c P ) or O(c I ) term.

In Section 2 we define existing contention measures and explain how to reason about them in terms of interval graphs. In Section 3, we show that in any finite execution the overall point contention cannot be twice as large as the point contention and that this bound is tight, and briefly show related results for the process contention and the overlapping-interval contention. In Section 4 we show empirically that replacing a helpful contains operation by a selfish one increases the performance of Fomitchev and Ruppert's linked list. We list directions to explore new contention metrics in Section 5. We present the related work in Section 6 and we conclude in Section 7.

Let a finite execution α involving P processes be a finite set O of operations with two mappings I and π. I : O → R×R maps operations to compact real intervals, and π : O → {1, . . . , P } maps operations to the processes that executed them. If for two operations op, op ∈ O we have I(op) ∩ I(op ) = ∅, we say that op and op overlap. Furthermore, I should be injective 4 , and the execution should be well-formed : any two operations mapping to the same process should not overlap. Figure 2 shows an example of a finite execution.

c P (op) = max x∈I(op) |S x | c I (op) = |S| c K (op) = |π(S)| c OI (op) = max op ∈S c I (op )
By these characterisations we find c OI (op) ≥ c I (op) because op ∈ S, and c I (op) ≥ c K (op) because a set is at least as large as its image under a map. Note that since the execution is well-formed, |S x | = |π(S x )|, and since we have S x ⊆ S for all x ∈ I, it follows that c P (op) ≤ c K (op). Finally, all of these bounds are tight by considering an execution containing one operation and one process.

All that is needed to calculate c I and c OI is information about which pairs of operations overlap. In fact, this is the case for c P as well. Hence a natural setting to analyse these measures of contention is an interval graph, which retains the information of which operations overlap, while hiding the complications of processes and exact points in time. First we introduce some terminology.

Any graphs G = (V, E) considered here are finite, undirected, and without multiple edges or loops. V denotes the vertex set and E denotes the edge set. For any vertex subset

U ⊆ V , G[U ] = (U, E ∩ (U × U )) is called the subgraph induced by U . A vertex subset U ⊆ V forms a clique if the subgraph G[U ] is complete. For any vertex v, its neighbourhood N (v) consists of all vertices incident to v. A vertex v is called simplicial if the subgraph induced by its neighbours and itself G[{v} ∪ N (v)] is complete. Definition 2.
The interval graph of a finite set of real intervals S is the graph with vertex set S, with an edge between two intervals I, J ∈ S if I = J and I ∩ J = ∅. Definition 3. A perfect elimination order is an ordering {v i } n i=1 of vertices in a graph such that for all

1 ≤ i ≤ n, v i is simplicial in G[v 1 , . . . , v i ].
Interval graphs belong to a larger class of graphs called chordal graphs, which are graphs in which any cycle of length 4 or more always contains a chord, an edge connecting two non-adjacent vertices of the cycle. It is a well-known fact that chordal graphs are characterised completely by the existence of a perfect elimination order. In the case of interval graphs the existence of such an order is easy to see, and so a short proof is given below. Lemma 1. Every interval graph on n vertices admits a perfect elimination order.

Proof. The case for n = 1 is clear. We proceed by induction: assume that the claim holds for interval graphs with n -1 vertices. Take the vertex v corresponding to the interval with earliest finishing time: this vertex is simplicial since the finishing time intersects every interval which overlaps v. We already have a perfect elimination order {v i } n-1 i=1 of G -v by assumption, and so setting v n = v gives a perfect elimination order {v i } n i=1 of G.

Finally, in the interval graph of an execution, the point contention of an interval is equal to the size of the largest clique containing the vertex corresponding to that interval. This can be seen by considering the mapping R → 2 O , x → {op ∈ O | x ∈ I(op)} which maps points to the operations active at that point in time: it will always map a point to an empty set, or a maximal clique. For this reason we consider the following lemma, which will allow us to put a lower bound on the overall point contention in terms of the number of vertices n and the number of edges m. Lemma 2. In an interval graph G, let M (v) be the size of a maximum clique containing the vertex v.

Then v∈V M (v) ≥ n + m.
Proof. Take a perfect elimination order {v i } n i=1 of the vertices of G, and define

G i = G[v 1 , . . . , v i ]. This gives a family of graphs G n , . . . , G 1 , such that G n = G, G 1 is a single vertex, and G j = G j+1 -v j+1 for all 1 ≤ j < n. Let d i be the degree of v i in G i . Since v i is simplicial in G i , {v i } ∪ N (v i ) forms a clique in G i
and hence also in G, so 1 + d i ≤ M (v i ). Finally, note that d i is the number of edges removed when removing v i from G i , so

n i=1 d i = m. So v∈V M (v) ≥ n i=1 (1 + d i ) = n + m.

Equivalence of amortised measures of contention

For any finite execution α, let c P (α) = op∈O c P (op), and likewise for the other measures of contention.

Theorem 1. In any finite execution α, c P (α) ≤ c I (α) < 2c P (α).

Proof. Form the interval graph using the intervals I(op) for each op ∈ α. By the definitions of contention given in Section 2, we can see that the interval contention of a single operation op is c I (op) = 1 + deg op, where deg denotes the degree of the operation's interval in the interval graph. Summing across all operations, c I (α) = n+2m, where n is the number of vertices and m the number of edges in the interval graph. As discussed previously, the point contention c P (op) is the size of the largest clique containing op in the interval graph. So by Lemma 2 we have n + m ≤ c P (α).

Putting these together with the inequality in Proposition 1, we find that

n + m ≤ c P (α) ≤ c I (α) ≤ n + 2m
and so by taking the ratio of c I (α) to c P (α),

1 ≤ c I (α) c P (α) ≤ n + 2m n + m = 1 + m n + m < 2
Although this fact alone tells us that in amortised terms, c P = Θ(c I ) and so the point contention and interval contention are equivalent, it is interesting to examine what a "worst-case" execution is. Intuitively, we want to keep the point contention small, while making intervals overlap as many times as possible. Such a construction is given in the proof of Theorem 2 and illustrated in Figure 4, and shows that the bound given above is tight.

Theorem 2. For any 0 < < 1/2, there exists a family of executions {α n } n≥1 where each α n has n operations and n processes, such that

lim n→∞ c I (α n ) c P (α n ) = 2 -.
Proof. Let α n be an execution containing n operations labelled op i for 0 ≤ i < n, and let 1 ≤ k ≤ n/2. We define the mappings π(op i ) = i (mod k) and

I(op i ) = [i, i + k -1 2 ] for all 0 ≤ i < n.
It is easy to check that at the start or end point of each operation there are k operations active at that point in time and so c P (op) ≥ k for all operations. Since there are only k processes, c P (op) = k for all operations, so c P (α n ) = nk.

By the length and placement of operations, for every operation op the set of operations intersecting its left endpoint is disjoint to the set of operations intersecting its right endpoint, and the union of these is every operation concurrent with op. Hence every operation but the first k -1 and the last k -1 operations have interval contention 2k -1. The first operation has interval contention k, the next k + 1, and so on until the kth operation has interval contention 2k -1, and similarly for the last k operations. By overcounting the interval contention overall and subtracting off the start and end defecits, we find that c I (α n ) = n(2k -1) -2(0 + 1 + . . . + (k -1)) = 2nk -n -k(k -1). Letting k = n and taking the ratio of interval to point contention, we get Finally, Theorem 1 and Proposition 1 give the chain of inequalities c P (α) ≤ c K (α) ≤ c I (α) < 2c P (α) and so the process contention is also amortised equivalent to the point contention. The overlapping-interval contention, on the other hand, cannot be bounded within a constant factor of the point contention. Consider an execution of two processes, where the first process has one long-running operation, and the second process runs n -1 short operations, all of which execute inside the interval of the long-running operation. In this execution α, we have c P (op) = 2 and c OI (op) = n for every operation, so c P (α) = 2n and c OI (α) = n 2 .

c I (α n )/c P (α n ) = 2 --1- n .

Evaluation of the Selfish linked list

A key application of Theorem 1 is that algorithms which had very strict helping requirements in order to attain a O(c P ) amortised additive complexity term may be able to be modified to have weaker helping requirements, without any change in asymptotic complexity. It has been observed in practice [START_REF] David | Asynchronized concurrency: The secret to scaling concurrent search data structures[END_REF] that having waitfree read-only operations on concurrent data structures often gives an increase in performance, regardless of asymptotic complexity. Here we modify an existing non-blocking linked-list algorithm by Fomitchev and Ruppert [START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF] to have a waitfree contains operation and show that the resulting algorithm, namely the Selfish linked list, gives better performance.

The Selfish linked list algorithm

First, we recall Fomitchev and Ruppert's construction of the list. Each node stores three fields: a key field, indicating the value represented by that node in the set, a backlink field, used when traversal is interrupted by a concurrent modification, and a successor field. The successor field stores a right pointer to the next node in the list and two booleans flag and mark. The list contains two dummy head and tail nodes, with keys -∞ and ∞ respectively.

When a node is to be deleted, its predecessor's flag bit is set, indicating that the predecessor's successor field may not be modified until the node has been removed. Following this, the node's mark bit is set, indicating its successor field may not be modified from now on, and the node's backlink field is set to point to the predecessor. Finally, the predecessor's successor field is modified to remove the flag bit and swing the right pointer over the node being deleted.

Every operation in the algorithm performs eager helping: as soon as a traversal encounters a node with a mark set, it attempts to help remove that node from the list. Removes and inserts which encounter nodes with flag bits set must help the concurrent remove operation to physically remove those nodes. In addition, any attempts to flag nodes may have to backtrack through chains of backlinks in order to reach nodes which are not logically deleted. The existence of the backlinks means that nodes do not ever have to restart from the beginning of the list and is key to an amortised O(n + c P ) time per operation.

Our modification is very similar to the modification of the Harris list presented in [START_REF] Heller | A lazy concurrent list-based set algorithm[END_REF][START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF] to replace the contains operation, which would usually attempt to help remove marked nodes from the list, with a read-only operation which makes a single pass through the list. The pseudocode of the contains operation is Algorithm 1 The wait-free Contains operation

1: procedure Contains(k) 2:
current ← head 3:

marked ← f alse 4:

while current.key < k do 5:

succ ← current.succ 6: marked ← succ.mark 7:

current ← succ.right 8:

end while 9:

return (current.key = k) ∧ (marked = f alse) 10: end procedure depicted in Algorithm 1. The operation is linearisable and wait-free, and replaces the original lock-free contains operation: all other operations of the list remain as in the original. Since the operations in the original list had an amortised complexity of O(n + c P ) and we change only the read-only operation, we conclude our new list has an amortised complexity of O(n + c I ) for each operation: in the presence of only updates, the complexity is O(n + c P ) as originally shown by Fomitchev and Ruppert, and introducing contains operations means that at most c I more is billed to each concurrent update by a contains operation that traverses a logically deleted node. We implemented both the original algorithm and our modification in C and we did not include any memory reclamation technique. Implementing a memory reclamation technique is not straightforward and can substantially impact performance [START_REF] Michael | High performance dynamic lock-free hash tables and list-based sets[END_REF].

Experimental evaluation

We performed the experiment with Synchrobench [START_REF] Gramoli | More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms[END_REF] on a 4 socket AMD Opteron 6378 2.4 GHz 16 cores (64 cores in total) machine running Fedora Linux 18. GCC 4.9.2 was used to compile the C code. The benchmarking program initialises the data structures with N elements randomly selected from {1, . . . , 2N }, and spawns from 1 to 78 threads. Each test runs for 10 seconds. Each thread chooses of the three operations contains, insert, or remove based on the update ratio. In the data shown here, the update ratio is always 10%, meaning that 10% of operations are contains operations, 45% are insert, and 45% are remove. Each datapoint shown is an average of 20 runs, and the error bars are the sample standard deviation of those runs.

As shown in Figure 5, the list with our modification has much higher throughput than the original algorithm, especially in the small case of a 128 element list, where there is a 20% throughput improvement. We conclude that limiting helping can increase performance in concurrent data structures, and our result in Theorem 1 gives a guarantee that our new O(n + c I ) algorithm is asympotically equivalent to the old O(n + c P ) algorithm. As discussed previously, there has been a view that by introducing more helping into an algorithm, the amortised step complexity can be "tightened" from an additive term of O(c I ) to O(c P ). By Theorem 1, we know these two quantities to be amortised equivalent, so clearly this cannot be distinguished by the point or interval contention. However, this does not rule out the existence of a more refined measure of contention that does separate these cases.

Q P1 P2 P3 P4 P5 Pm
Fig. 6. Suppose Q causes an inconsistency in the data structure and then gets suspended for a long time. If every operation performs eager helping, an inconsistency caused by Q will only be observed once. If no operations perform helping, it will be observed m times.

Consider an execution of one long-running process Q and m short-running processes P 1 , . . . , P m . Suppose we have a structure featuring logical deletions, and the first step in a removal is to mark a node logically deleted. The longrunning process Q marks an element as logically deleted before being suspended for a long time, while the short-running processes repeatedly access the data structure. This is illustrated in Figure 6. If the short running processes P i perform no helping to try to physically remove the node, each will spend extra time traversing a node not present in the set, and incur a constant cost. The total cost of these extra steps is Θ(m). On the other hand, if every operation eagerly tries to help finish any partially completed delete operation it comes across, the first short operation P 1 will suffer this (constant) cost, and the rest will traverse with no extra cost. So without helping, there are Θ(m) extra steps that need to be carried out, and with helping there is only O(1).

The current measures we have of contention, the point and interval contention, will not separate these cases. Some finer measure of contention is needed to capture this case and show when helping can really benefit an algorithm in an asymptotic sense. We believe that some of the theory developed here could be useful in determining and analysing a new measure of contention that separates these two cases.

Related work

For more than two decades, contention has been known to be an important complexity factor of concurrent algorithms [START_REF] Dwork | Contention in shared memory algorithms[END_REF]. This observation motivated the definitions of various contention measures: hot-spot contention [START_REF] Dwork | Contention in shared memory algorithms[END_REF], process contention (originally called interval contention) [START_REF] Afek | Long lived adaptive splitter and applications[END_REF], interval and point contentions [START_REF] Attiya | Algorithms adapting to point contention[END_REF], step contention [START_REF] Attiya | Computing with reads and writes in the absence of step contention[END_REF] and overlapping-interval contention [START_REF] Oshman | The SkipTrie: low-depth concurrent search without rebalancing[END_REF]. An overview of some of these properties was given in [START_REF] Hendler | Non-blocking algorithms[END_REF].

To diminish contention several techniques were adopted. Adaptive algorithms [START_REF] Attiya | Algorithms adapting to point contention[END_REF] were designed to implement applications that could adapt to the point contention during the execution of an operation. Contention-sensitive data structures [START_REF] Taubenfeld | Contention-sensitive data structures and algorithms[END_REF] propose to reduce the cost of lock-based data structures in the absence of contention.

A pragmatic way of reducing contention in data structures is to split operations into abstract updates and structural updates. The speculation-friendly binary search tree was the first algorithm to generalize this decoupling by both keeping logically deleted nodes and relaxing the balance constraints [START_REF] Crain | A speculation-friendly binary search tree[END_REF]. The contention-friendly binary search tree adopts the same decoupling but synchronises with locks rather than transactional memory [START_REF] Crain | A contention-friendly binary search tree[END_REF]. A non-blocking chromatic tree exploits this decoupling up to a constant number k of violations hence upper-bounding the imbalance at time t by k + c where the contention c represents the number of updates in progress at time t [START_REF] Brown | A general technique for non-blocking trees[END_REF]. Finally, this decoupling was used to implement efficient non-blocking skip lists that do not suffer traditional contention hotspots [START_REF] Crain | No hot spot non-blocking skip list[END_REF][START_REF] Dick | Logarithmic data structures for multicores[END_REF].

Many linked list algorithms have been proposed over the last two decades [START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF][START_REF] Heller | A lazy concurrent list-based set algorithm[END_REF][START_REF] Valois | Lock-free linked lists using compare-and-swap[END_REF][START_REF] Harris | A pragmatic implementation of non-blocking linked-lists[END_REF][START_REF] Gramoli | Brief announcement: A concurrency-optimal list-based set[END_REF]. Although potentially very efficient, lock-based linked lists [START_REF] Heller | A lazy concurrent list-based set algorithm[END_REF][START_REF] Gramoli | Brief announcement: A concurrency-optimal list-based set[END_REF] generally do not perform as well as non-blocking ones [START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF][START_REF] Harris | A pragmatic implementation of non-blocking linked-lists[END_REF] when the number of processes exceeds the number of available computing resources. This is typically due to the contention induced on locks. Non-blocking linked lists are thus particularly interesting. Harris' linked list [START_REF] Harris | A pragmatic implementation of non-blocking linked-lists[END_REF] is still one of the fastest [START_REF] Gramoli | More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms[END_REF] but its cost per operation can be Ω(nc P ) in some execution. Fomitchev and Ruppert provide a linked list with an amortized complexity of O(n+c P ) per operation [START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF]. Our Selfish list, of asymptotically equivalent complexity O(n + c I ), shows better performance.

Both wait-free and non-blocking properties guarantee progress regardless of the way the operating system schedules threads [START_REF] Herlihy | On the nature of progress[END_REF]. Our algorithm is nonblocking but not wait-free as it guarantees wait-freedom only of the contains operation. Recent results showed that under a stochastic scheduler, some nonblocking algorithms, also called single CAS universal, are wait-free with probability 1 [START_REF] Alistarh | Are lock-free concurrent algorithms practically wait-free?[END_REF], however, our algorithm does not fall in this category. There exist both methodologies [START_REF] Kogan | A methodology for creating fast wait-free data structures[END_REF] and simulation techniques [START_REF] Timnat | A practical wait-free simulation for lock-free data structures[END_REF] to obtain wait-freedom with a slight performance loss: one can run a lock-free fast path and start a wait-free slow path if the fast path was unsuccessful.

Conclusion

When summed across every operation in an execution, the point contention cannot be twice larger than interval contention. Our proof is interesting in its own right as it draws a natural relation between the theory of contention and the theory of interval graphs, where the point contention of an operation is its degree plus one in the graph and the interval contention is the size of one of the largest cliques the operation belongs to in the graph.

The execution α of several non-blocking data structure algorithms [START_REF] Fomitchev | Lock-free linked lists and skip lists[END_REF][START_REF] Oshman | The SkipTrie: low-depth concurrent search without rebalancing[END_REF][START_REF] Chatterjee | Efficient lock-free binary search trees[END_REF][START_REF] Ellen | The amortized complexity of nonblocking binary search trees[END_REF] is known to have an asymptotic amortised complexity with an additive contention term of either c I (α) or c P (α). Our result shows that these terms are equivalent, hence contradicting the folklore knowledge that operations should necessarily help each other to achieve a tighter complexity bound even in an amortised context.

We evaluated the performance of a non-blocking list and a new variant of it that consists of the same algorithm but with a selfish contains operation. Their complexities O(n + c P ) and O(n + c I ), respectively, are known now to be equivalent. Our results on a 64-core machine show that selfishness increases performance in all settings we tested, confirming the practical relevance of our bound.

We believe that our result will be useful to simplify the analysis of nonblocking data structures in terms of amortised complexity as deriving the complexity based on interval contention seems easier than point contention. As part of future work, we would like to analyse existing algorithms in the light of our new result.

Availability. The source code used in this paper is available in Synchrobench: https://sites.google.com/site/synchrobench.

Fig. 1 .

 1 Fig.1. It was recently noted[START_REF] Oshman | The SkipTrie: low-depth concurrent search without rebalancing[END_REF][START_REF] Chatterjee | Efficient lock-free binary search trees[END_REF] that if an update A creates a transient inconsistent state, incons, that is encountered by concurrent traversals B, C, D, E, F, G then making the other operations help another when encountering an inconsistency can reduce the interval contention O(cI ) to the point contention O(cP ) by simply resolving the inconsistency as early as the first operation, say B, encounters the inconsistency

Fig. 2 .Definition 1 .

 21 Fig. 2. An example execution involving 3 processes and 8 operations. The point contentions of A, C, D, and G are 3, while E, B, H, and F are 2. The process contention of E is 2, and of B is 3. The interval contentions of A, B, and C are 5, 4, and 3 respectively. The overlapping-interval contention of E is 5.

Fig. 3 .

 3 Fig. 3. The interval graph corresponding to the execution in Figure 2. The vertices C, D, H and F are simplicial in this graph.

Fig. 4 .

 4 Fig. 4. An example worst-case construction with n = 9 and k = 3.

Fig. 5 .

 5 Fig. 5. A comparison of Fomitchev and Ruppert's original algorithm to our modified version with a wait-free contains implementation. Both algorithms have the same asymptotic worst-case complexity. Each datapoint shown is an average of 20 runs of 10 seconds each. The vertical bars represent the sample standard deviation.

Note that non-blocking is sometimes used to refer to a larger class of progress conditions, instead we use the less general definition from[START_REF] Herlihy | Wait-free synchronization[END_REF].

This is not restrictive: any finite execution in which two intervals are identical may be perturbed slightly such that they are not, without affecting contention.

Acknowledgements. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.


Wenjia Ruan

Michael Spear
email: spear@cse.lehigh.edu

Hybrid Transactional Memory Revisited

Hybrid Transactional Memory (TM) uses available hardware TM resources to execute language-level transactions, and falls back to a software TM implementation for those transactions that cannot complete in hardware. Ideally, a hybrid TM would allow hardware and software transactions to run concurrently, but would not waste hardware TM resources on coordination between the two classes of transactions. In addition, it should scale well, incur little latency, offer strong safety guarantees, and provide some degree of fairness. We introduce a new hybrid TM algorithm, "Hybrid Cohorts", in which hardware transactions do not modify global metadata, and software transactions have extremely low per-access overhead. The tradeoff is that hardware transactions cannot commit while software transactions are in flight. Evaluation on an 8-thread Intel Haswell CPU shows competitive performance with the current state-of-the-art. Furthermore, it does so while providing acceptable levels of fairness and safety, and offering opportunities for hardware acceleration.

Introduction

Since the time when Hybrid Transactional Memory (TM) was first proposed [START_REF] Damron | Hybrid Transactional Memory[END_REF], hardware TM (HTM) support has become available in microprocessors from IBM [START_REF] Jacobi | Transactional Memory Architecture and Implementation for IBM System Z[END_REF][START_REF] Wang | Evaluation of Blue Gene/Q Hardware Support for Transactional Memories[END_REF] and Intel [START_REF]Intel Architecture Instruction Set Extensions Programming (Chapter 8: Transactional Synchronization Extensions[END_REF]. These HTM systems are "best effort", meaning that they do not guarantee that they will successfully commit any transaction attempt. Failure may arise for many reasons, to include conflicts with other transactions, memory footprints that exceed the HTM capacity, system calls, and timer interrupts. The goal of Hybrid TM (HyTM) is to exploit best-effort HTM whenever possible, and fall back to software TM (STM) when a transaction cannot complete in hardware [START_REF] Damron | Hybrid Transactional Memory[END_REF]. This approach promises to scale well and incur low latency when most transactions complete in hardware, with worst-case overhead and scalability comparable to the underlying STM.

The traditional approach to implementing HyTM is to begin with an STM, and try to accelerate it using HTM. Early STM algorithms required interaction with per-location metadata, and hybrid versions of these algorithms wasted limited hardware capacity on this metadata [START_REF] Damron | Hybrid Transactional Memory[END_REF][START_REF] Kumar | Hybrid Transactional Memory[END_REF][START_REF] Riegel | Optimizing Hybrid Transactional Memory: The Importance of Nonspeculative Operations[END_REF]. Worse yet, false sharing of cache lines that held metadata could result in additional HTM aborts, and increased fallback to the STM path. The use of NOrec STM [START_REF] Dalessandro | NOrec: Streamlining STM by Abolishing Ownership Records[END_REF] as a baseline enabled HyTM algorithms to avoid per-access overheads. In NOrec-based HyTM [START_REF] Dalessandro | Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory[END_REF][START_REF] Matveev | Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory[END_REF][START_REF] Riegel | Optimizing Hybrid Transactional Memory: The Importance of Nonspeculative Operations[END_REF], a sequence lock serializes the commit of the STM, and all conflicts are detected by comparing the values read by transactions. However, NOrec-based HyTM algorithms suffer from a scalability bottleneck, since hardware transactions must read, and often write, the sequence lock. Aborts from these accesses could be avoided if the hardware allowed nontransactional accesses [START_REF] Dalessandro | Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory[END_REF], but the accesses themselves are necessary. Furthermore, if these accesses are delayed until the end of the transaction [START_REF] Calciu | Invyswell: A Hybrid Transactional Memory for Haswell's Restricted Transactional Memory[END_REF][START_REF] Calciu | Improved Single Global Lock Fallback for Best-effort Hardware Transactional Memory[END_REF], the TM ceases to provide the minimum safety requirement of opacity [START_REF] Guerraoui | On the Correctness of Transactional Memory[END_REF], and it can admit erroneous behavior [START_REF] Dice | Pitfalls of Lazy Subscription[END_REF]. However, "eager subscription" to the metadata for coordinating hardware and software transactions causes all hardware transactions to abort on any software commit.

The most recent innovation in HyTM is to add hardware acceleration to the STM path, as in Reduced Hardware NOrec (RHNOrec) [START_REF] Matveev | Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory[END_REF]. The resulting "reduced transaction" technique transforms certain software transactions into hardware transactions, thereby avoiding fallback to a slow STM. The current state of the art achieves performance comparable to Hybrid NOrec, but does not require nontransactional loads.

A common assumption among HyTM algorithms is that STM and HTM transactions should coexist at any time, with neither favored over the other. In contrast, PhaseTM [START_REF] Lev | PhTM: Phased Transactional Memory[END_REF], required all transactions to use same mode, whether HTM, STM, or serialized on a single lock. Mode switches were expensive, but in return the HTM mode had no overhead for interacting with STM. The most popular HyTM in practice today is a PhaseTM that switches between HTM mode and a single global lock [START_REF] Yoo | Performance Evaluation of Intel Transactional Synchronization Extensions for High Performance Computing[END_REF]. If we accept that HTM capacities are more likely to increase than to decrease, then we may assume that STM fall-back will grow increasingly rare. However, as core counts rise, fall-back to a single lock becomes increasingly untenable. These observations motivate our approach. We seek to make the common case (HTM) as fast as possible, by avoiding interaction with (unlikely) concurrent software transactions. When a software transaction is needed, we want it to finish as quickly as possible, to limit its impact on current and future hardware transactions. We also require the HyTM to be opaque.

The innovation we propose is to prioritize software transactions while they are running, by augmenting the Cohorts algorithm [START_REF] Ruan | On the Platform Specificity of STM Instrumentation Mechanisms[END_REF]. In Cohorts, transactions block at their commit point, until such time as all threads are either (a) ready to commit a transaction, or (b) not executing a transaction. This allows software transactions to avoid any high-latency global metadata accesses during execution. In Hybrid Cohorts (HyCo), we prevent hardware transactions from committing when software transactions are inflight. We also apply the reduced transaction technique to the Cohorts commit phase, which prevents blocking and eliminates a bottleneck from Cohorts STM. The net effect is an opaque HyTM that scales well and avoids bottlenecks for hardware transactions.

The remainder of this paper is organized as follows. In Section 2, we discuss the overall approach of the Hybrid Cohorts algorithm, with a focus on the state machine that governs transaction behavior. Section 3 presents the pseudocode for one implementation of the state machine, which aims to limit the impact on transactions that use HTM resources throughout their execution. In Section 4, we present the results of performance experiments. Section 5 concludes and discusses future research directions.

The Hybrid Cohorts Approach

HyTM algorithms that descend from NOrec share two key properties: First, the opacity of each software transaction (STx) is preserved by requiring every hardware transac-tion (HTx) increment a global counter on hardware transaction commit; the counter is checked by every STx on every read of shared data. (Note that the increment may be elided if it can be proven that no STx exist.) Second, to prevent an HTx from observing inconsistent state, it must not perform reads or commit during the interval when an STx is committing its writes. In Hybrid NOrec, the second property was kept performant via a set of per-thread counters, or via special instrumentation on every load by an HTx. 1In RHNOrec, the overhead of second property is avoided by executing the suffix of all but the largest STx (the interval between its first write through the completion of their commit) as a hardware transaction.

HyCo takes a different approach to these challenges. First, to ensure the opacity of STx, HTx are not allowed to commit whenever any STx is between its begin and commit points. In the absence of nontransactional loads, this necessitates that HTx abort if they reach their commit point and then observe an active STx. However, it also means that HTx do not need to modify shared variables at commit time in order to notify concurrent STx of the need to validate. Second, to ensure that HTx do not observe inconsistent state, the commit-time validation and writeback of STx is first attempted as a "reduced" hardware transaction. If the reduced transaction cannot commit, the STx waits until all concurrent HTx complete, and then performs serialized writeback. Note that by also blocking STx commits when there are concurrent in-flight STx, validation by in-flight STx is no longer necessary: during any STx execution, memory is immutable. Less instrumentation is required within STx, which reduces STx execution time and should limit the impact of HTx blocking or aborting at their commit point due to concurrent STx execution.

To make the behavior of transactions in HyCo more clear, Figure 1 presents a state machine to describe the behavior of transactions. There are 6 states:

-No STx (NS): This is the default state of the system. In this state, HTx may begin, commit, and abort. -One Serial Transaction (S): Only one transaction is running, and it cannot be aborted.

This allows a transaction to perform I/O [START_REF] Spear | Implementing and Exploiting Inevitability in Software Transactional Memory[END_REF][START_REF] Welc | Irrevocable Transactions and their Applications[END_REF]. -HTx Commit: An HTx commits its changes to shared memory.

-
-HTx Abort: An HTx fails due to conflicts with other transactions.

-Serial Begin: A thread begins a serial transaction.

-Serial Commit: A serial transaction commits.

-STx Begin: A thread attempts to begin a transaction in STx mode.

-STx Commit (read-only): When an STx reaches its commit point, if it determines that it is read-only, it does not need to block in order to commit, since its commit cannot affect concurrent STx. -STx Ready to Commit: An STx reaches its commit point, and is not read-only.

-STx Abort: An STx, during its commit operation, validates and determines that it conflicts with a committed transaction. -STx HC Commit: An STx commits using a reduced hardware transaction.

-STx HC Fail: An STx cannot commit via a reduced hardware transaction (e.g.,

because it has accessed too many locations). -STx Slow Commit: An STx commits via the serialized commit protocol.

In Figure 1, the lack of a label on an arc indicates that a transaction behavior is either impossible or not allowed. For example, an HTx is not allowed to commit in the SA or CP states, and it is not possible for an STx to abort in these states. Labels marked with an asterisk( * ) are optional, and provide more opportunities for HTx to make progress. The order in which transactions are scheduled in the HC and SC modes can be governed by arbitrary contention management policies. For this discussion, we assume that the contention manager randomly chooses the order in which transactions attempt to commit in SC, and transactions attempt to commit immediately upon transition to HC.

Following Dalessandro et al. [START_REF] Dalessandro | Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory[END_REF], the underlying STM uses value-based validation. STx do not update memory directly, but instead buffer their writes in a private log, and then replay them at commit time. These decisions ensure that HTx do not observe uncommitted state during their execution, and need not check per-location metadata on each load and store. The only global metadata for HyCo is related to the state machine, and it is only accessed at transaction boundaries. This results in a constant amount of global metadata, and a constant overhead for HTx to access that metadata.

Section 3 discusses mechanisms for achieving those transitions that are not obvious. For example, the transition from NS to S can be achieved by either (a) forcibly aborting any in-flight hardware transactions, or (b) setting a flag to prevent subsequent HTx and STx from beginning, and then waiting for the system to be in the NS state with no HTx running. Our goal is to achieve each transition without causing HTx conflicts on state machine metadata. As an example, an HTx can start as long as the system is not in S or SC state, but it need not know the exact system state until it reaches its commit point. If the state changes during HTx execution (e.g., from NS to SA, or even from HC to NS), the HTx should not immediately abort. At commit time, the HTx should be able to quickly check the precise state, and then self abort if necessary (e.g., if the state is CP).

HyCo provides opacity [START_REF] Guerraoui | On the Correctness of Transactional Memory[END_REF] for STx by ensuring that when an STx is in-flight, no concurrent HTx or STx may perform an operation that modifies locations that have been, or may be, read by the in-flight STx. A concurrent STx may reach its commit point, but may not transition to the HC or SC state, and since its writes are buffered, it cannot modify memory. (Note that a read-only STx may commit during this time, but by definition it does not modify shared memory.) Thus no concurrent STx can perform an operation that changes the memory visible to the in-flight STx. Similarly, a concurrent HTx may not transition from SA to HC, where it can complete its transaction. In this case, the HTM provides write buffering for the not-yet-committed HTx.

When the underlying HTM is opaque, Dalessandro et al. established that in a lazy HyTM, an HTx transaction can only experience an opacity violation if it overlaps with an STx commit [START_REF] Dalessandro | Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory[END_REF]. Specifically, the STx might perform a partial write-back concurrent with the HTx, so that the HTx reads some of the STx's committed state, but not all of it. A sufficient condition is to prevent incomplete STx write-back from being visible to an HTx execution. In HyCo, this is achieved by (a) forbidding an STx from reaching the SC state until there are no concurrent HTx, and (b) attempting to commit STx in a reduced hardware transaction. In the HC state, the reduced transaction validates and performs write-back; consequently the STx cannot expose its partial state: the entire set of updates becomes visible when the hardware transaction commits.

HyCo supports a variety of approaches to ensuring fairness and progress. A few properties are relatively obvious: Any transaction can be guaranteed to complete if it executes in Serial mode, every read-only transaction will complete on its first attempt in STx mode, and an STx will not abort unless some other HTx or STx commits. Our implementation exposes two knobs for tuning progress. The first is a count of the number of HTx aborts before falling back to STx mode. The second is a count of the number of STx aborts before falling back to Serial mode. When combined with optional contention management at the beginning of the HC and SC states, there is ample opportunity to ensure that the most advantageous transactions are given priority. Additional scheduling decisions can be made when transitioning out of the CP state (i.e., by allowing a high priority transaction to abort all HTx, transition directly to SC, and commit first).

Implementation

The primary challenge in implementing HyCo is to achieve a low-latency implementation of the state machine from Figure 1. Our solution employs the metadata in Listing 1 to split the state machine into three parts. First, there is a list of Thread objects, through which per-thread states for non-transactional (NO), Serial, HTM, and STM modes can be discerned. Second, we use an Integer and three Booleans to control when HTx can begin, and when they must immediately abort. Finally, three Integers and one Boolean are used to manage the states of STx and Serial transactions. The code in Algorithm 1 uses these variables in flag-based and Dekker-style coordination.

The default system state is NS, in which HTx may begin and commit. Departing from this state requires an STx or Serial transaction to begin. To keep overheads low for HTx, we subscribe to the ser kill flag when an HTx begins. After becoming serial, but before accessing shared memory, a Serial transaction sets this flag to immediately abort all HTx. By optionally using the threads set first (TxBeginSerial lines 4-5), we can opt to prioritize running HTx over new Serial transactions.

Since HTx can execute concurrently with STx, we do not repeat this behavior when STx begin. Instead, we must ensure that HTx do not commit when either (a) STx are between their begin and end, or (b) STx are performing serial commit. The stx kill flag expresses condition (b). To handle condition (a), we use the started and cpending counters. When they are equal, every STx transaction has reached its commit point, and is trying to commit using HTM. In this case, HTx can commit, since the HTM will mediate conflicts. However, if they differ, then the HTx must abort.

STx are expected to be less frequent than HTx, and also to be longer-running. Thus we tolerate some contention over metadata, since it reduces the number of locations that HTx must check. Specifically, we use the started counter to track the number of STx that are not yet committed, and cpending to track the number of STx that have reached their commit point. The order and time counters are used only for SC Algorithm 1: The HyCo Algorithm. The parameter to xbegin (overridden by xabort) indicates the location to jump to when a hardware transaction aborts. commits, to enforce one-at-a-time commit of large STx. To maximize HTx concurrency with STx, we do not eagerly inform HTx of transitions between NS, SA, CP, and HC. Instead, we use the stx comm flag, which indicates that STx have moved to HC state. This reduces the frequency of reads of the started and cpending counters by HTx. To avoid additional synchronization on STx commit, we defer resetting stx comm to TxBeginSTx. Doing so is immaterial to HTx behavior, since HTx can progress in full from both the NS and HC modes.

The additional transition to SC for serialized commit of STx is expected to be rarest. We employ the same technique as Serial transactions, where a flag (stx kill) is coupled with a traversal of the threads set (TxCommitSTx lines [START_REF] Wang | Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language[END_REF][START_REF] Welc | Irrevocable Transactions and their Applications[END_REF] to allow HTx to complete before serial STx. A final complication is that, for the sake of fairness, we do not allow new STx to begin once any STx is ready to commit writes. This necessitates care in TxBeginSTx, since we must double-check cpending after incrementing started.

Serial transactions are least common, justifying more overhead whenever one be-After acquiring the serial token, a transaction will wait for all active STx and HTx to complete. Setting the serial flag first effectively prevents new STx. After allowing some HTx to complete, it sets ser kill to prevent additional HTx, at which point it can begin. Both flags are cleared when the transaction completes.

For completeness, Algorithm 1 also presents the read and write instrumentation for the HyCo algorithm. Per-access instrumentation is minimal, entailing neither metadata access nor memory fences. This is because (a) memory is immutable during STx execution, (b) Serial transactions execute in the absence of concurrency, and (c) HTx conflicts are mediated through the HTM, not through metadata.

Evaluation

We now evaluate the performance of HyCo using microbenchmarks, the STAMP benchmarks [START_REF] Minh | STAMP: Stanford Transactional Applications for Multi-processing[END_REF][START_REF] Ruan | STAMP Need Not Be Considered Harmful[END_REF] and Memcached [START_REF] Ruan | Transactionalizing Legacy Code: An Experience Report Using GCC and Memcached[END_REF]. Experiments were conducted on a machine with single-chip 3.40GHz Intel Core i7-4770 with 4 cores / 8 threads, running Ubuntu Linux 13.04, kernel 3.8.0-21, and a 4.9 GCC compiler with O3 and m64 flags. Results are the average of 5 trials. We compare the following TM implementations:

-STM Eager is the default STM provided with GCC. It is based on write-through TinySTM [START_REF] Felber | Dynamic Performance Tuning of Word-Based Software Transactional Memory[END_REF], using per-location ownership records, undo logging, encounter-time locking, and read set validation. The algorithm is opaque, and uses commit-time quiescence [START_REF] Wang | Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language[END_REF] to achieve privatization safety. -STM Lazy is a commit-time locking version of STM Eager. Writes are stored in a redo log, implemented as a hash table of 64-byte blocks. Ownership records are acquired at commit time. STM Lazy exposes overheads related to redo logs. -HTM is the default HTM implementation provided with GCC. It is a PhaseTM that falls back to serial mode after two consecutive HTM aborts. HTM 20 does not fall back to serial until 20 consecutive aborts. -HyNOrec: is the "P-counter" version of Hybrid NOrec, which does not require nontransactional loads [START_REF] Dalessandro | Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory[END_REF]. For Memcached, we also report the "2-counter" version. -HyNOrec RH is the most recent reduced hardware Hybrid NOrec implementation [START_REF] Matveev | Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory[END_REF]. We did not apply complier static analysis to reduce the instrumentation of read-only hardware transactions, for fair comparison with other TM implementations, which could all benefit from such analysis.

In the interest of fairness, we observe the following differences among systems: -Privatization: STM Eager and STM Lazy require quiescence-based privatization, whereas the HTM and hybrid algorithms do not. This can result in better scalability at high thread counts for hybrids, since they do not require blocking at commit time. -Mode Switching: The Serial modes of our HyTMs are achieved via spin waiting, whereas the GCC-based algorithms use a more heavyweight blocking mechanism. -Un-instrumented HTM Loads and Stores: GCC creates two code paths for transactions: an STM path, in which loads and stores of shared memory are instrumented, and an HTM path in which they are not. HyNOrec RH and HyCo HTx benefit from this lower-latency code path. We set HyCo thresholds as follows: An HTx transaction will switch to STx mode after 20 failed attempts to commit. An STx transaction will switch from committing in HC mode to committing in SC mode after 2 failed attempts. Fall-back to Serial mode occurs after 5 failed commit-time validations by an STx transaction. We also present HyCo-Turbo, which eagerly transitions STx to a mode where they run in isolation and perform all updates in-place. An STx can invoke turbo mode by a) confirming it is the only STx, (b) blocking new STx from starting, and (c) aborting all concurrent HTx. A turbo mode STx effectively executes as a Serial transaction.

Microbenchmark Performance

Figure 2 presents four red-black tree microbenchmarks. The experiments differ in terms of the range of keys present in the tree and the ratio of lookups to inserts and removes (inserts and removes are always performed in equal amount). All trees are pre-populated to 50% full. At one thread, HTM and HyCo performance are identical, and uniformly better than STM. This is expected, since most transactions are small enough to complete without exceeding hardware capacity. As we increase the thread count, and contention increases, we see a significant shift: the rapid fall-back to serial mode hurts HTM, both because it is too early, and because it limits concurrency. Even HTM 20, our version of the GCC HTM that retries 20 times before falling back to serial mode, cannot keep up with HyCo: the opportunity cost of serialization, even after 20 failed attempts, is simply too high. This is especially true for the highest contention configuration (8-bit keys, 33% lookup), where HTM 20 performance degrades beyond 4 threads.

Eager and Lazy STM scale well, and their use of validation affords for fewer aborts than HTM. However, latency is high: they incur a function call on every load and store, and Lazy pays even more due to accesses to the write log on many loads (these costs are only incurred in HyCo's STx mode). Furthermore, STM scales worse than HyCo, due to the overhead of quiescence, and the cost to support irrevocability via mode switching.

To gain a better understanding of the importance of HyTM versus PhaseTM, we measured the frequency of each type of commit for the HyCo execution of the benchmarks. While the majority of transactions can commit using HTM (NS state), up to 9% of HTx commit in HC mode. Thus while fallback to serial (for GCC) or STx (for HyCo) is rare, the impact on concurrent HTx can be significant. In HTM and HTM 20, every fallback to STx becomes a fallback to Serial, and all concurrency is lost. STAMP performance is shown in Figure 3. Unlike microbenchmark experiments, STAMP performance is shown as total time. The expectation is that more threads will result in a decreased execution time. We do not report Bayes performance, since it exhibits nondeterministic behavior. We also note that since Labyrinth was rewritten to match the Draft C++ TM Specification [START_REF] Ruan | STAMP Need Not Be Considered Harmful[END_REF], it shows little variation among algorithms because transactions no longer comprise a significant portion of execution time. Among the remaining 8 benchmark configurations, we see two trends emerge. First, on workloads with high contention, such as KMeans and Vacation, HTM performs best at one thread, but its performance degrades as the thread count increases, due to its reliance on serialization to ensure progress after repeated aborts. In contrast, HyCo manages to maintain its performance as contention increases, by falling back to STx. This trend peters out to some degree at 8 threads for Vacation-HC, due hardware multithreading effects: with four cores and 8 hardware threads, transaction write capacities are effectively halved at 8 threads. The low-contention variants of KMeans and Vacation show that as contention decreases, HTM is able to perform on-par with HyCo, but HyCo remains a superior choice overall. The same is true for SSCA2, where small transactions run bottleneck-free in HyCo and HTM. The second trend is shown by Genome, Intruder, and Yada, where HyCo incurs higher latency than HTM in order to interact with its write set. Recall that for STx transactions, HyCo must perform a lookup on each read, and must buffer its writes in a manner compatible with lookup. This necessitates a more complex data structure (hash of blocks with masks) than the undo log used by eager STM and the HTM fall-back. Consequently, we see that STM Lazy is a constant factor slower than STM Eager, and that HyCo similarly incurs higher overhead. The problem is most extreme in Yada, where HTx abort late in their execution, fall back to STx, and then incur write set overhead. Similarly, in Genome and Intruder, the frequency of lookups creates overhead.

On this last point, we conducted experiments with two different write set implementations: a hash table and an unbalanced BST. These tests showed that the data structure itself was not the slowdown. Rather, the cost came from manipulating bit masks in order to handle the case where a byte is accessed as part of multiple accesses of varying granularity (e.g., the byte is written, and then the enclosing word is read). These costs are shared by all of our Hybrid TM implementations.

Memcached Performance

Lastly, we evaluate all TM implementations on memcached. We followed the experiment configuration of Ruan et.al [START_REF] Ruan | Transactionalizing Legacy Code: An Experience Report Using GCC and Memcached[END_REF]. The configuration results in a number of operations proportional to the number of threads: flat curves indicate perfect scaling, higher values represent slowdown. The results are presented in Figure 4. Note that the number of transactions per thread is not constant, due to the use of transactions to read shared memory when spin waiting.

Memcached presents a number of interesting behaviors. First, we observed that Hybrid NOrec with P counters, where P is the number of threads, performed worse than the two-counter version. In our prior experiments, P-counter was superior. Second, HTM and HyCo performance were close, and HyNOrec-RH performed best at 8 threads. This was the first instance in which HyCo did not match or outperform HyNOrec-RH. Table 1 provides more detail. The data was collected by sampling one thread's behavior during a multithreaded execution. The top half shows that at high thread counts, a larger number of transactions execute as STx, and that they also cause more HTx to commit in the HC mode. We also see that the HyCo "turbo mode" optimization is valuable, accounting for more than 5% of commits.

The bottom half of the table shows that some overhead is a direct consequence of the HyCo design. At 8 threads, almost half of STx abort at commit time. These aborts imply wasted work: if STx could detect conflicts earlier, they might not spend as much time on attempts that ultimately failed. Furthermore, a quarter of execution time for the sampled transactions was spent waiting to start transactions. This time was due to both STx that could not start while other STx were in HC, SC, or turbo modes, and HTx that could not start due to STx in SC or turbo modes.

There are a number of solutions to these problems. First, as HTM capacities increase, these problems will naturally diminish as more transactions run as HTx. Second, it is likely that the knobs controlling turbo mode require more intelligence, and perhaps ought to adapt to the thread count and workload. Third, there is clearly an opportunity for advanced transaction scheduling and contention management. When so much time is already spent waiting at transaction begin, techniques such as [START_REF] Attiya | Transactional contention management as a non-clairvoyant scheduling problem[END_REF] and [START_REF] Yoo | Adaptive Transaction Scheduling for Transactional Memory Systems[END_REF] should not introduce latency. We leave further exploration of this topic as future work.

Conclusions and Future Work

This paper presented the Hybrid Cohorts (HyCo) algorithm. HyCo prioritizes softwaremode transactions over hardware-mode transactions, and then employs HTM resources to accelerate the commit phase of software transactions. Hardware transactions do not write to global metadata, and in-flight software transactions do not even read global metadata. Performance is on par with the current state-of-the-art, RHNOrec.

HyCo and RHNOrec represent distinct points in the HyTM design space. Both are informed by Riegel et al. [START_REF] Riegel | Optimizing Hybrid Transactional Memory: The Importance of Nonspeculative Operations[END_REF] and Dalessandro et al. [START_REF] Dalessandro | Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory[END_REF]: they use value-based validation to avoid wasting HTM capacity on per-location metadata, and they avoid serialization when transactions cannot complete in HTM. HyCo adapts the "reduced hardware transaction" innovation from RHNOrec: rather than execute the postfix of transactions in HTM, HyCo commits (validation and writeback) via HTM. Another significant difference is how the algorithms handle the worst case: in HyCo, many transactions can run in the slowest mode simultaneously, but they must validate; in RHNOrec, one transaction can use the slowest mode at a time, but fewer transactions require the slowest mode. Additionally, when a slow transaction runs, HyCo can still allow hardware transactions to commit, whereas RHNOrec does not. HyCo also appears to offer more opportunity for contention management, though we did not evaluate that possibility in this paper.

Which algorithm is "better" is likely to depend on how HTM evolves. Clearly, both systems can benefit from increased HTM capacity, which will allow more transactions to execute fully in hardware. As multi-chip HTM becomes more prevalent, HyCo may benefit more: RHNOrec inherits NOrec's requirement that some committing writers increment a global shared counter, which is known to scale poorly on multi-chip machines; HyCo has no such bottleneck. Another open question is how nontransactional loads might improve the algorithms: HyCo could employ nontransactional reads to allow hardware transactions to spin, rather than abort, when software transactions block their commit. No such opportunity is apparent for RHNOrec.

Unfortunately, we cannot draw stronger conclusions without better TM benchmarks. On microbenchmarks, and on STAMP, RHNOrec and HyCo perform similarly despite significant differences in design (especially in the fall-back path). On the only realistic workload available, Memcached, RHNOrec performs better at high core counts, where symmetric multithreading reduces HTM capacity. We are hopeful that as more programmers use TM, there will be new opportunities to contrast HyTM implementations and draw conclusions about what costs are most important to avoid.

Listing 1 :

 1 Hybrid Cohorts metadata. Global variables are clustered according to whether they assist in (a) coordinating all transactions, (b) coordinating HTx transactions, or (c) coordinating STx transactions.

8 -

 8 bit keys and 33% lookup ratio

Fig. 2 :

 2 Fig. 2: Red/black tree microbenchmarks

  Fig. 3: STAMP performance

  Fig. 4: Memcached Performance

STx Active (SA): At least one STx has started but has not yet reached its

	HTx or STx begin /
	Read-only STx commit / HTx abort		Writer STx ready to commit / Read-only STx commit /
		SA	HTx begin * / HTx abort *
			CP
			Last writer STx
			ready to commit
			& no read-only STx remain	STx HTM commit / STx abort /
			HC	HTx begin * / HTx commit * / HTx abort *
	S	SC	STx slow commit / STx slow abort
				commit
	point. No transaction is allowed to commit changes to shared state.
	-STx Commit Pending (CP): A proper, nonempty subset of STx have reached their
	commit points. No transaction is allowed to commit changes to shared state. To
	prevent extended blocking of ready-to-commit STx, new STx may not begin.
	-STx Hardware Commit (HC): All STx have reached their commit point, and are
	attempting to commit via reduced hardware transactions. STx cannot begin, since
	shared memory may be changed.
	-STx Software Commit (SC): A proper, nonempty subset of STx cannot commit via
	reduced hardware transactions, and are in the process of committing sequentially.
	No new transactions may begin.
	State transitions are triggered by the following transaction events. With the excep-
	tion of HTx Abort, these events occur on the boundaries of transactions:
	-HTx Begin: A thread attempts to begin a transaction in HTx mode.

NS

Fig. 1: State transitions of the Hybrid Cohorts algorithm.

Table 1 :

 1 Frequency of each type of commit for Memcached at different client counts with HyCo-Turbo. Values were reported by a randomly chosen thread.

	Serial

Client Count NS HTx:HC STx:RO STx:HC STx:SC STx:Turbo

This instrumentation requires nontransactional loads from within the transaction, which are not supported by TSX.

Acknowledgments

We thank our reviewers, and the TRANSACT community, for their excellent advice. This material is based upon work supported by the National Science Foundation under Grants CAREER-1253362 and CCF-1218530. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.