GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — gh-142145: Avoid timing measurements in quadratic behavior test by colesbury · Pull Request #143105 · python/cpython

Conversation

@colesbury

@colesbury colesbury commented Dec 23, 2025 •
edited by bedevere-app Bot
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

Count the number of Element attribute accesses as a proxy for work done. With double the amount of work, a ratio of 2.0 indicates linear scaling and 4.0 quadratic scaling. Use 3.2 as an intermediate threshold.

  • Issue: Remove quadratic behavior in node ID cache clearing #142145

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@colesbury
pythongh-142145: Avoid timing measurements in quadratic behavior test
cc9cf09 
Count the number of Element attribute accesses as a proxy for work done.
With double the amount of work, a ratio of 2.0 indicates linear scaling
and 4.0 quadratic scaling. Use 3.2 as an intermediate threshold.
@colesbury
colesbury requested a review from sethmlarson December 23, 2025 16:20
@colesbury colesbury added the skip news label Dec 23, 2025
@bedevere-app bedevere-app Bot added the tests Tests in the Lib/test dir label Dec 23, 2025
@bedevere-app bedevere-app Bot mentioned this pull request Dec 23, 2025
Remove quadratic behavior in node ID cache clearing #142145
Closed
@colesbury
colesbury marked this pull request as ready for review December 23, 2025 16:20
@bedevere-app bedevere-app Bot added the awaiting core review label Dec 23, 2025
@colesbury
colesbury requested a review from gpshead December 23, 2025 16:20
@colesbury
Lint
506e978
@colesbury

colesbury commented Dec 23, 2025

Copy link
Copy Markdown
Contributor Author

The context for this is that I'm trying to get the full test suite in a state where we can run it under TSan. TSan tends to be much slower, so timing tests are even more flaky.

Let me know what you think about this appraoch.

For context, I used ChatGPT to generate the test and then edited it. (It was pretty good, but not perfect).
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@sethmlarson

sethmlarson commented Dec 23, 2025

Copy link
Copy Markdown
Contributor

Thanks @colesbury, did you happen to run this test with the commit in question reverted to see that this test would indeed catch quadratic behavior in number of accesses?
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@colesbury

colesbury commented Dec 23, 2025

Copy link
Copy Markdown
Contributor Author

Yes, if you revert the fix then it fails with:

======================================================================
FAIL: testAppendChildNoQuadraticComplexity (test.test_minidom.MinidomTest.testAppendChildNoQuadraticComplexity)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/sgross/cpython/Lib/test/test_minidom.py", line 207, in testAppendChildNoQuadraticComplexity
    self.assertLess(
    ~~~~~~~~~~~~~~~^
        max(r1, r2), 3.2,
        ^^^^^^^^^^^^^^^^^
        msg=f"Possible quadratic behavior: work={w1,w2,w3} ratios={r1,r2}"
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    )
    ^
AssertionError: 3.9883495145631067 not less than 3.2 : Possible quadratic behavior: work=(1060864, 4218880, 16826368) ratios=(3.976833976833977, 3.9883495145631067)
sethmlarson reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
sethmlarson
sethmlarson approved these changes Dec 23, 2025
View reviewed changes

@sethmlarson sethmlarson left a comment

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

LGTM, thanks @colesbury!

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
colesbury reacted with thumbs up emoji
All reactions
  • 👍 1 reaction
@gpshead gpshead added needs backport to 3.13 only security fixes needs backport to 3.14 bugs and security fixes labels Dec 23, 2025
gpshead
gpshead reviewed Dec 23, 2025
View reviewed changes
Comment thread Lib/test/test_minidom.py Outdated

@support.requires_resource('cpu')
def testAppendChildNoQuadraticComplexity(self):
# Don't use wall-clock timing (too flaky). Instead count a proxy for the

@gpshead gpshead Dec 23, 2025

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Elide the model's explanatory comment about the old no longer present code.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
colesbury reacted with thumbs up emoji
All reactions
  • 👍 1 reaction
Comment thread Lib/test/test_minidom.py
self.assertEqual(dom.documentElement.childNodes[-1].data, "Hello")
dom.unlink()

@support.requires_resource('cpu')

@gpshead gpshead Dec 23, 2025

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

why remove this? i realize the test shouldn't be "slow" now, but the intent of adding it was to mark it as a test that may not be suitable for slow builds and loaded systems. some of our buildbots run with the cpu resource disabled for that reason. it's more of a performance test no matter how it is implemented.

for tests where it isn't platform specific and we just need something in our support tiers to catch an unlikely regression the issue, resource tags save effort.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@colesbury colesbury Dec 23, 2025

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

I'll add it back. I removed it because my understanding was that "cpu" was for tests that were CPU-heavy, and now this test is very fast (~30 ms in a debug build).

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Lib/test/test_minidom.py
total_calls += 1
return object.__getattribute__(self, attr)

with support.swap_attr(Element, "__getattribute__", getattribute_counter):

@gpshead gpshead Dec 23, 2025

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

doing this is... gross, but likely works. your assertGreater(w1, 0) below covers the case when it stops doing so. LGTM

the other thought i was having as i did the simple "raise the timeout to 4s" to unblock the earlier ones was that we don't need absolute times at all. measuring relative time taken as we increase the amount of work to ensure that it scales - similar to this scaling measurement of attribute accesses - would be sufficient and should produce similar results on super slow builds or heavily loaded systems. it would still be time based (so maybe use resource.getrusage(resource.RUSAGE_SELF).ru_utime instead of time. APIs... though i suspect rusage is low-res) but far less "works on my system"

we have a smattering of other timing based cpu performancy tests in the repo. i don't think we've codified a reusable best practice.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@colesbury colesbury Dec 23, 2025

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

measuring relative time taken as we increase the amount of work ... would be sufficient

It'd be great to have some sort of standard best practice for this. If resource.getrusage(resource.RUSAGE_SELF).ru_utime isn't too affected by other processes, that would be good.

Some other things I was thinking about:

  1. Count cycles (via perf_event_open?)
  2. Count bytecodes executed (by instrumenting ceval.c in debug builds)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@colesbury
Changes from review
ec362b3
@colesbury
colesbury merged commit 57937a8 into python:main Dec 24, 2025
44 checks passed

Uh oh!

There was an error while loading. Please reload this page.
@miss-islington-app

miss-islington-app Bot commented Dec 24, 2025

Copy link
Copy Markdown

Thanks @colesbury for the PR 🌮🎉.. I'm working now to backport this PR to: 3.13, 3.14.
🐍🍒⛏🤖
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app bedevere-app Bot removed the awaiting core review label Dec 24, 2025
@colesbury
colesbury deleted the gh-142145-no-timing branch December 24, 2025 13:01
miss-islington pushed a commit to miss-islington/cpython that referenced this pull request Dec 24, 2025
@colesbury @miss-islington
pythongh-142145: Avoid timing measurements in quadratic behavior test (…
b710edb 
…pythongh-143105)

Count the number of Element attribute accesses as a proxy for work done.
With double the amount of work, a ratio of 2.0 indicates linear scaling
and 4.0 quadratic scaling. Use 3.2 as an intermediate threshold.
(cherry picked from commit 57937a8)

Co-authored-by: Sam Gross <[email protected]>
miss-islington pushed a commit to miss-islington/cpython that referenced this pull request Dec 24, 2025
@colesbury @miss-islington
pythongh-142145: Avoid timing measurements in quadratic behavior test (…
49eb677 
…pythongh-143105)

Count the number of Element attribute accesses as a proxy for work done.
With double the amount of work, a ratio of 2.0 indicates linear scaling
and 4.0 quadratic scaling. Use 3.2 as an intermediate threshold.
(cherry picked from commit 57937a8)

Co-authored-by: Sam Gross <[email protected]>
@bedevere-app

bedevere-app Bot commented Dec 24, 2025

Copy link
Copy Markdown

GH-143139 is a backport of this pull request to the 3.14 branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app bedevere-app Bot removed the needs backport to 3.14 bugs and security fixes label Dec 24, 2025
@bedevere-app

bedevere-app Bot commented Dec 24, 2025

Copy link
Copy Markdown

GH-143140 is a backport of this pull request to the 3.13 branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app bedevere-app Bot removed the needs backport to 3.13 only security fixes label Dec 24, 2025
colesbury added a commit that referenced this pull request Dec 24, 2025
@miss-islington @colesbury
[3.14] gh-142145: Avoid timing measurements in quadratic behavior test (
41f4687 
gh-143105) (#143139)

Count the number of Element attribute accesses as a proxy for work done.
With double the amount of work, a ratio of 2.0 indicates linear scaling
and 4.0 quadratic scaling. Use 3.2 as an intermediate threshold.
(cherry picked from commit 57937a8)

Co-authored-by: Sam Gross <[email protected]>
colesbury added a commit that referenced this pull request Dec 24, 2025
@miss-islington @colesbury
[3.13] gh-142145: Avoid timing measurements in quadratic behavior test (
e91c114 
gh-143105) (#143140)

Count the number of Element attribute accesses as a proxy for work done.
With double the amount of work, a ratio of 2.0 indicates linear scaling
and 4.0 quadratic scaling. Use 3.2 as an intermediate threshold.
(cherry picked from commit 57937a8)

Co-authored-by: Sam Gross <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@gpshead gpshead gpshead left review comments
@sethmlarson sethmlarson sethmlarson approved these changes

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

skip news tests Tests in the Lib/test dir

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

3 participants

@colesbury @sethmlarson @gpshead
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.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.