Feature #22245: Reduce Array#& cost when self is much shorter than the argument

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

[[e-mail] (Andrey Samsonov)]

Abstract

For intersections of larger arrays, Ruby builds a temporary hash from the argument to Array#&. As a result, short & long can be slower and use much more temporary memory than long & short. Callers cannot always choose the cheaper order because Array#& preserves the objects and order of self. This proposal reduces that operand-order cost when self is much shorter, making performance less dependent on which result order the caller needs.

In a local test, 1000 & 10_000_000 reduced peak RSS from about 465 MB to about 94 MB. Benchmarks modeled on real call sites improved by about 1.7-2.7x. An unmodified Rails 8.1 Active Model benchmark improved by about 1.3x.

Array#intersection uses the same C function and gets the same change.

Background

When either array has more than 16 elements, Ruby uses a hash-based lookup and always builds the temporary hash from the argument. This creates a large cost difference between:

short & long
long & short

The first expression hashes long. The second hashes short, but it can return elements in a different order. Some callers need the first expression because of that order.

[Feature #17109] proposed removing the same operand-order cost by swapping the arrays. It was rejected because that changed the documented result order. This proposal instead preserves the objects and order from self.

This proposal hashes self when it is at most half as long as the argument. It then scans the argument and returns matches in self order. For normal #hash and #eql? implementations, the result contains the same objects from self, in the same order, without duplicates.

Proposal

Compatibility question

May Array#& and Array#intersection choose which array to hash based on their lengths?

The result stays the same for built-in values and custom equality methods where #eql? is an equivalence relation, equal elements have equal #hash values, and both methods are stable, have no side effects, and return normally.

For stable, side-effect-free methods, both hash-based paths make the same number of #hash calls. The receiver, order, and number of #eql? calls can change. Mutation or exceptions can also change how many calls complete. The patch makes the RDoc direction-neutral.

Array#intersect? has chosen the hash side by length since Ruby 3.1. This is relevant precedent, although intersect? returns only a boolean. This patch also preserves the objects and order from self.

Implementation

When len(self) <= len(argument) / 2, and the arrays use the hash-based path:

1. Build a hash from the distinct elements of self.
2. Keep their first positions in self.
3. Scan the argument and mark each match.
4. Return the marked elements in self order.

Small arrays, near-equal arrays, and a long self with a short argument keep the current path.

Array#| is not changed because its operand-order cost has a different cause. Array#- preserves repeated unmatched elements and needs a separate algorithm and compatibility analysis.

Why start at 2x?

The 2x threshold is an empirical starting point, not part of the API. Forced-threshold benchmarks gave mixed results below 2x. At 2x, all tested cases with distinct argument elements improved, with median gains of about 1.1-1.3x. I would welcome maintainer guidance on whether Ruby has an established method or relevant precedent for selecting thresholds like this.

Use cases

• In Rails 8.1, Array(only).map(&:to_s) & attribute_names in ActiveModel::Serialization#serializable_hash filters a full attribute list with keys from the caller.
• In Rails 8.1, Active Record collection replacement calls intersection(new_target, original_target). The ordinary HasManyAssociation helper implements this as a & b; HasManyThroughAssociation uses a separate implementation.
• Rails command lookup uses lookups & namespaces.keys.

Discussion

Results

The primary measurements ran on macOS arm64, with separate confirmation on Ubuntu 24.04 x86-64. Each comparison used the same Ruby commit with and without the patch.

Case	Benchmark case	Change
ActiveModel shape, 6 and 50 strings	attr-filter-6-and-50	~1.77x
Collection replacement shape, 10 and 10,000 ids	short-receiver-10-and-10k	~2.74x

On Linux, the same two shapes improved by 1.66x and 2.46x. Other id-list shapes moved by 1.11-1.23x there, but unchanged small-array cases moved by up to 1.16x in the same rounds, so I make no claim from those smaller deltas.

With unmodified Rails 8.1 Active Model code, ActiveModel#serializable_hash(only: 6 of 50 attributes) improved from about 3.6 µs to about 2.8 µs per call. The control path without only: did not change.

For memory, 1000 & 10_000_000 reduced peak RSS from about 465 MB to about 94 MB. The scan still takes time proportional to the long array; the change removes the hash build from that array.

The Rails 8.1.1 Lobsters workload entered the proposed branch 152 times across application boot and three iterations, mainly through Active Model serialization. Six alternating A/B batches found no detectable whole-workload change.

Known trade-offs

Arguments with many duplicates

The threshold uses array lengths, not the number of distinct elements. A long argument with few distinct values can be cheap to hash. In tested cases at the exact 2x threshold, throughput fell to about 0.64x on arm64 and about 0.90x on Linux.

The mirrored case is slow on current Ruby: a short duplicate-heavy self with a long distinct argument improved by about 2.4x on arm64 and 1.6x on Linux with this patch. No choice based only on lengths can make both shapes faster.

Hash collisions

The new path makes hash quality on self more important; the current path makes hash quality on the argument more important. The worst-case complexity does not change, but the array that triggers it can change at the threshold.

For example, 3,000 distinct elements in self with the same hash and a clean 6,000-element argument changed from about 0.5 ms to 63 ms. The reverse case changed from about 250 ms to 0.8 ms. Array#intersect? already makes the same trade when it chooses the shorter array.

Custom #hash and #eql?

Built-in integers, symbols, and strings cannot observe the call direction. User-defined methods can. The standard library provides an example with asymmetric #eql?:

require "delegate"

string = "abc"
delegator = SimpleDelegator.new(string)

delegator.hash == string.hash # => true
delegator.eql?(string)        # => true
string.eql?(delegator)        # => false

a = [delegator] + (1..20).map { |i| "x#{i}" }
b = [string] + (1..100).map { |i| "y#{i}" }

a & b           # Current Ruby: [delegator], proposal: []
a.intersect?(b) # Current Ruby and proposal: false
b & a           # Current Ruby and proposal: []

The proposal changes the first result and makes these three operations agree for this input. This agreement is not a compatibility guarantee. For values whose #eql? is symmetric, transitive, stable, and consistent with #hash, the result does not change.

Logging, mutation, exceptions, object reachability, and GC timing can expose a different call order. These behaviors are not specified.

Safety and tests

Calls to user #hash and #eql? can mutate either array or run the GC. The candidate loop cannot write past the initial length of self. Candidate objects live in a Ruby array; the only raw buffer contains bool flags.

Tests cover the 2x boundary, both lookup paths, equality edge cases, mutation, and GC compaction. ruby/test_array.rb and spec/ruby/core/array pass. A randomized comparison with current Ruby produced the same results for normal values.

Implementation: ruby/ruby#18333, one commit. It contains the change, the RDoc update, the tests, and the benchmarks

See also

• ruby/ruby#14855 also chose an array by length, but did not preserve both the objects and order from self.
• [Feature #15198] added Array#intersect?, which avoids materializing an intersection and can choose the hash side by length because it returns only a boolean.
• [Feature #13884] added an existing size-based strategy choice for these methods.
• [Bug #19622] led Ruby to document that these methods use both #hash and #eql?; it did not specify which operand receives the calls.

[[e-mail] (Andrey Samsonov)]

• Description updated (diff)