www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - popFrontExactly?

reply "monarch_dodra" <monarchdodra gmail.com> writes:
How does the community feel about having a "popFrontExactly" in 
phobos?

"popFrontN" is like "take": Safe, but more costly: It double 
checks there actually *are* "n" elements in the range, and if 
not, stops pop-ing.

When using popFrontN, more often than not, the "n" value is 
extracted from iterating the range already, so we *know* there 
are "n" elements in the range. In that case, popFrontN is 
un-necesarilly costly.

In that case, we could have "popFrontExactly", which would 
operate like "takeExactly": It would pre-assume that the *are* n 
elements, and assert otherwise.

--------
I know I've had the usecase for this in the past. Performance and 
convenience gains are there for both forward and sliceable ranges.

Should I push a pull request adding such a function (and its 
friends) to phobos? How does the group feel about such functions?
Nov 18 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, November 18, 2012 21:34:37 monarch_dodra wrote:
 Should I push a pull request adding such a function (and its
 friends) to phobos? How does the group feel about such functions?
In principle, it's a good idea, but I also worry about a proliferation of such functions. Personally, I think that I would have argued for popFrontN being popFrontExactly in the first place, but it's obviously too late for that. In probably all cases that I use popFrontN, what I'd want would be popFrontExactly (though popFrontNExactly would probably be a better name given its connection to popFrontN). So, you probably should create a pull request for it, but then you need popBackNExactly too, and possibly drop(Front)Exactly and dropBackExactly, and that's where things get a bit ugly. But given the concerns for efficiency and the prevalence of functions like popFrontN in range based code, popFrontNExactly would make good sense. - Jonathan M Davis
Nov 22 2012
parent reply "Kapps" <opantm2+spam gmail.com> writes:
On Thursday, 22 November 2012 at 13:08:56 UTC, Jonathan M Davis 
wrote:
 On Sunday, November 18, 2012 21:34:37 monarch_dodra wrote:
 Should I push a pull request adding such a function (and its
 friends) to phobos? How does the group feel about such 
 functions?
In principle, it's a good idea, but I also worry about a proliferation of such functions. Personally, I think that I would have argued for popFrontN being popFrontExactly in the first place, but it's obviously too late for that. In probably all cases that I use popFrontN, what I'd want would be popFrontExactly (though popFrontNExactly would probably be a better name given its connection to popFrontN). So, you probably should create a pull request for it, but then you need popBackNExactly too, and possibly drop(Front)Exactly and dropBackExactly, and that's where things get a bit ugly. But given the concerns for efficiency and the prevalence of functions like popFrontN in range based code, popFrontNExactly would make good sense. - Jonathan M Davis
Is it really that big an issue to have a few more methods than standard ranges would need? Before it certainly would be annoying to have to check if the range supported it, use that, and if not fake it, but now we have UFCS. It would be simple to have a basic fallback implementation of methods such as popFrontExactly, then simply use range.popFrontExactly to get the more performant one if the range supports it, and if not get the fallback. It would have to be clear in the documentation that these are optional methods however, and are recommended only if performance is required (and if the range supports it in a way that isn't simply an alternate implementation of the fallback).
Nov 22 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, November 23, 2012 03:55:21 Kapps wrote:
 Is it really that big an issue to have a few more methods than
 standard ranges would need? Before it certainly would be annoying
 to have to check if the range supported it, use that, and if not
 fake it, but now we have UFCS. It would be simple to have a basic
 fallback implementation of methods such as popFrontExactly, then
 simply use range.popFrontExactly to get the more performant one
 if the range supports it, and if not get the fallback.
 
 It would have to be clear in the documentation that these are
 optional methods however, and are recommended only if performance
 is required (and if the range supports it in a way that isn't
 simply an alternate implementation of the fallback).
You misunderstood. popFrontExactly/popFrontNExactly wouldn't be on any ranges any more than popFrontN or drop are on any ranges. They're free functions in std.range which either slice a range or call its popFront in a loop (depending on the type of range) in order to pop the appropriate number of elements off, and popFrontNExactly would be the same. It may very well be that we should add popFrontNExactly in order to get that extra efficiency gain over popFrontN in the cases where you know that the range contains at least the number of elements being popped. It's just that it's getting a bit ridiculous how many of these sorts of methods we have. If you add popFrontNExactly, you need popBackNExactly and probably drop(Front)Exactly and dropBackExactly as well. Any time that another function like this gets suggested, you end up having to add a number of similar functions, and it adds up. Its arguably a bit ridiculous to have so many functions that do almost the same thing but not quite. I think that we'll probably need to add them in this case due to efficiency concerns, but it's not without cost. We don't want too many stray functions doing almost the same thing in Phobos. - Jonathan M Davis
Nov 22 2012
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 23 November 2012 at 08:42:18 UTC, Jonathan M Davis 
wrote:
 I think that we'll probably need to add them in this case due 
 to efficiency
 concerns, but it's not without cost. We don't want too many 
 stray functions
 doing almost the same thing in Phobos.

 - Jonathan M Davis
I'd say it's all a matter of presentation. I'm sure they can all easily be regrouped into what feels like "a neat family of functions". What counts is the perceived complexity, more than the actual amount of function names. They aren't quite overloads, but it doesn't make them much more complex than, say, the "to" functions.
Nov 23 2012
prev sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
11/23/2012 9:19 AM, Jonathan M Davis пишет:
 On Friday, November 23, 2012 03:55:21 Kapps wrote:
 Is it really that big an issue to have a few more methods than
 standard ranges would need? Before it certainly would be annoying
 to have to check if the range supported it, use that, and if not
 fake it, but now we have UFCS. It would be simple to have a basic
 fallback implementation of methods such as popFrontExactly, then
 simply use range.popFrontExactly to get the more performant one
 if the range supports it, and if not get the fallback.

 It would have to be clear in the documentation that these are
 optional methods however, and are recommended only if performance
 is required (and if the range supports it in a way that isn't
 simply an alternate implementation of the fallback).
You misunderstood. popFrontExactly/popFrontNExactly wouldn't be on any ranges any more than popFrontN or drop are on any ranges. They're free functions in std.range which either slice a range or call its popFront in a loop (depending on the type of range) in order to pop the appropriate number of elements off, and popFrontNExactly would be the same. It may very well be that we should add popFrontNExactly in order to get that extra efficiency gain over popFrontN in the cases where you know that the range contains at least the number of elements being popped.
This gets interesting - how did you know it? The number of elements to pop I mean. I'd say the cases where hasLength is true and there is no slicing is quite rare. It'd be interesting to know what are these cases that it this set of helpers tries to speed up. I mean a list of: -algorithms where popFrontN is used -ranges that allow hasLength but not slicing and work with the said algorithm And I agree with Jonathan that adding a bunch of helpers should be justified. Any helper function like say 'enforce' has utility only as long as simplifies a usage of a _frequent_ enough pattern. If it simplifies/speed up certain algorithms there is no guilt in just using them internally. -- Dmitry Olshansky
Nov 23 2012
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 23 November 2012 at 15:48:04 UTC, Dmitry Olshansky 
wrote:
 11/23/2012 9:19 AM, Jonathan M Davis пишет:
 On Friday, November 23, 2012 03:55:21 Kapps wrote:
 Is it really that big an issue to have a few more methods than
 standard ranges would need? Before it certainly would be 
 annoying
 to have to check if the range supported it, use that, and if 
 not
 fake it, but now we have UFCS. It would be simple to have a 
 basic
 fallback implementation of methods such as popFrontExactly, 
 then
 simply use range.popFrontExactly to get the more performant 
 one
 if the range supports it, and if not get the fallback.

 It would have to be clear in the documentation that these are
 optional methods however, and are recommended only if 
 performance
 is required (and if the range supports it in a way that isn't
 simply an alternate implementation of the fallback).
You misunderstood. popFrontExactly/popFrontNExactly wouldn't be on any ranges any more than popFrontN or drop are on any ranges. They're free functions in std.range which either slice a range or call its popFront in a loop (depending on the type of range) in order to pop the appropriate number of elements off, and popFrontNExactly would be the same. It may very well be that we should add popFrontNExactly in order to get that extra efficiency gain over popFrontN in the cases where you know that the range contains at least the number of elements being popped.
This gets interesting - how did you know it? The number of elements to pop I mean.
Usually, either by a previous iteration, or just because it is statically know the range will have that many elements. Or that it *should* have that many elements. You could ask the question the other way around: Why would you pop a certain amount of elements, if you don't even know your range actually *holds* that many elements? Why do you even need the safeguard in the first place?
 I'd say the cases where hasLength is true and there is no 
 slicing is quite rare. It'd be interesting to know what are 
 these cases that it this set of helpers tries to speed up. I 
 mean a list of:
 -algorithms where popFrontN is used
 -ranges that allow hasLength but not slicing and work with the 
 said algorithm
What about the case of plain bidirectional ranges? That's the one that's being sped up. Still regardless of performance, the (my) motivating factor is that when you use "drop", it pretty much silently fails if your range doesn't have the amount of elements. IMO, in the long run, this makes "drop" *un*-safe...
Nov 23 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, November 23, 2012 17:01:04 monarch_dodra wrote:
 You could ask the question the other way around: Why would you
 pop a certain amount of elements, if you don't even know your
 range actually *holds* that many elements? Why do you even need
 the safeguard in the first place?
It would be easy to have a file or message format where the value of one sequence of bytes tells you how many are left or how many are in the next section. If you were going to pop those bytes without looking at them, then such a check would be necessary if you don't actually know how many bytes are left in the range (e.g. you're dealing with a simple, input range). That being said, I've never written code which used popFrontN when I didn't know how many elements were going to be popped off. If I use popFrontN, either I know the range's length, or I know that it has at least as many elements as I'm trying to pop off (because I used take on it or otherwise iterated over a part of the range). If I don't know how many elements there are to pop off, then I'm going to be popping them off one by one and checking empty - though if I relaly don't need to actually look at each element, it would arguably be better to just use popFrontN. In most cases though, if I don't know the number of elements left, then I'm probably looking at them. In any case, there _are_ cases where you could legitimately call popFrontN without knowing if there are at least n elements to pop off, but I never use it that way.
 Still regardless of performance, the (my) motivating factor is
 that when you use "drop", it pretty much silently fails if your
 range doesn't have the amount of elements. IMO, in the long run,
 this makes "drop" *un*-safe...
I don't know if we can get away with it or not (given the possibility of breaking code), but given that drop doesn't return how many elements were popped (unlike popFrontN), I'd favor simply making it drop the exact number of elements. Then if you wanted popFrontExactly, you could just do range = drop(range, n); It's slightly less efficient (assuming that the optimizer doesn't help you out), but it avoids having to create a new function. It was already one of Andrei's complaints about drop when it was introduced that there was no way to determine how many elements were actually dropped, so he might favor the idea of making drop assert that it drops the correct number of elements rather than using popFrontN. The one concern would be whether making that change would break any code. Given that you can't know how many elements were actually dropped and the fact that I suspect most of us don't call popFrontN unless we know that there were at least that many elements to drop, the amount of code broken might be negligle if not outright 0. But we don't want to break code, so that may just not be an option. Still, if we can't do that, and we're trying to minimize the number of stray functions in std.range, then we could just create drop(Front)Exactly and dropBackExactly and let people do range = dropExactly(range, 5); if they want popFrontExactly. - Jonathan M Davis
Nov 23 2012
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Friday, 23 November 2012 at 21:18:57 UTC, Jonathan M Davis 
wrote:
 Still, if we can't do that, and we're trying to minimize the 
 number of stray
 functions in std.range, then we could just create 
 drop(Front)Exactly and
 dropBackExactly and let people do

 range = dropExactly(range, 5);

 if they want popFrontExactly.

 - Jonathan M Davis
Well, if the goal was reducing the amount of functions, or avoiding hard to grasp variants, then I'd agree. But in this case, the goal (IMO) is to provide convenient and intuitive tools for coding. I think (but this is my point of view), that while there are several different names and variants, it all remains in a simple and comprehensive package. The function names alone are enough to know what it does, and it's not like there are any "traps", or things where you'd need to read documentation 10 minutes to understand *why* there are different functions. I don't see it as a problem to have all these functions, but that's my point of view.
Nov 26 2012
prev sibling parent Tobias Pankrath <lists pankrath.net> writes:
 I think that we'll probably need to add them in this case due to efficiency
 concerns, but it's not without cost. We don't want too many stray functions
 doing almost the same thing in Phobos.

 - Jonathan M Davis
Better to have them in phobos instead of every ones own little helper library. And I would call in popFrontExactly, not popFrontNExactly. The latter is just hard to read and unnecessarily so.
Nov 23 2012
prev sibling parent reply "Mehrdad" <wfunction hotmail.com> writes:
I wouldn't mind also adding a popFrontApproximately()

=P
Nov 23 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, November 24, 2012 07:43:26 Mehrdad wrote:
 I wouldn't mind also adding a popFrontApproximately()
 
 =P
So, what's it do? Randomly pick a number close to the number that you give it and try to pop that many? :) - Jonathan M Davis
Nov 23 2012
parent "Mehrdad" <wfunction hotmail.com> writes:
On Saturday, 24 November 2012 at 06:50:43 UTC, Jonathan M Davis 
wrote:
 On Saturday, November 24, 2012 07:43:26 Mehrdad wrote:
 I wouldn't mind also adding a popFrontApproximately()
 
 =P
So, what's it do? Randomly pick a number close to the number that you give it and try to pop that many? :) - Jonathan M Davis
That's an implementation detail.
Nov 23 2012