[ruby-core:126393] [Ruby Feature#22245] Reduce Array#& cost when self is much shorter than the argument
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/
Issue #22245 has been updated by andrey.samsonov@gmail.com (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: ```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 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](https://github.com/ruby/ruby/pull/18333), one commit with 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?`. - [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. ---------------------------------------- Feature #22245: Reduce Array#& cost when self is much shorter than the argument https://bugs.ruby-lang.org/issues/22245#change-118954 * 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: [ruby/ruby#18333](https://github.com/ruby/ruby/pull/18333), one commit. 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/
participants (1)
-
andrey.samsonov＠gmail.com (Andrey Samsonov)