[ruby-core:118930] [Ruby master Feature#20692] Rewrite Array#bsearch in Ruby

[ruby-core:118930] [Ruby master Feature#20692] Rewrite Array#bsearch in Ruby

[sebyx07 (Sebastian Buza) via ruby-core]

Issue #20692 has been reported by sebyx07 (Sebastian Buza).

----------------------------------------
Feature #20692: Rewrite Array#bsearch in Ruby
https://bugs.ruby-lang.org/issues/20692

* Author: sebyx07 (Sebastian Buza)
* Status: Open
----------------------------------------
inspired by https://bugs.ruby-lang.org/issues/20182

Benchmark results (average over 10000000 iterations):

user system total real

Original bsearch: 7.011691 0.000038 7.011729 ( 7.013117)

Native bsearch: 2.809711 0.001000 2.810711 ( 2.812067)


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



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:118931] [Ruby master Feature#20692] Rewrite Array#bsearch in Ruby

[sebyx07 (Sebastian Buza) via ruby-core]

Issue #20692 has been updated by sebyx07 (Sebastian Buza).


added more optimizations

```
Benchmark results (average over 10000000 iterations):
                           user     system      total        real
Original bsearch:     12.329160   0.009148  12.338308 ( 12.337310)
Native bsearch:        3.437350   0.000057   3.437407 (  3.437270)
```



----------------------------------------
Feature #20692: Rewrite Array#bsearch in Ruby
https://bugs.ruby-lang.org/issues/20692#change-109499

* Author: sebyx07 (Sebastian Buza)
* Status: Open
----------------------------------------
inspired by https://bugs.ruby-lang.org/issues/20182

Benchmark results (average over 10000000 iterations):

user system total real

Original bsearch: 7.011691 0.000038 7.011729 ( 7.013117)

Native bsearch: 2.809711 0.001000 2.810711 ( 2.812067)


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



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:118958] [Ruby master Feature#20692] Rewrite Array#bsearch in Ruby

[Hanmac (Hans Mackowiak) via ruby-core]

Issue #20692 has been updated by Hanmac (Hans Mackowiak).


`find_minimum_mode = finder || !finder` isn't this always true?

----------------------------------------
Feature #20692: Rewrite Array#bsearch in Ruby
https://bugs.ruby-lang.org/issues/20692#change-109530

* Author: sebyx07 (Sebastian Buza)
* Status: Open
----------------------------------------
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

    finder = yield(self[mid])
    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
      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 (average over 10000000 iterations):
                           user     system      total        real
Original bsearch:     12.329160   0.009148  12.338308 ( 12.337310)
Native bsearch:        3.437350   0.000057   3.437407 (  3.437270)
```



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:118968] [Ruby master Feature#20692] Rewrite Array#bsearch in Ruby

[sebyx07 (Sebastian Buza) via ruby-core]

Issue #20692 has been updated by sebyx07 (Sebastian Buza).


ty Hanmac 

----------------------------------------
Feature #20692: Rewrite Array#bsearch in Ruby
https://bugs.ruby-lang.org/issues/20692#change-109541

* Author: sebyx07 (Sebastian Buza)
* Status: Open
----------------------------------------
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])
    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)
```



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:119071] [Ruby master Feature#20692] Rewrite Array#bsearch in Ruby

[tenderlovemaking (Aaron Patterson) via ruby-core]

Issue #20692 has been updated by tenderlovemaking (Aaron Patterson).


I think this is a good idea, but I think we need to make a few changes.  First, `to_enum` and `block_given?` are both method calls. It's possible for people to monkey patch Array and add those methods, but the original implementation of `Array#bsearch` would ignore such monkey patches.  To maintain existing behavior, we must use code that doesn't depend on those methods [the same way the Array#each implementation works](https://github.com/tenderlove/ruby/blob/18744851eb4e1e14be8435f77dabf3bc62bbb81d/array.rb#L47-L49).

Additionally, I think this proposal has the same problem as the initial version of the `Array#each` implementation in Ruby, specifically [a possible thread safety problem between the `<` comparison at the `[]` fetch](https://github.com/ruby/ruby/pull/6687#discussion_r1139265240).  I think we can address that by doing [the same trick as `Array#each`](https://github.com/tenderlove/ruby/blob/18744851eb4e1e14be8435f77dabf3bc62bbb81d/array.rb#L52).

----------------------------------------
Feature #20692: Rewrite Array#bsearch in Ruby
https://bugs.ruby-lang.org/issues/20692#change-109654

* Author: sebyx07 (Sebastian Buza)
* Status: Open
----------------------------------------
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])
    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)
```



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/

[ruby-core:119075] [Ruby master Feature#20692] Rewrite Array#bsearch in Ruby

[mame (Yusuke Endoh) via ruby-core]

Issue #20692 has been updated by mame (Yusuke Endoh).


I tried `make test-all TESTS=test/ruby/test_array.rb` with the proposed implementation, but several tests failed. They should be solved before discussing performance.

```
[ 47/447] TestArray#test_bsearch_in_find_any_mode = 0.00 s
  1) Error:
TestArray#test_bsearch_in_find_any_mode:
TypeError: wrong argument type (must be -1, 0, 1, true, or false)
    <internal:array>:245:in 'Array#bsearch'
    /home/mame/work/ruby/test/ruby/test_array.rb:3360:in 'TestArray#test_bsearch_in_find_any_mode'

[174/447] TestArray#test_bsearch_typechecks_return_values = 0.00 s
  2) Failure:
TestArray#test_bsearch_typechecks_return_values [/home/mame/work/ruby/test/ruby/test_array.rb:3337]:
Expected Exception(TypeError) was raised, but the message doesn't match.
Expected /C\u{309a 26a1 26c4 1f300}/ to match "wrong argument type (must be -1, 0, 1, true, or false)".

[198/447] TestArray#test_bsearch_with_no_block = 0.00 s
  3) Failure:
TestArray#test_bsearch_with_no_block [/home/mame/work/ruby/test/ruby/test_array.rb:3345]:
Expected 5 to be nil.

[269/447] TestArraySubclass#test_bsearch_in_find_any_mode = 0.00 s
  4) Error:
TestArraySubclass#test_bsearch_in_find_any_mode:
TypeError: wrong argument type (must be -1, 0, 1, true, or false)
    <internal:array>:245:in 'Array#bsearch'
    /home/mame/work/ruby/test/ruby/test_array.rb:3360:in 'TestArray#test_bsearch_in_find_any_mode'

[396/447] TestArraySubclass#test_bsearch_typechecks_return_values = 0.00 s
  5) Failure:
TestArraySubclass#test_bsearch_typechecks_return_values [/home/mame/work/ruby/test/ruby/test_array.rb:3337]:
Expected Exception(TypeError) was raised, but the message doesn't match.
Expected /C\u{309a 26a1 26c4 1f300}/ to match "wrong argument type (must be -1, 0, 1, true, or false)".

[420/447] TestArraySubclass#test_bsearch_with_no_block = 0.00 s
  6) Failure:
TestArraySubclass#test_bsearch_with_no_block [/home/mame/work/ruby/test/ruby/test_array.rb:3345]:
Expected 5 to be nil.
```

I am also concerned about the performance when YJIT is not enabled.

----------------------------------------
Feature #20692: Rewrite Array#bsearch in Ruby
https://bugs.ruby-lang.org/issues/20692#change-109659

* Author: sebyx07 (Sebastian Buza)
* Status: Open
----------------------------------------
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])
    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)
```



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/