Skip Menu |
Report information
Id: 130437
Status: open
Priority: 0/
Queue: perl6

Owner: Nobody
Requestors: alex.jakimenko [at] gmail.com
Cc:
AdminCc:

Severity: (no value)
Tag: (no value)
Platform: (no value)
Patch Status: (no value)
VM: (no value)



Subject: [RFC] Ranges with Infs on endpoints could be smarter ((0..Inf)[99999999999])
Download (untitled) / with headers
text/plain 367b
Consider this code: say (0..9999999999999)[9999999999] Result: 9999999999 In other words, we can calculate the value without turning the Range into a list. However: Code: say (0..Inf)[9999999999] Result: (it hangs attempting to .list it) This can be easily solved. However, the question is what should be done with other cases (e.g. (-Inf..0)[*-5] and similar)
Download (untitled) / with headers
text/plain 645b
`Range` does `Positional`: ➜ say Range.^roles' ((Positional) (Iterable)) `Positional` is the "Role for objects which support indexing them using postcircumfix:«[ ]»" (https://docs.perl6.org/type/Positional.html). This suggests that `Range` should implement the `[ ]` subscript natively so that it can complete in O(1), rather than falling back to `.list.[ ]` which makes it O(n). So maybe this is more of a performance bug/oversight than an RFC? Show quoted text
> However, the question is what should be done with other cases
I think all cases should give the same result that they do now. They just should do it in O(1) instead of O(n).
RT-Send-CC: perl6-compiler [...] perl.org
Download (untitled) / with headers
text/plain 2.2k
On Thu, 29 Dec 2016 13:49:40 -0800, smls75@gmail.com wrote: Show quoted text
> So maybe this is more of a performance bug/oversight than an RFC? > I think all cases should give the same result that they do now. > They just should do it in O(1) instead of O(n).
It's a bit more involved than that due to floating point math and its host of issues creeping up in many of the cases. The fast range observed by OP is an Int range that doesn't suffer from those. For the rest of the range types, the current complexity for many cases is not 0(n), but 0(Inf), because it just infiniloops trying to get a .succ of an element, but precision isn't available for such a fine grain. For example, .elems on range (2e89..2e100) would return Inf if it could ever complete and all elements in that range are 2e89, never reaching the end point, because there's no precision available to store +1 increment. I created a branch to play around with this ticket, but I'm already hitting issues just trying to make .elems figure out the result fast. How many elements are in ranges (2e0..2e100), (2e20..2e100), (2e40..2e100), (2e60..2e100), (2e75..2e100), and (2e85..2e100)? The answer for all of them is 2e+100 elements because of lack of precision bits. How many elements there are in range 2.000_000_000_000_001e20..2.000_000_000_000_002e20? If we do the math in our heads, we get 100_000 elements, but thanks to floating point math precision, the actual answer is ONE element, and it's 2e+20. Note that this element is LOWER than the lowest end point of the range we used. Another example is (^2e20)[*-1]. The last element is 2e20, but the end point is excluded, so what do we return?; considering (2e20-1) is still 2e20. And it'd continue to give that number as value for the next 500000 elements or so (counting from end), until it'd switch to giving 1.99999999999999e+20 as the element for another half a million elements. And most of that range is in these chunks. So is a weird, chunked, unpredictable, and at-times absolutely wrong result better than correct but slow range, that at large enough values can be made to be non-increasing, infinite, and one that hangs when you attempt to fully reify it? I think Rats can be improved, so I'll still hack around on this ticket in that scope, but I'm not so sure the Num ranges should be changed.
From: Parrot Raiser <1parrota [...] gmail.com>
Date: Wed, 11 Jan 2017 11:42:08 -0500
To: perl6-bugs-followup [...] perl.org
Subject: Re: [perl #130437] [RFC] Ranges with Infs on endpoints could be smarter ((0..Inf)[99999999999])
Download (untitled) / with headers
text/plain 429b
Show quoted text
> "So is a weird, chunked, unpredictable, and at-times absolutely wrong result better than correct but slow range, that at large enough values can be made to be non-increasing, infinite, and one that hangs when you attempt to fully reify it?"
"I'm sorry, Dave, I can't do that". In some cases, a refusal to cooperate might be the least objectionable behaviour. How much would a feasibility check beforehand affect performance?


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

For issues related to this RT instance (aka "perlbug"), please contact perlbug-admin at perl.org