www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - opIndex, opSlice, length for joiner?

reply Maverick Chardet <chardetm gmail.com> writes:
Hi everyone,

After reading the thread "Distributed Memory implementation": 
http://forum.dlang.org/post/oqcfifzolmolcvyupsef forum.dlang.org

And more precisely the suggestion of Dragos Carp on page 2: 
http://forum.dlang.org/post/txgabyyoutitketlpvgm forum.dlang.org

I looked at the joiner source code 
(std.algorithm.iteration.joiner) and I have several ideas to make 
it have the opIndex, opSlice and length methods under certain 
conditions.

First question: what do you think of making this possible if all 
the considered ranges have opIndex, opSlice and length? I think 
that all the ranges types don't have to all implement the three 
methods in all cases (for instance length would actually only 
require ElementType!RoR and Separator to implement length) but we 
can discuss all that later...

The most important issue that comes to my mind is that the 
operations would not take constant time... A trivial 
implementation would be in O(k) where k is the number of joined 
ranges, and with some precomputation in O(k) time and space we 
can make length O(1) and opIndex and opSlice O(log k)... Would 
that be a problem?

Thank you in advance for your remarks!
Jan 20
next sibling parent Jack Stouffer <jack jackstouffer.com> writes:
On Wednesday, 20 January 2016 at 17:36:29 UTC, Maverick Chardet 
wrote:
 The most important issue that comes to my mind is that the 
 operations would not take constant time... A trivial 
 implementation would be in O(k) where k is the number of joined 
 ranges, and with some precomputation in O(k) time and space we 
 can make length O(1) and opIndex and opSlice O(log k)... Would 
 that be a problem?
I definitely think you should open a PR with your ideas regardless of what people say in this thread. Secondly, giving the user more options than he/she had before can't really be a bad thing, even if the options aren't perfect. That is, if you clearly document the trade-offs in the documentation. But I am saying this before I see the code, so I can't really say one way or the other.
Jan 20
prev sibling next sibling parent Ilya <ilyayaroshenko gmail.com> writes:
On Wednesday, 20 January 2016 at 17:36:29 UTC, Maverick Chardet 
wrote:
 Hi everyone,

 After reading the thread "Distributed Memory implementation": 
 http://forum.dlang.org/post/oqcfifzolmolcvyupsef forum.dlang.org

 And more precisely the suggestion of Dragos Carp on page 2: 
 http://forum.dlang.org/post/txgabyyoutitketlpvgm forum.dlang.org

 I looked at the joiner source code 
 (std.algorithm.iteration.joiner) and I have several ideas to 
 make it have the opIndex, opSlice and length methods under 
 certain conditions.

 First question: what do you think of making this possible if 
 all the considered ranges have opIndex, opSlice and length? I 
 think that all the ranges types don't have to all implement the 
 three methods in all cases (for instance length would actually 
 only require ElementType!RoR and Separator to implement length) 
 but we can discuss all that later...

 The most important issue that comes to my mind is that the 
 operations would not take constant time... A trivial 
 implementation would be in O(k) where k is the number of joined 
 ranges, and with some precomputation in O(k) time and space we 
 can make length O(1) and opIndex and opSlice O(log k)... Would 
 that be a problem?

 Thank you in advance for your remarks!
O(K) looks OK for joiner. However this will cause additional performance problem because a couple of Phobos algorithm assumes that opIndex is fast as front+popFront. Perhaps a special UDA can be introduced, something like optimized("forward range"). See also `byElement` for multidimensional random access slices. It has opIndex and slicing. https://github.com/D-Programming-Language/phobos/blob/v2.070.0-b2/std/experimental/ndslice/selection.d#L893 Ilya
Jan 20
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Wednesday, 20 January 2016 at 17:36:29 UTC, Maverick Chardet 
wrote:
 The most important issue that comes to my mind is that the 
 operations would not take constant time... A trivial 
 implementation would be in O(k) where k is the number of joined 
 ranges, and with some precomputation in O(k) time and space we 
 can make length O(1) and opIndex and opSlice O(log k)... Would 
 that be a problem?
The various range primitives all need to be O(1). We need to be able to rely on the big-o complexity of the primitives used by ranges, or the performance of various algorithms will tank when used with ranges that don't stick to the expected big-o complexities. So, if a range type cannot provide a primitive as O(1), it should not provide that primitive. If that weren't the case, then we'd have stuff like length, opIndex, and opSlice for narrow strings, but we don't. std.container lists the algorithmic complexity for its various operations for the same reason, and as I understand it, its replacement that Andrei is working on is going to do the same. - Jonathan M Davis
Jan 20
parent Maverick Chardet <chardetm gmail.com> writes:
Thank you all for your comments! I'm not making a PR for now 
because however I implement this, there will be complexity issues 
that need to be discussed...

On Wednesday, 20 January 2016 at 20:23:08 UTC, Jonathan M Davis 
wrote:
 On Wednesday, 20 January 2016 at 17:36:29 UTC, Maverick Chardet 
 wrote:
 The most important issue that comes to my mind is that the 
 operations would not take constant time... A trivial 
 implementation would be in O(k) where k is the number of 
 joined ranges, and with some precomputation in O(k) time and 
 space we can make length O(1) and opIndex and opSlice O(log 
 k)... Would that be a problem?
The various range primitives all need to be O(1). We need to be able to rely on the big-o complexity of the primitives used by ranges, or the performance of various algorithms will tank when used with ranges that don't stick to the expected big-o complexities. So, if a range type cannot provide a primitive as O(1), it should not provide that primitive. If that weren't the case, then we'd have stuff like length, opIndex, and opSlice for narrow strings, but we don't. std.container lists the algorithmic complexity for its various operations for the same reason, and as I understand it, its replacement that Andrei is working on is going to do the same. - Jonathan M Davis
That makes sense, so it won't happen unless we can make all of them run in O(1) time right? And this seems hopeless to me, even if all ranges are random access and implement opIndex, opSlice and length... Maybe with some precomputing in O(k) or O(n) (with k the number of ranges and n the total number of elements) with some fancy data structure? But the whole thing would lose a lot of interest with a precomputing in O(n) time, appart from the syntaxic point of view... Maverick Chardet
Jan 20
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 01/20/2016 12:36 PM, Maverick Chardet wrote:
 Hi everyone,

 After reading the thread "Distributed Memory implementation":
 http://forum.dlang.org/post/oqcfifzolmolcvyupsef forum.dlang.org

 And more precisely the suggestion of Dragos Carp on page 2:
 http://forum.dlang.org/post/txgabyyoutitketlpvgm forum.dlang.org

 I looked at the joiner source code (std.algorithm.iteration.joiner) and
 I have several ideas to make it have the opIndex, opSlice and length
 methods under certain conditions.

 First question: what do you think of making this possible if all the
 considered ranges have opIndex, opSlice and length? I think that all the
 ranges types don't have to all implement the three methods in all cases
 (for instance length would actually only require ElementType!RoR and
 Separator to implement length) but we can discuss all that later...

 The most important issue that comes to my mind is that the operations
 would not take constant time... A trivial implementation would be in
 O(k) where k is the number of joined ranges, and with some
 precomputation in O(k) time and space we can make length O(1) and
 opIndex and opSlice O(log k)... Would that be a problem?

 Thank you in advance for your remarks!
Thanks for askin. Consider chain(), which currently DOES offer random access if its constituents to. In that case, the number of ranges chained is a compile-time constant dictated by the source code being compiled; no data dependency. In contrast, the performance of joiner()'s proposed primitives would be dependent on the data. For your simplest example, length would be linear in the number of ranges. One way to improve on that would be to compute length upon the first call and then memoize (and update) it. There is a risk it could go out of sync if someone changes the ranges involved surreptitiously. One good thing to do here would be to specialize joiner().walkLength. Then people writing r.walkLength would benefit from the quicker specialized version. For indexed access, things get a fair amount more complicated. You can't afford linear time, so you need some serious data structure to ensure good performance there. That seems to take joiner() in a design space that makes it less attractive; currently it's a simple spec with a somewhat straightforward implementation. Andrei
Jan 20
parent reply Maverick Chardet <chardetm gmail.com> writes:
On Thursday, 21 January 2016 at 01:22:43 UTC, Andrei Alexandrescu 
wrote:
 Thanks for askin. Consider chain(), which currently DOES offer 
 random access if its constituents to. In that case, the number 
 of ranges chained is a compile-time constant dictated by the 
 source code being compiled; no data dependency.

 In contrast, the performance of joiner()'s proposed primitives 
 would be dependent on the data. For your simplest example, 
 length would be linear in the number of ranges. One way to 
 improve on that would be to compute length upon the first call 
 and then memoize (and update) it. There is a risk it could go 
 out of sync if someone changes the ranges involved 
 surreptitiously.

 One good thing to do here would be to specialize 
 joiner().walkLength. Then people writing r.walkLength would 
 benefit from the quicker specialized version.

 For indexed access, things get a fair amount more complicated. 
 You can't afford linear time, so you need some serious data 
 structure to ensure good performance there. That seems to take 
 joiner() in a design space that makes it less attractive; 
 currently it's a simple spec with a somewhat straightforward 
 implementation.


 Andrei
Thank you for your remarks! I just finished to implement the specialized version of walkLength (this was a great idea), I just have to write a few comments and clever unittests before the PR, I may send it later today or tomorrow! Just a question: is it possible for a range to be considered infinite and at the same time have a length? I suppose that if it is possible, such a range would be ill-formed... I'm asking because for my specialized version to compile in the case where there is no separator, I require hasLength!(ElementType!RoR) (otherwise the specialization is useless), and I'm wondering wether testing for !isInfinite!(ElementType!RoR) for the version with no "upTo" parameter is useful or not at all... Maverick Chardet
Jan 21
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 01/21/2016 05:22 PM, Maverick Chardet wrote:
 Just a question: is it possible for a range to be considered infinite
 and at the same time have a length? I suppose that if it is possible,
 such a range would be ill-formed...
Indeed that range would be ill-formed. -- Andrei
Jan 21
parent reply Maverick Chardet <chardetm gmail.com> writes:
On Friday, 22 January 2016 at 01:02:10 UTC, Andrei Alexandrescu 
wrote:
 On 01/21/2016 05:22 PM, Maverick Chardet wrote:
 Just a question: is it possible for a range to be considered 
 infinite
 and at the same time have a length? I suppose that if it is 
 possible,
 such a range would be ill-formed...
Indeed that range would be ill-formed. -- Andrei
Okay so I'll just use an assert! Something is bothering me though, I'm wondering why walkLength does not save the range when possible (when it is an input range)? For now it's just making a copy, couldn't it be problematic in some cases? The current code is: auto walkLength(Range)(Range range) if (isInputRange!Range && !isInfinite!Range) { static if (hasLength!Range) return range.length; else { size_t result; for ( ; !range.empty ; range.popFront() ) ++result; return result; } } Why not something like this: auto walkLength(Range)(const ref Range range) if (isInputRange!Range && !isInfinite!Range) { static if (hasLength!Range) return range.length; else { size_t result; static if (isForwardRange!range) { Range rangeCopy = range.save; } else { Range rangeCopy = range; } for ( ; !rangeCopy.empty ; rangeCopy.popFront() ) ++result; return result; } } Maverick Chardet
Jan 22
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, 22 January 2016 at 10:18:20 UTC, Maverick Chardet 
wrote:
 On Friday, 22 January 2016 at 01:02:10 UTC, Andrei Alexandrescu 
 wrote:
 On 01/21/2016 05:22 PM, Maverick Chardet wrote:
 Just a question: is it possible for a range to be considered 
 infinite
 and at the same time have a length? I suppose that if it is 
 possible,
 such a range would be ill-formed...
Indeed that range would be ill-formed. -- Andrei
Okay so I'll just use an assert! Something is bothering me though, I'm wondering why walkLength does not save the range when possible (when it is an input range)? For now it's just making a copy, couldn't it be problematic in some cases? The current code is: auto walkLength(Range)(Range range) if (isInputRange!Range && !isInfinite!Range) { static if (hasLength!Range) return range.length; else { size_t result; for ( ; !range.empty ; range.popFront() ) ++result; return result; } } Why not something like this: auto walkLength(Range)(const ref Range range) if (isInputRange!Range && !isInfinite!Range) { static if (hasLength!Range) return range.length; else { size_t result; static if (isForwardRange!range) { Range rangeCopy = range.save; } else { Range rangeCopy = range; } for ( ; !rangeCopy.empty ; rangeCopy.popFront() ) ++result; return result; } }
Arguably, walkLength shouldn't even accept a range that isn't a forward range, since if it's not, then walkLength is just going to eat the range. As for calling save, there's no point. It's too late as soon as you've passed the range into the function, since that copied the range, which is undefined behavior due to the fact that the exact semantics of copying a range vary wildly depending on how a range is implemented. In generic code, if you want to use a range after passing it to a function, you have to call save and pass that to the function; otherwise, you get undefined behavior when you do anything with the range after passing it to the function. Also, I would point out that passing by const ref isn't going to work. The range would be const, so you couldn't iterate over it (and save returns the exact same type as the range, so it wouldn't remove const even if it could - at it probably can't anyway). And if the function takes the range by ref, then it will consume it, which you really don't want. Calling save would get around that problem, but then you'd still have the problem that the function wouldn't accept rvalues, which would be highly annoying. - Jonathan M Davis
Jan 22
parent reply Maverick Chardet <chardetm gmail.com> writes:
On Friday, 22 January 2016 at 11:23:05 UTC, Jonathan M Davis 
wrote:
 Arguably, walkLength shouldn't even accept a range that isn't a 
 forward range, since if it's not, then walkLength is just going 
 to eat the range. As for calling save, there's no point. It's 
 too late as soon as you've passed the range into the function, 
 since that copied the range, which is undefined behavior due to 
 the fact that the exact semantics of copying a range vary 
 wildly depending on how a range is implemented. In generic 
 code, if you want to use a range after passing it to a 
 function, you have to call save and pass that to the function; 
 otherwise, you get undefined behavior when you do anything with 
 the range after passing it to the function.
Yes actually this was my point, why not forcing the range to be a forward range? The only advantage I see is that it allows to count the number of elements of an input range, but then I guess it would need to be mentioned in the documentation somewhere, what do you think? Yes my code is wrong sorry about that, I was just trying to figure out how to force the saving in some way...
Jan 22
parent reply Maverick Chardet <chardetm gmail.com> writes:
And coming back to the specialized version of walkLength: in the 
case where joiner does not implement save, should I still allow 
the specialized version? (and in this case do what: consume the 
range, make a copy of "this" and hope for the best, something 
else?)

Maverick Chardet
Jan 22
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 01/22/2016 07:59 AM, Maverick Chardet wrote:
 And coming back to the specialized version of walkLength: in the case
 where joiner does not implement save, should I still allow the
 specialized version? (and in this case do what: consume the range, make
 a copy of "this" and hope for the best, something else?)

 Maverick Chardet
walkLength is what walkLength does: it accepts even an input range and has the discretion to consume it. So let them eat cake. -- Andrei
Jan 22