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.

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)

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!

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

"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!

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?

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?

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

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?

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