Issue #22446 has been updated by byroot (Jean Boussier).

Conversions between Float and String:

For this specifically [Feature #21308] has been open for a while. I'd like to see it addressed, but this is a field that's been strangely moving fast with new implementation coming out regularly. But they're all miles ahead of `dtoa.c` so... ---------------------------------------- Feature #22446: Speed up several core methods in Array, Range, String, Integer, Float and Time https://bugs.ruby-lang.org/issues/22446#change-119537 * Author: sferik (Erik Berlin) * Status: Open ---------------------------------------- I've opened a set of pull requests that speed up commonly used core methods. This issue collects them in one place for discussion. Each PR stands on its own, adds its benchmark in the first commit, and has its own tests. All of the numbers below are from an arm64 Mac with clang. Several of these changes depend on the compiler inlining or vectorizing a loop, so numbers from Linux with gcc, and from Windows with MSVC, would be especially welcome. ## Array * **Array#sort and Enumerable#sort_by on numeric arrays**: https://github.com/ruby/ruby/pull/19306 When every element is a Fixnum, or every element is a Float, and `<=>` hasn't been redefined, the elements are sorted directly with a pattern-defeating quicksort (the one used by Rust and Go) instead of going through `ruby_qsort` with a callback for each comparison. Random Integers sort 4–5x faster at 1,000 to 100,000 elements, and reversed arrays sort about 9x faster. `sort_by` now uses the same code instead of its own introsort and goes up to 2.4x faster. For `sort_by`, elements with equal keys may come out in a different order (the docs already call that order indeterminate). The error message for an invalid key may also name a different key than before. * **Array#include?, #index, #rindex and #count with immediate values**: https://github.com/ruby/ruby/pull/19308 When the argument is a Fixnum, a Float or a static Symbol, elements of the same kind are compared as raw VALUEs, eight at a time, instead of calling `rb_equal` on each one. Arrays of 1,000 or more elements are 10–15x faster. Arrays of other kinds of elements are within 1–2% of master. * **Array#eql? when elements are identical**: https://github.com/ruby/ruby/pull/19360 `eql?` now walks the element buffers the way `==` already does, and calls `rb_eql()` only for elements that aren't the same VALUE. On an array of 1,000 Integers it's 4.8x faster, so it's no longer about 4x slower than `==`. ## Range * **Range#to_a on Integer ranges**: https://github.com/ruby/ruby/pull/19319 For Fixnum ranges where `Range#each` hasn't been redefined, the array is allocated at its final size and filled in a loop instead of going through `Enumerable#to_a`. That's 7.7x faster at 10 elements and 35x faster at 1,000. `[*range]` and `Array(range)` are faster too. Because this path doesn't call `super`, a `to_a` from a module included into Range, or a redefined `Enumerable#to_a`, is no longer reached for these ranges. * **Range#include? on ranges of numeric Strings**: https://github.com/ruby/ruby/pull/13959 This fills in the `TODO` in `rb_str_include_range_p` for ranges whose ends are all digits. The digits are checked directly instead of iterating with `String#upto`, and the result is the same as iterating would give. `('1'..'200000').include?('199999')` drops from 13 ms to 150 ns. ## String and Integer * **String#casecmp and #casecmp? on similar strings**: https://github.com/ruby/ruby/pull/19311 This builds on https://github.com/ruby/ruby/pull/17444. The ASCII fast path now compares 16 bytes at a time and looks at single bytes only inside a chunk that differs. Identical strings, or strings that differ only in the case of one letter, are 4–5x faster at 360 bytes and 7–14x faster at 3.6 KB and up. * **String#to_i and Integer() for Bignum results**: https://github.com/ruby/ruby/pull/19332 `str2big_normal` now multiplies once per `BDIGIT`-sized group of digits instead of once per character, the way `str2big_karatsuba` already builds its initial digits. Also, `rb_int_parse_cstr` stops its first scan once the input is too long to fit in an `unsigned long`. Parsing is 1.5x faster at 20 decimal digits and 6.3x faster at 600. Results that fit in a Fixnum aren't affected. ## Float * **Conversions between Float and String**: https://github.com/ruby/ruby/pull/19309 `Float#to_s` gets its digits from Schubfach (the algorithm behind OpenJDK's `Double.toString`) instead of `ruby_dtoa`. `ruby_strtod` tries Eisel-Lemire (the algorithm behind `fast_float`, which the json extension already vendors) before falling back to the existing code. For a random Float, `to_s` is 7x faster and `String#to_f` is 3.2x faster, and `Marshal.dump` and `Marshal.load` are faster as well. This is the largest of the PRs. It adds new code under the Boost and MIT licenses, credited in `LEGAL`, plus a generated table with its generator in `tool/`. It also fixes `Rational#to_f` and `Integer#fdiv`, which could be off by one unit in the last place for large operands, and a `strtod` bug on 32-bit x86. I'm happy to split those fixes into their own tickets if that makes review or backporting easier. ## Time * **Time#strftime**: https://github.com/ruby/ruby/pull/19341 Numeric fields are written directly instead of through `rb_str_catf`, and the result buffer is sized up front so that typical results stay embedded. Common formats are 2.4–4x faster, including the ones used by Logger's default formatter and by Rails' `to_fs(:db)` and `to_fs(:usec)`. I'd appreciate any feedback, here or on the PRs. That includes whether you'd like any of these split up, merged together, or moved into their own tickets. Thank you so much for reviewing! I hope it's not too late for these performance improvements to make it into Ruby 4.1! -- https://bugs.ruby-lang.org/

Issue #22446 has been updated by byroot (Jean Boussier).

Let's ship a better algorithm in 4.1, and an even better one in 4.2, and an even better one if 4.3…

It's not that simple though, there's a maintenance cost to all this (e.g. backports), and these algorithm can have subtly different behavior on fringe cases, which can result in a bunch of tests suites failing etc. So it would be best not to constantly change that implementation.

Array#include?, #index, #rindex and #count with immediate values:

This one is interesting because a large part of the complexity of the implementation is caused by the semantic of these methods is that the comparison is done as `element == searched_item`. Reversing that condition would be a spec change, so perhaps tricky, but would make it much easier to optimize the method as you'd only need to check for immediate values once. ---------------------------------------- Feature #22446: Speed up several core methods in Array, Range, String, Integer, Float and Time https://bugs.ruby-lang.org/issues/22446#change-119545 * Author: sferik (Erik Berlin) * Status: Open ---------------------------------------- I've opened a set of pull requests that speed up commonly used core methods. This issue collects them in one place for discussion. Each PR stands on its own, adds its benchmark in the first commit, and has its own tests. All of the numbers below are from an arm64 Mac with clang. Several of these changes depend on the compiler inlining or vectorizing a loop, so numbers from Linux with gcc, and from Windows with MSVC, would be especially welcome. ## Array * **Array#sort and Enumerable#sort_by on numeric arrays**: https://github.com/ruby/ruby/pull/19306 When every element is a Fixnum, or every element is a Float, and `<=>` hasn't been redefined, the elements are sorted directly with a pattern-defeating quicksort (the one used by Rust and Go) instead of going through `ruby_qsort` with a callback for each comparison. Random Integers sort 4–5x faster at 1,000 to 100,000 elements, and reversed arrays sort about 9x faster. `sort_by` now uses the same code instead of its own introsort and goes up to 2.4x faster. For `sort_by`, elements with equal keys may come out in a different order (the docs already call that order indeterminate). The error message for an invalid key may also name a different key than before. * **Array#include?, #index, #rindex and #count with immediate values**: https://github.com/ruby/ruby/pull/19308 When the argument is a Fixnum, a Float or a static Symbol, elements of the same kind are compared as raw VALUEs, eight at a time, instead of calling `rb_equal` on each one. Arrays of 1,000 or more elements are 10–15x faster. Arrays of other kinds of elements are within 1–2% of master. * **Array#eql? when elements are identical**: https://github.com/ruby/ruby/pull/19360 `eql?` now walks the element buffers the way `==` already does, and calls `rb_eql()` only for elements that aren't the same VALUE. On an array of 1,000 Integers it's 4.8x faster, so it's no longer about 4x slower than `==`. ## Range * **Range#to_a on Integer ranges**: https://github.com/ruby/ruby/pull/19319 For Fixnum ranges where `Range#each` hasn't been redefined, the array is allocated at its final size and filled in a loop instead of going through `Enumerable#to_a`. That's 7.7x faster at 10 elements and 35x faster at 1,000. `[*range]` and `Array(range)` are faster too. Because this path doesn't call `super`, a `to_a` from a module included into Range, or a redefined `Enumerable#to_a`, is no longer reached for these ranges. * **Range#include? on ranges of numeric Strings**: https://github.com/ruby/ruby/pull/13959 This fills in the `TODO` in `rb_str_include_range_p` for ranges whose ends are all digits. The digits are checked directly instead of iterating with `String#upto`, and the result is the same as iterating would give. `('1'..'200000').include?('199999')` drops from 13 ms to 150 ns. ## String and Integer * **String#casecmp and #casecmp? on similar strings**: https://github.com/ruby/ruby/pull/19311 This builds on https://github.com/ruby/ruby/pull/17444. The ASCII fast path now compares 16 bytes at a time and looks at single bytes only inside a chunk that differs. Identical strings, or strings that differ only in the case of one letter, are 4–5x faster at 360 bytes and 7–14x faster at 3.6 KB and up. * **String#to_i and Integer() for Bignum results**: https://github.com/ruby/ruby/pull/19332 `str2big_normal` now multiplies once per `BDIGIT`-sized group of digits instead of once per character, the way `str2big_karatsuba` already builds its initial digits. Also, `rb_int_parse_cstr` stops its first scan once the input is too long to fit in an `unsigned long`. Parsing is 1.5x faster at 20 decimal digits and 6.3x faster at 600. Results that fit in a Fixnum aren't affected. ## Float * **Conversions between Float and String**: https://github.com/ruby/ruby/pull/19309 `Float#to_s` gets its digits from Schubfach (the algorithm behind OpenJDK's `Double.toString`) instead of `ruby_dtoa`. `ruby_strtod` tries Eisel-Lemire (the algorithm behind `fast_float`, which the json extension already vendors) before falling back to the existing code. For a random Float, `to_s` is 7x faster and `String#to_f` is 3.2x faster, and `Marshal.dump` and `Marshal.load` are faster as well. This is the largest of the PRs. It adds new code under the Boost and MIT licenses, credited in `LEGAL`, plus a generated table with its generator in `tool/`. It also fixes `Rational#to_f` and `Integer#fdiv`, which could be off by one unit in the last place for large operands, and a `strtod` bug on 32-bit x86. I'm happy to split those fixes into their own tickets if that makes review or backporting easier. ## Time * **Time#strftime**: https://github.com/ruby/ruby/pull/19341 Numeric fields are written directly instead of through `rb_str_catf`, and the result buffer is sized up front so that typical results stay embedded. Common formats are 2.4–4x faster, including the ones used by Logger's default formatter and by Rails' `to_fs(:db)` and `to_fs(:usec)`. I'd appreciate any feedback, here or on the PRs. That includes whether you'd like any of these split up, merged together, or moved into their own tickets. Thank you so much for reviewing! I hope it's not too late for these performance improvements to make it into Ruby 4.1! -- https://bugs.ruby-lang.org/

Issue #22446 has been updated by byroot (Jean Boussier).

you like me to do that for PR #19360?

We don't backport performance patches, only bugfixes.

When you have a moment, would you mind taking a look at PR #19309?

I already saw it, but's that's not how Ruby works, that's not for me to decide such a big change with user visible (albeit minor) impact on my own. That's why I've added the question to the next dev meeting agenda: https://bugs.ruby-lang.org/issues/22417#note-3 ---------------------------------------- Feature #22446: Speed up several core methods in Array, Range, String, Integer, Float and Time https://bugs.ruby-lang.org/issues/22446#change-119547 * Author: sferik (Erik Berlin) * Status: Open ---------------------------------------- I've opened a set of pull requests that speed up commonly used core methods. This issue collects them in one place for discussion. Each PR stands on its own, adds its benchmark in the first commit, and has its own tests. All of the numbers below are from an arm64 Mac with clang. Several of these changes depend on the compiler inlining or vectorizing a loop, so numbers from Linux with gcc, and from Windows with MSVC, would be especially welcome. ## Array * **Array#sort and Enumerable#sort_by on numeric arrays**: https://github.com/ruby/ruby/pull/19306 When every element is a Fixnum, or every element is a Float, and `<=>` hasn't been redefined, the elements are sorted directly with a pattern-defeating quicksort (the one used by Rust and Go) instead of going through `ruby_qsort` with a callback for each comparison. Random Integers sort 4–5x faster at 1,000 to 100,000 elements, and reversed arrays sort about 9x faster. `sort_by` now uses the same code instead of its own introsort and goes up to 2.4x faster. For `sort_by`, elements with equal keys may come out in a different order (the docs already call that order indeterminate). The error message for an invalid key may also name a different key than before. * **Array#include?, #index, #rindex and #count with immediate values**: https://github.com/ruby/ruby/pull/19308 When the argument is a Fixnum, a Float or a static Symbol, elements of the same kind are compared as raw VALUEs, eight at a time, instead of calling `rb_equal` on each one. Arrays of 1,000 or more elements are 10–15x faster. Arrays of other kinds of elements are within 1–2% of master. * **Array#eql? when elements are identical**: https://github.com/ruby/ruby/pull/19360 `eql?` now walks the element buffers the way `==` already does, and calls `rb_eql()` only for elements that aren't the same VALUE. On an array of 1,000 Integers it's 4.8x faster, so it's no longer about 4x slower than `==`. ## Range * **Range#to_a on Integer ranges**: https://github.com/ruby/ruby/pull/19319 For Fixnum ranges where `Range#each` hasn't been redefined, the array is allocated at its final size and filled in a loop instead of going through `Enumerable#to_a`. That's 7.7x faster at 10 elements and 35x faster at 1,000. `[*range]` and `Array(range)` are faster too. Because this path doesn't call `super`, a `to_a` from a module included into Range, or a redefined `Enumerable#to_a`, is no longer reached for these ranges. * **Range#include? on ranges of numeric Strings**: https://github.com/ruby/ruby/pull/13959 This fills in the `TODO` in `rb_str_include_range_p` for ranges whose ends are all digits. The digits are checked directly instead of iterating with `String#upto`, and the result is the same as iterating would give. `('1'..'200000').include?('199999')` drops from 13 ms to 150 ns. ## String and Integer * **String#casecmp and #casecmp? on similar strings**: https://github.com/ruby/ruby/pull/19311 This builds on https://github.com/ruby/ruby/pull/17444. The ASCII fast path now compares 16 bytes at a time and looks at single bytes only inside a chunk that differs. Identical strings, or strings that differ only in the case of one letter, are 4–5x faster at 360 bytes and 7–14x faster at 3.6 KB and up. * **String#to_i and Integer() for Bignum results**: https://github.com/ruby/ruby/pull/19332 `str2big_normal` now multiplies once per `BDIGIT`-sized group of digits instead of once per character, the way `str2big_karatsuba` already builds its initial digits. Also, `rb_int_parse_cstr` stops its first scan once the input is too long to fit in an `unsigned long`. Parsing is 1.5x faster at 20 decimal digits and 6.3x faster at 600. Results that fit in a Fixnum aren't affected. ## Float * **Conversions between Float and String**: https://github.com/ruby/ruby/pull/19309 `Float#to_s` gets its digits from Schubfach (the algorithm behind OpenJDK's `Double.toString`) instead of `ruby_dtoa`. `ruby_strtod` tries Eisel-Lemire (the algorithm behind `fast_float`, which the json extension already vendors) before falling back to the existing code. For a random Float, `to_s` is 7x faster and `String#to_f` is 3.2x faster, and `Marshal.dump` and `Marshal.load` are faster as well. This is the largest of the PRs. It adds new code under the Boost and MIT licenses, credited in `LEGAL`, plus a generated table with its generator in `tool/`. It also fixes `Rational#to_f` and `Integer#fdiv`, which could be off by one unit in the last place for large operands, and a `strtod` bug on 32-bit x86. I'm happy to split those fixes into their own tickets if that makes review or backporting easier. ## Time * **Time#strftime**: https://github.com/ruby/ruby/pull/19341 Numeric fields are written directly instead of through `rb_str_catf`, and the result buffer is sized up front so that typical results stay embedded. Common formats are 2.4–4x faster, including the ones used by Logger's default formatter and by Rails' `to_fs(:db)` and `to_fs(:usec)`. I'd appreciate any feedback, here or on the PRs. That includes whether you'd like any of these split up, merged together, or moved into their own tickets. Thank you so much for reviewing! I hope it's not too late for these performance improvements to make it into Ruby 4.1! -- https://bugs.ruby-lang.org/

Issue #22446 has been updated by sferik (Erik Berlin).

This one is interesting because a large part of the complexity of the implementation is caused by the semantic of these methods is that the comparison is done as element == searched_item.

Reversing that condition would be a spec change, so perhaps tricky, but would make it much easier to optimize the method as you'd only need to check for immediate values once.

This comment inspired another optimization PR: https://github.com/ruby/ruby/pull/19394 ---------------------------------------- Feature #22446: Speed up several core methods in Array, Range, String, Integer, Float and Time https://bugs.ruby-lang.org/issues/22446#change-119552 * Author: sferik (Erik Berlin) * Status: Open ---------------------------------------- I've opened a set of pull requests that speed up commonly used core methods. This issue collects them in one place for discussion. Each PR stands on its own, adds its benchmark in the first commit, and has its own tests. All of the numbers below are from an arm64 Mac with clang. Several of these changes depend on the compiler inlining or vectorizing a loop, so numbers from Linux with gcc, and from Windows with MSVC, would be especially welcome. ## Array * **Array#sort and Enumerable#sort_by on numeric arrays**: https://github.com/ruby/ruby/pull/19306 When every element is a Fixnum, or every element is a Float, and `<=>` hasn't been redefined, the elements are sorted directly with a pattern-defeating quicksort (the one used by Rust and Go) instead of going through `ruby_qsort` with a callback for each comparison. Random Integers sort 4–5x faster at 1,000 to 100,000 elements, and reversed arrays sort about 9x faster. `sort_by` now uses the same code instead of its own introsort and goes up to 2.4x faster. For `sort_by`, elements with equal keys may come out in a different order (the docs already call that order indeterminate). The error message for an invalid key may also name a different key than before. * **Array#include?, #index, #rindex and #count with immediate values**: https://github.com/ruby/ruby/pull/19308 When the argument is a Fixnum, a Float or a static Symbol, elements of the same kind are compared as raw VALUEs, eight at a time, instead of calling `rb_equal` on each one. Arrays of 1,000 or more elements are 10–15x faster. Arrays of other kinds of elements are within 1–2% of master. * **Array#eql? when elements are identical**: https://github.com/ruby/ruby/pull/19360 `eql?` now walks the element buffers the way `==` already does, and calls `rb_eql()` only for elements that aren't the same VALUE. On an array of 1,000 Integers it's 4.8x faster, so it's no longer about 4x slower than `==`. ## Range * **Range#to_a on Integer ranges**: https://github.com/ruby/ruby/pull/19319 For Fixnum ranges where `Range#each` hasn't been redefined, the array is allocated at its final size and filled in a loop instead of going through `Enumerable#to_a`. That's 7.7x faster at 10 elements and 35x faster at 1,000. `[*range]` and `Array(range)` are faster too. Because this path doesn't call `super`, a `to_a` from a module included into Range, or a redefined `Enumerable#to_a`, is no longer reached for these ranges. * **Range#include? on ranges of numeric Strings**: https://github.com/ruby/ruby/pull/13959 This fills in the `TODO` in `rb_str_include_range_p` for ranges whose ends are all digits. The digits are checked directly instead of iterating with `String#upto`, and the result is the same as iterating would give. `('1'..'200000').include?('199999')` drops from 13 ms to 150 ns. ## String and Integer * **String#casecmp and #casecmp? on similar strings**: https://github.com/ruby/ruby/pull/19311 This builds on https://github.com/ruby/ruby/pull/17444. The ASCII fast path now compares 16 bytes at a time and looks at single bytes only inside a chunk that differs. Identical strings, or strings that differ only in the case of one letter, are 4–5x faster at 360 bytes and 7–14x faster at 3.6 KB and up. * **String#to_i and Integer() for Bignum results**: https://github.com/ruby/ruby/pull/19332 `str2big_normal` now multiplies once per `BDIGIT`-sized group of digits instead of once per character, the way `str2big_karatsuba` already builds its initial digits. Also, `rb_int_parse_cstr` stops its first scan once the input is too long to fit in an `unsigned long`. Parsing is 1.5x faster at 20 decimal digits and 6.3x faster at 600. Results that fit in a Fixnum aren't affected. ## Float * **Conversions between Float and String**: https://github.com/ruby/ruby/pull/19309 `Float#to_s` gets its digits from Schubfach (the algorithm behind OpenJDK's `Double.toString`) instead of `ruby_dtoa`. `ruby_strtod` tries Eisel-Lemire (the algorithm behind `fast_float`, which the json extension already vendors) before falling back to the existing code. For a random Float, `to_s` is 7x faster and `String#to_f` is 3.2x faster, and `Marshal.dump` and `Marshal.load` are faster as well. This is the largest of the PRs. It adds new code under the Boost and MIT licenses, credited in `LEGAL`, plus a generated table with its generator in `tool/`. It also fixes `Rational#to_f` and `Integer#fdiv`, which could be off by one unit in the last place for large operands, and a `strtod` bug on 32-bit x86. I'm happy to split those fixes into their own tickets if that makes review or backporting easier. ## Time * **Time#strftime**: https://github.com/ruby/ruby/pull/19341 Numeric fields are written directly instead of through `rb_str_catf`, and the result buffer is sized up front so that typical results stay embedded. Common formats are 2.4–4x faster, including the ones used by Logger's default formatter and by Rails' `to_fs(:db)` and `to_fs(:usec)`. I'd appreciate any feedback, here or on the PRs. That includes whether you'd like any of these split up, merged together, or moved into their own tickets. Thank you so much for reviewing! I hope it's not too late for these performance improvements to make it into Ruby 4.1! -- https://bugs.ruby-lang.org/

Issue #22446 has been updated by sferik (Erik Berlin).

I'll second Jean, we should absolutely not do this. Im also eager to replace dtoa.c, but if we're changing the algorithm (and especially if that changes the output in any cases) we should do it at most once over the next ~5 years.

To be clear, I would be very happy if we updated this in 4.1 and kept it stable for 5 years after that. That is still much better than not updating it at all. I didn't mean to minimize the maintenance burden of changing algorithms.

If we are replacing dtoa.c I would like whatever choice we make have a path to actually removing it in full. That makes #22256 more compelling to me, at least on first glance.

Sounds good to me!

Is float formatting or parsing showing up in real-world profiles of your application (and if so is it parsing or formatting, and what does the pattern look like)? That's been a question that's come up previously when discussing dtoa alternatives.

A common pattern with the `openai` gem is caching embeddings so they aren't requested twice. For example: ```ruby Rails.cache.fetch(["embedding", text]) do client.embeddings.create(model: "text-embedding-3-small", input: text).data.first.embedding end ``` That's 1,536 full-precision Floats per entry, and `Rails.cache` stores them with Marshal: | One embedding | master | PR | |---|---:|---:| | `Marshal.dump` (cache write) | 910 µs | 136 µs | | `Marshal.load` (cache read) | 424 µs | 142 µs | An app that reads 30 cached embeddings per request, for example to rank search results, spends about 13 ms in `Marshal.load` on master vs. about 4 ms with this PR. ---------------------------------------- Feature #22446: Speed up several core methods in Array, Range, String, Integer, Float and Time https://bugs.ruby-lang.org/issues/22446#change-119556 * Author: sferik (Erik Berlin) * Status: Open ---------------------------------------- I've opened a set of pull requests that speed up commonly used core methods. This issue collects them in one place for discussion. Each PR stands on its own, adds its benchmark in the first commit, and has its own tests. All of the numbers below are from an arm64 Mac with clang. Several of these changes depend on the compiler inlining or vectorizing a loop, so numbers from Linux with gcc, and from Windows with MSVC, would be especially welcome. ## Array * **Array#sort and Enumerable#sort_by on numeric arrays**: https://github.com/ruby/ruby/pull/19306 When every element is a Fixnum, or every element is a Float, and `<=>` hasn't been redefined, the elements are sorted directly with a pattern-defeating quicksort (the one used by Rust and Go) instead of going through `ruby_qsort` with a callback for each comparison. Random Integers sort 4–5x faster at 1,000 to 100,000 elements, and reversed arrays sort about 9x faster. `sort_by` now uses the same code instead of its own introsort and goes up to 2.4x faster. For `sort_by`, elements with equal keys may come out in a different order (the docs already call that order indeterminate). The error message for an invalid key may also name a different key than before. * **Array#include?, #index, #rindex and #count with immediate values**: https://github.com/ruby/ruby/pull/19308 When the argument is a Fixnum, a Float or a static Symbol, elements of the same kind are compared as raw VALUEs, eight at a time, instead of calling `rb_equal` on each one. Arrays of 1,000 or more elements are 10–15x faster. Arrays of other kinds of elements are within 1–2% of master. * **Array#eql? when elements are identical**: https://github.com/ruby/ruby/pull/19360 `eql?` now walks the element buffers the way `==` already does, and calls `rb_eql()` only for elements that aren't the same VALUE. On an array of 1,000 Integers it's 4.8x faster, so it's no longer about 4x slower than `==`. ## Range * **Range#to_a on Integer ranges**: https://github.com/ruby/ruby/pull/19319 For Fixnum ranges where `Range#each` hasn't been redefined, the array is allocated at its final size and filled in a loop instead of going through `Enumerable#to_a`. That's 7.7x faster at 10 elements and 35x faster at 1,000. `[*range]` and `Array(range)` are faster too. Because this path doesn't call `super`, a `to_a` from a module included into Range, or a redefined `Enumerable#to_a`, is no longer reached for these ranges. * **Range#include? on ranges of numeric Strings**: https://github.com/ruby/ruby/pull/13959 This fills in the `TODO` in `rb_str_include_range_p` for ranges whose ends are all digits. The digits are checked directly instead of iterating with `String#upto`, and the result is the same as iterating would give. `('1'..'200000').include?('199999')` drops from 13 ms to 150 ns. ## String and Integer * **String#casecmp and #casecmp? on similar strings**: https://github.com/ruby/ruby/pull/19311 This builds on https://github.com/ruby/ruby/pull/17444. The ASCII fast path now compares 16 bytes at a time and looks at single bytes only inside a chunk that differs. Identical strings, or strings that differ only in the case of one letter, are 4–5x faster at 360 bytes and 7–14x faster at 3.6 KB and up. * **String#to_i and Integer() for Bignum results**: https://github.com/ruby/ruby/pull/19332 `str2big_normal` now multiplies once per `BDIGIT`-sized group of digits instead of once per character, the way `str2big_karatsuba` already builds its initial digits. Also, `rb_int_parse_cstr` stops its first scan once the input is too long to fit in an `unsigned long`. Parsing is 1.5x faster at 20 decimal digits and 6.3x faster at 600. Results that fit in a Fixnum aren't affected. ## Float * **Conversions between Float and String**: https://github.com/ruby/ruby/pull/19309 `Float#to_s` gets its digits from Schubfach (the algorithm behind OpenJDK's `Double.toString`) instead of `ruby_dtoa`. `ruby_strtod` tries Eisel-Lemire (the algorithm behind `fast_float`, which the json extension already vendors) before falling back to the existing code. For a random Float, `to_s` is 7x faster and `String#to_f` is 3.2x faster, and `Marshal.dump` and `Marshal.load` are faster as well. This is the largest of the PRs. It adds new code under the Boost and MIT licenses, credited in `LEGAL`, plus a generated table with its generator in `tool/`. It also fixes `Rational#to_f` and `Integer#fdiv`, which could be off by one unit in the last place for large operands, and a `strtod` bug on 32-bit x86. I'm happy to split those fixes into their own tickets if that makes review or backporting easier. ## Time * **Time#strftime**: https://github.com/ruby/ruby/pull/19341 Numeric fields are written directly instead of through `rb_str_catf`, and the result buffer is sized up front so that typical results stay embedded. Common formats are 2.4–4x faster, including the ones used by Logger's default formatter and by Rails' `to_fs(:db)` and `to_fs(:usec)`. I'd appreciate any feedback, here or on the PRs. That includes whether you'd like any of these split up, merged together, or moved into their own tickets. Thank you so much for reviewing! I hope it's not too late for these performance improvements to make it into Ruby 4.1! -- https://bugs.ruby-lang.org/

Issue #22446 has been updated by sferik (Erik Berlin). The [neighbor](https://github.com/ankane/neighbor) gem is another example, commonly used by Rails apps to store embeddings with pgvector. pgvector's wire format is text, so `Neighbor::Type::Vector#serialize` does `"[#{value.to_a.map(&:to_f).join(",")}]"`. This runs on every write and also on every `nearest_neighbors` search, since the query embedding is serialized into the SQL. | One 1,536-dim embedding | master | PR | |---|---:|---:| | `serialize` (every write and search) | 1,306 µs | 337 µs | Each semantic search request is about 1 ms faster, so a job that indexes 1,000 document chunks saves about a second. There's probably some way to optimize this code as well, but there are thousands of real-world applications using neighbor that would become significantly faster with by improving `Float#to_s` performance. ---------------------------------------- Feature #22446: Speed up several core methods in Array, Range, String, Integer, Float and Time https://bugs.ruby-lang.org/issues/22446#change-119593 * Author: sferik (Erik Berlin) * Status: Open ---------------------------------------- I've opened a set of pull requests that speed up commonly used core methods. This issue collects them in one place for discussion. Each PR stands on its own, adds its benchmark in the first commit, and has its own tests. All of the numbers below are from an arm64 Mac with clang. Several of these changes depend on the compiler inlining or vectorizing a loop, so numbers from Linux with gcc, and from Windows with MSVC, would be especially welcome. ## Array * **Array#sort and Enumerable#sort_by on numeric arrays**: https://github.com/ruby/ruby/pull/19306 When every element is a Fixnum, or every element is a Float, and `<=>` hasn't been redefined, the elements are sorted directly with a pattern-defeating quicksort (the one used by Rust and Go) instead of going through `ruby_qsort` with a callback for each comparison. Random Integers sort 4–5x faster at 1,000 to 100,000 elements, and reversed arrays sort about 9x faster. `sort_by` now uses the same code instead of its own introsort and goes up to 2.4x faster. For `sort_by`, elements with equal keys may come out in a different order (the docs already call that order indeterminate). The error message for an invalid key may also name a different key than before. * **Array#include?, #index, #rindex and #count with immediate values**: https://github.com/ruby/ruby/pull/19308 When the argument is a Fixnum, a Float or a static Symbol, elements of the same kind are compared as raw VALUEs, eight at a time, instead of calling `rb_equal` on each one. Arrays of 1,000 or more elements are 10–15x faster. Arrays of other kinds of elements are within 1–2% of master. * **Array#eql? when elements are identical**: https://github.com/ruby/ruby/pull/19360 `eql?` now walks the element buffers the way `==` already does, and calls `rb_eql()` only for elements that aren't the same VALUE. On an array of 1,000 Integers it's 4.8x faster, so it's no longer about 4x slower than `==`. ## Range * **Range#to_a on Integer ranges**: https://github.com/ruby/ruby/pull/19319 For Fixnum ranges where `Range#each` hasn't been redefined, the array is allocated at its final size and filled in a loop instead of going through `Enumerable#to_a`. That's 7.7x faster at 10 elements and 35x faster at 1,000. `[*range]` and `Array(range)` are faster too. Because this path doesn't call `super`, a `to_a` from a module included into Range, or a redefined `Enumerable#to_a`, is no longer reached for these ranges. * **Range#include? on ranges of numeric Strings**: https://github.com/ruby/ruby/pull/13959 This fills in the `TODO` in `rb_str_include_range_p` for ranges whose ends are all digits. The digits are checked directly instead of iterating with `String#upto`, and the result is the same as iterating would give. `('1'..'200000').include?('199999')` drops from 13 ms to 150 ns. ## String and Integer * **String#casecmp and #casecmp? on similar strings**: https://github.com/ruby/ruby/pull/19311 This builds on https://github.com/ruby/ruby/pull/17444. The ASCII fast path now compares 16 bytes at a time and looks at single bytes only inside a chunk that differs. Identical strings, or strings that differ only in the case of one letter, are 4–5x faster at 360 bytes and 7–14x faster at 3.6 KB and up. * **String#to_i and Integer() for Bignum results**: https://github.com/ruby/ruby/pull/19332 `str2big_normal` now multiplies once per `BDIGIT`-sized group of digits instead of once per character, the way `str2big_karatsuba` already builds its initial digits. Also, `rb_int_parse_cstr` stops its first scan once the input is too long to fit in an `unsigned long`. Parsing is 1.5x faster at 20 decimal digits and 6.3x faster at 600. Results that fit in a Fixnum aren't affected. ## Float * **Conversions between Float and String**: https://github.com/ruby/ruby/pull/19309 `Float#to_s` gets its digits from Schubfach (the algorithm behind OpenJDK's `Double.toString`) instead of `ruby_dtoa`. `ruby_strtod` tries Eisel-Lemire (the algorithm behind `fast_float`, which the json extension already vendors) before falling back to the existing code. For a random Float, `to_s` is 7x faster and `String#to_f` is 3.2x faster, and `Marshal.dump` and `Marshal.load` are faster as well. This is the largest of the PRs. It adds new code under the Boost and MIT licenses, credited in `LEGAL`, plus a generated table with its generator in `tool/`. It also fixes `Rational#to_f` and `Integer#fdiv`, which could be off by one unit in the last place for large operands, and a `strtod` bug on 32-bit x86. I'm happy to split those fixes into their own tickets if that makes review or backporting easier. ## Time * **Time#strftime**: https://github.com/ruby/ruby/pull/19341 Numeric fields are written directly instead of through `rb_str_catf`, and the result buffer is sized up front so that typical results stay embedded. Common formats are 2.4–4x faster, including the ones used by Logger's default formatter and by Rails' `to_fs(:db)` and `to_fs(:usec)`. I'd appreciate any feedback, here or on the PRs. That includes whether you'd like any of these split up, merged together, or moved into their own tickets. Thank you so much for reviewing! I hope it's not too late for these performance improvements to make it into Ruby 4.1! -- https://bugs.ruby-lang.org/