Feature #22446: Speed up several core methods in Array, Range, String, Integer, Float and Time

• Status: Open
• Assignee: -
• Target version: -

[sferik (Erik Berlin)]

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!

[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...

[sferik (Erik Berlin)]

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...

Yeah, I hope we don't let perfect win out over good here. 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…

[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.

[sferik (Erik Berlin)]

Thank you for merging PR #19360!

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.

I'm happy to volunteer to help with the maintenance of these patches. For any PRs that are merged, I will commit to backporting them to Ruby 4.0, 3.4, and 3.3. Would you like me to do that for PR #19360?

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.

Yes, this would be great optimization if we could get away with it. In theory, #== should be symmetric, but I can think of several examples of this not being true in the standard library. For example:

Gem::Version.new("1.0") == "1.0"  # => true
"1.0" == Gem::Version.new("1.0")  # => false

IPAddr.new("192.168.1.1") == "192.168.1.1"  # => true
"192.168.1.1" == IPAddr.new("192.168.1.1")  # => false

Mime[:html] == :html  # => true
:html == Mime[:html]  # => false

When you have a moment, would you mind taking a look at PR #19309? It's implementing an optimization in Ruby that you already vendored in JSON.

[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

[sferik (Erik Berlin)]

We don't backport performance patches, only bugfixes.

That's what I thought, but you said:

It's not that simple though, there's a maintenance cost to all this (e.g. backports)…

Anyway, I am happy to help cover the maintenance cost in whatever way I can.

That's why I've added the question to the next dev meeting agenda: https://bugs.ruby-lang.org/issues/22417#note-3

Ah, thank you. I did not previously see your update there. I eagerly await the next meeting. If the core team decides to move away from dtoa.c in November, will that allow enough time for this to ship in Ruby 4.1 or will it have to wait until 4.2?

[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

[jhawthorn (John Hawthorn)]

sferik (Erik Berlin) wrote in #note-2:

Yeah, I hope we don't let perfect win out over good here. 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…

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. dtoa has been a maintenance burden already and it would be painful to support 3 or more libraries. There are also gems like bigdecimal which are including dtoa and expect to match Ruby's behaviour 1:1.

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. To be clear that doesn't mean we need to delete it immediately (if we want to do parsing separate from formatting or separate the fixed length formatting), but whatever path we choose should lead clearly towards it's removal rather than adding thousands of lines of code to maintain.

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.

[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:

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.