www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Is this thread safe?

reply dsimcha <dsimcha yahoo.com> writes:
I'm very new to concurrent programming and am trying to implement some high
performance math stuff in D.  Could someone please tell me whether the
following simple function would be considered thread safe?

real logFactorial(uint n) {
    static real* factorial_table = ([0.0L]).ptr;
    static size_t length = 1;
    //Length is guaranteed to never decrease.
    //At least at an abstract level, the synchronized part is guaranteed to
    //only write to elements >= length.
    if(length > n) return factorial_table[n];
    synchronized {
        if(capacity(factorial_table) < (n + 1) * real.sizeof) {
            //Is it safe to update the factorial_table pointer like this?
            factorial_table = cast(real*) realloc(factorial_table, (n + 1) *
real.sizeof);
        }
        for(uint i = length; i<=n; i++) {
            factorial_table[i] = factorial_table[i-1] + log2(i);
        }
        //Set new length after all numbers are calculated.
        length = n;
        return factorial_table[n];
    }
}

This function computes the log of the factorial of n, and caches the results.
 If it's possible without resorting to any low-level tricks that would make
this function horribly unreadable, I'd like to avoid having the reads of
factorial_table synchronized for performance reasons.  I would guess that
updating pointers and size_t variables (which are of the same representation
as pointers, at least on the architectures I'm aware of) should be atomic,
since otherwise the GC would not be able to properly scan pointers that were
in the middle of being updated.
Jul 11 2008
next sibling parent reply BCS <ao pathlink.com> writes:
It's new NG thread, and generally this is a friendly NG so probably it is.

(I'm sorry, it was to good a straight line to pass up)
Jul 11 2008
next sibling parent superdan <super dan.org> writes:
BCS Wrote:


 It's new NG thread, and generally this is a friendly NG so probably it is.
 
 (I'm sorry, it was to good a straight line to pass up)


took me a few seconds. now i agree with you: no contention!
Jul 11 2008
prev sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"BCS" <ao pathlink.com> wrote in message 
news:55391cb32f1a78cab18010ed04f8 news.digitalmars.com...

 It's new NG thread, and generally this is a friendly NG so probably it is.

 (I'm sorry, it was to good a straight line to pass up)


DAMN!  You beat me to it!
Jul 11 2008
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
dsimcha wrote:

 I'm very new to concurrent programming and am trying to implement some high
 performance math stuff in D.  Could someone please tell me whether the
 following simple function would be considered thread safe?


No, it is not thread safe. It's the old double checked locking problem. 
The reasons are difficult to understand, but understanding it is crucial 
to writing thread safe code.

http://www.ddj.com/184405726

http://en.wikipedia.org/wiki/Double_checked_locking_pattern
Jul 11 2008
parent reply dsimcha <dsimcha yahoo.com> writes:
From reading over these links, it makes sense to me why my previous
implementation
would not work. However, the articles, which were written with C++, not D, in
mind, recommend using the volatile keyword to solve this.  In D, volatile is
deprecated, even though, according to microbenchmarks I just tried, it has much
less overhead than synchronized.  I also understand from reading previous forum
posts that it applies to statements, not variables.  If my understanding of
volatile is correct, my function could be made correct as follows, by simply
inserting a volatile at the statement that reads factorial_table*.

real logFactorial(uint n) {
    static real* factorial_table = ([0.0L]).ptr;
    static size_t length = 1;
    //Length is guaranteed to never decrease.
    //At least at an abstract level, the synchronized part is guaranteed to
    //only write to elements >= length.
    if(length > n) {  //Length can only get larger, cached length is fine.
        volatile real result = factorial_table[n]; //Doesn't use cached
factorial_table*
        return result;
    }
    synchronized {
        if(capacity(factorial_table) < (n + 1) * real.sizeof) {
            //Is it safe to update the factorial_table pointer like this?
            factorial_table = cast(real*) realloc(factorial_table, (n + 1) *
real.sizeof);
        }
        for(uint i = length; i<=n; i++) {
            factorial_table[i] = factorial_table[i-1] + log2(i);
        }
        //Set new length after all numbers are calculated.
        length = n;
        return factorial_table[n];
    }
}

Other than the fact that volatile is deprecated, would this be a correct fix? 
If
so, why is volatile deprecated?  If not, is it not correct?
Jul 11 2008
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
Never mind, I see at least one reason why my last post would be incorrect.  The
length variable could be set out-of-order before all of the factorials up to
length are calculated.  Is there any simple way to write this function so it's
thread-safe without using synchronized just to access cached results?
Jul 11 2008
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
dsimcha wrote:

 Never mind, I see at least one reason why my last post would be incorrect.  The
 length variable could be set out-of-order before all of the factorials up to
 length are calculated.  Is there any simple way to write this function so it's
 thread-safe without using synchronized just to access cached results?


No. There are three choices:

1) synchronize it

2) make thread-local versions

3) insert fences with the inline assembler
Jul 11 2008
prev sibling parent "Koroskin Denis" <2korden+dmd gmail.com> writes:
On Sat, 12 Jul 2008 04:52:15 +0400, dsimcha <dsimcha yahoo.com> wrote:


 Never mind, I see at least one reason why my last post would be  
 incorrect.  The
 length variable could be set out-of-order before all of the factorials  
 up to
 length are calculated.  Is there any simple way to write this function  
 so it's
 thread-safe without using synchronized just to access cached results?


The following approach would be easier, I think:

1) Have an array that reallocates without invalidating old data, so that
all the pointers and iterators remain valid after array resize took place

2) When need to access Nth element do the following:
    a) if size > N, return array[N]
    b) increase the capacity (atomically)
    c) set the array[N] to the calculated value
    d) use compareAndSwap (atomicStoreIf in Tango) to increase array.length
    e) return value

Using my SafeGrowingArray from here -  
http://www.everfall.com/paste/id.php?tmjp3qzeo622
your code could be simplified to the following:

// Important invariant assumption:
// if the size is N, then values 0..N-1 are evaluated and correct.
//
// The steps are taken in the following order:
// 1) increase capacity
// 2) calculate and set the value
// 3) increase size
//
// As a result, if another thread changes the array size to some K then it  
means that it is guarantied that values 0..K-1 are correct

class FactorialTable : SafeGrowingArray!(real,  
ThreadSafetyPolicy.ThreadSafe)
{
     real opIndex(size_t index)
     {
         size_t size = _size;
         if (size > index) {
             return super.opIndex(index);
         }

         reserve(index + 1); // step 1, ensure the capacity

         for (size_t i = size; i <= index; ++i) {
             real value = calcFactorialValue(i);   // step 2 a, calculate  
the value
             this.opIndexAssign(index, value);     // step 2 b, set the  
value. It is safe
                                                   // because capacity is  
large and faction is deterministic
         }

         while (true) {
             if (atomicStoreIf(_size, size, index + 1)) { // step 3, the  
most important one
                 break; // succeeded                      // if succeeded,  
the size is updated
             }

             // failed                                    // if failed ->  
size is changed in another thread
             size = _size;
             if (size > index) {                          // check whether  
the size is large enough
                 break;
             }

             // try again
         }

         return super.opIndex(index);
     }
}

FactorialTable factorialTable;

static this() {
     factorialTable = new FactorialTable();
}

real logFactorial(uint n) {
    return factorialTable[n];
}

Use anything at your will.
NOTE: not tested
Jul 13 2008
prev sibling parent Jason House <jason.james.house gmail.com> writes:
I think the following should work.  Note the use of a temporary when
rebuilding the table and the two volatile variables.


real logFactorial(uint n) {
    static volatile real* factorial_table = ([0.0L]).ptr;
    static volatile size_t length = 1;
    //Length is guaranteed to never decrease.
    //At least at an abstract level, the synchronized part is guaranteed
    to //only write to elements >= length.
    if(length > n) {  // Length can only get larger
        return factorial_table[n]; // factorial_table can only get longer
    }
    synchronized {
      if (n >= length){
        real* new_factorial_table
        if(capacity(factorial_table) < (n + 1) * real.sizeof) {
            new factorial_table = cast(real*) realloc(factorial_table, 
            (n + 1) * real.sizeof);
        }
        else {
            new_factorial_table = factorial_table;
        }
        for(uint i = length; i<=n; i++) {
            new_factorial_table[i] = factorial_table[i-1] + log2(i);
        }
        factorial_table = new_factorial_table; // safe, length too short
        length = n; // safe now that factorial_table is set
      }
    }
    return factorial_table[n];
}



dsimcha wrote:


 From reading over these links, it makes sense to me why my previous
 implementation would not work. However, the articles, which were written
 with C++, not D, in
 mind, recommend using the volatile keyword to solve this.  In D, volatile
 is deprecated, even though, according to microbenchmarks I just tried, it
 has much
 less overhead than synchronized.  I also understand from reading previous
 forum
 posts that it applies to statements, not variables.  If my understanding
 of volatile is correct, my function could be made correct as follows, by
 simply inserting a volatile at the statement that reads factorial_table*.
 
 real logFactorial(uint n) {
     static real* factorial_table = ([0.0L]).ptr;
     static size_t length = 1;
     //Length is guaranteed to never decrease.
     //At least at an abstract level, the synchronized part is guaranteed
     to //only write to elements >= length.
     if(length > n) {  //Length can only get larger, cached length is fine.
         volatile real result = factorial_table[n]; //Doesn't use cached
 factorial_table*
         return result;
     }
     synchronized {
         if(capacity(factorial_table) < (n + 1) * real.sizeof) {
             //Is it safe to update the factorial_table pointer like this?
             factorial_table = cast(real*) realloc(factorial_table, (n + 1)
             *
 real.sizeof);
         }
         for(uint i = length; i<=n; i++) {
             factorial_table[i] = factorial_table[i-1] + log2(i);
         }
         //Set new length after all numbers are calculated.
         length = n;
         return factorial_table[n];
     }
 }
 
 Other than the fact that volatile is deprecated, would this be a correct
 fix?  If
 so, why is volatile deprecated?  If not, is it not correct?
Jul 12 2008