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

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

[[e-mail] (Andrey Samsonov)]

Abstract

Array#& returns the objects of self, in self order. On the hash-based path, Ruby always builds a temporary hash from the argument. So short & long costs much more time and temporary memory than long & short, and callers who need self order cannot swap the arrays.

This proposal hashes self instead when it is at most half as long as the argument. The result keeps the objects and order of self. Benchmarks modeled on Rails call sites improved by about 1.7-2.7x. 1000 & 10_000_000 reduced peak RSS from about 465 MB to about 94 MB.

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

Background

[Feature #17109] proposed swapping the arrays. It was rejected because that changed the documented result order. This proposal keeps the order.

Proposal

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

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

All other inputs keep the current path. The 2x threshold is an empirical starting point, not part of the API. Below 2x the benchmarks were mixed: the new path fills the result array, keeps a flag buffer, and compacts, so it must win the hash-build asymmetry by more than that overhead.

Array#| and Array#- are not changed. Their operand-order costs have different causes.

Compatibility question

The patch changes which object receives the internal #eql? call. Today it is always self_element.eql?(argument_element). With the patch it depends on the lengths: when self is at most half as long as the argument, the call is argument_element.eql?(self_element). Built-in values and any symmetric #eql? give the same result either way. An asymmetric #eql? can give a different result:

require "delegate"

string = "abc"
delegator = SimpleDelegator.new(string)
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: []
b & a           # Current Ruby and proposal: []
a.intersect?(b) # Current Ruby and proposal: false

Current Ruby already answers this input inconsistently: a & b finds a match, a.intersect?(b) does not. The proposal makes them agree.

The current RDoc says that #eql? is the one "defined in each element of self". That sentence describes the current implementation. Is it an API guarantee? Array#intersect? and Set#& already choose the side by length. This proposal applies the same rule to Array#& and Array#intersection, still returns objects from self in self order, and changes the RDoc to say that the side is not specified.

Use cases

In Rails 8.1, ActiveModel::Serialization#serializable_hash filters the attribute list with Array(only).map(&:to_s) & attribute_names, and Active Record collection replacement intersects the new and old targets with a & b. Both are short-left, long-right shapes.

Discussion

Results

Each comparison used the same Ruby commit with and without the patch, on macOS arm64. Ubuntu 24.04 x86-64 confirmed the direction of the two headline cases (1.66x and 2.46x).

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
Argument with many duplicates, at the 2x threshold	partial-dup-arg-5k-and-10k	~0.64x

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 Rails 8.1.1 Lobsters workload enters the new branch mainly through this call and showed no detectable whole-workload change.

Known trade-offs

• The threshold uses lengths, not the number of distinct elements. A long argument with few distinct values can be cheaper to hash, as the last table row shows. The mirrored shape, a duplicate-heavy self with a long distinct argument, improved by about 2.4x. No choice based only on lengths makes both shapes faster.
• Hash-collision sensitivity moves from the argument to self. The worst-case complexity does not change; the input that triggers it does. Array#intersect? makes the same trade.
• Asymmetric #eql?, mutation, exceptions, object reachability, and GC timing can expose the different call direction. These behaviors are not specified.

Safety and tests

Candidate objects live in a Ruby array; the only raw buffer holds bool flags. Tests cover the 2x boundary, both lookup paths, equality edge cases, mutation during #hash, and GC compaction. ruby/test_array.rb and spec/ruby/core/array pass, and a randomized comparison with current Ruby produced the same results for normal values.

Implementation: ruby/ruby#18333, one commit with 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?.
• [Feature #13884] added the existing size-based strategy choice in these methods.
• [Bug #19622] documented that these methods use #hash and #eql?, without specifying which operand receives the calls.

[[e-mail] (Andrey Samsonov)]

• Description updated (diff)

[[e-mail] (Andrey Samsonov)]

• Description updated (diff)