gistfile1.h

/* CAS lock comparison to mutex */
/* 
   mthomas@atticus:~$ gcc -O3 -m64 -march=core2 -mfpmath=sse -msse4 cas_queue.c -o cas_queue -lpthread
   mthomas@atticus:~$ ./cas_queue
   cas locks 4.77 seconds
   mutex locks 38.05 seconds
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <pthread.h>


struct node {
    void        *data;
    struct node *next;
};

struct queue {
    struct node *head;
    struct node *tail;
};


struct queue *global_queue;

struct node *
node_init(void *data)
{
    struct node *node;

    node = calloc(sizeof(struct node), 1);
    node->data = data;
    node->next = NULL;
    return(node);
}

void
queue_add(struct queue *q, struct node *n, pthread_mutex_t *mutex)
{
    struct node *tail;
    struct node *next;
    struct node *head;

    if (mutex) {
        pthread_mutex_lock(mutex);
        tail = q->tail;
        tail->next = n;
        q->tail = n;
        pthread_mutex_unlock(mutex);
        return;
    }


    while (1) {
        tail = q->tail;
        next = tail->next;

        if (tail != q->tail) {
            /* half write from another thread */
            continue;
        }

        if (next != NULL) {

            /* if tail == q->tail then q->tail = next; */
            __sync_bool_compare_and_swap(&q->tail, tail, next);
            continue;
        }

        if (__sync_bool_compare_and_swap(&tail->next, NULL, n)) {
            /* if tail->next == NULL, then tail->next = n */
            break;
        }

    }

    /* if q->tail == tail, then q->tail = n; */
    __sync_bool_compare_and_swap(&q->tail, tail, n);
} /* queue_add */

void *
thread_work(void *arg)
{
    int num_nodes = 100000;
    int i;


    for (i = 0; i < num_nodes; i++) {
        queue_add(global_queue, node_init("data"), NULL);
    }

    return(NULL);
}


void *
thread_mutex_work(void *arg)
{
    int              num_nodes = 100000;
    int              i;
    pthread_mutex_t *mutex = (pthread_mutex_t *)arg;

    for (i = 0; i < num_nodes; i++) {
        queue_add(global_queue, node_init("data"), mutex);
    }


    return(NULL);
}


void
do_cas_threads(void)
{
    int        num_threads = 100;
    int        i;
    pthread_t *threads;

    threads = (pthread_t *)malloc(num_threads  * sizeof(*threads));

    for (i = 0; i < num_threads; i++) {
        pthread_create(&threads[i], NULL, thread_work, NULL);
    }

    for (i = 0; i < num_threads; i++) {
        pthread_join(threads[i], NULL);
    }

}

void
do_mutex_threads(void)
{
    int             num_threads = 100;
    int             i;
    pthread_t      *threads;
    pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

    threads = (pthread_t *)malloc(num_threads * sizeof(*threads));

    for (i = 0; i < num_threads; i++) {
        pthread_create(&threads[i], NULL, thread_mutex_work, (void *)&mutex);
    }

    for (i = 0; i < num_threads; i++) {
        pthread_join(threads[i], NULL);
    }
}

int main(int argc, char **argv)
{
    struct queue *q;
    char         *data = "hello there";
    clock_t       t0;
    clock_t       t1;

    q = calloc(sizeof(struct queue), 1);
    q->tail = calloc(sizeof(struct node), 1);
    q->head = q->tail;

    global_queue = q;

    t0 = clock();
    do_cas_threads();
    t1 = clock();

    printf("cas locks %g seconds\n",
           (double)(t1 - t0) / (double)CLOCKS_PER_SEC);

    t0 = clock();
    do_mutex_threads();
    t1 = clock();

    printf("mutex locks %g seconds\n",
           (double)(t1 - t0) / (double)CLOCKS_PER_SEC);


    return(0);
}