https://github.com/python/cpython/commit/57937a8e5e293f0dcba5115f7b7a11b1e0c9a273
commit: 57937a8e5e293f0dcba5115f7b7a11b1e0c9a273
branch: main
author: Sam Gross <[email protected]>
committer: colesbury <[email protected]>
date: 2025-12-24T08:01:45-05:00
summary:
gh-142145: Avoid timing measurements in quadratic behavior test (gh-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.
files:
M Lib/test/test_minidom.py
diff --git a/Lib/test/test_minidom.py b/Lib/test/test_minidom.py
index 69fae957ec7fc9..46249e5138aed5 100644
--- a/Lib/test/test_minidom.py
+++ b/Lib/test/test_minidom.py
@@ -2,7 +2,6 @@
import copy
import pickle
-import time
import io
from test import support
import unittest
@@ -178,23 +177,36 @@ def testAppendChild(self):
def testAppendChildNoQuadraticComplexity(self):
impl = getDOMImplementation()
- newdoc = impl.createDocument(None, "some_tag", None)
- top_element = newdoc.documentElement
- children = [newdoc.createElement(f"child-{i}") for i in range(1, 2 **
15 + 1)]
- element = top_element
-
- start = time.monotonic()
- for child in children:
- element.appendChild(child)
- element = child
- end = time.monotonic()
-
- # This example used to take at least 30 seconds.
- # Conservative assertion due to the wide variety of systems and
- # build configs timing based tests wind up run under.
- # A --with-address-sanitizer --with-pydebug build on a rpi5 still
- # completes this loop in <0.5 seconds.
- self.assertLess(end - start, 4)
+ def work(n):
+ doc = impl.createDocument(None, "some_tag", None)
+ element = doc.documentElement
+ total_calls = 0
+
+ # Count attribute accesses as a proxy for work done
+ def getattribute_counter(self, attr):
+ nonlocal total_calls
+ total_calls += 1
+ return object.__getattribute__(self, attr)
+
+ with support.swap_attr(Element, "__getattribute__",
getattribute_counter):
+ for _ in range(n):
+ child = doc.createElement("child")
+ element.appendChild(child)
+ element = child
+ return total_calls
+
+ # Doubling N should not ~quadruple the work.
+ w1 = work(1024)
+ w2 = work(2048)
+ w3 = work(4096)
+
+ self.assertGreater(w1, 0)
+ r1 = w2 / w1
+ r2 = w3 / w2
+ self.assertLess(
+ max(r1, r2), 3.2,
+ msg=f"Possible quadratic behavior: work={w1,w2,w3} ratios={r1,r2}"
+ )
def testSetAttributeNodeWithoutOwnerDocument(self):
# regression test for gh-142754
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
