Two points:<br><br>1. I generally consider making copying arbitrarily expensive via this(this) to be a <b>terrible</b> practice that we shouldn't bend over backwards to support efficiently. Using this(this) to give eager value semantics is a holdover from C++, where objects must have a clear owner and aliasing must be controlled due to lack of GC. In a GC'd language containers should have reference semantics with explicit duplication. The proper use of this(this) is for simple O(1) things like reference counting. My general feeling is that range definitions are getting too complex to support a corner case.<br>
<br>2. What's the difference between moveFront(Widget rhs) and front(Widget rhs)? I understand the difference for the case of moveFront() vs. front(), but not for the assignment case.<br><br>Ignoring the complexities of this(this)-related stuff, though, I definitely like the work on sealed containers, etc.<br>
<br>--Dave<br><br><div class="gmail_quote">On Tue, Aug 17, 2010 at 1:57 PM, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:andrei@erdani.com">andrei@erdani.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Apologies for the late answer (the message is from 2009!). This is about David Simcha's thoughts on improving std.range.Zip. In spite of its lateness, the response is rather timely for the ongoing discussion of lockstep().<br>
<br>
Zip was indeed a kludge because it required algorithms to be modified to recognize it. Now I think we have a general method for expressing types that should be assignable and swappable, yet don't expose references.<br>
<br>
The problem<br>
===========<br>
<br>
We want to define read and write methods for e.g. the front of a range. In addition we also want to swap a front of a range with another object of the same type without incurring unnecessary copies. This is because copying objects can be arbitrarily expensive due to this(this).<br>
<br>
If all ranges exposed references, that all would be simple because access to objects is immediate. Yet some ranges don't want to expose references to their internals. I define below such ranges as "sealed ranges". Example of non-sealed range:<br>
<br>
struct NonSealed {<br>
@property bool empty();<br>
@property ref Widget front();<br>
void popFront();<br>
}<br>
<br>
struct Sealed {<br>
@property bool empty();<br>
@property Widget front();<br>
void popFront();<br>
}<br>
<br>
Solution<br>
========<br>
<br>
Sealed ranges must define additional members as follows:<br>
<br>
struct Sealed {<br>
@property bool empty();<br>
@property Widget front();<br>
@property void front(Widget rhs);<br>
@property Widget moveFront(Widget rhs);<br>
void popFront();<br>
}<br>
<br>
Similarly, if a range offers back() it should also offer back(Widget) and moveBack(). Finally, if a range offers opIndex(), it should also offer opIndeAssign(), opIndexOpAssign(), and Widget moveAt(size_t).<br>
<br>
These three routines are all that's needed for implementing a host of efficient algorithms, starting of course with swap. I've already changed std.algorithm.swap and many other functions in std.algorithm to support this new concept. (I think most of these changes are not yet committed.) I haven't yet updated e.g. Zip.<br>
<br>
I have followed a very similar pattern in std.container, which I'll check in soon.<br>
<br>
Any comments, please chime in.<br><font color="#888888">
<br>
<br>
Andrei</font><div><div></div><div class="h5"><br>
<br>
On 11/13/2009 11:08 AM, David Simcha wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I was thinking about std.range.Zip and ways to improve it. It would be<br>
really nice if we could give Zip assignable elements because right now,<br>
sorting of it works by a bunch of special-case ad-hockery. Furthermore,<br>
Andrei has mentioned the need for a stable O(N log N) sort in Phobos.<br>
The most obvious (and possibly the only) algorithm is a merge sort, but<br>
this can only be done (AFAIK) if you have assignable elements, not just<br>
swappable elements. Using some magic of postblits and opAssign, I think<br>
we can get assignable elements to work with Zip. First of all, there<br>
should be two kinds of Proxy structs: A value one and a reference one.<br>
This information would be stored in a flag in each instance. The compile<br>
time type would be the same. The values and the pointers would be stored<br>
together in a union. It would look something like this:<br>
<br>
struct Proxy {<br>
union {<br>
staticMap!(pointers, R) ptrs;<br>
R vals;<br>
}<br>
<br>
bool isReference; // Always true if this is stored inside a Zip.<br>
this(this) {<br>
if(isReference) {<br>
// Overwrite pointers with values.<br>
isReference = false;<br>
}<br>
}<br>
<br>
void opAssign(ref Proxy rhs) {<br>
if(isReference) {<br>
// Assign the values of <a href="http://rhs.at" target="_blank">rhs.at</a>!(0)...<br>
// <a href="http://rhs.at" target="_blank">rhs.at</a>!(rhs.length) to the deref<br>
// ptrs.<br>
} else {<br>
// Assign rhs's values to vals.<br>
}<br>
}<br>
<br>
auto at(int index)() {<br>
if(isReference) {<br>
return *(ptrs[index]);<br>
} else {<br>
return vals[index];<br>
}<br>
}<br>
}<br>
<br>
Then, the standard swap algorithm would work. Assuming random access:<br>
<br>
auto temp = myZip[index1]; // Postblit makes this a value proxy.<br>
myZip[index1] = myZip[index2]; // Writes to dereferences in myZip[index1].<br>
myZip[index2] = temp; // Writes to dereferences in myZip[index2].<br>
<br>
Furthermore, you could store Proxy structs in an array as a buffer, etc.<br>
and it would (I think) just work. Yes, there would be some performance<br>
cost to all this branching and postblitting, but IMHO it's worth it to<br>
make Zip work the way that people who don't understand the<br>
implementation details would expect it to work.<br>
<br>
The only problem I see is uninitialized Proxy objects:<br>
<br>
Proxy proxy = void;<br>
proxy = myZip[5];<br>
</blockquote></div></div><div><div></div><div class="h5">
_______________________________________________<br>
phobos mailing list<br>
<a href="mailto:phobos@puremagic.com" target="_blank">phobos@puremagic.com</a><br>
<a href="http://lists.puremagic.com/mailman/listinfo/phobos" target="_blank">http://lists.puremagic.com/mailman/listinfo/phobos</a><br>
</div></div></blockquote></div><br>