Skip to content

Choose smaller difference scans and install completed intersections - #8881

Merged
youknowone merged 1 commit into
RustPython:mainfrom
1ndahous3:set_sized_operations
Sep 28, 2026
Merged

Choose smaller difference scans and install completed intersections#8881
youknowone merged 1 commit into
RustPython:mainfrom
1ndahous3:set_sized_operations

Conversation

@1ndahous3

@1ndahous3 1ndahous3 commented Sep 28, 2026 •
edited by coderabbitai Bot
Loading

Copy link
Copy Markdown
Contributor

Summary

  • Choose difference scan direction by operand size, avoiding a full scan and temporary snapshot of large exclusion sets while matching CPython's comparison direction.
  • Reuse the completed intersection table in intersection_update and &= instead of rebuilding it. Removed-item finalizers now observe the completed set, and their mutations are preserved.

Follow-up to #8869.

Performance

Windows 11 x64

Operation Before After Speedup
difference: 100 candidates, 1,000 exclusions 15.18 µs 2.96 µs 5.1×
difference: 100 candidates, 10,000 exclusions 158.15 µs 3.50 µs 45.2×
copy + difference_update: 100 candidates, 10,000 exclusions 158.88 µs 4.75 µs 33.5×
copy + intersection_update: 10,000 entries per operand 484.14 µs 335.72 µs 1.4×

AI assistance

Written with Codex (GPT-6), reviewed by a human before submission.

Summary by CodeRabbit

  • Bug Fixes
    • Set and frozenset difference operations now handle multiple operands and preserve existing behavior across supported collection types.
    • Set intersection and in-place updates now produce correct results when collections differ in size or share their contents.
    • Replacing a dictionary’s contents no longer leaves stale cached key-version information.

@coderabbitai

coderabbitai Bot commented Sep 28, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor

Review in Change Stack →

Navigate logical layers of code changes, visualize relationships, and explore their blast radius.

No actionable comments were generated in the recent review. 🎉

ℹ️ Recent review info
⚙️ Run configuration

Configuration used: Repository: RustPython/RustPython/.coderabbit.yml

Review profile: CHILL

Plan: Advanced

Run ID: a5b1125c-ccbf-484e-9f4f-3a11bbbf0c3b

📥 Commits

Reviewing files that changed from the base of the PR and between 908368e and cf9cf16.

📒 Files selected for processing (3)
  • crates/vm/src/builtins/set.rs
  • crates/vm/src/dict_inner.rs
  • extra_tests/snippets/builtin_set.py

Included review availability: This review used your included allowance. Your plan provides up to 10 included reviews per hour; 6 remain after this review.

📝 Walkthrough

Walkthrough

Set and frozenset difference and intersection operations now use dedicated result-building paths. In-place updates include content replacement and additional handling for shared or much larger operands. Tests cover difference behavior, dictionary version invalidation, and finalizer behavior during intersection updates.

Changes

Set Operations

Layer / File(s) Summary
Difference and intersection result algorithms
crates/vm/src/builtins/set.rs		 New helpers build difference results using operand sizes and build intersections by scanning the smaller set when contents differ.
Difference methods and operators
crates/vm/src/builtins/set.rs, extra_tests/snippets/builtin_set.py		 Set and frozenset difference methods and subtraction operators use the new helpers. Tests cover operand types, comparison direction, left-side key retention, and removal without rehashing keys.
In-place updates and content replacement
crates/vm/src/builtins/set.rs, crates/vm/src/dict_inner.rs, extra_tests/snippets/builtin_set.py		 Intersection updates replace receiver contents. Difference updates handle shared contents and large set operands. Dictionary content replacement invalidates cached key-version data. Tests cover replacement and finalizer behavior.

Priority: ⬇️ Low

Estimated code review effort: 3 (Moderate) | ~25 minutes

Change: Bug fix

Suggested reviewers: youknowone

Merge Risk: ⚪ Minimal · up to cf9cf

No demonstrated issue blocks merging, subject to normal checks.

Security Architecture Review

Security architecture risk: 🟡 Moderate · up to cf9cf

An in-place difference update can now leave elements removed when an input iterator fails. Previously, that operand was fully read before its elements were removed. No privileged boundary is shown, but callers recovering from an error can observe unexpected partial state.

Retained concerns

  • Medium · reliability · observed: A failing generic iterable can now leave partial deletions in the receiver, changing per-operand failure containment for in-place difference updates.
Security review details

Security Blast Radius

  • inferred — The demonstrated partial-state effect is confined to a receiver operated on through the VM set API. Whether a downstream caller uses that set for security decisions is not established.

Trust Boundaries and Controls

  • inferred — The changed public wrappers still delegate to VM set operations; the inspected paths show no changed authentication, authorization, or tenant-ownership control.

Resilience and Maintainability Implications

  • observed — Replacement invalidates cached keys-version data before installing the new table, and the displaced table is dropped outside the replacement's write-locked block.
🚥 Pre-merge checks | ✅ 4 | ❌ 1

❌ Failed checks (1 warning)

Check name Status Explanation Resolution
Docstring Coverage ⚠️ Warning Docstring coverage is 20.83% which is insufficient. The required threshold is 80.00%. Docstring coverage is scoped to functions touched by this diff. Analyzed 24 functions across 3 files. Write docstrings for the functions missing them to satisfy the coverage threshold.
✅ Passed checks (4 passed)
Check name Status Explanation
Description Check ✅ Passed Check skipped - CodeRabbit’s high-level summary is enabled.
Title check ✅ Passed The title clearly and concisely describes both primary changes: choosing smaller difference scans and installing completed intersections.
Linked Issues check ✅ Passed Check skipped because no linked issues were found for this pull request.
Out of Scope Changes check ✅ Passed Check skipped because no linked issues were found for this pull request.
  • Fix all pre-merge checks with AI
✨ Finishing Touches
🧪 Generate unit tests (beta)
  • Create a new PR

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

Comment @coderabbitai help to get the list of available commands.

@codspeed

codspeed Bot commented Sep 28, 2026

Copy link
Copy Markdown
Contributor

Merging this PR will not alter performance

✅ 62 untouched benchmarks
⏩ 4 skipped benchmarks1

Comparing 1ndahous3:set_sized_operations (cf9cf16) with main (908368e)

Open in CodSpeed

Footnotes

  1. 4 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩

youknowone
youknowone approved these changes Sep 28, 2026
View reviewed changes

@youknowone youknowone left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

interesting 👍

@youknowone
youknowone merged commit 56eadb2 into RustPython:main Sep 28, 2026
22 checks passed
@1ndahous3
1ndahous3 deleted the set_sized_operations branch September 28, 2026 16:09
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@youknowone youknowone youknowone approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@1ndahous3 @youknowone