On Mon, Nov 1, 2010 at 1:39 PM, Michel Fortin <michel.fortin at michelf.com>wrote:

>
> Is "i++" really atomic when i is a size_t? I though it was a read-modify-write operation. The read might be atomic, the write might be atomic, but the whole isn't. And in addition to atomicity, it needs to be sequentially consistent unless we change the GC to keep threads frozen while calling the destructors.
>
>
In theory it could be read-modify-write because you never know if some incredibly stupid compiler will do something like:

mov EAX, [someAddress];
inc EAX;
mov [someAddress], EAX;

instead of just:

inc [someAddress];

However, I'm pretty sure the second form is atomic, and even if it's not formally guaranteed, any reasonable compiler would use the single inc instruction form.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20101101/086bcfec/attachment.html>

On 11/1/2010 10:39 AM, Michel Fortin wrote:
> Le 2010-11-01 ? 12:30, David Simcha a ?crit :
> 
>> Can someone please fill me in?  Despite Michael Fortin's repeated attempts to explain it, I still don't understand how the status quo could generate a race condition under reasonable, real-world scenarios.  As I understand it (please correct whatever reasoning is wrong):
>>
>> 1.  Incrementing/decrementing a size_t is atomic (i.e. has no intermediate state) on x86 and probably just about any other arch.  It is not, however, guaranteed sequentially consistent unless you use the lock instruction.
>>
> 
>> 2.  Stopping the world to do GC acts as an implicit fence.  If it didn't, then GC would be horribly broken.  This means that all refcount increments/decrements that happened in the owner thread should be visible to the collecting thread upon starting a collection.
>>
>> 3.  You'd need some kind of fence (explicit or implicit) on terminating GC anyhow, to make data structures updated by the GC thread visible to all threads, thus making any increment/decrement of the reference count field done in the GC thread visible to all threads.
> 
> 
> The current GC stops other threads only during mark and sweep, it then restarts the other threads and after that it call destructors. That could be changed, but it'd stop the world for a little longer.
> 
> Is "i++" really atomic when i is a size_t? I though it was a read-modify-write operation. The read might be atomic, the write might be atomic, but the whole isn't. And in addition to atomicity, it needs to be sequentially consistent unless we change the GC to keep threads frozen while calling the destructors.
> 
> One option to avoid atomic ops would be to make the GC call destructors in the thread that owns the object, but for that you have to figure out which thread owns what and postpone destruction until that thread allocates new memory from the GC again. And this approach won't work for immutable objects anyway: they're implicitly shared.
> 

Not relevant.  In either case the memory is still referenced so won't be released.

Increment is not atomic on most processors, including x86 (inc [someAddress] does not exist).

Andrei

On 11/1/10 12:49 PM, David Simcha wrote:
>
>
> On Mon, Nov 1, 2010 at 1:39 PM, Michel Fortin <michel.fortin at michelf.com <mailto:michel.fortin at michelf.com>> wrote:
>
>
>     Is "i++" really atomic when i is a size_t? I though it was a
>     read-modify-write operation. The read might be atomic, the write
>     might be atomic, but the whole isn't. And in addition to atomicity,
>     it needs to be sequentially consistent unless we change the GC to
>     keep threads frozen while calling the destructors.
>
>
> In theory it could be read-modify-write because you never know if some incredibly stupid compiler will do something like:
>
> mov EAX, [someAddress];
> inc EAX;
> mov [someAddress], EAX;
>
> instead of just:
>
> inc [someAddress];
>
> However, I'm pretty sure the second form is atomic, and even if it's not formally guaranteed, any reasonable compiler would use the single inc instruction form.
>
>
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

On 11/1/10 10:22 AM, Masahiro Nakagawa wrote:
> On Mon, 01 Nov 2010 13:21:23 +0900, Andrei Alexandrescu <andrei at erdani.com> wrote:
>
>> Alright, then how do we solve refcounting of constant objects (see Michel Fortin's question)? My solution involves casting away const and keeping immutability information at runtime. Is that acceptable?
>
> Your approach seems to be C++'s mutable. I am acceptable.
>
> You said "There are several solutions possible" on digitalmars.D. Can you show the example of other solutions?

One other solution is to simply say

@refcounted struct Widget { ... }

and let the compiler take care of everything.

> "the compiler knowing about the idiom" means Python-like approach? If so, I think such approach makes the compiler more complex :(

I agree.


Andrei

On Mon, 01 Nov 2010 14:32:39 -0400, Andrei Alexandrescu <andrei at erdani.com> wrote:
> Increment is not atomic on most processors, including x86 (inc [someAddress] does not exist).
>
> Andrei

Umm, inc [address] does exits. However, in order to make it atomic, you're supposed to use the lock prefix. I.e.

ref int atomic_inc(ref int value) {
     asm {
         lock;				// Makes this instruction atomic.
         inc [EAX];			 // implicit pointer type
         //inc int ptr [EAX]; // explicit pointer type
     }
}

----- Original Message ----
> From: Brad Roberts <braddr at puremagic.com>
> To: phobos at puremagic.com
> Sent: Mon, November 1, 2010 1:51:34 PM
> Subject: Re: [phobos] Fwd: Re: Ruling out arbitrary cost copy construction?
> 
> On 11/1/2010 10:39 AM, Michel Fortin wrote:
> > Le 2010-11-01 ? 12:30, David  Simcha a ?crit :
> > 
> >> Can someone please fill me in?   Despite Michael Fortin's repeated attempts to explain it, I still  don't understand how the status quo could generate
a
> >> race condition  under reasonable, real-world scenarios.  As I understand it
> >>  (please correct whatever reasoning is wrong):
> >>
> >> 1.   Incrementing/decrementing a size_t is atomic (i.e. has no
intermediate
> >> state) on x86 and probably just about any other  arch.  It is not, however, guaranteed sequentially consistent  unless you use the lock instruction.
> >>
> > 
> >> 2.   Stopping the world to do GC acts as an implicit fence.  If it  didn't, then GC would be horribly broken.  This means that all  refcount increments/decrements that happened in the owner thread  should be visible
>to
> >> the collecting thread upon starting a  collection.
> >>
> >> 3.  You'd need some kind of fence  (explicit or implicit) on terminating GC anyhow, to make data  structures updated by the GC thread visible to all threads, thus  making any increment/decrement of the reference count field done in  the GC thread visible to all threads.
> > 
> > 
> > The current GC  stops other threads only during mark and sweep, it then
>restarts the other  threads and after that it call destructors. That could be changed, but it'd stop  the world for a little longer.
> > 
> > Is "i++" really atomic when i is  a size_t? I though it was a
>read-modify-write operation. The read might be  atomic, the write might be atomic, but the whole isn't. And in addition to  atomicity, it needs to be sequentially consistent unless we change the GC to  keep threads frozen while calling the destructors.
> > 
> > One option  to avoid atomic ops would be to make the GC call destructors in
>the thread that  owns the object, but for that you have to figure out which thread owns what and  postpone destruction until that thread allocates new memory from the GC again.  And this approach won't work for immutable objects anyway: they're implicitly  shared.
> > 
> 
> Not relevant.  In either case the memory is still  referenced so won't be
>released.

Yes it is.  The item being destroyed is not the refcounted item, but the reference to the refcounted item.

For instance, imagine a File member of a class object.  The File's destructor is called when the object is destroyed in the GC, so it decrements the ref count in the File struct, which could have a race with a thread which has a stack-based File struct going out of scope.

I thought the GC does only mark with the world stopped, and then does sweep and destructors after restarting the threads?  I somewhat remember the conversation that we had on Tango IRC when Sean changed it.  It was introduced to fix a very real problem -- if the destructors called some C code that tried to acquire a lock that a stopped thread currently held, there would be a deadlock (this was happening to someone, which is what prompted the discussion).  I don't think we can go back.

-Steve

Le 2010-11-01 ? 14:39, Andrei Alexandrescu a ?crit :

> On 11/1/10 10:22 AM, Masahiro Nakagawa wrote:
>> On Mon, 01 Nov 2010 13:21:23 +0900, Andrei Alexandrescu <andrei at erdani.com> wrote:
>> 
>>> Alright, then how do we solve refcounting of constant objects (see Michel Fortin's question)? My solution involves casting away const and keeping immutability information at runtime. Is that acceptable?
>> 
>> Your approach seems to be C++'s mutable. I am acceptable.
>> 
>> You said "There are several solutions possible" on digitalmars.D. Can you show the example of other solutions?
> 
> One other solution is to simply say
> 
> @refcounted struct Widget { ... }
> 
> and let the compiler take care of everything.

I think that'd be better. If later you make the optimizer aware that the 'retain' and 'release' operations cancel each other, then a lot of them might simply vanish in optimized code. And other tricks might apply too, like coalescing multiple 'retain' or 'release' into one operation where you increment/decrement the counter by more than one.

But I'm biased: having that in the compiler would also be a great service to me who is currently implementing the (reference-counted) Objective-C object model. Even better: combine that with an ARM backend and D becomes better than Objective-C for iPhone/iPad development (where garbage-collected Objective-C doesn't exist (yet) and you must call retain/release/autorelease explicitly everywhere).

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

On Mon, 1 Nov 2010, Steve Schveighoffer wrote:

> > From: Brad Roberts <braddr at puremagic.com>
> > 
> > Not relevant.  In either case the memory is still  referenced so won't be
> >released.
> 
> Yes it is.  The item being destroyed is not the refcounted item, but the reference to the refcounted item.
> 
> For instance, imagine a File member of a class object.  The File's destructor is called when the object is destroyed in the GC, so it decrements the ref count in the File struct, which could have a race with a thread which has a stack-based File struct going out of scope.
> 
> I thought the GC does only mark with the world stopped, and then does sweep and destructors after restarting the threads?  I somewhat remember the conversation that we had on Tango IRC when Sean changed it.  It was introduced to fix a very real problem -- if the destructors called some C code that tried to acquire a lock that a stopped thread currently held, there would be a deadlock (this was happening to someone, which is what prompted the discussion).  I don't think we can go back.
> 
> -Steve

I stand corrected, and you're correct. Either mode has flaws.  Restart threads before destructors and you introduce races that only exist due to the gc.  Restart after destructors and you risk deadlocks caused by the gc.

I can't remember the reference off the top of my head, but I think inc [EAX] w/o the lock prefix is atomic for weak definitions of atomic, i.e. it has no intermediate states.  However, without the lock prefix it is not sequentially consistent.

On Mon, Nov 1, 2010 at 2:47 PM, Robert Jacques <sandford at jhu.edu> wrote:

> On Mon, 01 Nov 2010 14:32:39 -0400, Andrei Alexandrescu <andrei at erdani.com> wrote:
>
>> Increment is not atomic on most processors, including x86 (inc
>> [someAddress] does not exist).
>>
>> Andrei
>>
>
> Umm, inc [address] does exits. However, in order to make it atomic, you're supposed to use the lock prefix. I.e.
>
> ref int atomic_inc(ref int value) {
>    asm {
>        lock;                           // Makes this instruction atomic.
>        inc [EAX];                       // implicit pointer type
>        //inc int ptr [EAX]; // explicit pointer type
>
>    }
> }
>
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20101101/57df72a5/attachment.html>

On Mon, 01 Nov 2010 15:53:51 -0400, David Simcha <dsimcha at gmail.com> wrote:
> I can't remember the reference off the top of my head, but I think inc
> [EAX]
> w/o the lock prefix is atomic for weak definitions of atomic, i.e. it
> has no
> intermediate states.  However, without the lock prefix it is not
> sequentially consistent.

Well, inc[EAX] is not multi-thread safe on my PC (Core i7), and every
article I've seen mentions the lock instruction. So I think lock; inc int
ptr [EAX]; is the only way to ensure all increments are seen. Also,
inc[EAX] is not implicitly a integer, but instead a byte.