Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Ranges with Infs on endpoints could be smarter ((0..Inf)[99999999999]) #5935

Open
p6rt opened this issue Dec 29, 2016 · 5 comments
Open

Ranges with Infs on endpoints could be smarter ((0..Inf)[99999999999]) #5935

p6rt opened this issue Dec 29, 2016 · 5 comments
Labels
9999 RFC Request For Comments

Comments

@p6rt
Copy link

p6rt commented Dec 29, 2016

Migrated from rt.perl.org#130437 (status was 'open')

Searchable as RT130437$

@p6rt
Copy link
Author

p6rt commented Dec 29, 2016

From @AlexDaniel

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)

@p6rt
Copy link
Author

p6rt commented Dec 29, 2016

From @smls

`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?

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).

@p6rt
Copy link
Author

p6rt commented Dec 29, 2016

The RT System itself - Status changed from 'new' to 'open'

@p6rt
Copy link
Author

p6rt commented Jan 11, 2017

From @zoffixznet

On Thu, 29 Dec 2016 13​:49​:40 -0800, smls75@​gmail.com wrote​:

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.

@p6rt
Copy link
Author

p6rt commented Jan 11, 2017

From 1parrota@gmail.com

"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?

@p6rt p6rt added 9999 RFC Request For Comments labels Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
9999 RFC Request For Comments
Projects
None yet
Development

No branches or pull requests

1 participant