On Thu, Jan 14, 2010 at 10:20 PM, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:andrei@erdani.com">andrei@erdani.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="im">Michel Fortin wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Le 2010-01-14 à 22:01, Andrei Alexandrescu a écrit :<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Michel Fortin wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Le 2010-01-14 à 18:07, Andrei Alexandrescu a écrit :<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Unfortunately, this(this) is called after the bits have been<br>
copied, so if there was any tearing, it already happened. I don't<br>
know how we can solve this.<br>
</blockquote>
Where is the copy-constructor when we need one? :-)<br>
</blockquote>
I realized that fortunately that's not a problem: during memcpy, the target is not yet shared. Whew. So it all holds water.<br>
<br>
this(this) shared { ... }<br>
<br>
should work.<br>
</blockquote>
<br>
But the source is shared. Couldn't it be updated while memcpy does its work, creating an incoherent state? Something like: memcpy copies half of it, context switch, other thread update first and last bytes, context switch, memcpy finishes its work. Result, last byte of the copy doesn't match first byte.<br>
</blockquote>
<br></div>
I just meant that we're not constrained by the memcpy prior to this(this).<br>
<br>
I don't know whether we should disallow such copies. Probably we should, but I don't have a strong case. If we disable it, cowboys will be unhappy. If we enable it, others will.<br>
<br>
The problem is, if we disable even "this(this) shared" there's no chance to copy a shared object, even if you're willing to fix the inconsistencies.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Now, the really tricky question is should this one be copyable when<br>
shared:<br>
struct D { immutable string a; long b; }<br>
Since 'a' is immutable, you don't need to copy it atomically, only<br>
'b' requires an atomic copy. So copying the struct "atomically" is<br>
possible by copying 'a' normally and 'b' atomically. Now, is that<br>
going to be supported?<br>
</blockquote>
But long isn't atomically copyable. Did you mean int?<br>
</blockquote>
<br>
Well, that depends on the architecture. I meant a type which is atomically copyable yes.<br>
</blockquote>
<br></div>
Speaking of which: is it reasonable to assume that all 32-bit modern architectures have a 64-bit atomic assign? How about 64-bit atomic CAS?<br><font color="#888888">
<br>
<br>
Andrei</font><div><div></div><div class="h5"><br>
_______________________________________________<br>
dmd-concurrency mailing list<br>
<a href="mailto:dmd-concurrency@puremagic.com" target="_blank">dmd-concurrency@puremagic.com</a><br>
<a href="http://lists.puremagic.com/mailman/listinfo/dmd-concurrency" target="_blank">http://lists.puremagic.com/mailman/listinfo/dmd-concurrency</a><br>
</div></div></blockquote></div><br>Could you create a global array of something like 256 spinlocks, and then hash the pointer to what you are trying to modify to find the right lock? The shared operation (read or write) will consist of getting the lock, accessing the object in question, then releasing the lock. This requires two CAS like operations to lock any sized object rather than one CAS for four bytes. With 256 such locks, we should be able to keep a lot of threads busy even with the occasional accidental contention.<br>
<br>The first tricky thing is how to deal with thread death during a shared operation. If you use the thread number as what is swapped into the spinlock, you can clean up when threads die.<br><br>The second tricky thing is nested objects, e.g. how can you tell if the object you are fiddling with is locked at a higher level? I think you can do so by dividing memory into non-overlapping regions (say,. cache line sized, which I think is 64 bytes) and locking all of those that the object overlaps with instead of locking by object. This multiplies the number of CAS steps for larger objects, and you need to be tricky with the hashing of the pointer (you need a hash function such that a 256 byte object can't deadlock to itself due to colliding hashes) but I think it could still work.<br>
<br>
The final bit of the design is that if your architecture can do atomic ops on objects of 8 or 16 bytes, then you
can just use a normal CAS, for that specific object. Since normal lock free designs tend to fall into the case where the compiler knows this integer <br><br>Note that some parts of the above rely on knowing the object size. This might be tricky in some special cases but usually, I would think it is available to the compiler and when it isn't you could use the GC to find it as with dynamic array expansion.<br>
<br>
Kevin<br><br>