Project

General

Profile

Feature #20692

Updated by sebyx07 (Sebastian Buza) 2 months ago

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

 # Proporsal 

 Rewrite Array#bsearch 

 ```ruby 
 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]) finder = yield(self[mid]) 
     when true, false find_minimum_mode = finder || !finder 

     if find_minimum_mode 
       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 12.329160     0.000000 0.009148    11.499511 12.338308 ( 11.500056) 12.337310) 
 Native bsearch:          2.923645 3.437350     0.003860 0.000057     2.927505 3.437407 (    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) 3.437270) 
 ```

Back