Skip to content

Preallocate dictionary storage in dict.fromkeys - #8874

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

Preallocate dictionary storage in dict.fromkeys#8874
youknowone merged 1 commit into
RustPython:mainfrom
1ndahous3:dict_fromkeys_capacity

Conversation

@1ndahous3

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

Copy link
Copy Markdown
Contributor

Summary

  • Reserve entry and index capacity in the builtin dict.fromkeys for exact
    dict, set or frozenset inputs, avoiding repeated vector growth and table
    rebuilding.
  • Preserve subclass constructors, stored hashes, key order and generic iterable
    behavior. Failed preallocation falls back to normal incremental growth.

Follow-up to #8503; addresses the remaining preallocation work in #3586.

Performance

Windows 11 x64

dict.fromkeys(source, 0), 128 string keys, median of seven runs:

Source Before After Speedup
dict 5.41 µs 4.86 µs 1.11×
set 5.39 µs 4.90 µs 1.10×
frozenset 5.42 µs 4.88 µs 1.11×

AI assistance

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

Summary by CodeRabbit

  • Performance

    • dict.fromkeys can reserve storage in advance for built-in dictionaries when the number of keys is known, reducing the need for capacity growth during insertion.

  • Tests

    • Added coverage for result ordering, shared values, duplicate keys, and custom iterables without a length hint.

@coderabbitai

coderabbitai Bot commented Sep 27, 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: 917fd3d5-7dff-4199-8f86-c71ae5f08723

📥 Commits

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

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

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

📝 Walkthrough

Walkthrough

dict.fromkeys now reserves storage for known keys when the requested class is the exact built-in dict. New tests cover dictionary capacity reservation and fromkeys behavior with several source types, shared values, and duplicate keys.

Changes

Dictionary fromkeys preallocation

Layer / File(s) Summary
Reserve storage for empty dictionaries
crates/vm/src/dict_inner.rs		 Adds guarded reservation for empty, unused dictionaries. Tests check overflow handling, unchanged keys-version, insertion without further capacity growth, and preservation of existing and tombstoned layouts.
Use reservation in dict.fromkeys
crates/vm/src/builtins/dict.rs, extra_tests/snippets/builtin_dict.py		 fromkeys reserves capacity when the requested class is the exact built-in dict. Tests check source iteration order, shared value identity, and duplicate keys without calling length methods.

Priority: ⬇️ Low

Estimated code review effort: 2 (Simple) | ~10 minutes

Change: Refactor

Suggested reviewers: youknowone

Merge Risk: ⚪ Minimal · up to 1966d

No identified issue blocks merging after normal checks.

Security Architecture Review

Security architecture risk: 🔵 Low · up to 1966d

The change preallocates memory for known-size inputs without changing which inputs or constructors are accepted. The reviewed paths preserve dictionary behavior and fall back to normal growth if reservation fails. Large-input and allocation-failure behavior has not been stress-tested.

Retained concerns
No architecture-level concerns identified.

Security review details

Security Blast Radius

  • inferred — The independently usable new path is confined to dictionary construction in the VM. No changed cross-service, credential, or deployment path is established by the reviewed call and storage code.

Trust Boundaries and Controls

  • observed — Exact-type checks select the known-hash sources and gate result preallocation; generic iterables and subclass construction do not enter the new reservation step.

Resilience and Maintainability Implications

  • observed — Overflow and failed entry reservation return without changing logical dictionary state. If index reservation fails after entry capacity is reserved, insertion can still use the existing index-growth path.
🚥 Pre-merge checks | ✅ 4 | ❌ 1

❌ Failed checks (1 warning)

Check name Status Explanation Resolution
Docstring Coverage ⚠️ Warning Docstring coverage is 62.50% which is insufficient. The required threshold is 80.00%. Docstring coverage is scoped to functions touched by this diff. Analyzed 8 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 the main change: preallocating dictionary storage in dict.fromkeys.
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 27, 2026

Copy link
Copy Markdown
Contributor

Merging this PR will not alter performance

✅ 62 untouched benchmarks
⏩ 4 skipped benchmarks1

Comparing 1ndahous3:dict_fromkeys_capacity (1966d31) 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.

👍

@youknowone
youknowone merged commit 19e9b7c into RustPython:main Sep 28, 2026
22 checks passed
@1ndahous3
1ndahous3 deleted the dict_fromkeys_capacity branch September 28, 2026 16:09
@youknowone youknowone mentioned this pull request Oct 6, 2026
Closed
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