Render inline tables in O(n) instead of O(n²)#525
Open
tfoutrein wants to merge 1 commit into
Open
Conversation
e8f3f3b to
33b0903
Compare
InlineTable.as_string() recomputed, on every separator comma, two any(body[i + 1:]) tail scans (is there a following Null / a following key?) to decide whether to drop a dangling separator. On an inline table with many keys that is O(n^2). Precompute the needed facts in a single pass instead -- whether any explicit-comma whitespace is present, the index of the last real key, and the index of the last Null (deleted) element -- and turn the two per-comma scans into O(1) index comparisons. The render is now O(n). No behaviour change: the precomputed predicates are exactly equivalent to the tail scans. Full suite incl. toml-test conformance passes; round-trip output is byte-identical -- including edited inline tables (keys added/removed, trailing/leading commas, comments, dotted/nested) -- verified by a differential over ~7k generated inline tables with del/setitem mutations. ~4x faster rendering a 50-key inline table, ~40x at 800 keys.
33b0903 to
414199e
Compare
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
What
InlineTable.as_string()recomputed, on every separator comma, twoany(self._value.body[i + 1:])scans of the remaining body — "is there a followingNull?" and "is there a following key?" — to decide whether a dangling separator comma should be dropped. On an inline table with many keys that is O(n²) in the number of elements.The two predicates only depend on the position of the last real key and the last
Null(deleted) element, both of which can be found once. Precompute them in a single pass — together withhas_explicit_commas, which already needed a full pass — and turn the two per-comma scans into O(1) index comparisons:The render is now O(n).
Benchmark
as_string()of an inline table withnkeys (median, interleaved A/B vsmaster):masteris quadratic (~0.23 → 2.7 → 41 ms/render); the patched render is linear. No effect on small inline tables or other rendering.Tests
No behaviour change: the precomputed predicates are exactly equivalent to the tail scans. Full suite incl. the toml-test conformance submodule passes. The delicate part is the deferred-separator / removed-key comma logic, so round-trip output was verified byte-identical — including edited inline tables (keys added/removed, trailing/leading commas, comments, dotted/nested) — by a differential over ~7k generated inline tables with
del/__setitem__mutations. Added a focused regression test pinning the rendered output after key deletions.