Feature #20692

open

Rewrite Array#bsearch in Ruby

Added by sebyx07 (Sebastian Buza) 9 days ago. Updated 4 days ago.

Status:

Open

Assignee:

Target version:

[ruby-core:118930]

Description

inspired by https://bugs.ruby-lang.org/issues/20182

Proporsal¶

Rewrite Array#bsearch

class Array
  def bsearch
    return to_enum(:bsearch) { size } unless block_given?

    return nil if empty?

    low = 0
    high = size - 1
    mid = size / 2

    case yield(self[low])
    when true, false
      while low < high
        if yield(self[mid])
          high = mid
        else
          low = mid + 1
        end
        mid = low + (high - low) / 2
      end
      yield(self[low]) ? self[low] : nil
    else
      # Find-any mode
      while low <= high
        case yield(self[mid])
        when 0
          return self[mid]
        when 1
          high = mid - 1
        when -1
          low = mid + 1
        else
          raise TypeError, 'wrong argument type (must be -1, 0, 1, true, or false)'
        end
        mid = low + (high - low) / 2
      end
      nil
    end
  end
end

https://github.com/sebyx07/native_ruby/blob/master/lib/native_ruby/array/bsearch.rb

I also created this gem:
https://github.com/sebyx07/native_ruby/ - to load patches w/o depending on the ruby/master

Benchmark¶

ruby 3.3.3 (2024-06-12 revision f1c7b6f435) +YJIT [x86_64-linux]

Benchmark results sorted array (average over 10000000 iterations):
                           user     system      total        real
Original bsearch:     11.499511   0.000000  11.499511 ( 11.500056)
Native bsearch:        2.923645   0.003860   2.927505 (  2.927539)


Benchmark results shuffled (average over 10000000 iterations):
                           user     system      total        real
Original bsearch:      8.726749   0.000001   8.726750 (  8.727679)
Native bsearch:        3.073027   0.000006   3.073033 (  3.073231)