Feature #22245
Updated by andrey.samsonov@gmail.com (Andrey Samsonov) 18 days ago
# Abstract `Array#&` returns the objects For intersections of `self`, in `self` order. On the hash-based path, larger arrays, Ruby always builds a temporary hash from the argument. So argument to `Array#&`. As a result, `short & long` costs can be slower and use much more time and temporary memory than `long & short`, and callers who need `self` order short`. Callers cannot swap always choose the arrays. This proposal hashes `self` instead when it is at most half as long as cheaper order because `Array#&` preserves the argument. The result keeps the objects and order of `self`. Benchmarks modeled This proposal reduces that operand-order cost when `self` is much shorter, making performance less dependent on Rails call sites improved by about 1.7-2.7x. 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 keeps 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 When ## 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 arrays use methods are stable, have no side effects, and return normally. For stable, side-effect-free methods, both hash-based paths make the hash-based path 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`: 2`, and the arrays use the hash-based path: 1. Build a hash from the distinct elements of `self`, keeping `self`. 2. Keep their first positions. positions in `self`. 2. 3. Scan the argument and mark each match. 3. 4. Return the marked elements in `self` order. All other inputs 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` 2x threshold is an empirical starting point, not part of the API. Below `2x` the Forced-threshold 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 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 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: ```ruby 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 whether 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 has 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. 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 the a full attribute list with `Array(only).map(&:to_s) & attribute_names`, and keys from the caller. - In Rails 8.1, Active Record collection replacement intersects the new and old targets with calls `intersection(new_target, original_target)`. The ordinary `HasManyAssociation` helper implements this as `a & b`. Both are short-left, long-right shapes. 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, on macOS arm64. Ubuntu 24.04 x86-64 confirmed the direction of the two headline cases (1.66x and 2.46x). 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 | | Argument with many duplicates, at On Linux, the `2x` threshold | `partial-dup-arg-5k-and-10k` | ~0.64x | 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 enters entered the new proposed branch 152 times across application boot and three iterations, mainly through this call and showed 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 cheaper cheap to hash, as hash. In tested cases at the last table row shows. exact `2x` threshold, throughput fell to about 0.64x on arm64 and about 0.90x on Linux. The mirrored shape, case is slow on current Ruby: a short duplicate-heavy `self` with a long distinct argument, argument improved by about 2.4x. 2.4x on arm64 and 1.6x on Linux with this patch. No choice based only on lengths makes can make both shapes faster. - Hash-collision sensitivity moves from ### Hash collisions The new path makes hash quality on `self` more important; the current path makes hash quality on the argument to `self`. more important. The worst-case complexity does not change; change, but the input array that triggers it does. 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. 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 - 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 the a different call direction. 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 holds contains `bool` flags. Tests cover the `2x` boundary, both lookup paths, equality edge cases, mutation during `#hash`, mutation, and GC compaction. `ruby/test_array.rb` and `spec/ruby/core/array` pass, and a pass. A randomized comparison with current Ruby produced the same results for normal values. Implementation: [ruby/ruby#18333](https://github.com/ruby/ruby/pull/18333), one commit with commit. It contains the change, the RDoc update, the tests, and the benchmarks. 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?`. `Array#intersect?`, which avoids materializing an intersection and can choose the hash side by length because it returns only a boolean. - [Feature #13884] added the an existing size-based strategy choice in for these methods. - [Bug #19622] documented led Ruby to document that these methods use both `#hash` and `#eql?`, without specifying `#eql?`; it did not specify which operand receives the calls.