Range#bsearch updates

[headius]

I have ported the bsearch C code from CRuby master to Ruby for use in JRuby. It may be useful to you.

I'm not sure how to do this without the JRuby/Java dependency because there's no way to roundtrip a Float through long bits using standard APIs. Other than that it should be easy to add to backports. I do not know which changes were added when, but I believe most of the differences came with infinite ranges in 2.6.

I will link to two versions in comments.

[headius]

This version uses a BSearch state object and a "return sled" for the "check" behavior (which corresponds to BSEARCH_CHECK macro in the C code).

https://github.com/jruby/jruby/blob/460155e99c86d7bcaa5302605b6166fe2b6ee437/core/src/main/ruby/jruby/kernel/range.rb

To avoid the cost of the BSearch object and the instance variables, JRuby will ship this version that inlines the "check" calls:

https://github.com/jruby/jruby/blob/ade293b854f85136949f6462fdb12c5a4a6e9c34/core/src/main/ruby/jruby/kernel/range.rb

[marcandre]

Hi! Thanks, but I've backported Range#bsearch years ago (current version is here ) so unless I'm missing something all should be good already?

[headius]

I've backported Range#bsearch years ago

Yes, and that's the one we were using in JRuby up to now, but it doesn't handle infinite ranges.

[marcandre]

Oh, right, I'll check out infinite ranges. I expect the treatment of (1..) to be the same as (1..Float::INFINITY), right?

[headius]

Aha, I see you use packing to handle the Float long bits! That's probably heavier than using the Java methods so I won't be adopting it, but you should be able to swap those calls out.

I have another refinement coming that splits the main method up a bit more (for better optimization and separation of concerns).

I expect the treatment of (1..) to be the same as (1..Float::INFINITY), right?

Actually the way it works in MRI for infinite integer ranges is that it starts with the finite edge and adds 1, 2, 4... (or -1, -2, -4) until it has a finite range that brackets the desired value, and then it proceeds with a normal integer binary search.

[headius]

Additional tweaks are here: https://github.com/jruby/jruby/commit/672777703b37f09c4e1efb4aea15ed32c61d02d1

[headius]

I was also thinking the long bits logic should be added to Ruby proper... since you encountered this problem first, do you want to open the feature request?

I'm thinking Math.float_to_bits and Math.bits_to_float would be a starting place.

[marcandre]

Oh, right, I'll check out infinite ranges.

I just "woke up"... I can't backport limitless ranges, as you can't type them in older rubies and it looks like a terrible idea to attempt to backport Range.new(1,nil).

I was also thinking the long bits logic should be added to Ruby proper... since you encountered this problem first, do you want to open the feature request?

I'm thinking Math.float_to_bits and Math.bits_to_float would be a starting place.

I'm not convinced that it would be useful enough to justify new methods. I doubt anybody actually needs it, and if they do that's what pack/unpack are already doing... I'd actually "vote" against such methods tbh.

[headius]

Oh drat, I forgot about that too. Doesn't help much to have the logic for infinite ranges when you can't define infinite ranges, I guess!

In any case the ported code is there... maybe there's something of value, or maybe it will be useful going forward to keep up with future Range#bsearch changes.