Hi,

Another feature I want to implement in core.thread is cooperative suspension. In this model, the thread_suspendAll() routine flips a global variable that notifies all threads that they need to suspend. Now, a thread that has marked itself as cooperative is then expected to regularly check this variable and, when it notices that it needs to suspend, does so. This means that the suspension machinery trusts cooperative threads to read this global variable as fast as possible (note that races in reading the variable are acceptable).

The question is how the API should work. I have something like this in mind:

class Thread
{
    // ...

    private bool m_isCooperative;

    @property final bool isCooperative()
    {
        return m_isCooperative;
    }

    @property final void isCooperative(bool value)
    {
        synchronized (slock) // needed because changing this value can
affect the entire suspension process
        {
            m_isCooperative = value;
        }
    }
}

thread_suspendAll() then trivially checks Thread.m_isCooperative and makes
appropriate decisions (i.e. suspend all cooperative threads first and so
on).

Any thoughts?

Regards,
Alex

Oops, didn't send the whole thing:

__gshared bool g_shouldSuspend; // set by thread_suspendAll()

class Thread
{
    // ...

    private bool m_isCooperative;

    @property final bool isCooperative()
    {
        return m_isCooperative;
    }

    @property final void isCooperative(bool value)
    {
        synchronized (slock) // needed because changing this value can
affect the entire suspension process
        {
            m_isCooperative = value;
        }
    }

    @property static bool shouldSuspend()
    {
        return g_shouldSuspend;
    }

    final void suspendIfNeeded()
    {
        if (g_shouldSuspend) // can only race against
thread_suspendAll() setting it to false, which is ok
            suspend(this);
    }
}

Regards,
Alex

On Sat, May 5, 2012 at 6:45 AM, Alex Rønne Petersen <xtzgzorex@gmail.com> wrote:
>
> Hi,
>
> Another feature I want to implement in core.thread is cooperative suspension. In this model, the thread_suspendAll() routine flips a global variable that notifies all threads that they need to suspend. Now, a thread that has marked itself as cooperative is then expected to regularly check this variable and, when it notices that it needs to suspend, does so. This means that the suspension machinery trusts cooperative threads to read this global variable as fast as possible (note that races in reading the variable are acceptable).
>
> The question is how the API should work. I have something like this in mind:
>
> class Thread
> {
>     // ...
>
>     private bool m_isCooperative;
>
>     @property final bool isCooperative()
>     {
>         return m_isCooperative;
>     }
>
>     @property final void isCooperative(bool value)
>     {
>         synchronized (slock) // needed because changing this value can affect the entire suspension process
>         {
>             m_isCooperative = value;
>         }
>     }
> }
>
> thread_suspendAll() then trivially checks Thread.m_isCooperative and makes appropriate decisions (i.e. suspend all cooperative threads first and so on).
>
> Any thoughts?
>
> Regards,
> Alex
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

Le 2012-05-05 à 0:45, Alex Rønne Petersen a écrit :

> (note that races in reading the variable are acceptable).
> 
>    private bool m_isCooperative;
> 
>    @property final bool isCooperative()
>    {
>        return m_isCooperative;
>    }

Even if races are acceptable, the code above is buggy. You need to make the read volatile if you don't want the compiler to optimize things by reading the variable only once when the function is inlined. (And I know volatile is deprecated.)


-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/





_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

I don't follow. Why would inlining the function have any impact on how many times the variable is actually read? That seems like a totally separate issue.

Regards,
Alex

On Sat, May 5, 2012 at 3:19 PM, Michel Fortin <michel.fortin@michelf.com> wrote:
> Le 2012-05-05 à 0:45, Alex Rønne Petersen a écrit :
>
>> (note that races in reading the variable are acceptable).
>>
>>    private bool m_isCooperative;
>>
>>    @property final bool isCooperative()
>>    {
>>        return m_isCooperative;
>>    }
>
> Even if races are acceptable, the code above is buggy. You need to make the read volatile if you don't want the compiler to optimize things by reading the variable only once when the function is inlined. (And I know volatile is deprecated.)
>
>
> --
> Michel Fortin
> michel.fortin@michelf.com
> http://michelf.com/
>
>
>
>
>
> _______________________________________________
> D-runtime mailing list
> D-runtime@puremagic.com
> http://lists.puremagic.com/mailman/listinfo/d-runtime
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

Le 2012-05-05 à 10:37, Alex Rønne Petersen a écrit :

> I don't follow. Why would inlining the function have any impact on how many times the variable is actually read? That seems like a totally separate issue.

Ok, for one thing, I quoted the wrong code. I'm still unsure about isCooperative, but I meant to quote shouldSuspend and suspendIfNeeded.

    __gshared bool g_shouldSuspend; // set by thread_suspendAll()

    @property static bool shouldSuspend()
    {
        return g_shouldSuspend;
    }

    final void suspendIfNeeded()
    {
        if (g_shouldSuspend) // can only race against thread_suspendAll() setting it to false, which is ok
            suspend(this);
    }

If you inline shouldSuspend and suspendIfNeeded inside a loop in some function, here's what you get:

	int i = 0;
	while (true)
	{
		if (g_shouldSuspend)
			suspend();
		++i;
	}

Here the compiler can coalesce every read to g_shouldSuspend into a single read because it assumes g_shouldSuspend is thread local and sees no code in the loop that could potentially change the variable. Hence why you need volatile to force the compiler to always read from memory.

The optimized code would behave like this one, which is obviously not what you want:

	int i = 0;
	bool local_shouldSuspend = g_shouldSuspend; // single read from memory to a register
	while (true)
	{
		if (local_shouldSuspend)
			suspend();
		++i;
	}


-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/





_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

> Here the compiler can coalesce every read to g_shouldSuspend into a single read because it assumes g_shouldSuspend is thread local and sees no code in the loop that could potentially change the variable. Hence why you need volatile to force the compiler to always read from memory.

OK, I understand what you are getting at. A C compiler would probably make this assumption at -O3 or something. However, things aren't quite the same in D as they are in C here. In D, __gshared explicitly tells the compiler "this variable is global -- it is shared among threads -- and can change at any time". If a compiler still chooses to do the read only once, then it is generating wrong code. Keep in mind that in D, we have an explicit differentiation between thread-local and global data.

Besides, if the compiler did do this optimization, I think a lot of druntime and phobos code would break.

Regards,
Alex

On Sat, May 5, 2012 at 4:54 PM, Michel Fortin <michel.fortin@michelf.com> wrote:
> Le 2012-05-05 à 10:37, Alex Rønne Petersen a écrit :
>
>> I don't follow. Why would inlining the function have any impact on how many times the variable is actually read? That seems like a totally separate issue.
>
> Ok, for one thing, I quoted the wrong code. I'm still unsure about isCooperative, but I meant to quote shouldSuspend and suspendIfNeeded.
>
>    __gshared bool g_shouldSuspend; // set by thread_suspendAll()
>
>    @property static bool shouldSuspend()
>    {
>        return g_shouldSuspend;
>    }
>
>    final void suspendIfNeeded()
>    {
>        if (g_shouldSuspend) // can only race against thread_suspendAll() setting it to false, which is ok
>            suspend(this);
>    }
>
> If you inline shouldSuspend and suspendIfNeeded inside a loop in some function, here's what you get:
>
>        int i = 0;
>        while (true)
>        {
>                if (g_shouldSuspend)
>                        suspend();
>                ++i;
>        }
>
> Here the compiler can coalesce every read to g_shouldSuspend into a single read because it assumes g_shouldSuspend is thread local and sees no code in the loop that could potentially change the variable. Hence why you need volatile to force the compiler to always read from memory.
>
> The optimized code would behave like this one, which is obviously not what you want:
>
>        int i = 0;
>        bool local_shouldSuspend = g_shouldSuspend; // single read from memory to a register
>        while (true)
>        {
>                if (local_shouldSuspend)
>                        suspend();
>                ++i;
>        }
>
>
> --
> Michel Fortin
> michel.fortin@michelf.com
> http://michelf.com/
>
>
>
>
>
> _______________________________________________
> D-runtime mailing list
> D-runtime@puremagic.com
> http://lists.puremagic.com/mailman/listinfo/d-runtime
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

Argh:

>     final void suspendIfNeeded()
>     {
>         if (g_shouldSuspend) // can only race against
> thread_suspendAll() setting it to false, which is ok
>             suspend(this);
>     }

was meant to say "true", not "false".

Regards,
Alex

On Sat, May 5, 2012 at 6:50 AM, Alex Rønne Petersen <xtzgzorex@gmail.com> wrote:
> Oops, didn't send the whole thing:
>
> __gshared bool g_shouldSuspend; // set by thread_suspendAll()
>
> class Thread
> {
>     // ...
>
>     private bool m_isCooperative;
>
>     @property final bool isCooperative()
>     {
>         return m_isCooperative;
>     }
>
>     @property final void isCooperative(bool value)
>     {
>         synchronized (slock) // needed because changing this value can
> affect the entire suspension process
>         {
>             m_isCooperative = value;
>         }
>     }
>
>     @property static bool shouldSuspend()
>     {
>         return g_shouldSuspend;
>     }
>
>     final void suspendIfNeeded()
>     {
>         if (g_shouldSuspend) // can only race against
> thread_suspendAll() setting it to false, which is ok
>             suspend(this);
>     }
> }
>
> Regards,
> Alex
>
> On Sat, May 5, 2012 at 6:45 AM, Alex Rønne Petersen <xtzgzorex@gmail.com> wrote:
>>
>> Hi,
>>
>> Another feature I want to implement in core.thread is cooperative suspension. In this model, the thread_suspendAll() routine flips a global variable that notifies all threads that they need to suspend. Now, a thread that has marked itself as cooperative is then expected to regularly check this variable and, when it notices that it needs to suspend, does so. This means that the suspension machinery trusts cooperative threads to read this global variable as fast as possible (note that races in reading the variable are acceptable).
>>
>> The question is how the API should work. I have something like this in mind:
>>
>> class Thread
>> {
>>     // ...
>>
>>     private bool m_isCooperative;
>>
>>     @property final bool isCooperative()
>>     {
>>         return m_isCooperative;
>>     }
>>
>>     @property final void isCooperative(bool value)
>>     {
>>         synchronized (slock) // needed because changing this value can affect the entire suspension process
>>         {
>>             m_isCooperative = value;
>>         }
>>     }
>> }
>>
>> thread_suspendAll() then trivially checks Thread.m_isCooperative and makes appropriate decisions (i.e. suspend all cooperative threads first and so on).
>>
>> Any thoughts?
>>
>> Regards,
>> Alex
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

I think __gshared is treated just like static in C. You'd probably want shared.

On May 5, 2012, at 8:11 AM, Alex Rønne Petersen <xtzgzorex@gmail.com> wrote:

>> Here the compiler can coalesce every read to g_shouldSuspend into a single read because it assumes g_shouldSuspend is thread local and sees no code in the loop that could potentially change the variable. Hence why you need volatile to force the compiler to always read from memory.
> 
> OK, I understand what you are getting at. A C compiler would probably make this assumption at -O3 or something. However, things aren't quite the same in D as they are in C here. In D, __gshared explicitly tells the compiler "this variable is global -- it is shared among threads -- and can change at any time". If a compiler still chooses to do the read only once, then it is generating wrong code. Keep in mind that in D, we have an explicit differentiation between thread-local and global data.
> 
> Besides, if the compiler did do this optimization, I think a lot of druntime and phobos code would break.
> 
> Regards,
> Alex
> 
> On Sat, May 5, 2012 at 4:54 PM, Michel Fortin <michel.fortin@michelf.com> wrote:
>> Le 2012-05-05 à 10:37, Alex Rønne Petersen a écrit :
>> 
>>> I don't follow. Why would inlining the function have any impact on how many times the variable is actually read? That seems like a totally separate issue.
>> 
>> Ok, for one thing, I quoted the wrong code. I'm still unsure about isCooperative, but I meant to quote shouldSuspend and suspendIfNeeded.
>> 
>>    __gshared bool g_shouldSuspend; // set by thread_suspendAll()
>> 
>>    @property static bool shouldSuspend()
>>    {
>>        return g_shouldSuspend;
>>    }
>> 
>>    final void suspendIfNeeded()
>>    {
>>        if (g_shouldSuspend) // can only race against thread_suspendAll() setting it to false, which is ok
>>            suspend(this);
>>    }
>> 
>> If you inline shouldSuspend and suspendIfNeeded inside a loop in some function, here's what you get:
>> 
>>        int i = 0;
>>        while (true)
>>        {
>>                if (g_shouldSuspend)
>>                        suspend();
>>                ++i;
>>        }
>> 
>> Here the compiler can coalesce every read to g_shouldSuspend into a single read because it assumes g_shouldSuspend is thread local and sees no code in the loop that could potentially change the variable. Hence why you need volatile to force the compiler to always read from memory.
>> 
>> The optimized code would behave like this one, which is obviously not what you want:
>> 
>>        int i = 0;
>>        bool local_shouldSuspend = g_shouldSuspend; // single read from memory to a register
>>        while (true)
>>        {
>>                if (local_shouldSuspend)
>>                        suspend();
>>                ++i;
>>        }
>> 
>> 
>> --
>> Michel Fortin
>> michel.fortin@michelf.com
>> http://michelf.com/
>> 
>> 
>> 
>> 
>> 
>> _______________________________________________
>> D-runtime mailing list
>> D-runtime@puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/d-runtime
> _______________________________________________
> D-runtime mailing list
> D-runtime@puremagic.com
> http://lists.puremagic.com/mailman/listinfo/d-runtime
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

On May 4, 2012, at 9:45 PM, Alex Rønne Petersen wrote:

> Hi,
> 
> Another feature I want to implement in core.thread is cooperative suspension. In this model, the thread_suspendAll() routine flips a global variable that notifies all threads that they need to suspend. Now, a thread that has marked itself as cooperative is then expected to regularly check this variable and, when it notices that it needs to suspend, does so. This means that the suspension machinery trusts cooperative threads to read this global variable as fast as possible (note that races in reading the variable are acceptable).

Where would the checking be done?  I guess the user would have to call Thread.checkSuspend() or whatever at the appropriate times?
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

I have an initial version for this functionality done here: https://github.com/alexrp/druntime/commit/5b60e88ace41d2126c5754dab1eacb149a3895b3

Suggestions for improvements welcome! (And yes, I know the sleep heuristic sucks; I'll fix that later.)

The idea is simple:

Thread.getThis().isCooperative = true;

while (doWork)
{
    /* work goes here */

    if (thread_shouldSuspend())
        thread_cooperativeSuspendSync(); // or
thread_cooperativeSuspend() to just blindly continue doing work and
let thread_suspendAll() suspend at any point
}

Regards,
Alex

On Sat, May 5, 2012 at 6:45 AM, Alex Rønne Petersen <xtzgzorex@gmail.com> wrote:
> Hi,
>
> Another feature I want to implement in core.thread is cooperative suspension. In this model, the thread_suspendAll() routine flips a global variable that notifies all threads that they need to suspend. Now, a thread that has marked itself as cooperative is then expected to regularly check this variable and, when it notices that it needs to suspend, does so. This means that the suspension machinery trusts cooperative threads to read this global variable as fast as possible (note that races in reading the variable are acceptable).
>
> The question is how the API should work. I have something like this in mind:
>
> class Thread
> {
>     // ...
>
>     private bool m_isCooperative;
>
>     @property final bool isCooperative()
>     {
>         return m_isCooperative;
>     }
>
>     @property final void isCooperative(bool value)
>     {
>         synchronized (slock) // needed because changing this value can
> affect the entire suspension process
>         {
>             m_isCooperative = value;
>         }
>     }
> }
>
> thread_suspendAll() then trivially checks Thread.m_isCooperative and makes
> appropriate decisions (i.e. suspend all cooperative threads first and so
> on).
>
> Any thoughts?
>
> Regards,
> Alex
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime