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/