On Thu, 29 Dec 2016 13:49:40 -0800, [email protected] 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.
