Musings

A random collection

Archive for May 2011

TECH: Compare and Swap

Here is an example of Compare-And-Swap code:

  1. GCC (On Linux), you should use sync_bool_compare_and_swap
    bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
    

    Details are here:

    // To compile:
    //
    // gcc -O2 -lpthread example.c
    #include <assert.h>
    #include <stdio.h>
    #include <pthread.h>
    
    // Delay function waits a variable time controlled by "d". Note that
    // it is set to be non-inlined so that the computation is not
    // completely optimized away. (Without inlining, gcc does not realize
    // that the return value is not actually needed).
    static __attribute__ ((noinline))
    int delay(int d)
    {
        int i,k;
        int x = 0;
        for (i = 0; i<d; i++) {
            for (k = 0; k<100000; k++) {
                x+=i+k;
            }
        }
        return x;
    }
    
    // Example thread function. This just delays for a little while,
    // controlled by the parameter passed when the thread is started.
    static
    void *thread_fn(void *arg)
    {
        int arg_val = *(int*)arg;
        printf("Thread running, arg=%d\n", arg_val);
        delay(arg_val);
        printf("Thread done\n");
        return NULL;
    }
    
    // Shared variable for use with example atomic compare and swap
    // operations (__sync_val_compare_and_swap in this example).
    static volatile int x = 0;
    
    // Main function
    int main(int argc, char **argv)
    {
        // Start a new thread, and then wait for it to complete:
        int thread_arg;
        pthread_t new_thread;
        thread_arg = 100000;
        int r = pthread_create(&new_thread,
                               NULL, // Attributes
                               thread_fn,
                               &thread_arg); // Parameter for thread_fn
        assert(r==0 && "pthread_create failed");
        printf("Waiting for thread\n");
        void *ret;
        r = pthread_join(new_thread, &ret);
        assert(r==0 && "pthread_join failed");
        printf("Joined with thread ret=%p\n", ret);
    
        // Example compare and swap operations
        int v = 0;
        printf("x=%d\n", x);
        v = __sync_val_compare_and_swap(&x, 0, 1);
        printf("x=%d v=%d\n", x, v);
        v = __sync_val_compare_and_swap(&x, 0, 2);
        printf("x=%d v=%d\n", x, v);
        v = __sync_val_compare_and_swap(&x, 1, 2);
        printf("x=%d v=%d\n", x, v);
        return 0;
    }
    
  2. On Windows using VC++, take a look at InterlockedCompareExchange
    // To compile:
    //
    // cl /O2 example.c
    #include <windows.h>
    #include <assert.h>
    
    // Delay function waits a variable time controlled by "d". Note that
    // optimization is disabled for this function so that the (useless)
    // computation is left to form a delay.
    #pragma optimize("", off)
    static int delay(int d)
    {
        int i,k;
        int x = 0;
        for (i = 0; i<d; i++) {
            for (k = 0; k<1000000; k++) {
                x+=i+k;
            }
        }
        return x;
    }
    #pragma optimize("", on)
    
    // Example thread function. This just delays for a little while,
    // controlled by the parameter passed when the thread is started.
    static DWORD WINAPI thread_fn(LPVOID lpParam)
    {
        int arg_val = *(int*)lpParam;
        printf("Thread running, arg=%d\n", arg_val);
        delay(arg_val);
        printf("Thread done\n");
        return 17;
    }
    
    // Shared variable for use with example atomic compare and swap
    // operations (InterlockedCompareExchange in this example).
    static volatile LONG x = 0;
    
    // Main function
    int
    main(int argc, char **argv)
    {
        // Start a new thread, and then wait for it to complete:
        int thread_arg;
        DWORD r;
        LONG v;
        HANDLE new_thread;
        thread_arg = 1000;
        new_thread = CreateThread(NULL,
                                  0, // Default stack size
                                  thread_fn,
                                 &thread_arg, // Parameter for thread_fn
                                  0, // 0 => Run immediately
                                  NULL);
        assert(new_thread != NULL && "CreateThread failed");
        printf("Waiting for thread\n");
        r = WaitForSingleObject(new_thread, INFINITE);
        assert(r == WAIT_OBJECT_0 && "WaitForSingleObject failed");
        printf("Joined with thread\n");
    
        // Example compare and swap operations
        printf("x=%d\n", x);
        v = InterlockedCompareExchange(&x, 1, 0);
        printf("x=%d v=%d\n", x, v);
        v = InterlockedCompareExchange(&x, 2, 0);
        printf("x=%d v=%d\n", x, v);
        v = InterlockedCompareExchange(&x, 2, 1);
        printf("x=%d v=%d\n", x, v);
        return 0;
    }
    
  3. In C#, one would use: Interlocked.CompareExchange
    // To compile:
    //
    // csc Example.cs
    using System;
    using System.Threading;
    public class Example
    {
        // Delay function waits a variable time controlled by "d". NB: you
        // may need to modify the delay function if a different
        // implementation of the compiler and .NET runtime system optimize
        // away the computation being used to form the delay -- e.g., using
        // the return value in the caller.
        public static int delay(int d) {
            int i,k;
            int x = 0;
            for (i = 0; i<d; i++) {
                for (k = 0; k<1000000; k++) {
                    x+=i+k;
                }
            }
            return x;
        }
    
        // Constructor for an "Example" object. Fields in the object can be
        // used to pass values to/from the thread when it is started and
        // when it finishes.
        int Arg;
        public Example(int arg) {
            this.Arg = arg;
        }
    
        // Example thread function. This just delays for a little while,
        // controlled by the parameter passed when the thread is started.
        public void ThreadProc() {
            Console.Out.WriteLine("Thread running, arg=" + this.Arg);
            delay(this.Arg);
            Console.Out.WriteLine("Thread done");
        }
    
        // Shared variable for use with example atomic compare and swap
        // operations (Interlocked.CompareExchange in this example).
        static int x = 0;
    
        // Main function
        public static void Main()
        {
            // Start a new thread, and then wait for it to complete:
            Console.Out.WriteLine("Start");
            Example e1 = new Example(1000);
            Thread t1 = new Thread(e1.ThreadProc);
            t1.Start();
            t1.Join();
            Console.Out.WriteLine("Joined with thread");
    
            // Example compare and swap operations
            int v;
            Console.Out.WriteLine("x=" + x);
            v = Interlocked.CompareExchange(ref x, 1, 0);
            Console.Out.WriteLine("x=" + x + " v=" + v);
            v = Interlocked.CompareExchange(ref x, 2, 0);
            Console.Out.WriteLine("x=" + x + " v=" + v);
            v = Interlocked.CompareExchange(ref x, 2, 1);
            Console.Out.WriteLine("x=" + x + " v=" + v);
        }
    }
    
  4. Java: you would use AtomicOperation
    // To compile:
    //
    // javac Example.java
    
    import java.util.concurrent.atomic.*;
    
    class Example implements Runnable {
        // Delay function waits a variable time controlled by "d". The function
        // writes to a per-object volatile field -- this aims to prevent the compiler
        // from optimizing the delay away completely.
        volatile int temp;
    
        void delay(int arg) {
            for (int i = 0; i < arg; i++) {
                for (int j = 0; j < 1000000; j++) {
                    this.temp += i + j;
                }
            }
        }
    
        // Constructor for an "Example" object. Fields in the object can be
        // used to pass values to/from the thread when it is started and
        // when it finishes.
        int arg;
        int result;
        Example(int arg) {
            this.arg = arg;
        }
    
        // Example thread function. This just delays for a little while,
        // controlled by the parameter passed when the thread is started.
        public void run() {
            System.out.println("Thread started arg=" + arg);
            delay(arg);
            result = 42;
            System.out.println("Thread done result=" + result);
        }
    
        // Shared variable for use with example atomic compare and swap
        // operations (ai.compareAndSet in this example).
        static AtomicInteger ai = new AtomicInteger(0);
    
        // Main function
        public static void main(String args[]) {
            // Start a new thread, and then wait for it to complete:
            System.out.println("Start");
            try {
                Example e1 = new Example(100);
                Thread t1 = new Thread(e1);
                t1.start();
                t1.join();
                System.out.println("Joined with thread, ret=" + e1.result);
            } catch (InterruptedException ie) {
                System.out.println("Caught " + ie);
            }
            System.out.println("End");
    
            // Example compare and swap operations
            boolean s;
            System.out.println("ai=" + ai);
            s = ai.compareAndSet(0, 1);
            System.out.println("ai=" + ai + " s=" + s);
            s = ai.compareAndSet(0, 2);
            System.out.println("ai=" + ai + " s=" + s);
            s = ai.compareAndSet(1, 2);
            System.out.println("ai=" + ai + " s=" + s);
        }
    }
    

Written by curious

May 26, 2011 at 11:37 am

Posted in programming