Skip to content

Rewrite Array#each in Ruby using Primitive#9533

Merged
k0kubun merged 5 commits intoruby:masterfrom
k0kubun:primitive-array-each
Jan 23, 2024
Merged

Rewrite Array#each in Ruby using Primitive#9533
k0kubun merged 5 commits intoruby:masterfrom
k0kubun:primitive-array-each

Conversation

@k0kubun
Copy link
Copy Markdown
Member

@k0kubun k0kubun commented Jan 14, 2024 •
edited
Loading

Same as #6687, but race condition-free.

microbenchmark

Interpreter

Thanks to Primitive, the interpreter doesn't slow down.

$ benchmark-driver benchmark/loop_each.yml -v --chruby 'before;after'
before: ruby 3.4.0dev (2024-01-20T01:12:07Z master 99d6e2f1ee) [x86_64-linux]
after: ruby 3.4.0dev (2024-01-20T01:36:08Z primitive-array-each 3aaa6de3ec) [x86_64-linux]
Warming up --------------------------------------
           loop_each      1.539 i/s -       2.000 times in 1.299363s (649.68ms/i)
Calculating -------------------------------------
                         before       after
           loop_each      1.551       1.796 i/s -       4.000 times in 2.578413s 2.227167s

Comparison:
                        loop_each
               after:         1.8 i/s
              before:         1.6 i/s - 1.16x  slower

YJIT

Even faster than #6687.

$ benchmark-driver benchmark/loop_each.yml -v --chruby 'before::before --yjit-call-threshold=1;after::after --yjit-call-threshold=1'
before: ruby 3.4.0dev (2024-01-20T01:12:07Z master 99d6e2f1ee) +YJIT [x86_64-linux]
after: ruby 3.4.0dev (2024-01-20T01:36:08Z primitive-array-each 3aaa6de3ec) +YJIT [x86_64-linux]
Warming up --------------------------------------
           loop_each      1.789 i/s -       2.000 times in 1.118068s (559.03ms/i)
Calculating -------------------------------------
                         before       after
           loop_each      1.790      12.986 i/s -       5.000 times in 2.793497s 0.385044s

Comparison:
                        loop_each
               after:        13.0 i/s
              before:         1.8 i/s - 7.26x  slower

yjit-bench

See #9622.

@k0kubun k0kubun force-pushed the primitive-array-each branch 6 times, most recently from dca75f2 to 35f3b4e Compare January 15, 2024 05:20
@maximecb
Copy link
Copy Markdown
Contributor

maximecb commented Jan 15, 2024

Nice. Happy to see this working. Surprised it's so far in YJIT as well!

Ideally, for YJIT, we'd like to be able to avoid doing a function call at all, so we can generate tight inlined code though, so we might need a specialized instruction instead of a cexpr? What do you think?

@k0kubun
Copy link
Copy Markdown
Member Author

k0kubun commented Jan 16, 2024 •
edited
Loading

Ideally, for YJIT, we'd like to be able to avoid doing a function call at all, so we can generate tight inlined code though, so we might need a specialized instruction instead of a cexpr? What do you think?

I think it's possible without a new instruction. cexpr! already gets a somewhat special instruction, invokebuiltin (opt_invokebuiltin_delegate for this ISEQ to be precise). Since we use this instruction for converting a C method, each ISEQ typically has up to one invokebuiltin (at least we could assume it for select ISEQs YJIT specializes). If we specialize invokebuiltin for Array#each ISEQ as if it was the new instruction you proposed, we'll get what we want.

nobu
nobu reviewed Jan 17, 2024
View reviewed changes
Comment thread array.rb Outdated
nobu
nobu reviewed Jan 17, 2024
View reviewed changes
Comment thread array.rb Outdated
nobu
nobu reviewed Jan 17, 2024
View reviewed changes
Comment thread tool/mk_builtin_loader.rb Outdated
@k0kubun k0kubun force-pushed the primitive-array-each branch from 3c97813 to bede16a Compare January 17, 2024 18:11
@nobu nobu mentioned this pull request Jan 18, 2024
Draft
@k0kubun k0kubun mentioned this pull request Jan 18, 2024
Closed
@k0kubun k0kubun force-pushed the primitive-array-each branch from bede16a to 3aaa6de Compare January 20, 2024 01:36
@k0kubun k0kubun mentioned this pull request Jan 20, 2024
Merged
@k0kubun k0kubun force-pushed the primitive-array-each branch from 0d58851 to 4f30c21 Compare January 21, 2024 05:47
@k0kubun k0kubun force-pushed the primitive-array-each branch from 4f30c21 to 6b5e44b Compare January 21, 2024 06:04
maximecb
maximecb reviewed Jan 22, 2024
View reviewed changes
Comment thread array.rb
XrXr
XrXr approved these changes Jan 23, 2024
View reviewed changes
Comment thread test/ruby/test_gc_compact.rb Outdated
@k0kubun k0kubun force-pushed the primitive-array-each branch from 2e2cd3f to d98ac2c Compare January 23, 2024 19:01
@k0kubun k0kubun marked this pull request as ready for review January 23, 2024 19:40
@k0kubun k0kubun enabled auto-merge (squash) January 23, 2024 20:00
@k0kubun k0kubun merged commit c84237f into ruby:master Jan 23, 2024
@k0kubun k0kubun deleted the primitive-array-each branch January 23, 2024 21:05
paracycle added a commit to Shopify/sorbet that referenced this pull request Feb 12, 2024
@paracycle
Encapsulate backtrace location searching logic to a single method
8b66bf5 
In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
@paracycle paracycle mentioned this pull request Feb 12, 2024
Merged
paracycle added a commit to Shopify/sorbet that referenced this pull request Feb 12, 2024
@paracycle
Encapsulate backtrace location searching logic to a single method
204b876 
In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
paracycle added a commit to Shopify/sorbet that referenced this pull request Feb 12, 2024
@paracycle
Encapsulate backtrace location searching logic to a single method
13f5072 
In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
paracycle added a commit to Shopify/sorbet that referenced this pull request Feb 12, 2024
@paracycle
Encapsulate backtrace location searching logic to a single method
4bb6948 
In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
neilparikh pushed a commit to sorbet/sorbet that referenced this pull request Feb 13, 2024
@paracycle @neilparikh
Encapsulate backtrace location searching logic to a single method
ffb8dbe 
In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
neilparikh pushed a commit to sorbet/sorbet that referenced this pull request Feb 14, 2024
@paracycle @neilparikh
Encapsulate backtrace location searching logic to a single method
65a04c6 
In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
paracycle added a commit to Shopify/sorbet that referenced this pull request Feb 16, 2024
@paracycle
Encapsulate backtrace location searching logic to a single method
1104458 
In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
jez pushed a commit to sorbet/sorbet that referenced this pull request Feb 21, 2024
@paracycle @jez
Encapsulate backtrace location searching logic to a single method
06df55e 
In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
jez pushed a commit to sorbet/sorbet that referenced this pull request Feb 21, 2024
@paracycle
Encapsulate backtrace location searching logic to a single method (#7687
58b2550 
)

In order to provide compatibility with TruffleRuby that implements a lot
of its core library methods in Ruby, and for future versions of CRuby
that is increasingly doing the same, we need to be able to filter
all backtrace locations where the `path` starts with `<internal:`.

[This gist](https://gist.github.com/eregon/912e6359e83781c5fa1c638d3768c526)
shows the current state of the methods implemented in Ruby in CRuby,
JRuby and TruffleRuby.

Most recently [CRuby started implementing `Array#each` in Ruby](ruby/ruby#9533), making it usages of `each` visible in backtraces with an `<internal:array>` path. This means that in order to be compatible with CRuby 3.4, Sorbet runtime needs to start filtering out backtrace locations that start with `<internal:`.

By encapsulating the caller location search logic into a singleton
method, we can apply that filtering in a single location and avoid
having to repeat it in multiple places.
@k0kubun k0kubun mentioned this pull request Feb 27, 2024
Merged
@k0kubun k0kubun mentioned this pull request Oct 28, 2024
Merged
swebb added a commit to swebb/ruby that referenced this pull request Jan 11, 2026
@swebb
Rewrite Array#find in ruby
1a40ece 
Inspired by https://bugs.ruby-lang.org/issues/20182 and ruby#9533.

This PR provides a performance boost to Array#find when run using JIT
compilation. This is achieved by implementing Array#find in Ruby, which
the JIT compiler can optimise.

[PR#15189](ruby#15189) added a C
implementation for Array#find instead of relying on Enumerable#find.
This PR extends this by adding a Ruby implementation.

I used the so_fasta benchmark to measure performance. No change in
interpreted performance before/after:

  $ benchmark-driver -e "~/.rubies/ruby-master/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-master/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby
              so_fasta                          0.393                                       0.393 i/s -       1.000 times in 2.543209s 2.545514s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-master/bin/ruby:         0.4 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.00x  slower

With YJIT enabled the speed is almost twice as fast:

  $ benchmark-driver -e "~/.rubies/ruby-array-find-native/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby --yjit" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-array-find-native/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby --yjit
              so_fasta                                     0.393                                              0.770 i/s -       1.000 times in 2.547550s 1.298371s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-array-find-native/bin/ruby --yjit:         0.8 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.96x  slower
swebb added a commit to swebb/ruby that referenced this pull request Jan 11, 2026
@swebb
Rewrite Array#find in ruby
89e2257 
Inspired by https://bugs.ruby-lang.org/issues/20182 and ruby#9533.

This PR provides a performance boost to Array#find when run using JIT
compilation. This is achieved by implementing Array#find in Ruby, which
the JIT compiler can optimise.

[PR#15189](ruby#15189) added a C
implementation for Array#find instead of relying on Enumerable#find.
This PR extends this by adding a Ruby implementation.

I used the so_fasta benchmark to measure performance. No change in
interpreted performance before/after:

  $ benchmark-driver -e "~/.rubies/ruby-master/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-master/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby
              so_fasta                          0.393                                       0.393 i/s -       1.000 times in 2.543209s 2.545514s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-master/bin/ruby:         0.4 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.00x  slower

With YJIT enabled Array#find is almost twice as fast:

  $ benchmark-driver -e "~/.rubies/ruby-array-find-native/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby --yjit" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-array-find-native/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby --yjit
              so_fasta                                     0.393                                              0.770 i/s -       1.000 times in 2.547550s 1.298371s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-array-find-native/bin/ruby --yjit:         0.8 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.96x  slower
@swebb swebb mentioned this pull request Jan 11, 2026
Merged
nobu pushed a commit to swebb/ruby that referenced this pull request Feb 2, 2026
@swebb @nobu
Rewrite Array#find in ruby
b8f4416 
Inspired by https://bugs.ruby-lang.org/issues/20182 and ruby#9533.

This PR provides a performance boost to Array#find when run using JIT
compilation. This is achieved by implementing Array#find in Ruby, which
the JIT compiler can optimise.

[PR#15189](ruby#15189) added a C
implementation for Array#find instead of relying on Enumerable#find.
This PR extends this by adding a Ruby implementation.

I used the so_fasta benchmark to measure performance. No change in
interpreted performance before/after:

  $ benchmark-driver -e "~/.rubies/ruby-master/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-master/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby
              so_fasta                          0.393                                       0.393 i/s -       1.000 times in 2.543209s 2.545514s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-master/bin/ruby:         0.4 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.00x  slower

With YJIT enabled Array#find is almost twice as fast:

  $ benchmark-driver -e "~/.rubies/ruby-array-find-native/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby --yjit" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-array-find-native/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby --yjit
              so_fasta                                     0.393                                              0.770 i/s -       1.000 times in 2.547550s 1.298371s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-array-find-native/bin/ruby --yjit:         0.8 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.96x  slower
nobu pushed a commit that referenced this pull request Feb 2, 2026
@swebb @nobu
Rewrite Array#find in ruby
9368ec5 
Inspired by https://bugs.ruby-lang.org/issues/20182 and #9533.

This PR provides a performance boost to Array#find when run using JIT
compilation. This is achieved by implementing Array#find in Ruby, which
the JIT compiler can optimise.

[PR#15189](#15189) added a C
implementation for Array#find instead of relying on Enumerable#find.
This PR extends this by adding a Ruby implementation.

I used the so_fasta benchmark to measure performance. No change in
interpreted performance before/after:

  $ benchmark-driver -e "~/.rubies/ruby-master/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-master/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby
              so_fasta                          0.393                                       0.393 i/s -       1.000 times in 2.543209s 2.545514s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-master/bin/ruby:         0.4 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.00x  slower

With YJIT enabled Array#find is almost twice as fast:

  $ benchmark-driver -e "~/.rubies/ruby-array-find-native/bin/ruby; ~/.rubies/ruby-array-find-native/bin/ruby --yjit" ../benchmark/so_fasta.rb
  Calculating -------------------------------------
                       ~/.rubies/ruby-array-find-native/bin/ruby   ~/.rubies/ruby-array-find-native/bin/ruby --yjit
              so_fasta                                     0.393                                              0.770 i/s -       1.000 times in 2.547550s 1.298371s

  Comparison:
                           so_fasta
  ~/.rubies/ruby-array-find-native/bin/ruby --yjit:         0.8 i/s
  ~/.rubies/ruby-array-find-native/bin/ruby:         0.4 i/s - 1.96x  slower
@k0kubun k0kubun mentioned this pull request Feb 7, 2026
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@nobu nobu nobu left review comments

@eregon eregon eregon left review comments

@maximecb maximecb maximecb left review comments

@XrXr XrXr XrXr approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@k0kubun @maximecb @nobu @eregon @XrXr