Benchmarks for Ticket Lock AWN in C11

We ran our microbenchmark for the C11 implementations of the Ticket Lock AWN (all three variants), compared them against a basic Ticket Lock, and here are the results.

-----------------------------------------------------
AMD Opteron (2 NUMA nodes, total of 32 cores)

1 Thread
pthread_mutex_t                  5291403 ops/second
Ticket Lock                     17275652 ops/second
Ticket AWN - Negative Egress    15946079 ops/second
Ticket AWN - Ends on Egress     15876117 ops/second
Ticket AWN - Spins on Both      17062574 ops/second

2 Threads
pthread_mutex_t                  1575780 ops/second
Ticket Lock                      9078627 ops/second
Ticket AWN - Negative Egress     8065764 ops/second
Ticket AWN - Ends on Egress      7946022 ops/second
Ticket AWN - Spins on Both       8693872 ops/second

4 Threads
pthread_mutex_t                  1313133 ops/second
Ticket Lock                      7383215 ops/second
Ticket AWN - Negative Egress     6463225 ops/second
Ticket AWN - Ends on Egress      6712847 ops/second
Ticket AWN - Spins on Both       6676756 ops/second

8 Threads
pthread_mutex_t                  1377882 ops/second
Ticket Lock                      7335856 ops/second
Ticket AWN - Negative Egress     6542371 ops/second
Ticket AWN - Ends on Egress      7233964 ops/second
Ticket AWN - Spins on Both       7207002 ops/second

16 Threads
pthread_mutex_t                  1302257 ops/second
Ticket Lock                      4915970 ops/second
Ticket AWN - Negative Egress     5810103 ops/second
Ticket AWN - Ends on Egress      5934175 ops/second
Ticket AWN - Spins on Both       6204561 ops/second

32 Threads
pthread_mutex_t                  1299800 ops/second
Ticket Lock                      3925222 ops/second
Ticket AWN - Negative Egress     5185931 ops/second
Ticket AWN - Ends on Egress      5550168 ops/second
Ticket AWN - Spins on Both       5755218 ops/second


-----------------------------------------------------
Intel i7-3740QM (4 cores, 8 hyper threads)

1 Thread
pthread_mutex_t                 13931684 ops/second
Ticket Lock                     37615670 ops/second
Ticket AWN - Negative Egress    34421877 ops/second
Ticket AWN - Ends on Egress     34367820 ops/second
Ticket AWN - Spins on Both      38167859 ops/second

2 Threads
pthread_mutex_t                  4169864 ops/second
Ticket Lock                     20957181 ops/second
Ticket AWN - Negative Egress    19841579 ops/second
Ticket AWN - Ends on Egress     19541868 ops/second
Ticket AWN - Spins on Both      24479835 ops/second

4 Threads
pthread_mutex_t                  4215837 ops/second
Ticket Lock                     20065448 ops/second
Ticket AWN - Negative Egress    17473789 ops/second
Ticket AWN - Ends on Egress     17397894 ops/second
Ticket AWN - Spins on Both      22530033 ops/second

After a quick look at the numbers, we see that the Spins on Both variant is pretty much the winner of the three variants, and that when compared with the basic Ticket Lock, it follows closely and sometimes can vastly surpass it (for the scenario with 32 threads in the AMD machine).



When the Ticket AWN variants are faster than the basic ticket Lock, it seems to be for most of the same reasons that the CLH and MCS locks are better than a Ticket Lock: the waiting threads are each spinning on their own cache line, which reduces traffic in the cache-coherence system.
Moreover, in the Ticket AWN variants each node belongs to a thread and is used (and re-used) by that thread alone. This means that there is no node "passing" from thread to thread like there is on CLH, which means that the tlNode thread-local variable is a pointer whose cache-line is never touched, i.e. it is always pointing to the same object in memory (unlike CLH). This represents a (small) advantage of the Ticket AWN when compared to the CLH.

Something to keep in mind is that on our benchmark each thread tries to immediately acquire the lock after it releases it, which means that with N threads there are always N-1 or N-2 threads waiting. The Ticket AWN algorithms are more favorable in situations where there are at least 1 other thread already waiting, and this is is not very visible in the results, but we should keep in mind that a more realistic scenario where threads try to acquire the lock in "bursts" could yield somewhat different results.

For the moment, that's all we've got on Ticket Locks, but if you're interested in Ticket Lock variants, here is another variant by Dave Dice you can take a look at:
https://blogs.oracle.com/dave/entry/partitioned_ticket_lock1

Ticket Lock AWN - Spins on Both variant

On this post we are going to cover the third and last of the three variants of Ticket AWN. We call this variant the Spins on Both because the at the end of the lock() method we have to spin on both egress and lockIsMine if and only if egress is ticket-1.
Here's what the lock() and unlock() methods look like in this variant:

void ticket_awnsb_mutex_lock(ticket_awnsb_mutex_t * self)

{

    const long long ticket = atomic_fetch_add(&self->ingress, 1);

    if (atomic_load(&self->egress) == ticket) return;

    while (atomic_load_explicit(&self->egress, memory_order_relaxed) >= ticket-1) {

        if (atomic_load(&self->egress) == ticket) return;

        sched_yield();

    }

    // If there is no slot to wait, spin until there is

    while (ticket-atomic_load(&self->egress) >= (self->maxArrayWaiters-1)) sched_yield();

    // There is a spot for us on the array, so place our node there

    awnsb_node_t * wnode = &tlNode;

    // Reset lockIsMine from previous usages

    atomic_store_explicit(&wnode->lockIsMine, false, memory_order_relaxed);

    atomic_store(&self->waitersArray[(int)(ticket % self->maxArrayWaiters)], wnode);

    if (atomic_load(&self->egress) < ticket-1) {

        // Spin on lockIsMine

        while (!atomic_load(&wnode->lockIsMine)) sched_yield();

        atomic_store_explicit(&self->egress, ticket, memory_order_relaxed);

    } else {

        // Spin on both lockIsMine and egress

        while (atomic_load(&self->egress) != ticket) {

            if (atomic_load(&wnode->lockIsMine)) {

                atomic_store_explicit(&self->egress, ticket, memory_order_relaxed);

                return; // Lock acquired

            }

            sched_yield();

        }

    }

    // Lock acquired

}

void ticket_awnsb_mutex_unlock(ticket_awnsb_mutex_t * self)

{

    long long ticket = atomic_load_explicit(&self->egress, memory_order_relaxed);

    // Clear up our entry in the array before releasing the lock.

    atomic_store_explicit(&self->waitersArray[(int)(ticket % self->maxArrayWaiters)], NULL, memory_order_relaxed);

    // We could do this load as relaxed per se but then the store on egress of -(ticket+1) could be re-ordered to be before, and we don't want that

    awnsb_node_t * wnode = atomic_load(&self->waitersArray[(int)((ticket+1) % self->maxArrayWaiters)]);

    if (wnode != NULL) {

        // We saw the node in waitersArray

        atomic_store(&wnode->lockIsMine, true);

    } else {

        atomic_store(&self->egress, ticket+1);

    }

}

In the "Spins on Both" variant we may have to spin on both egress and lockIsMine, but notice that this only happens if the egress is equal to ticket-1 (or to ticket). For all other cases we spin on lockIsMine only.
The main advantage of this technique is that we can place the store of the egress advancing to the current ticket right in the lock() function (with a relaxed store) and this way, on the unlock(), we only do one store, either on egress or on lockIsMine.
Surprisingly, this seems to be the best of the three variants, at least on our C11 benchmarks (more on that in a future post).

Sample Scenario

To understand how this mechanism works, imagine a sample scenario where Thread 1 (T1) gets a ticket of 10:

• egress is 10: T1 has the lock
• egress is  9: T1 will add its node to the waitersArray and will spin both on egress and lockIsMine and exit when:
• egress is       10: T1 has the lock
• lockIsMine is true: T1 has the lock and sets egress to 10
• egress is  8: T1 will add its node to the waitersArray and wait until lockIsMine is true, once lockIsMine is true T1 has the lock and sets egress to 10

Relaxed Atomics

There are a few places in this algorithm where we use relaxed atomic loads or stores in the C11/C++1x implementation:

• In lock(), the store on wnode->lockIsMine to false can be relaxed because it will become visible on the release-store of the wnode in the array and it will only be accessible from that instant in time.
• In lock(), the store to egress of ticket can be made relaxed because it will become visible at the end of unlock() when we do a store with release on either lockIsMine or egress.
• In unlock(), the first load on egress can be relaxed because it was read last by the same thread in lock() so it is guaranteed to be up to date.
• In unlock(), the store on the self entry of the array to NULL can be relaxed because it will become visible either with the store with release on the wnode->lockIsMine to true or on the egress to ticket+1.

Here is the source code in Java and C11:

https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/locks/experimental/TicketAWNSpinsBothLock.java

https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/ticketawn/ticket_awnsb_mutex.h
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/ticketawn/ticket_awnsb_mutex.c

Ticket Lock AWN - Negative Egress variant

On this post we are going to cover the second of the three variants of Ticket AWN. We call this variant the Negative Egress because the thread doing the unlock() uses the sign of the egress to tell the next waiting thread whether it saw a waiting node or not.
Here's what the lock() and unlock() methods look like in this variant:

void ticket_awnne_mutex_lock(ticket_awnne_mutex_t * self)

{

    const long long ticket = atomic_fetch_add(&self->ingress, 1);

    if (atomic_load(&self->egress) == ticket) return;

    while (get_pos_egress_relaxed(self) >= ticket-1) {

        if (get_pos_egress(self) == ticket) return;

        sched_yield();

    }

    // If there is no slot to wait, spin until there is

    while ((ticket-get_pos_egress(self)) >= (self->maxArrayWaiters-1)) sched_yield();

    // There is a spot for us on the array, so place our node there

    awnne_node_t * wnode = &tlNode;

    // Reset lockIsMine from previous usages

    atomic_store_explicit(&wnode->lockIsMine, false, memory_order_relaxed);

    atomic_store(&self->waitersArray[(int)(ticket % self->maxArrayWaiters)], wnode);

    // If there is only one left before egress becomes our ticket, wait for it

    while (true) {

        const long long localEgress = atomic_load(&self->egress);

        // Break to spin on lockIsMine

        if (get_pos_egress_relaxed(self) < ticket-1 || -localEgress == ticket) break;

        if (localEgress == ticket) return; // egress was positive and matches. Lock acquired

        sched_yield();

    }

    // Spin on our own cache line waiting for the lock

    while (!atomic_load(&wnode->lockIsMine)) {

        sched_yield();

    }

}

void ticket_awnne_mutex_unlock(ticket_awnne_mutex_t * self)

{

    long long ticket = get_pos_egress_relaxed(self);

    // Clear up our entry in the array before releasing the lock.

    atomic_store_explicit(&self->waitersArray[(int)(ticket % self->maxArrayWaiters)], NULL, memory_order_relaxed);

    // We could do this load as relaxed per se but then the store on egress

    // of -(ticket+1) could be re-ordered to be before, and we don't want that

    awnne_node_t * wnode = atomic_load(&self->waitersArray[(int)((ticket+1) % self->maxArrayWaiters)]);

    if (wnode != NULL) {

        // We saw the node in waitersArray, so tell the thread to spin

        // on lockIsMine by setting a negative egress

        atomic_store_explicit(&self->egress, -(ticket+1), memory_order_relaxed);

        atomic_store(&wnode->lockIsMine, true);

    } else {

        // No node was seen, so set a positive egress

        atomic_store(&self->egress, ticket+1);

    }

}

In the "Negative Egress" variant we use one bit of the egress for the current thread to indicate to the next waiting thread that it has seen its waiting node, and as such, the next waiting thread needs only to spin on the wnode->lockIsMine (and not on egress). In our implementation we use the sign bit of the integer for this purpose, but other techniques can be used, like for example, the least significant bit (lsb) and then do the getAndAdd() in steps of 2.
When a waiting thread sees its ticket with a negative value it can not go into its critical section because the current thread may still be about to increment egress and then there could be multiple threads incrementing egress simultaneously, which could leave it in a bad state, unless we would use getAndIncrement()/atomic_fetch_add() at the end of unlock() but that is a more expensive operation than a store with release, so we want to make sure we do it with a store with release.
This variant is slightly "tricky" because on the unlock() we can do a store on egress and then on lockIsMine or a store just on egress, and both code paths must be "correct".

Sample Scenario

To understand how this mechanism works, imagine a sample scenario where Thread 1 (T1) gets a ticket of 10:

• egress is 10: T1 has the lock
• egress is  9: T1 will spin on egress waiting for it to become 10
• egress is  8: T1 will add its node to the waitersArray and check egress again:
• egress is still     8: T1 will spin on lockIsMine 
• egress is now  -9: T1 will spin on egress (egress may be about to change to 10)
• egress is now    9: T1 will spin on egress (egress may be about to change to 10)
• egress is now -10: T1 will spin on lockIsMine (previous thread has seen T1's node)
• egress is now   10: T1 has the lock

Relaxed Atomics

There are a few places in this algorithm where we use relaxed atomic loads or stores in the C11/C++1x implementation:

• In lock(), the store on wnode->lockIsMine to false can be relaxed because it will become visible on the release-store of the wnode in the array and it will only be accessible from that instant in time.
• In unlock(), the first load on egress can be relaxed because it was read last by the same thread in lock() so it is guaranteed to be up to date.
• In unlock(), the store on the self entry of the array to NULL can be relaxed because it will become visible either with the store with release on the wnode->lockIsMine to true or on the egress to ticket+1.
• In unlock(), the store in egress of -(ticket+1) can be relaxed because before there is a load with acquire of the array which prevents reordering above, and the store will become visible when we do the store with release of wnode->lockIsMine to true.

Here is the source code in Java and C11:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/locks/experimental/TicketAWNNegativeEgressLock.java

https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/ticketawn/ticket_awnne_mutex.h
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/ticketawn/ticket_awnne_mutex.c