Issue #22245 has been reported by andrey.samsonov@gmail.com (Andrey Samsonov). ---------------------------------------- Feature #22245: Reduce Array#& cost when self is much shorter than the argument https://bugs.ruby-lang.org/issues/22245 * Author: andrey.samsonov@gmail.com (Andrey Samsonov) * Status: Open ---------------------------------------- # 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: ```ruby 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?`: ```ruby 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: [one-commit fork branch](https://github.com/ruby/ruby/compare/master...kryzhovnik:array-and-hash-shor...). It contains the change, the RDoc update, the tests, and the benchmarks. # See also - [ruby/ruby#14855](https://github.com/ruby/ruby/pull/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. -- https://bugs.ruby-lang.org/